∘Wikipedia category graph

Далее было выполнено "расщепление" ядра на связные компоненты. Это особенно важно, т.к. пути между циклами, сами не входящие в циклы, составляют самостоятельную интересную часть ядра. И оказалось, что имеется одна большая компонента - 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 - количество узлов.

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

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

ССК 41

Рисунок графа компоненты:

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

Заголовки узлов:

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

Линзы

Итак мы ищем в ядре два узла такие что: У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) нет!

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

http://dbpedia.org

Через точку входа для 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.}

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

Вот первая:

Она действительно есть в 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.

http://jens-lehmann.org/files/2009/dbpedia_jws.pdf

[САОД] Матьяш В.А., Путилов В.А., Фильчаков В.В. , Щёкин С.В.Структуры и алгоритмы обработки данных - Апатиты, КФ ПетрГУ, 2000. - 80 с.

http://khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/guap/index4.htm

[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

Обсуждение