Термин «
граф свойств » стал обозначать атрибутивный многореляционный граф. То есть график, на котором ребра помечены, а вершины и ребра могут иметь любое количество свойств ключ / значение, связанных с ними.
s
Пример графа свойств с двумя вершинами и одним ребром приведен ниже.
Графики свойств являются более сложными, чем общеизвестные стандартные однореляционные графы . Причина этого заключается в том, что существуют разные типы вершин (например, люди , компании , программное обеспечение ) и разные типы ребер (например, знает , works_for , импорт ). Сложности, добавленные этой структурой данных (и вообще многомерными графами, например графами RDF ), влияют на то, как определяются и оцениваются алгоритмы графов.
Стандартные учебники по теории графов, как правило, представляют общие алгоритмы, такие как различные центральности , геодезические , ассортативные микширования и т. Д. Эти алгоритмы обычно поставляются в комплекте с однореляционными наборами инструментов и средами (например, NetworkX , iGraph ).
Обычно люди желают таких алгоритмов графа, когда они начинают работать с программным обеспечением графа свойств. Меня много раз спрашивали:
«Поддерживает ли программное обеспечение графа свойств, над которым вы работаете, какой-либо из общих алгоритмов центральности? Например, PageRank , близость , промежуточность и т. Д.? »
Мой ответ на этот вопрос всегда:
«Что вы подразумеваете под центральностью в графе свойств?»
Когда неоднородный набор вершин может быть связан неоднородным набором ребер, существует множество способов вычисления центральности ( или любого другого стандартного алгоритма графа в этом отношении ).
- Не обращайте внимания на метки ребер и используйте стандартные алгоритмы централизации с одним реляционным графом.
- Выделите определенный «фрагмент» графа (например, подграф знает ) и используйте стандартные алгоритмы центральности для одного реляционного графа.
- Используйте абстрактные смежности для вычисления центральности с семантикой высшего порядка.
Цель этого сообщения в блоге состоит в том, чтобы подчеркнуть пункт № 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)
Вышеуказанные выражения имеют следующие значения:
- Сотрудничество центральность
- Корпорация ACME центральный сотрудник
- Коллеги, которые импортируют 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/