community detection 社區發現 (Louvain)

Louvain 算法是一種基於多層次優化 Modularity 的算法，具有快速、準確的優點，在效率和效果上都表現比較好，並且能夠發現層次性的社區結構，被認為是性能最好的社區發現算法之一。

Louvain 算法模型

大型網絡（如社交網路服務或移動電話網路）的典型規模現在以數百萬個節點為單位，並且這些規模要求使用新方法從其結構中檢索綜合信息。

一種有效的方法是將網路分解為子單元或社區，其中連接較為緊密的部分可以被看成一個社區，而在兩個社區間則相對連接較為稀疏。

Modularity 的定義是衡量社區內的緊密程度，它的取值範圍是 [-0.5,1）。該算法來源於論文 《Fast unfolding of communities in large networks》。

• Aij：代表 i 和 j 之間的邊權重，當網路圖不帶權重時，所有邊權重可視為 1。
• m：所有邊的權重和(邊的數量)
• ki：所有與節點 i 相連的邊權重和，kj同理
• Ci：節點 i 的社區，Cj同理。δ(Ci, Cj) 表示若Ci與Cj為同一社區，則回傳 1，否則回傳 0

公式簡化後，可以簡單地理解為社區內部所有邊權重和減去與社區節點相連的邊權重和。

• Σin：表示社區內的邊權重和
• Σtot：表示與社區內的節點相連的所有的邊權重和

Louvain 算法過程

1. 針對每個節點與其鄰近節點做計算，衡量把該節點加入其鄰近節點的社區的 Modularity。選擇最大化 Modularity 值的節點，加入其所在的社區，直到不再發生變化。
2. 將步驟 1 中形成的社區壓縮成一個點，分別計算這些點之間的邊與權重，以及社區內的所有點的邊與權重，用於下一輪的步驟 1 計算。