初識機器學習:Louvain 社群發現演算法
這是我參與「掘金日新計劃 · 8 月更文挑戰」的第6天,點選檢視活動詳情
本篇介紹一種社會網路分析演算法 Louvain,Louvain 是一個基於模組度的社群發現演算法,可以高效地在網路中找出群組。
社會網路分析
社會網路分析(Social network analysis, SNA)是一種使用網路和圖來分析社會化結構的一種方法。可以運用於多個領域,比如社交媒體、知識網路、病毒式營銷、傳染病建模等等。
Louvain 演算法可以在一個網路中找出群組,比如,識別社交媒體中熟人關係網路中的社交圈子、識別國際貿易關係網路中的利益聯盟,等等。
Louvain 的基本原理簡述
在一個網路中,存在「節點」和「邊」兩種元素。一個節點代表網路中的一個個體,比如社交網路中的一個人,邊則表示被它連線的兩個節點之間的關係,比如,連線 A 和 B 兩個節點的邊,表示一個社交網路中 A 和 B 是好友關係,除此之外,還可以用權重(比如表現為邊的粗細)來表示兩者之間關係的強弱。
Louvain 演算法的目標是在一個網路中識別群組,使得:
- 同一個群組中的節點之間,邊的數量和強度最大化
- 屬於不同群組的邊數和強度最小化
這個目標其實跟聚類演算法要實現的最終目標很相似(02. 初識機器學習:k均值聚類 )。它們的運算原理其實也很相似,需要一個初始的狀態,然後通過重複執行幾個步驟,不斷迭代,最終達到理想的狀態:
- 把每一個節點都看成一個小的群組。
- 對每一個節點執行操作:把它重新分配給能最提高模組度的群組,如果無法在提高模組度,則不進行重新分配。
- 把上一步中發現的每一個群組作為一個節點,並將之前群組之間的邊合併成新的帶權重的邊。
- 重複第 2 步和第 3 步,直到無法再進行分配。
侷限性
Louvain 的到的結果包含的一些缺陷,與聚類演算法也很類似,那就是它無法找出有重疊或者巢狀關係的群組。並且,它無法識別一些規模較小但是比較重要的群組,如果需要找到這些群組,只能人為干預。
「其他文章」
- Spring 原始碼閱讀 42:AutowiredAnnotationBeanPostProcessor 分析(3)
- Spring 原始碼閱讀 41:AutowiredAnnotationBeanPostProcessor 分析(2)
- Kafka 消費者組 Rebalance 詳細過程
- Spring 原始碼閱讀 01:Resource 資源抽象
- 初識機器學習:迴歸分析
- 初識機器學習:Louvain 社群發現演算法
- 初識機器學習:關聯規則
- 使用 Redis 實現分散式鎖的方法
- Kafka 目錄裡的指令碼那麼多,它們都是用來幹什麼的?
- Kafka 消費者組位移重設的幾種方式
- LeetCode - 84. 柱狀圖中最大的矩形
- LeetCode - 22. 括號生成