Статьи

Изучение графического представления Википедии с помощью Gremlin

График представляет собой структуру данных , состоящая из вершин и ребер. Эти термины являются синонимами следующего:

  • вершины, точки, узлы, вещи, точки
  • ребра, линии, ссылки, отношения, дуги

На основе вершин и ребер можно моделировать и обрабатывать многочисленные искусственные и реальные системы. Цель этого поста — изучить графическое представление Википедии, сохраненное в базе данных графов Neo4j и обработанное с использованием языка обхода графов Gremlin . Обратите внимание, что DBPedia предоставила дружественное для анализа представление Википедии, а настоящий анализ и презентация предоставлены совместными усилиями Aurelius и Лаборатории интеллектуальных систем в PARC ( компания Xerox ).

На графике природы Википедии

Существует множество способов представления Википедии в виде графика. Статьи и гиперссылки между ними — это один из способов. Этот тип графа известен как реляционный граф, потому что все ребра имеют одинаковое значение — гиперссылка. Более сложный рендеринг может представлять людей, обсуждаемых в статьях, как «людей-вершин», которые знают других «людей-вершин» и живут в определенных «городах-вершинах» и работают на различные «компании-вершины» — и так далее, и тому подобное. до тех пор, пока не появится многоотносительный граф понятий . Для целей данного поста используется представление среднего уровня. Вершинами являются статьи Википедии и категории Википедии . Края гиперссылкимежду статьями, а также таксономические отношения между категориями.

Используя Gremlin, вычисляется некоторая описательная графическая статистика этого представления. Наряду с количеством вершин и ребер, распределение графа в градусах и градусах приведено ниже. Эти расчеты распределения не зависят от меток ребер.

gremlin> g = new Neo4jGraph('/data/dbpedia')
neo4jgraph[/data/dbpedia]
gremlin> g.V.count()
30962172
gremlin> g.E.count()
191767951 
gremlin> outDegrees = [:]; inDegrees = [:]
gremlin> g.V.transform{it.out.count()}.groupCount(outDegrees).iterate()
gremlin> g.V.transform{it.in.count()}.groupCount(inDegrees).iterate()
gremlin> f = new File('out-degrees.txt')
gremlin> outDegrees.each{k,v -> f.append(k + '\t' + v + '\n')}
gremlin> f = new File('in-degrees.txt')
gremlin> inDegrees.each{k,v -> f.append(k + '\t' + v + '\n')}

Сгенерированные Gremlin файлы out-степень.txt и in-степень.txt загружаются в R Statistics и выводятся на график.

R version 2.13.1 (2011-07-08)
Copyright (C) 2011 The R Foundation for Statistical Computing

 out.degrees <- read.table('out-degrees.txt', sep='\t')
 in.degrees <- read.table('in-degrees.txt', sep='\t')
 plot(out.degrees, log='xy', main='Wikipedia Out-Degree Distribution', xlab='Out Degree', ylab='Frequency', cex.lab=1.5, cex.axis=1.5, cex.main=1.5)
 plot(in.degrees, log='xy', main='Wikipedia In-Degree Distribution', xlab='In Degree', ylab='Frequency', cex.lab=1.5, cex.axis=1.5, cex.main=1.5)

 

О ссылочной природе идей

Одним ленивым воскресным днем ​​Гремлин входит в свою библиотеку. Запах кожи и красного дерева побеждает его чувства. Его глаза сканируют полки, заполненные книгами на все мыслимые темы. В один вдохновенный день много лун назад Гремлин распечатал каждую статью в Википедии, связал ее и сохранил. В этом конкретном случае Гремлин решает рассмотреть один из своих любимых предметов: теорию графов. С полки Гремлин достает книгу с уважением под названием « Теория графов» .

gremlin> v = g.idx(T.v)[[uri:'http://dbpedia.org/resource/Graph_theory']].next()
v[26634]
gremlin> v.map()
name=graph theory
uri=http://dbpedia.org/resource/Graph_theory

Гремлин взламывает крышку теории графов. К своему изумлению, он замечает, что слова в книге ссылаются на другие книги на его полке! [строка 1] Он задается вопросом, сколько таких ссылок существует? [строка 7]

gremlin> v.out('href').name[0..4]
mathematics
computer science
graph (mathematics)
vertex (graph theory)
graph of a function
gremlin> v.out('href').count()
240

