∘Wikipedia category graph

Исследование графа категорий 

английской версии Wikipedia





Сообщение о результатах первого этапа





Александр Шкотин
ashkotin@acm.org




Лето 2011, 2012


Последние изменения: 29.09.2011

Может найтись много причин поинтересоваться строением ГКВ (граф категорий Википедиа) (aka WCG http://synthesis.ipi.ac.ru/sigmod/seminar/korshunov20110428.pdf) см. также [CDA]. 
Являясь по идее системой тем он поддерживает систематизацию знаний и мы интересуемся из чего эта систематизация состоит и как она устроена.
Важно помнить, что далее изучается дамп ГКВ на некоторый момент времени и в нём есть незавершённая "динамическая" часть. Поэтому выводы надо делать с осторожностью.
Естественно ввести термин "точка роста", когда мы натыкаемся "в дампе" на часть, которая ещё не завершена.

Введение

ГКВ есть подграф графа в котором обычные статьи Википедии приписаны категориям, а категории - над-категориям. Выделение ГКВ из этого полного графа есть первая техническая задача. Дамп полного графа получен из ИСП РАН и соответствует 16 сентября 2010г. Это текстовый файл каждая строка которого имеет вид N1 N2 N3, где N1, N2 - номера страниц Wikipedia и соответствуют  отношению "N2 есть категория для N1", а N3 равно 0, что означает, что N1 - простая страница; или 1 - N1 - страница категории.
Подробнее см.

На ГКВ узлы (категории) связаны отношением "N1 есть подкатегория N2" если из N1 в N2 идёт стрелка. Всего таких стрелок 1221133.
Множество узлов ГКВ (593796 штук), как и любого произвольного графа, распадается на два подмножества: изолированные узлы (26272) и узлы связанные стрелками (567524 узлов). Изолированная категория это скорее всего "точка роста": на момент снятия дампа она уже есть, но в ГКВ ещё не включена.

Далее анализируется только "граф стрелок", т.е. все характеристики даны без учёта изолированных узлов. 
Состав изолированных узлов можно посмотреть в таблице
Состав и характеристики узлов со стрелками можно посмотреть в таблице
Граф стрелок в таблице

Важный вопрос - количество связных компонент графа, т.к. в дальнейшем их строение можно изучать отдельно. Таких компонент оказалось 1987. Изолированные узлы при этом учитываются отдельно. Алгоритм разбиения можно посмотреть здесь
Впрочем проще воспользоваться программой, например, Pajek [Pajek] умеющий разбивать узлы графа на слабо связные компоненты.

Вот количество узлов в первых 10 самых больших компонентах.

cn, count
1, 561636
21727, 210
14332, 36
2863, 29
20842, 27
6680, 20
19212, 19
20868, 19
13325, 17
13287, 16

Здесь cn - уникальный номер компоненты, присвоенный при разбиении.
Конечно в случае с Wikipedia малые компоненты это точки роста.

Петель (N1  N1) в графе нет. Это логично.

Источников (узлов в которые нет входящих стрелок) - 345597. Это категории нижнего уровня.
Стоков (узлов из которых нет исходящих стрелок) - 11767. Это категории верхнего уровня дампа и скорее всего "точки роста".
Промежуточных узлов, соответственно - 210160.

Наконец несколько рекордов.
Максимальное количество исходящих из одного узла стрелок - 85. Это промежуточный узел с node_id = 690451, а заголовок "Category:World War II". Итак эта категория приписана 85 над-категориям!
Максимальное количество входящих стрелок (12625) имеет промежуточный узел 692309 с проясняющим заголовком - "Category:Albums by artist";-)

Анализ заголовков

Так что же там в этом графе? Что за темы?...

Заголовки всех узлов категорий (включая изолированные) можно посмотреть в таблице
Она содержит (как легко видеть;-) - 584606 узлов. Таким образом 9190 узлов ГКВ не имеют заголовков. Они ждут своего исследователя;-)

Анализ текстов заголовков даже безотносительно их подчинения отдельная увлекательная задача. Но начать надо с использованного состава букв.

Алфавит

