グラフでコミュニティ情報を維持する方法

Question

NEO4Jで持続するグラフデータベース（友達ネットワーク、購入履歴など）がいくつかあります。これらを分析する予定です コミュニティ検出アルゴリズム そのような Girvan Newman. 。これらのアルゴリズムは通常、aを返します 樹状図, 、ネットワーク全体から個々のノードへのグラフの分割を表します。私はこれらの結果をどのように持続させるのだろうと思っています。別のグラフとして保存できると思いますが、グラフ自体に保存する方法はありますか？そうすることの私の懸念は、グループを表すノードを作成する必要性です。これは私が避けたいものです。

Answer 1

樹状図を表す1つの方法は、N要素の（n-1）ペアを含むペアのリストとしてです。ペアの左要素がコミュニティ内のすべての要素を参照するためにIDが保持されているものであると仮定すると、サンプル樹状図は次のように見えるかもしれません

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

したがって、各ノードに保存する可能性のある別の方法は、その時点で別のノードにマージされます（以前にマージされたすべてのノードと一緒に）。

したがって、（0：0）を1、（1：2）から3、（2：0）から2（Timestep：New 'Name' of Node）に添付します。

編集：具体的には、これは、各neo4jノードオブジェクトに「merge_timestep」と「merge_into」などの2つの整数値属性を添付することを意味する場合があります。

Answer 2

ほとんどのコミュニティ検出アルゴリズムは、グラフ内の既存のエッジに沿ってコミュニティを集積することにより機能します。 Girvan-Newmanは、エッジを切ることで機能するという点で少し珍しいです。いずれにせよ、樹状図は、グラフのエッジ上の操作の順序を示すものとして見ることができます。したがって、樹状図を別のオブジェクトとして保存する代わりに、どの順序でマージ/カットする必要があるかを示すエッジ（関係）にプロパティを取り付けることができます。 Neo4Jの私の知識は非常に限られているので、詳細をお知らせします。

一般に複数の同等のエッジがあり、それぞれがコミュニティ内の異なる頂点を合併するためにリンクするため、マージにはいくつかの合併症があります。基本的に、エッジからリンクされたコミュニティを把握できる戦略を選択するだけです。