Как сохранить информацию сообщества в графе

Question

У меня есть несколько графических баз данных (сети друзей, история покупок и т. Д.), Которые я сохраняю с Neo4j. Я планирую проанализировать их с помощью алгоритмов обнаружения сообщества , таких как Girvan Newman . Эти алгоритмы обычно возвращают дендрограмму , представляющую разделение графа от всей сети до отдельных узлов. Мне интересно, как я мог бы сохранить эти результаты. Я предполагаю, что это может быть сохранено как отдельный граф, но есть ли способ сохранить его в самом графике? В связи с этим меня беспокоит необходимость создания узлов для представления групп, чего я бы хотел избежать.

Answer 1

Одним из способов представления дендрограммы является список пар, содержащий (n-1) пар для n элементов. Предполагая, что левый элемент пары - это тот, чей идентификатор сохраняется для ссылки на все элементы в сообществе, образец дендрограммы может выглядеть как

[[0,1],[2,3],[0,2]]

Таким образом, альтернативный способ сохранения, который может заключаться в хранении на каждом узле, на каком временном шаге он объединяется с другим узлом (вместе со всеми узлами, которые ранее были объединены в него).

Таким образом, вы прикрепите (0: 0) к 1, (1: 2) к 3 и (2: 0) к 2 (временной шаг: новое «имя» узла).

edit: Конкретно, это может означать присоединение двух целочисленных атрибутов, например 'merge_timestep' и 'merge_into' для каждого объекта узла Neo4J.

Answer 2

Большинство алгоритмов обнаружения сообществ работают путем объединения сообществ вдоль существующих ребер в графе; Girvan-Newman немного необычен тем, что работает режущими кромками. В любом случае, дендрограмму можно рассматривать как показывающую порядок операций на краях графа. Таким образом, вместо сохранения дендрограммы как отдельного объекта, вы можете прикрепить свойства к ребрам (отношениям), показывающим, в каком порядке они должны быть объединены / вырезаны. Мои знания о Neo4j чрезвычайно ограничены, поэтому я оставлю вам детали.

Существуют некоторые сложности с объединением, так как обычно будет несколько эквивалентных ребер, каждое из которых связывает разные вершины в сообществах для объединения. По сути, просто выберите стратегию, которая позволит вам определить связанные сообщества с самых краев.