Конечно получив текст первый вопрос к нему - состав букв (characters). В эпоху Юникода да ещё "в мировом масштабе" в тексте может быть всё что угодно. Хотя от категорий да и вообще от энциклопедии ждёшь сдержанности.
Текстовый файл (UTF-8) содержащий состав алфавита см. в приложении cat2title.abc0.txt.
Как разделитель букв используется '|'.
Вот он:
| |!|"|&|'|(|)|*|+|,|-|.|/|0|1|2|3|4|5|6|7|8|9|:|;|?|@|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|~|¡|ª|°|µ|·|º|½|Á|Â|Ä|Å|Æ|Ç|É|Í|Î|Ñ|Ó|Õ|Ö|×|Ø|Ú|Ü|Þ|ß|à|á|â|ã|ä|å|æ|ç|è|é|ê|ë|ì|í|î|ï|ð|ñ|ò|ó|ô|õ|ö|ø|ù|ú|û|ü|ý|þ|ÿ|Ā|ā|ă|ą|Ć|ć|Č|č|ď|Đ|đ|ē|ė|ę|ě|ğ|Ħ|ħ|Ī|ī|İ|ı|ļ|Ľ|ľ|Ł|ł|ń|ņ|ň|Ō|ō|ő|œ|ř|Ś|ś|Ş|ş|Š|š|Ţ|ţ|ť|ū|ŭ|ů|ŵ|ź|Ż|ż|Ž|ž|ơ|ș|ʻ|̧|̱|ḵ|ṭ|ạ|ầ|ậ|ắ|ế|ề|ể|ễ|ệ|ị|ọ|ộ|ụ|ỳ|ỹ|–|—|‘|’|…|共|台|和|國|歲|灣|萬|!|

Задействовано 225 букв. И буквы "|" среди ниx нет;-)
Первое субъективное впечатление см. в
Конечно большинство букв за пределами латинского алфавита это диакритические, что впрочем тоже интересно. Но есть и совершенно неожиданные. Чего стоит "~" или "¡".
А относительно "чего угодно" посмотрите алфавит заголовков всех статей (страниц) Wikipedia (en) в прикрепе id2title.abc.txt, а первое впечатление в 

Термины в заголовках

Просто для начала: количество заголовков в который встречается слово album - 17591.

Немного о стоках

В Приложении-1 начало таблицы стоков с самым большим количеством входящих стрелок. В основном это точки роста.

Длинные пути

от Анастасии к Музыке

В Приложении-2 путь рекордсмен предоставленный Антоном Коршуновым (см. также приложение A_K_1.csv):

Path: [13196325, 5760285, 16489372, 777306, 6837182, 696410, 1037152, 22149558, 4826123, 11325464, 1403800, 866705, 1519596, 2012004, 2118729, 11323367, 696790, 11277715, 1312487, 12717273, 1055671, 7439251, 7297152, 7296998, 983652, 695868, 695042, 1633936, 5183917, 1926287, 2217510, 16703584, 693800, 894191, 716308, 18335592, 716910, 900479, 2699217, 717159, 1101998, 4476466, 8531018, 838546, 5577702, 24327627, 23392786, 706388, 8103827, 12363278, 8103981, 6509623, 13703287, 696811, 915759, 21868604, 25513756, 765986, 5962269, 3704881, 24061212, 6372014, 1951386, 780121, 16609007, 24395596, 27130452, 28559348, 888485, 876384, 11547492, 15773812, 697397, 5362957, 707244, 15715670, 12589261, 24004709, 691702, 4954683, 24078316, 700983, 823369, 7475458, 702527, 713466, 18165898, 1880992, 1880923, 23903398, 23903307, 24014339, 7060742, 1091466, 22450964, 15918831, 3679023, 693798, 8017451, 1004110, 815917, 691182, 700914, 1055691, 696763, 2348651, 1017749, 1055905, 1784082, 26201565, 826247, 824950, 890039, 5105298, 8546750, 912575, 13926197, 13857729, 918375, 3615452, 17503782, 26352924, 23357224, 21991760, 22991469, 974363, 15335942, 2687547, 4516109, 24909288, 16705267, 751381, 2389032, 17321675, 2766046, 7297212, 2665289, 25192170, 1058986, 20860353, 691820, 3743303, 749645, 1703604, 10156905, 19089053, 828361, 19307021, 728925, 10382571, 2955178, 1896041, 25506713, 691484]

В нём 154 вершины!

Начальная категория:

5760285 Category:Anastacia songs

Конечная категория

691484 Category:Music

Вроде бы логично, но почему так длинно? Что там на пути от Анастасии к Музыке? Интересно проанализировать - нет ли там ошибочного подчинения категорий?!

А самый длинный путь - 294 вершины.

Строение ГКВ в целом

Вот характеристика системы категорий [DBpCP], с.9 :

