初識機器學習:Louvain 社區發現算法

語言: CN / TW / HK

這是我參與「掘金日新計劃 · 8 月更文挑戰」的第6天,點擊查看活動詳情

本篇介紹一種社會網絡分析算法 Louvain,Louvain 是一個基於模塊度的社區發現算法,可以高效地在網絡中找出羣組。

社會網絡分析

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

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

Louvain 的基本原理簡述

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

Louvain 算法的目標是在一個網絡中識別羣組,使得:

  • 同一個羣組中的節點之間,邊的數量和強度最大化
  • 屬於不同羣組的邊數和強度最小化

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

  1. 把每一個節點都看成一個小的羣組。
  1. 對每一個節點執行操作:把它重新分配給能最提高模塊度的羣組,如果無法在提高模塊度,則不進行重新分配。
  1. 把上一步中發現的每一個羣組作為一個節點,並將之前羣組之間的邊合併成新的帶權重的邊。
  1. 重複第 2 步和第 3 步,直到無法再進行分配。

侷限性

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