По одной ссылке за раз, Гремлин достает соответствующую книгу со своей полки и просматривает ее страницы. Невероятно, эти книги также ссылаются на другие книги! [строка 1] Сколько ссылок имеют ссылки на Теорию графов? [строка 8] Ошеломленный обходной природой идей, определяемых в терминах других идей, Гремлин приходит к пониманию внутренней структуры графа знания — его самореференциальной природы [строка 9].

gremlin> v.out('href').out('href').name[0..4]
mathematics (disambiguation)
math (disambiguation)
euclid
greek language
quantity
gremlin> v.out('href').out('href').count()   
21182
gremlin> v.out('href').dedup.out('href').out('href').retain([v]).paths{it.name}[0..4]
[graph theory, mathematics, logic, graph theory]
[graph theory, mathematics, history of mathematics, graph theory]
[graph theory, mathematics, operations research, graph theory]
[graph theory, mathematics, paul erdős, graph theory]
[graph theory, mathematics, theoretical computer science, graph theory]

Есть только так много времени, когда маленький зеленый Гремлин начинает жить. Он задается вопросом, в чем он будет экспертом, если продолжит читать книгу за книгой, как продиктовано ссылками, которые они поддерживают друг с другом.

gremlin> v.in('href').name[0..4]
semiotics of the structure
sones graphdb
trapezoid graph
alpha centrality
block graph

О периодической природе мысли

Часами часами и днями днями Гремлин переходит от книги к книге. Иногда снова возвращаюсь к чтению предыдущей книги. С точки зрения фильма с большой выдержкой его форма выглядит как пятно среди его коллекции. Однако это размытие не равномерно распределено по его библиотеке. На самом деле, он более склонен читать одни книги, чем другие. Те книги, которые являются наиболее важными в структуре гиперссылок, — те, которые наиболее вероятно встретятся на случайной прогулке Гремлин, В своей книге Гремлин решает записать потенциал того, что он будет читать какую-то одну книгу в любое время. Изначально все страницы одинаково вероятны. [строка 1] Он начинает свое путешествие в теории графов. [строка 2] Он смотрит, сколько «потенциала» существует для теории графов. [строка 3] Затем он извлекает всех исходящих соседей Теории графов. [строка 4] Он определяет общее количество соседей. [строка 5] Каждому соседу он равномерно распределяет потенциал Теории графов среди них. [строки 6–8] Затем Гремлин переходит к упомянутым книгам теории графов и продолжает процесс снова и снова, снова и снова, 100 000 шагов. Начиная с вершины теории графов, Gremlin диффундирует себя как волны над структурой , которая окружает.

gremlin> m = [:].withDefault{1}
gremlin> v.transform{
  rank = m[it.name]; 
  neighbors = it.out('href').toList();
  degree = neighbors.size();
  neighbors.each {
    m[it.name] = m[it.name] + (rank/degree);
  }
  neighbors;
}.scatter.range(0,100000).loop(3){true}.iterate()
null

Гремлин просматривает 10 лучших записей в своей книге. Именно здесь его распространение показывает наибольшее количество повторений — оно определяет, какую книгу он, скорее всего, прочитает в любой момент из следующих 100 000 прочитанных книг.

gremlin> m.sort{a,b -> b.value <=> a.value}[0..9]
mathematics=8.2325984930913507177010807338237871640327644591
graph theory=6.3579261869065686025097269665928272601625649213
graph (mathematics)=3.8056391897097907459393869524402476473212892533
computer science=3.2189950001323052861187247709061777261390151631
real number=2.942860316400352223267769366106131293745859000
mathematician=2.751409475433875926984889918863144276736916
number theory=2.7296994022747017139496107107489077766999403538
combinatorics=2.6983273156966484352429094611889032326648909856
topology=2.6822253369205954921236082679389161746453858919
set theory=2.5682887400468326671894663603540368070624776875

О таксономической природе категорий

 Библиотека Гремлин — это не просто полки с книгами. В его библиотеке также есть карточный каталог. Каталог индексирует книги по категориям. Более того, в каждой книге есть ссылка на свою предметную категорию. Например, предметная категория теории графов, ну … «теория графов». Каталог также структурирован так, что категории ссылаются друг на друга. Например, «комбинаторика» является более широкой категорией, чем «теория графов». Ради удовольствия Гремлин решает переключаться между книгами и категориями.

gremlin> v.out('subject').name
graph theory
gremlin> v.out('subject').out('broader').name
combinatorics
mathematics

Чтобы увидеть слои в широком масштабе , Гремлин выставляет категорию «кольца», исходящую из «теории графов».