"Wikipedia Categories. DBpedia contains a SKOS representation of the
Wikipedia category system. The category system consists of 415,000 categories.
The main advantage of the category system is that it is collaboratively
extended and kept up-to-date by thousands of Wikipedia editors. A
disadvantage is that categories do not form a proper topical hierarchy, as
there are cycles in the category system and as categories often only represent
a rather loose relatedness between articles."

Итак в ГКВ есть циклы. По идее циклы это аномалия на графе подчинения категорий. И должны занимать малую его часть.
Назовём для краткости объединение ор-циклов графа и ор-путей между циклами  - ядро, а дополнительную часть графа - мантия. Стрелки же между мантией и ядром пусть будут связующие.
Итак в целом граф состоит из ядра, мантии и связующих стрелок часть из которых идёт из ядра в мантию, а часть - из мантии в ядро.

Чтобы выделить ядро, был применён широко известный в узких кругах алгоритм следующей идеи: Находим в графе источники и стоки и удаляем их. И так до тех пор пока не получим граф где нет ни источников ни стоков. Либо пока граф не кончится. См. алгоритм.

На странице get_circles_report можно посмотреть протокол процесса выделения ядра.

Ядро ГКВ


Состав ядра

Количество стрелок в ядре - 38538! Узлов же 13545. Граф ядра ипубликован:

http://www.google.com/fusiontables/DataSource?dsrcid=1143932 А теперь летом 2012 может быть даже увиден:

Include gadget (iframe)


Далее было выполнено "расщепление" ядра на связные компоненты. Это особенно важно, т.к. пути между циклами, сами не входящие в циклы, составляют самостоятельную интересную часть ядра. И оказалось, что имеется одна большая компонента - 13507 узлов! И ещё 19 пар узлов.

Характеристики узлов ядра включая разбиение на связные компоненты можно посмотреть в

http://www.google.com/fusiontables/DataSource?dsrcid=1144213

Вот пример пары, которая является даже связной компонентой не только ядра, а самого ГКВ:

Компонента №764 ядра
Узлы:
28736601, Category:Wikipedia sockpuppets of ShantanuSingh198
28736686, Category:Suspected Wikipedia sockpuppets of ShantanuSingh198.

Смотрим в Wikipedia: ДА они ссылаются друг на друга и больше ни на что!

Анализ. Что бы ни обозначало "Wikipedia sockpuppets of ShantanuSingh198" очевидно что нечто под него подпадающее (как под понятие) не может быть одновременно лишь "подозреваемым" на подпадание. Равно как и наоборот. Эти две категории не пересекаются! И обе стрелки должны быть удалены. Отношения же между ними на OWL FS должно было бы быть:
DisjointClasses (wcg:Wikipedia_sockpuppets_of_ShantanuSingh198, wcg:Suspected_Wikipedia_sockpuppets_of_ShantanuSingh198)
При это более правильно ссылаться в обоих статьях друг на друга через тэг See also.

Сильно связные компоненты (ССК) ядра

Трудно оторваться от ядра не увидев ни одного контура, т.е. кольца, т.е. зацикливания отношения под-категория - над-категория. Тут есть два подхода:
- общий - применить алгоритм поиска сильно связных компонент;
- частный - найти так называемые "линзы" - два узла ссылающиеся друг на друга (как под-категория - над-категория).
Второй путь вполне приемлем для ГКВ, т.к. по идее в нём вообще не должно быть контуров. Впрочем как для линз так и для контуров большей длины следует заметить, что они математически утверждают эквивалентность соответствующих терминов, т.е. синонимию, что в принципе возможно. Но конкретно в Википедия может быть реализовано через redirect. Но интуитивно в большинстве случаем мы обнаружим ошибку, т.е. какие-то стрелки контура ошибочны.
Чтобы получить состав сильно связных компонент ядра была использована программа Pajek [Pajek]. Если в неё загрузить граф (network) в виде net-файла и выполнить 
Net  Components  Strong
задав минимальный размер компоненты 2, то появится разбиение (partition) в котором узлы попавшие в ССК получат номер компоненты (1...), а узлы не попавшие в ССК получат 0.
Заметим, что петель в ГКВ нет, а поэтому узлы ядра не попавшие в ССК это узлы на путях между циклами (см. выше).
ССК оказалось 457. Узлов не входящих в ССК, так сказать связующих - 7646. Есть одна гигантская по сравнению с остальными ССК - в ней 3967 узлов!
Вот таблица самых больших ССК:

val num
0
7646
1
3967
20
96
29
95
245
68
348
52
52
52
280
52
232
52
127
52
66
52
65
52
307
51
106
51
67
51
399
18
41
9
31
9

val - номер компонеты, num - количество узлов.

