pythonのエッジの密度と重さに基づいてネットワークを持つクラスタを見つける方法 - networkxパッケージ

Question

pythonパッケージnetworkxを使ってネットワークを構築しました。各エッジには、相関。

クラスタ化されたグラフを返すアルゴリズムが組み込まれており、各ノードにクラスタID（1〜k）を割り当てるのが理想的です。

これが行うことができる方法を任意のアイデアそれはエッジの重量に基づいてクラスタ化することができればさらに良いことが、重要ではない...

でしょうか？

Answer 1

python-louvainのパッケージを調べるとよいでしょう。これを使用すると、関数best_partitionを使用してグラフ内のコミュニティを検出できます。機能の説明から：

Compute the partition of the graph nodes which maximises the modularity (or try..) using the Louvain heuristices

This is the partition of highest modularity, i.e. the highest partition of the dendrogram generated by the Louvain algorithm.

私の例で私はkarate_club_graphのためのコミュニティを計算します。 （私は私のグラフは、エッジを加重ていないにもかかわらず、weightキーワードでbest_partitionを使用することに注意してください - 私はちょうどあなたがあなたのケースで機能を使用する方法を示しています）

import networkx as nx 
import community 

G = nx.karate_club_graph() 
p = community.best_partition(G, weight='weight') 
print(p) 

出力：

{0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 0, 8: 2, 9: 0, 10: 1, 11: 0, 12: 0, 13: 0, 14: 2, 15: 2, 16: 1, 17: 0, 18: 2, 19: 0, 20: 2, 21: 0, 22: 2, 23: 3, 24: 3, 25: 3, 26: 2, 27: 3, 28: 3, 29: 2, 30: 2, 31: 3, 32: 2, 33: 2} 

出力は辞書（key = node、value = partition）です。区画は0からk-1になる。 1からkにする必要がある場合は、ディクショナリの値を+1するだけで済みます。

for k, v in p.items(): 
    p[k] = v + 1