Статьи

Еженедельный алгоритм: Алгоритмы графа свойств


Термин «
граф свойств » стал обозначать атрибутивный многореляционный граф. То есть график, на котором ребра помечены, а вершины и ребра могут иметь любое количество свойств ключ / значение, связанных с ними.


s

 

Пример графа свойств с двумя вершинами и одним ребром приведен ниже.

Графики свойств являются более сложными, чем общеизвестные стандартные однореляционные графы . Причина этого заключается в том, что существуют разные типы вершин (например, люди , компании , программное обеспечение ) и разные типы ребер (например, знает , works_for , импорт ). Сложности, добавленные этой структурой данных (и вообще многомерными графами, например графами RDF ), влияют на то, как определяются и оцениваются алгоритмы графов.

Стандартные учебники по теории графов, как правило, представляют общие алгоритмы, такие как различные центральности , геодезические , ассортативные микширования и т. Д. Эти алгоритмы обычно поставляются в комплекте с однореляционными наборами инструментов и средами (например, NetworkX , iGraph ).

Обычно люди желают таких алгоритмов графа, когда они начинают работать с программным обеспечением графа свойств. Меня много раз спрашивали:

«Поддерживает ли программное обеспечение графа свойств, над которым вы работаете, какой-либо из общих алгоритмов центральности? Например, PageRank , близость , промежуточность и т. Д.? »

Мой ответ на этот вопрос всегда:

«Что вы подразумеваете под центральностью в графе свойств?»

Когда неоднородный набор вершин может быть связан неоднородным набором ребер, существует множество способов вычисления центральности ( или любого другого стандартного алгоритма графа в этом отношении ).

  1. Не обращайте внимания на метки ребер и используйте стандартные алгоритмы централизации с одним реляционным графом.
  2. Выделите определенный «фрагмент» графа (например, подграф знает ) и используйте стандартные алгоритмы центральности для одного реляционного графа.
  3. Используйте абстрактные смежности для вычисления центральности с семантикой высшего порядка.

Цель этого сообщения в блоге состоит в том, чтобы подчеркнуть пункт № 3 и мощь алгоритмов графа свойств. В Gremlin вы можете вычислить многочисленные центральности собственных векторов для одного экземпляра графа свойств. В этот момент вы можете спросить: «Как граф может иметь более одного первичного собственного вектора?» Ответ заключается в том, чтобы увидеть все графы, которые существуют внутри графа, то есть увидеть все производные, неявные, виртуальные, абстрактные смежности высшего порядка. Каждая строка ниже иллюстрирует точки # 1, # 2 и # 3 в списке выше, соответственно. В примерах кода используется степенной метод для вычисления рангов центральности вершин, которые хранятся в карте m .

g.V.outE.inV.groupCount(m).loop(3){c++ < 10000} // point #1
g.V.outE[[label:'knows']].inV.groupCount(m).loop(4){c++ < 10000} // point #2
g.V.???.groupCount(m).loop(?){c++ < 10000} // point #3

??? в строке 3 указывается на то, что ??? может быть любое произвольное вычисление. Например, ??? возможно:

outE[[label:'works_for']].inV.inE[[label:'works_for']].outV
outE[[label:'works_for']].inV[[name:'ACME']].inE[[label:'works_for']].outV
outE[[label:'develops']].inV.outE[[label:'imports']].inV[[name:'Blueprints']].back(7).outE[[label:'works_for']].inV.inE[[label:'works_for']].outV.outE[[label:'develops']].inV.outE[[label:'imports']].inV[[name:'Blueprints']].back(7)

Вышеуказанные выражения имеют следующие значения:

  1. Сотрудничество центральность
  2. Корпорация ACME центральный сотрудник
  3. Коллеги, которые импортируют Blueprints в свою центральную часть программного обеспечения

Есть множество графиков внутри графика. Таким образом, «что вы подразумеваете под центральностью?»

Эти идеи более подробно рассматриваются в следующей статье и слайд-шоу.

Родригес М.А., Шинавье Дж. « Экспонирование много-реляционных сетей в алгоритмах анализа одно-реляционных сетей », журнал Informetrics, 4 (1), с. 29-41, Elsevier, doi: 10.1016 / j.joi.2009.06. 004, 2009.

 

Гремлин в графе


Посмотреть больше
презентаций от

Источник: 
http://markorodriguez.com/2011/02/08/property-graph-algorithms/