Полностью привязку узлов ядра к ССК можно посмотреть в таблице WCG. Core strong components.

Рассмотрим для примера компоненту 41.

ССК 41

Рисунок графа компоненты:
Если номер накладывается на стрелку то под ним наконечника (треугольничка) нет. Это важно т.к. Pajek рисует "линзы" (У1  У2  У1) как одну стрелку с наконечниками на обоих окончаниях. В данной ССК линза одна - слева внизу вертикально.
using Pajek
Заголовки узлов:


ni

title

717227

Category:Orthodox rabbis

717302

Category:Talmud rabbis

799461

Category:Mishnah

799587

Category:Talmud

6110893

Category:Talmudists

8398752

Category:Talmud people

11334178

Category:Rabbinic literature

15249105

Category:Talmud concepts and terminology

26795615

Category:Chazal

Анализ ждёт своего героя;-)!

Линзы

Итак мы ищем в ядре два узла такие что: У1  У2 и У2  У1. Они могут быть отдельной ССК, а могут входить в ССК как часть. В любом случае это интересно!
В ядре оказалось 1269 линз. Из них 1260 имеют заголовки для обоих узлов и опубликованы: https://www.google.com/fusiontables/DataSource?snapid=S250297tuci
08.09. 2011 автор взял на себя смелость написать по поводу первой строчки, что её надо бы ликвидировать а точнее заменить на взаимное See also.
А третьей строчки (про балетные премьеры) уже нет, а есть именно See also на обеих страницах.

Мантия - ациклическая часть ГКВ


Итак чтобы получить мантию мы удаляем из ГКВ ядро.
При этом оказывается, что часть источников и стоков станет изолированными. В первом случае все их исходящие попали в ядро, во втором - все входящие - из ядра.
Изолировавшихся источников - 14421, а стоков - 60.
Кроме того в мантии появляются ложные вершины (пики). Это те её узлы, которые стали стоками после удаления ядра, а вообще-то имели исходящие стрелки, которые все попадали в ядро. Таких вершин 18157! Причём максимальная высота - 28.
Для сравнения, стоков ГКВ получивших уровень, т.е. не изолированных - 11707, максимальная высота - 24!
Эта ложная вершина - рекордсмен (высоты 28) имеет ni=15715670, а заголовок "Category:Creation myths".
Что-то в этом есть;-)

Замечание: конечно ГКВ можно мыслить и в виде "галстука бабочки", но в данном случае сравнение с горами нагляднее - вверх к более обширным темам. 
Горами в которых "зарыто" ядро из 20-ти связных компонент. Одна из которых большая, а 19 - линзы.

Количество узлов на уровнях показано ниже в табличке и оправдывает сравнение с горами:


В таблице - у NULL - количество изолированных узлов мантии, а у 0 - количество узлов в ядре.
Полностью характеристики узлов со стрелками, включая привязку к уровням в мантии можно посмотреть здесь. А агрегированное представление аналогичное таблице выше, показывающее также количество входящих и исходящих стрелок каждого уровня здесь.

Связующие стрелки

Между мантией и ядром есть стрелки - связующие.
Стрелок из ядра в мантию - 591.
Стрелок из мантии в ядро210514.

Сводная диаграмма

14421 - количество изолировавшихся источников. 60 -  количество изолировавшихся стоков. В сумме они дают 14481 узел мантии у которых уровень NULL. Уровень 0 технически приписан узлам ядра.
1. Влияние ядра на строение мантии оказывается существенным. Чего стоит хотя бы ложный сток высотой 28 при максимальной высоте настоящего стока - 24! Такое может случиться только если ядро находится на вершине! Кроме того появилось 29 ложных источников - в них шли стрелки только из ядра. Да и количество ложных стоков 18157 впечатляет. При этом ядро состоит всего лишь из одной большой связной компоненты и 19-и линз.
2. Хотя "физически" отдельное изучении мантии оправдано, для совокупного строения графа лучше не удалять ядро из ГКВ, а свернуть его ССК в "тяжёлые" узлы пометив их количеством узлов в ССК. Такой тяжёлый узел наследует все внешние ССК стрелки, а образовавшиеся петли внутренних стрелок стоит удалить. Тогда мы получим ациклический граф, т.к. ССК не могут образовывать цикл. Уровни такого графа с указанием распределения по ним тяжёлых узлов дадут более реалистичную картину ГКВ. При это есть все основания полагать, что по крайней мере одна из тяжёлых вершин будет стоком.
3. В растущем графе, которым по преимуществу является ГКВ "точки роста" (изолированные узлы, все СК кроме главной, стоки вне главной СК) не представляют особого интереса. Поэтому стоит сразу выделить главную СК и изучать только её.
4. В заключение вот узел для которого в дампе нет заголовка: «29045675», а он участвует в линзе! Правда у его пары «Category:Wikipedia awards» пустой категории уже (Wikipedia(en) лето 2012) нет!

