=Paper=
{{Paper
|id=None
|storemode=property
|title=Исследование графа категорий английской версии Wikipedia
(Investigation of the English Version of the Wikipedia Categories Graph)
|pdfUrl=https://ceur-ws.org/Vol-934/paper17.pdf
|volume=Vol-934
|dblpUrl=https://dblp.org/rec/conf/rcdl/Shkotin12
}}
==Исследование графа категорий английской версии Wikipedia
(Investigation of the English Version of the Wikipedia Categories Graph)
==
https://ceur-ws.org/Vol-934/paper17.pdf
Исследование графа категорий английской версии
Wikipedia
© А. В. Шкотин
Государственный Геологический Музей РАН
Москва
ashkotin@acm.org
любого произвольного графа, распадается на два
Аннотация подмножества: изолированные узлы (26272) и узлы
Wikipedia является выдающимся проектом
связанные стрелками (567524 узлов). Изолированная
по накоплению знаний, как общего пользо-
категория это скорее всего "точка роста": на момент
вания, так и различных областей специали- снятия дампа она уже есть, но в ГКВ ещё не
зации. Проверка качества этих знаний, включена.
особенно автоматическая, чрезвычайна
важна. В работе представлены результаты Далее анализируется только "граф стрелок", т.е.
изучения строения английской версии ГКВ все характеристики даны без учёта изолированных
(орграф категорных статей Википедии) в узлов. Состав изолированных узлов можно
целом. Являясь по идее системой тем он посмотреть в отчёте [4] (далее - отчёт) в таблице
поддерживает систематизацию знаний и мы указанной во введении. Состав и характеристики
интересуемся из чего эта систематизация узлов со стрелками можно посмотреть в таблице
состоит и как она устроена. Показано, что в указанной там же, равно как и граф стрелок.
графе есть неприемлемые логические Важный вопрос - количество связных компонент
нарушения и обсуждаются организации- графа, т.к. в дальнейшем их строение можно изучать
онные и технические методы их устранения. отдельно. Таких компонент оказалось 1987.
Изолированные узлы при этом учитываются
1 Введение отдельно. Алгоритм разбиения описан в отчёте [5].
Впрочем проще воспользоваться программой,
ГКВ [1] есть подграф графа в котором статьи например, Pajek [2] умеющий разбивать узлы графа
Википедии приписаны категорным статьям. на слабо связные компоненты.
Выделение ГКВ из этого полного графа есть первая Первые 10 самых больших компонент:
техническая задача. Важно, что далее изучается
дамп ГКВ на некоторый момент времени и в нём cn count cn count
есть незавершённая "строящаяся" часть. Поэтому
выводы надо делать с осторожностью. Естественно 1 561636 6680 20
ввести термин "точка роста", когда мы натыкаемся
21727 210 19212 19
"в дампе" на часть, которая ещё не завершена. Дамп
полного графа получен из ИСП РАН и 14332 36 20868 19
соответствует 16 сентября 2010г. Дамп состоит из
двух текстовых файлов: файла отображения номера 2863 29 13325 17
страницы Википедии в номер категорной страницы,
что приписывает страницу категории; а также файла 20842 27 13287 16
в котором номеру страницы Википедии приписано Здесь cn - уникальный номер компоненты,
её наименование. Математически ГКВ есть орграф присвоенный при разбиении. Конечно в случае с
каждый узел которого взаимно-однозначно Wikipedia малые компоненты это точки роста.
соответствует категорной странице и помечен её Петель (N1 → N1) в графе нет.
номером. Дуга из узла N1 в узел N2 идёт тогда и
только тогда, когда страница с номером N1 есть Источников (узлов в которые нет входящих
под-категория страницы с номером N2. Всего таких стрелок) - 345597. Это категории нижнего уровня.
стрелок 1221133. Стоков (узлов из которых нет исходящих стрелок) -
11767. Это категории верхнего уровня дампа и
В статье исторически вместо термина «дуга» скорее всего "точки роста". Промежуточных узлов,
употребляется термин «стрелка». соответственно - 210160.
Множество узлов ГКВ (593796 штук), как и Максимальное количество исходящих из одного
Труды 14-й Всероссийской научной конференции узла стрелок - 85. Это промежуточный узел №
«Электронные библиотеки: перспективные методы и 690451, а заголовок "Category:World War II", т.е. эта
технологии, электронные коллекции» — RCDL-2012, категория приписана 85 над-категориям. Макси-
Переславль-Залесский, Россия, 15-18 октября 2012 г. мальное количество входящих стрелок (12625)
97
имеет промежуточный узел № 692309 с проясня- 4 Строение ГКВ в целом
ющим заголовком - "Category:Albums by artist".
В работе [3], с.9 указывается что в ГКВ есть
2 Анализ заголовков циклы. По идее циклы это аномалия на графе
подчинения категорий. И должны занимать малую
Заголовки всех узлов категорий (включая его часть. Назовём для краткости объединение ор-
изолированные) можно посмотреть в отчёте в циклов графа и ор-путей между циклами - ядро, а
таблице указанной в разделе «Анализ заголовков». дополнительную часть графа - мантия. Стрелки же
Таблица содержит - 584606 узлов. Таким образом между мантией и ядром назовём - связующие. Таким
9190 узлов ГКВ не имеют заголовков. Они ждут образом в целом граф состоит из ядра, мантии и
своего исследователя. Анализ текстов заголовков связующих стрелок часть из которых идёт из ядра в
даже безотносительно их подчинения отдельная мантию, а часть - из мантии в ядро. Чтобы выделить
увлекательная задача. Но начать надо с ядро, был применён следующий алгоритм:
использованного состава букв. 1. Находим в графе источники и стоки и удаляем их.
2. Если в графе не осталось узлов то стоп.
2.1 Алфавит 3. Если есть источники или стоки то идти на 1. Стоп.
Рассмотрим состав букв (characters),
употреблённых при именовании категорных статей. 5 Ядро ГКВ
Текстовый файл (UTF-8) содержащий состав
алфавита можно посмотреть в прикреплении 5.1 Состав ядра
cat2title.abc0.txt к отчёту. Как разделитель букв Количество стрелок в ядре - 38538. Узлов же
используется '|'. Вот он: 13545. Граф ядра опубликован в таблице указанной
в разделе «Состав ядра» отчёта. Далее было
| |!|"|&|'|(|)|*|+|,|- выполнено "расщепление" ядра на связные компо-
|.|/|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|~|¡|ª|°|µ|· лось, что имеется одна большая компонента - 13507
|º|½|Á|Â|Ä|Å|Æ|Ç|É|Í|Î|Ñ|Ó|Õ|Ö|×|Ø|Ú| узлов. И ещё 19 пар узлов. Характеристики узлов
Ü|Þ|ß|à|á|â|ã|ä|å|æ|ç|è|é|ê|ë|ì|í|î|ï ядра включая разбиение на связные компоненты
|ð|ñ|ò|ó|ô|õ|ö|ø|ù|ú|û|ü|ý|þ|ÿ|Ā|ā|ă| можно посмотреть в таблице указанной в разделе
ą|Ć|ć|Č|č|ď|Đ|đ|ē|ė|ę|ě|ğ|Ħ|ħ|Ī|ī|İ|ı «Состав ядра» отчёта.
|ļ|Ľ|ľ|Ł|ł|ń|ņ|ň|Ō|ō|ő|œ|ř|Ś|ś|Ş|ş|Š|
Рассмотрим компоненту №764 ядра. Это пример
š|Ţ|ţ|ť|ū|ŭ|ů|ŵ|ź|Ż|ż|Ž|ž|ơ|ș|ʻ|||ḵ|ṭ|ạ пары, которая является даже связной компонентой
|ầ|ậ|ắ|ế|ề|ể|ễ|ệ|ị|ọ|ộ|ụ|ỳ|ỹ|–|— не только ядра, а самого ГКВ. В компоненте два
|‘|’|…|共|台|和|國|歲|灣|萬|！| узла:
В прикреплении id2title.abc.txt к отчёту можно 28736601, Category:Wikipedia sockpuppets of
посмотреть впечатляющее разнообразие букв ShantanuSingh198
заголовков всех статей Wikipedia(en). и
28736686, Category:Suspected Wikipedia sockpuppets
2.2 Термины в заголовках of ShantanuSingh19
Это может быть отдельное важное исследование. В Wikipedia они также ссылаются друг на друга
Например, количество заголовков в которых и больше ни на что.
встречается слово album - 17591. Анализ. Что бы ни обозначало "Wikipedia
sockpuppets of ShantanuSingh198" очевидно что
3 Стоки нечто под него подпадающее (как под понятие) не
может быть одновременно лишь "подозреваемым"
В Приложении-1 к отчёту можно посмотреть
на подпадание. Равно как и наоборот, т.е. логически
начало таблицы стоков с самым большим
эти две категории не пересекаются. И обе стрелки
количеством входящих стрелок.
должны быть удалены. Отношения же между ними
3.1 От Анастасии к Музыке на, например, OWL 2 [7] должно было бы быть:
DisjointClasses(
В Приложении-2 к отчёту можно посмотреть
wcg:Wikipedia_sockpuppets_of_Shantanu
путь рекордсмен предоставленный Антоном
Singh198,
Коршуновым.
wcg:Suspected_Wikipedia_sockpuppets_o
Самый длинный путь - 294 вершины. Его f_ShantanuSingh198)
начальная категория - № 5760285 Category:Anastacia
songs, а конечная - № 691484 Category:Music. При этом более правильно ссылаться в обоих
статьях друг на друга через тэг Wikipedia «See also».
98
Заголовки узлов:
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
Category:Talmud concepts and
15249105
Рис. 1 Рисунок графа компоненты ССК 41 terminology
5.2 Сильно связные компоненты ядра 26795615 Category:Chazal
В ядре нас интересует зацикливание отношения
под-категория - над-категория. Тут есть два 5.3 Линзы
подхода:
- общий - применить алгоритм поиска сильно Линза это два узла такие что: У1 → У2 и У2 →
связных компонент (ССК); У1. Она может быть отдельной ССК, а может
входить в ССК как часть.
- частный - найти так называемые "линзы" - два
узла ссылающиеся друг на друга (как под-категория В ядре оказалось 1269 линз. Из них 1260 имеют
- над-категория). заголовки для обоих узлов. Их можно посмотреть в
таблице указанной в разделе «Линзы» отчёта.
Второй путь вполне приемлем для ГКВ, т.к. по
идее в нём вообще не должно быть циклов. Впрочем 6 Мантия - ациклическая часть ГКВ
как для линз так и для циклов большей длины
следует заметить, что они математически утверж- Чтобы получить мантию мы удаляем из ГКВ
дают эквивалентность соответствующих терминов, ядро. При этом оказывается, что часть источников и
т.е. синонимию, что в принципе возможно. Но стоков станет изолированными. В первом случае все
конкретно в Википедия может быть реализовано из них исходящие стрелки попали в ядро, во втором
через redirect. Интуитивно же в большинстве - все входящие в них стрелки шли из ядра.
случаев мы обнаружим ошибку, т.е. какие-то Изолировавшихся источников - 14421, а стоков - 60.
стрелки цикла ошибочны. Кроме того в мантии появляются ложные
Чтобы получить состав сильно связных вершины (пики). Это те её узлы, которые стали
компонент ядра была использована программа Pajek стоками после удаления ядра, а вообще-то имели
[2]. Заметим, что петель в ГКВ нет, а поэтому узлы исходящие стрелки, которые все попадали в ядро.
ядра не попавшие в ССК это узлы на путях между Таких вершин 18157. Причём максимальная высота
циклами (см. выше). - 28. Для сравнения, стоков ГКВ получивших
уровень, т.е. не изолированных - 11707,
ССК оказалось 457. Узлов не входящих в ССК,
максимальная высота - 24.
так сказать связующих ядра — 7646. Есть одна
гигантская по сравнению с остальными ССК - в ней Ложная вершина - рекордсмен (высоты 28) имеет
3967 узлов. №15715670, а заголовок "Category:Creation myths".
В отчёте в разделе «Сильно связные компоненты Замечание. Конечно ГКВ можно представить и в
ядра» приведена таблица самых больших ССК. виде "галстука-бабочки" как в работе [6], где орграф
Рассмотрим для примера компоненту №41 у кото- был использован для представления схемы связей
рой всего 9 узлов (см. рис. 1). между транснациональными корпорациями. Но в
данном случае сравнение с горами нагляднее - вверх
Если номер накладывается на стрелку то под ним
к более обширным темам; горами в которых есть
наконечника (треугольничка) нет. Это важно т.к.
ядро из 20-ти связных компонент. Одна из которых
Pajek рисует "линзы" (У1 → У2 → У1) как одну
большая, а 19 - линзы.
стрелку с наконечниками на обоих окончаниях. В
данной ССК линза одна - слева внизу вертикально. Количество узлов на уровнях показано ниже в
табличке и оправдывает сравнение с горами:
99
Основных вопросов два:
1. Как к такому подходу отнесутся авторы
страниц категорий? Это можно проверить
экспериментально.
2. Как к логическим противоречиям относятся
идеологи Википедии? Те кто задаёт правила
классификации. Судя по всему индифферентно.
Общая рекомендация. Многие отношения между
категориями попавшие в sub-category of следует
перенести в See also.
Оценить предстоящую работу можно так: для
начала надо разобраться с 1269 линзами. Они
сильно убавят размер ССК.
Только если это нужно википедистам можно
В таблице в строке с level = NULL - количество было бы продолжить и:
изолированных узлов мантии, а у 0 - количество - Исследовать длинные пути.
узлов в ядре. - Попытаться представить архитектуру графа в
целом. Например применить 3D визуализацию.
7 Связующие стрелки - Проанализировать состав и логику связи
Между мантией и ядром есть стрелки-связу- заголовков (особенно ССК).
ющие. Стрелок из ядра в мантию - 591. Стрелок из Особняком стоит задача получить и
мантии в ядро — 210514. проанализировать русский ГКВ. В проекте dbpedia
можно получить дамп русской версии, надо только
8 Другие способы исследования перекодировать с rdf-кодов букв (например, \u0432)
в UTF-8.
Можно напрямую изучать http://dbpedia.org через
точку входа для SPARQL: http://dbpedia.org/sparql. Литература
Привязка к категории идёт через свойство
http://purl.org/dc/terms/subject. 1. Anton Korshunov, Denis Turdakov, Jinguk
Jeong, Minho Lee, Changsung Moon. A Category-
Вот пример запроса, который начинает выдавать
Driven Approach to Deriving Domain Specific
полный граф связи страниц и категорий:
Subset of Wikipedia. Proceedings of
select ?x ?z where {?x dcterms:subject ?z} SYRCoDIS'11: The Seventh Spring Researchers
Надо только поставить timeout, например, 1000. Colloquium on Databases and Information
Запрос Systems, 2011, pp. 43-53.
select ?x ?z where {?x skos:broader ?z} 2. Batagelj V., Mrvar A. Pajek reference manual.
выдаёт отношение "x is a sub-category of z". см. с. Ljubljana, April 16, 2012.
p.5 "Categories." [3] 3. Christian Bizer, Jens Lehmann, Georgi
А вот запрос Kobilarov, Soren Auer, Christian Becker, Richard
Cyganiak, Sebastian Hellmann. DBpedia - A
select ?x ?z where
Crystallization Point for the Web of Data. May 25
{?x skos:broader ?z. ?z skos:broader ?x.} 2009.
выдаёт "линзы". 4. Шкотин А., Исследование графа категорий
Вот узлы первой: английской версии Wikipedia, Сообщение о
http://dbpedia.org/resource/Category:Poli результатах первого этапа, Интернет, 2011.
tical_philosophers и https://sites.google.com/site/alex0shkotin/grafy/wi
http://dbpedia.org/resource/Category:Poli kipedia-category-graph
tical_theorists 5. Шкотин А., Разбиение графа на связные
Она действительно есть в Wikipedia(en). компоненты, Алгоритм и программа,
А всего запрос выдаёт 2000 линз, что наверно не Интернет, 2011.
предел. https://sites.google.com/site/alex0shkotin/grafy/sv
aznye-komponenty
9 Заключение 6. Stefania Vitali, James B. Glattfelder, Stefano
Battiston. The network of global corporate control.
Естественно считать, что ГКВ должен быть
ArXiv.org, 2011
ациклическим графом. Таким образом исследование
http://arxiv.org/abs/1107.5728
показало, что аномалии значительны.
7. OWL 2 Web Ontology Language: Structural
Можно создать средства, которые обнаруживая Specification and Functional-Style Syntax. Boris
аномалию, например линзу, будут размещать на Motik, Peter F. Patel-Schneider, Bijan Parsia, eds.
соответствующих страницах в Discussion
уведомление о логическом противоречии.
100
W3C Recommendation, 27 October 2009. as well of various specialization domains. Quality
http://www.w3.org/TR/owl2-syntax/ check of this knowledge, especially automatic, is very
important. In this paper results of studying of a structure
of the English version of WCG (Wikipedia Categories
Investigation of the English version of the Graph) as a whole are presented. WCG is a system that
Wikipedia categories graph supports structure of knowledge and we are interested in
WCG content and its arrangement. It is shown that in
Alexander Shkotin graph there are unacceptable logical violations; organi-
zational and technical methods for their elimination are
Wikipedia is the outstanding project of knowledge
discussed.
accumulation. The knowledge is both of the general use,
101