Аннотация Wikipedia является выдающимся проектом по накоплению знаний, как общего пользования, так и различных областей специализации. Проверка качества этих знаний, особенно автоматическая, чрезвычайна важна. В работе представлены результаты изучения строения английской версии ГКВ (орграф категорных статей Википедии) в целом. Являясь по идее системой тем он поддерживает систематизацию знаний и мы интересуемся из чего эта систематизация состоит и как она устроена. Показано, что в графе есть неприемлемые логические нарушения и обсуждаются организациионные и технические методы их устранения.
ГКВ [
Множество узлов ГКВ (593796 штук), как и Труды 14-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» — RCDL-2012, Переславль-Залесский, Россия, 15-18 октября 2012 г.
Далее анализируется только "граф стрелок", т.е.
все характеристики даны без учёта изолированных
узлов. Состав изолированных узлов можно
посмотреть в отчёте [
Первые 10 самых больших компонент: cn 1 21727 14332 2863 20842
count 561636 210 36 29 27
cn 6680 19212 20868 13325 13287 count 20 19 19 17 16 Здесь cn - уникальный номер компоненты, присвоенный при разбиении. Конечно в случае с Wikipedia малые компоненты это точки роста. Петель (N1 → N1) в графе нет.
Источников (узлов в которые нет входящих стрелок) - 345597. Это категории нижнего уровня. Стоков (узлов из которых нет исходящих стрелок) 11767. Это категории верхнего уровня дампа и скорее всего "точки роста". Промежуточных узлов, соответственно - 210160.
Максимальное количество исходящих из одного узла стрелок - 85. Это промежуточный узел № 690451, а заголовок "Category:World War II", т.е. эта категория приписана 85 над-категориям. Максимальное количество входящих стрелок (12625) имеет промежуточный узел № 692309 с проясняющим заголовком - "Category:Albums by artist". 2 Анализ заголовков Заголовки всех узлов категорий (включая изолированные) можно посмотреть в отчёте в таблице указанной в разделе «Анализ заголовков». Таблица содержит - 584606 узлов. Таким образом 9190 узлов ГКВ не имеют заголовков. Они ждут своего исследователя. Анализ текстов заголовков даже безотносительно их подчинения отдельная увлекательная задача. Но начать надо с использованного состава букв. 2.1 Алфавит
Рассмотрим состав букв (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|~|¡|ª|°|µ|· |º|½|Á|Â|Ä|Å|Æ|Ç|É|Í|Î|Ñ|Ó|Õ|Ö|×|Ø|Ú| Ü|Þ|ß|à|á|â|ã|ä|å|ae|ç|è|é|ê|ë|ì|í|î|ï |ð|ñ|ò|ó|ô|õ|ö|ø|ù|ú|û|ü|ý|þ|ÿ|Ā|ā|ă| ą|Ć|ć|Č|č|ď|Đ|đ|ē|ė|ę|ě|ğ|Ħ|ħ|Ī|ī|İ|ı |ļ|Ľ|ľ|Ł|ł|ń|ņ|ň|Ō|ō|ő|oe|ř|Ś|ś|Ş|ş|Š| š|Ţ|ţ|ť|ū|ŭ|ů|ŵ|ź|Ż|ż|Ž|ž|ơ|ș|ʻ|||ḵ|ṭ|ạ |ầ|ậ|ắ|ế|ề|ể|ễ|ệ|ị|ọ|ộ|ụ|ỳ|ỹ|–|— |‘|’|…|共|台|和|國|歲|灣|萬|！|
В прикреплении id2title.abc.txt к отчёту можно посмотреть впечатляющее разнообразие букв заголовков всех статей Wikipedia(en). 2.2 Термины в заголовках
Это может быть отдельное важное исследование. Например, количество заголовков в которых встречается слово album - 17591. 3 Стоки
В Приложении-1 к отчёту можно посмотреть начало таблицы стоков с самым большим количеством входящих стрелок. 3.1 От Анастасии к Музыке
В Приложении-2 к отчёту можно посмотреть путь рекордсмен предоставленный Антоном Коршуновым.
Самый длинный путь - 294 вершины. Его начальная категория - № 5760285 Category:Anastacia songs, а конечная - № 691484 Category:Music. 4 Строение ГКВ в целом
В работе [
Количество стрелок в ядре - 38538. Узлов же 13545. Граф ядра опубликован в таблице указанной в разделе «Состав ядра» отчёта. Далее было выполнено "расщепление" ядра на связные компоненты. Это особенно важно, т.к. пути между циклами, сами не входящие в циклы, составляют самостоятельную интересную часть ядра. Оказалось, что имеется одна большая компонента - 13507 узлов. И ещё 19 пар узлов. Характеристики узлов ядра включая разбиение на связные компоненты можно посмотреть в таблице указанной в разделе «Состав ядра» отчёта.
Рассмотрим компоненту №764 ядра. Это пример пары, которая является даже связной компонентой не только ядра, а самого ГКВ. В компоненте два узла: 28736601, Category:Wikipedia sockpuppets of ShantanuSingh198 и 28736686, Category:Suspected Wikipedia sockpuppets of ShantanuSingh19
В Wikipedia они также ссылаются друг на друга
и больше ни на что.
Анализ. Что бы ни обозначало "Wikipedia
sockpuppets of ShantanuSingh198" очевидно что
нечто под него подпадающее (как под понятие) не
может быть одновременно лишь "подозреваемым"
на подпадание. Равно как и наоборот, т.е. логически
эти две категории не пересекаются. И обе стрелки
должны быть удалены. Отношения же между ними
на, например, OWL 2 [
При этом более правильно ссылаться в обоих статьях друг на друга через тэг Wikipedia «See also». Рис. 1 Рисунок графа компоненты ССК 41 5.2 Сильно связные компоненты ядра
В ядре нас интересует зацикливание отношения под-категория - над-категория. Тут есть два подхода:
- общий - применить алгоритм поиска сильно связных компонент (ССК);
- частный - найти так называемые "линзы" - два узла ссылающиеся друг на друга (как под-категория - над-категория).
Второй путь вполне приемлем для ГКВ, т.к. по идее в нём вообще не должно быть циклов. Впрочем как для линз так и для циклов большей длины следует заметить, что они математически утверждают эквивалентность соответствующих терминов, т.е. синонимию, что в принципе возможно. Но конкретно в Википедия может быть реализовано через redirect. Интуитивно же в большинстве случаев мы обнаружим ошибку, т.е. какие-то стрелки цикла ошибочны.
Чтобы получить состав сильно связных
компонент ядра была использована программа Pajek
[
ССК оказалось 457. Узлов не входящих в ССК, так сказать связующих ядра — 7646. Есть одна гигантская по сравнению с остальными ССК - в ней 3967 узлов.
В отчёте в разделе «Сильно связные компоненты ядра» приведена таблица самых больших ССК. Рассмотрим для примера компоненту №41 у которой всего 9 узлов (см. рис. 1).
Если номер накладывается на стрелку то под ним наконечника (треугольничка) нет. Это важно т.к. Pajek рисует "линзы" (У1 → У2 → У1) как одну стрелку с наконечниками на обоих окончаниях. В данной ССК линза одна - слева внизу вертикально. ni 717227 717302 799461 799587 6110893 8398752 title
5.3 Линзы
Линза это два узла такие что: У1 → У2 и У2 → У1. Она может быть отдельной ССК, а может входить в ССК как часть.
В ядре оказалось 1269 линз. Из них 1260 имеют заголовки для обоих узлов. Их можно посмотреть в таблице указанной в разделе «Линзы» отчёта. 6 Мантия - ациклическая часть ГКВ
Чтобы получить мантию мы удаляем из ГКВ ядро. При этом оказывается, что часть источников и стоков станет изолированными. В первом случае все из них исходящие стрелки попали в ядро, во втором - все входящие в них стрелки шли из ядра. Изолировавшихся источников - 14421, а стоков - 60.
Кроме того в мантии появляются ложные вершины (пики). Это те её узлы, которые стали стоками после удаления ядра, а вообще-то имели исходящие стрелки, которые все попадали в ядро. Таких вершин 18157. Причём максимальная высота - 28. Для сравнения, стоков ГКВ получивших уровень, т.е. не изолированных - 11707, максимальная высота - 24.
Ложная вершина - рекордсмен (высоты 28) имеет №15715670, а заголовок "Category:Creation myths".
Замечание. Конечно ГКВ можно представить и в
виде "галстука-бабочки" как в работе [
Количество узлов на уровнях показано ниже в табличке и оправдывает сравнение с горами: В таблице в строке с level = NULL - количество изолированных узлов мантии, а у 0 - количество узлов в ядре. 7 Связующие стрелки
Между мантией и ядром есть стрелки-связующие. Стрелок из ядра в мантию - 591. Стрелок из мантии в ядро — 210514. 8 Другие способы исследования
Можно напрямую изучать 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." [
А вот запрос select ?x ?z where выдаёт "линзы".
Вот узлы первой: {?x skos:broader ?z. ?z skos:broader ?x.} http://dbpedia.org/resource/Category:Poli tical_philosophers http://dbpedia.org/resource/Category:Poli tical_theorists Она действительно есть в Wikipedia(en). и А всего запрос выдаёт 2000 линз, что наверно не предел. 9 Заключение
Естественно считать, что ГКВ должен быть ациклическим графом. Таким образом исследование показало, что аномалии значительны.
Можно создать средства, которые обнаруживая аномалию, например линзу, будут размещать на соответствующих страницах в Discussion уведомление о логическом противоречии.
2. Как к логическим противоречиям относятся идеологи Википедии? Те кто задаёт правила классификации. Судя по всему индифферентно.
Общая рекомендация. Многие отношения между категориями попавшие в sub-category of следует перенести в See also.
Оценить предстоящую работу можно так: для начала надо разобраться с 1269 линзами. Они сильно убавят размер ССК.
Только если это нужно википедистам можно было бы продолжить и: - Исследовать длинные пути.
- Попытаться представить архитектуру графа в целом. Например применить 3D визуализацию.
- Проанализировать состав и логику связи заголовков (особенно ССК).
Особняком стоит задача получить и проанализировать русский ГКВ. В проекте dbpedia можно получить дамп русской версии, надо только перекодировать с rdf-кодов букв (например, \u0432) в UTF-8. Литература Investigation of the English version of the Wikipedia categories graph
Wikipedia is the outstanding project of knowledge accumulation. The knowledge is both of the general use, as well of various specialization domains. Quality 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 Graph) as a whole are presented. WCG is a system that supports structure of knowledge and we are interested in WCG content and its arrangement. It is shown that in graph there are unacceptable logical violations; organizational and technical methods for their elimination are discussed.