初識機器學習：Louvain 社群發現演算法

這是我參與「掘金日新計劃 · 8 月更文挑戰」的第6天，點選檢視活動詳情

本篇介紹一種社會網路分析演算法 Louvain，Louvain 是一個基於模組度的社群發現演算法，可以高效地在網路中找出群組。

社會網路分析

社會網路分析（Social network analysis, SNA）是一種使用網路和圖來分析社會化結構的一種方法。可以運用於多個領域，比如社交媒體、知識網路、病毒式營銷、傳染病建模等等。

Louvain 演算法可以在一個網路中找出群組，比如，識別社交媒體中熟人關係網路中的社交圈子、識別國際貿易關係網路中的利益聯盟，等等。

Louvain 的基本原理簡述

在一個網路中，存在「節點」和「邊」兩種元素。一個節點代表網路中的一個個體，比如社交網路中的一個人，邊則表示被它連線的兩個節點之間的關係，比如，連線 A 和 B 兩個節點的邊，表示一個社交網路中 A 和 B 是好友關係，除此之外，還可以用權重（比如表現為邊的粗細）來表示兩者之間關係的強弱。

Louvain 演算法的目標是在一個網路中識別群組，使得：

• 同一個群組中的節點之間，邊的數量和強度最大化

• 屬於不同群組的邊數和強度最小化

這個目標其實跟聚類演算法要實現的最終目標很相似（02. 初識機器學習：k均值聚類 ）。它們的運算原理其實也很相似，需要一個初始的狀態，然後通過重複執行幾個步驟，不斷迭代，最終達到理想的狀態：

1. 把每一個節點都看成一個小的群組。

1. 對每一個節點執行操作：把它重新分配給能最提高模組度的群組，如果無法在提高模組度，則不進行重新分配。

1. 把上一步中發現的每一個群組作為一個節點，並將之前群組之間的邊合併成新的帶權重的邊。

1. 重複第 2 步和第 3 步，直到無法再進行分配。

侷限性

Louvain 的到的結果包含的一些缺陷，與聚類演算法也很類似，那就是它無法找出有重疊或者巢狀關係的群組。並且，它無法識別一些規模較小但是比較重要的群組，如果需要找到這些群組，只能人為干預。