コミュニティ検出入門：クラスタリングからLouvain法まで

はじめに

ネットワーク分析において、コミュニティ検出は重要なタスクの1つです。本記事では、コミュニティ検出の基礎から実践的な実装まで、Google Colabを使って学んでいきましょう。

目次

1. コミュニティ検出とは
2. モジュラリティの概念
3. Louvain法の実装と可視化
4. 実データでの分析例

1. コミュニティ検出とは

コミュニティ検出とは、ネットワーク内で密接に結合したノードのグループを見つけ出す手法です。例えば：

• SNSでの友人グループの特定
• 論文の引用ネットワークにおける研究分野の分類
• 製品の推薦システムにおける類似商品のグルーピング

2. モジュラリティの概念

モジュラリティ（Q）は、コミュニティ分割の品質を評価する指標です：

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from community import community_louvain

# モジュラリティの計算
def calculate_modularity(G, communities):
    Q = 0
    m = G.number_of_edges()
    
    for community in set(communities.values()):
        nodes_in_community = [n for n in G.nodes() if communities[n] == community]
        subgraph = G.subgraph(nodes_in_community)
        
        internal_edges = subgraph.number_of_edges()
        total_degree = sum(dict(G.degree(nodes_in_community)).values())
        
        Q += (internal_edges/m) - (total_degree/(2*m))**2
        
    return Q

# サンプルネットワークの作成
G = nx.karate_club_graph()

3. Louvain法の実装と可視化

Louvain法は、モジュラリティの最適化に基づくコミュニティ検出アルゴリズムです：

# 必要なライブラリのインストール
!pip install python-louvain
!pip install networkx matplotlib
import networkx as nx
from community import community_louvain  # ←ここを変更
import matplotlib.pyplot as plt

# Louvain法によるコミュニティ検出
def detect_communities(G):
    communities = community_louvain.best_partition(G)
    return communities

# 可視化関数
def visualize_communities(G, communities):
    plt.figure(figsize=(10, 10))
    pos = nx.spring_layout(G)
    
    # ノードの描画
    nx.draw_networkx_nodes(G, pos,
                          node_color=list(communities.values()),
                          cmap=plt.cm.rainbow,
                          node_size=500)
    
    # エッジの描画
    nx.draw_networkx_edges(G, pos, alpha=0.5)
    
    plt.title("detect_communities")
    plt.axis('off')
    plt.show()

# 実行例
G = nx.karate_club_graph()
communities = detect_communities(G)
visualize_communities(G, communities)

Louvain法による検出結果の解釈

赤グループ：中心的なノードを含む密なコミュニティ（ハブ構造）
紫グループ：中程度の密度を持つ中間的コミュニティ
水色グループ：比較的小規模な周辺コミュニティ
黄緑グループ：独立性の高い小規模コミュニティ

特徴：

コミュニティ間のエッジは疎
各色のグループ内は密な接続
中心（赤）から周辺（他色）への階層的構造

まとめ

本記事では、以下の内容を学びました：

• コミュニティ検出の基本概念
• モジュラリティによる評価方法
• Louvain法の実装と可視化