gremlin> x = [];
gremlin> v.out('subject').out('broader').gather{t = it.unique(); x.add(t*.name); t}.scatter.loop(3){it.loops < 7}.iterate()
null
gremlin> x
[combinatorics, mathematical relations]
[subdivisions of mathematics, discrete mathematics, mathematics, predicate logic]
[mathematics, subfields by academic discipline, subdivisions of mathematics, main topic classifications, abstraction, formal sciences, structure, scientific disciplines, systems of formal logic]
[main topic classifications, abstraction, formal sciences, structure, scientific disciplines, categories by topic, academic disciplines, mathematics, subfields by academic discipline, articles, thought, innovation, problem solving, creativity, analogy, concepts, logic, interdisciplinary fields, formalism (deductive), matter, dimension, form, science, mathematical logic, formal systems]
[articles, thought, structure, innovation, problem solving, creativity, analogy, concepts, academic disciplines, logic, interdisciplinary fields, scientific disciplines, formalism (deductive), matter, dimension, form, science, subfields by academic discipline, categories by parameter, academia, categories by topic, main topic classifications, abstraction, formal sciences, contents, mind, cognition, mental processes, mental content, technological change, intelligence, critical thinking, human skills, human behavior, action, quality, fundamental categories, branches of philosophy, axiology, theories of deduction, formalism, fundamental physics concepts, universe, nature, ontology, manifolds, physical quantities, knowledge, subdivisions of mathematics, discrete mathematics, mathematical logic, metalogic, formal theories, logical syntax]
[contents, mind, cognition, mental processes, mental content, matter, concepts, dimension, form, technological change, intelligence, creativity, innovation, critical thinking, human skills, human behavior, action, quality, thought, fundamental categories, academia, categories by topic, abstraction, branches of philosophy, interdisciplinary fields, axiology, science, academic disciplines, subfields by academic discipline, theories of deduction, formalism, fundamental physics concepts, universe, nature, ontology, manifolds, physical quantities, knowledge, main topic classifications, categories, education, categories by parameter, articles, structure, problem solving, analogy, logic, scientific disciplines, formalism (deductive), cognitive science, concepts in metaphysics, philosophy of mind, consciousness, epistemology, psychology, technology, economic development, technological change, and growth, neurology, neuroscience, memory, learning, educational psychology, philosophical logic, evaluation, life skills, skills, humans, behavior, phenomena, determinism, free will, motion, management, philosophy by field, value, deduction, scientific theories, philosophical theories, philosophy of mathematics, physics, concepts by field, physical cosmology, astrophysics, astronomical dynamical systems, reality, everything, life, metaphysics, philosophy of science, topological spaces, differential geometry, geometric topology, measurement, information, perception, concepts in epistemology, mathematics, subdivisions of mathematics, discrete mathematics, metaphilosophy, metatheory, theories, formal languages, formal sciences, syntax]

Эти кольца полезны для того, чтобы увидеть, что касается каждого шага прогулки. Однако, чтобы увидеть перевернутую древовидную структуру, Гремлин вкладывает свой обход, чтобы категории были сгруппированы по дочерним элементам . Гремлин записывает иерархию потребления как категории, расширяющие друг друга.

gremlin> v.out('subject').out('broader').groupBy{it.name}{
  it.out('broader').groupBy{it.name}{
    it.out('broader').name
  }.cap.next()
}.cap.next()
mathematical relations=[{mathematics=[main topic classifications, abstraction, formal sciences, structure, scientific disciplines], predicate logic=[systems of formal logic]}]
combinatorics=[{discrete mathematics=[subdivisions of mathematics], subdivisions of mathematics=[mathematics, subfields by academic discipline]}]

Библиотека Гремлин — это приключение в увлекательном мире взаимосвязанных идей.

Рекомендации

Бизер, С., Леманн, Дж., Кобиларов, Г., Ауэр, С., Беккер, С., Циганияк, Р., Хеллманн, С., « DBpedia — точка кристаллизации для сети данных », журнал Семантика Сети, 7 (3), 2009.

Родригес М.А., Пепе А., Шинавье Дж. « Тройная дилатация », Emergent Web Intelligence: передовые семантические технологии, серия усовершенствованной обработки информации и знаний, 3–16, 2010.

Ньюман, MEJ, « Структура и функции сложных сетей », SIAM Review, 45, 167–256, 2003.

Bollen, J., Ван де Sompel, Х., Хагберг А., Бетанкур, LMA, парашюта, Р. Родригес, М., Балакирева, LL, « Clickstream данных Урожайность высоким разрешением High Resolution карты науки » PLoS One, Общественные Научная библиотека, 4 (3), e4803, 2009.