Louvain(ルーヴァン)法の概要と使い方
概要
- Louvain法は、ネットワークのコミュニティ検出アルゴリズムの一つ
- 基本的に使用するネットワークは無向グラフ
- コミュニティを検出した結果からページランクや中心性などの指標を計算することができる
動作方法
- 最初にすべてのノードを個別のコミュニティとして初期化
- ノードを順に処理し、隣接するノードとの結合を試みる
- 結合によってコミュニティのモジュラリティが最大化される場合、そのノードをコミュニティに追加
- モジュラリティとは、ネットワークの内部リンクと外部リンクの比率を示す指標
- ランダムにリンクを配置した場合の期待値と比較して、実際のリンク数がどれだけ多いかを示す
- モジュラリティとは、ネットワークの内部リンクと外部リンクの比率を示す指標
- このプロセスを繰り返し、コミュニティの構造が安定するまで続ける
- 最終的に、各ノードが所属するコミュニティが決定される
ライブラリ
$ pip install python-louvain networkx
使用例
import networkx as nx
import community as community_louvain
import matplotlib.pyplot as plt
# 1. グラフの作成 (例として空手クラブのグラフを使用)
G = nx.karate_club_graph()
# 2. Louvain法によるコミュニティ分割の計算
# best_partitionは, 各ノードがどのコミュニティに属するかを辞書形式で返す
partition = community_louvain.best_partition(G)
# 3. 結果の可視化
pos = nx.spring_layout(G)
cmap = plt.cm.get_cmap('viridis', max(partition.values()) + 1)
nx.draw_networkx_nodes(G, pos, partition.keys(), node_size=200,
cmap=cmap, node_color=list(partition.values()))
nx.draw_networkx_edges(G, pos, alpha=0.5)
plt.title("Louvain Community Detection")
plt.show()
# 4. モジュラリティの計算
modularity_value = community_louvain.modularity(partition, G)
print(f"Modularity: {modularity_value}")