Другие способы исследования

Через точку входа для SPARQL: http://dbpedia.org/sparql 
Привязка к категории идёт через свойство http://purl.org/dc/terms/subject
Вот пример запроса, который начинает выдавать полный граф связи страниц и категорий:

select ?x ?z where {?x dcterms:subject ?z}

Надо только поставить timeout, например, 1000.

Запрос 

select ?x ?z where {?x skos:broader ?z}

выдаёт отношение "x is a sub-category of z". см. с. p.5 "Categories." [DBpCP]

А вот запрос

select ?x ?z where {?x skos:broader ?z. ?z skos:broader ?x.}

выдаёт "линзы".

Вот первая:

http://dbpedia.org/resource/Category:Political_philosophers http://dbpedia.org/resource/Category:Political_theorists

Она действительно есть в Wikipedia(en).
А всего запрос выдаёт 2000 линз, что наверно не предел. см. прикреп DBpedia_sparql_answer_lens.csv

Заключение

Мы считаем, что ГКВ должен быть ациклическим графом. Таким образом исследование показало, что аномалии значительны.
Можно создать средства, которые обнаруживая аномалию, например линзу, будут размещать на соответствующих страницах в Discussion уведомление о логическом противоречии.
Основных вопросов два:
- Как к такому подходу отнесутся авторы страниц категорий? Это можно проверить экспериментально.
- Как к логическим противоречиям относятся идеологи Википедия? Те кто задаёт правила классификации. Судя по всему индифферентно;-)

Общая рекомендация:
Многие отношения между категориями попавшие в subcategory of следует перенести в See also.

Оценить предстоящую работу можно так: для начала надо разобраться с 1269 линзами. Они сильно убавят размер ССК. 

Только если это нужно википедистам можно было бы продолжить и:

  • Исследовать длинные пути. 
  • Попытаться представить архитектуру графа в целом. Например применить 3D визуализацию.
  • Проанализировать состав и логику связи заголовков (особенно ССК).
  • ...
Особняком стоит задача получить и проанализировать русский ГКВ. В проекте dbpedia можно добыть дамп русской версии, надо только перекодировать с rdf-кодов букв (например. \u0432) в UTF-8.

Благодарности

Автор благодарен:

1. Антону Коршунову (ИСП РАН) за предоставленный дамп и путь.

2. Stefan Haustein (http://www.stefan-haustein.com/), который указал как (infusion.jar) можно загрузить таблицу заголовков в GFT.

3. Создателям Pajek [Pajek]. 

Литература

[CDA] Anton Korshunov, Denis Turdakov, Jinguk Jeong, Minho Lee, Changsung Moon. A Category-Driven Approach to Deriving Domain Specific Subset of Wikipedia. Proceedings of SYRCoDIS'11: The Seventh Spring Researchers Colloquium on Databases and Information Systems, 2011, pp. 43-53
[DBpCP] Christian Bizer, Jens Lehmann, Georgi Kobilarov, Soren Auer, Christian Becker, Richard Cyganiak, Sebastian Hellmann. DBpedia - A Crystallization Point for the Web of Data. May 25 2009.
[САОД] Матьяш В.А., Путилов В.А., Фильчаков В.В. , Щёкин С.В.Структуры и алгоритмы обработки данных - Апатиты, КФ ПетрГУ, 2000. - 80 с.
[Pajek] Batagelj V., Mrvar A.: Pajek reference manual.  Retrieved from http://pajek.imfm.si/doku.php?id=download
Pajek - Program for Large Network Analysis. http://pajek.imfm.si/doku.php?id=pajek


Обсуждение

Google Moderator - дискуссия

Добавленный гаджет недействителен

ċ
A_K_1.csv
(7k)
Alex Shkotin,
14 июл. 2011 г., 10:23
Ĉ
Alex Shkotin,
10 сент. 2011 г., 04:56
ċ
cat2title.abc0.txt
(1k)
Alex Shkotin,
9 июл. 2011 г., 00:58
ċ
id2title.abc.txt
(34k)
Alex Shkotin,
11 сент. 2011 г., 21:41
Ċ
Alex Shkotin,
14 окт. 2012 г., 06:04
Comments