Mímisbrunnr知恵の泉

← ネットワーク科学 一覧

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：クラスタ係数と推移性　|　関連：モジュラリティ最大化・近接中心性・媒介中心性

要点（BLUF）

概念：ネットワークの中の集団

ソーシャルネットワークには友人グループ、Web には話題クラスタ、タンパク質ネットワークには機能モジュール。多くの実ネットワークは「内部が密・外部が疎」な部分集団に分かれます。これを見つけるのがコミュニティ検出。データ点をグループ分けする統計のクラスタリングを、グラフという関係データに持ち込んだものです（クラスタリング一般は機械学習・統計のturf、ここはグラフ特有の構造に集中）。

問題設定と「良さ」の難しさ

コミュニティに普遍的な厳密定義はありません。「密」をどれくらい密と言うか、ノードが複数集団にまたがる場合（重複コミュニティ）をどう扱うかで流儀が分かれます。そこで実務では「分割の良さ」を測る目的関数を決め、それを最適化します。最も標準的な目的関数が次トピックのモジュラリティ（モジュラリティ最大化）です。

古典手法：Girvan–Newman

直観的なアプローチとして、橋渡しエッジを切っていく方法があります。コミュニティ間をつなぐエッジは多くの最短路が通る（エッジ媒介中心性が高い、近接中心性・媒介中心性）。そこを順に除去すると、ネットワークが自然に集団へ割れていきます。

import networkx as nx
from networkx.algorithms.community import girvan_newman

G = nx.karate_club_graph()
comp = girvan_newman(G)
first = tuple(sorted(c) for c in next(comp))
print("Girvan-Newman 最初の2分割サイズ:", [len(c) for c in first])

clubs = nx.get_node_attributes(G, "club")
mr = [n for n in G if clubs[n] == "Mr. Hi"]
print("実際の派閥 'Mr. Hi' サイズ:", len(mr), " もう一方:", G.number_of_nodes()-len(mr))

実行結果：

Girvan-Newman 最初の2分割サイズ: [15, 19]
実際の派閥 'Mr. Hi' サイズ: 17  もう一方: 17

空手クラブは実際に2つの派閥に分裂しました（各17人）。Girvan–Newman の最初の2分割は [15, 19] — おおむね正しいが完全一致ではありません。コミュニティ検出は「正解」を当てる作業ではなく、構造の近似だという点が重要です。

分割の考え方

graph TD
    subgraph C1["コミュニティ A（密）"]
        a1((・)) --- a2((・))
        a2 --- a3((・))
        a1 --- a3
    end
    subgraph C2["コミュニティ B（密）"]
        b1((・)) --- b2((・))
        b2 --- b3((・))
        b1 --- b3
    end
    a3 -. "橋（疎）" .- b1

コミュニティ内は三角形が多く密。集団をつなぐのは少数の「橋」。橋を見つけて切るか、密な塊をまとめ上げるか、アプローチは二通りあります。

数式の直観的意味

コミュニティ検出が難しいのは、「良い分割」が組合せ最適化だからです。nn ノードを集団に分ける方法は天文学的にあり（ベル数）、全探索は不可能。だから「分割の良さ」をスカラー値（モジュラリティ）で測り、それを貪欲に・階層的に改善するヒューリスティクスに頼ります。Girvan–Newman の「媒介中心性の高いエッジ＝橋」という発想は、距離指標（近接中心性・媒介中心性）が集団境界を浮かび上がらせることを利用しています。

⚠️ よくある誤解・落とし穴

対応シミュレーション

本文のコードがそのまま検証用です。良さの定量化は モジュラリティ最大化。

関連