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

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

источник

2011-12-05 Paul Jackson

Вы хотите специальное решение для Neo4j, или вы ищете более общую стратегию? –

Я хотел бы сохранить его в Neo4J (хотя ответ должен применяться к любому хранилищу графиков свойств). Я хотел бы избежать использования альтернативного механизма сохранения, такого как хранилище SQL или B-tree. –

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

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

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

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

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

источник

2011-12-06 14:34:08 Nicolas78

Я думаю, что предпочитаю это решение для свойств края по нескольким причинам; Я могу разделить эту информацию на два свойства и запрос для n-го узла, а также для всех узлов, подключенных под n; Я не могу запросить свойства края; Все узлы (кроме последнего) имеют свойство; И, наконец, он предоставляет имя для виртуального узла, представляющего сообщество. Благодарю. –

@PaulJackson Это решение является довольно стандартным (и хорошим) подходом к хранению дендрограммы. Он также явно противоречит тому, что вы задаете в своем вопросе. Возможно, некоторые изменения вашего вопроса - это порядок, если на самом деле вам не нужно хранить информацию сообщества в самом графике. –

@ MichaelJ.Barber (прежде всего, это большая честь, я на самом деле цитирую вашу статью о двухпартийном обнаружении сообщества в моей диссертации). Я предлагаю хранить один атрибут на узел, обозначающий его роль в дендрограмме, прикрепленную к самому узлу в графическом представлении Neo4J, а не хранение дендрограммы где-то вне графика. – Nicolas78

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

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

источник

2011-12-05 15:22:22

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

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

ответ

Смежные вопросы