基于Louvain算法的社交網絡社區發現研究

胡章榮

摘要：社區發現常用來了解復雜網絡的結構，挖掘社區成員之間內在的關聯關系，當今檢測大型網絡中社區最廣泛使用的方法之一是Louvain算法。Louvain是一種用于識別大型網絡中的社區的簡單，高效且易于實現的方法，它揭示了社區的層次結構，并允許在社區中進行縮放以發現子社區。本文分析了Louvain算法的基本思想，并用該算法對兩個社交網絡進行分類，得到了較好的分類結果。

關鍵詞：社區發現;Louvain算法;社交網絡

中圖分類號：? TP311? ? ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2020）23-0197-02

在線社交網絡，通訊網絡中的交互可以自然地建模為圖形。圖中的結構群落通常定義為圖中的高度連接的頂點/節點的組。這些群體通常代表相似的興趣群體，朋友社區等，彼此之間有更多的互動或相似之處。社區檢測和分析是了解各種現實世界網絡的組織的一種重要方法，并且在包括（但不限于）科學計算、生命科學、社會網絡分析和互聯網應用程序[1]在內的各個領域的數據分析中變得越來越普遍。給定一個圖，社區檢測的問題是將圖中的頂點劃分到不同的社區，使同一個社區內的社區成員之間具有較大的相似度，不同社區的成員之間具有較小的相似度。模塊化[2]是一個可以衡量社區劃分效果好壞的重要指標，也是Louvain算法的核心思想，Louvain算法是一種基于模塊度優化的高效算法，除了時間上的優勢，還能探測到層次的社區結構，不會遺漏一些小型的社區[3]。在本文中，我們分析了Louvain算法思想和評價模型，并用該算法對兩個社交網絡數據集進行了分析，效果較好。

1 Louvain 算法

1.1 算法思想

Louvain算法是由Blondel在2008年提出的用于網絡社區發現的方法，算法思想簡單，算法主要分為節點的局部移動和網絡社區聚合兩個階段[4]。首將每個節點看作一個獨立的類，并依次迭代每個節點，將單個節點移動到產生最大質量函數增長的社區，并做好標識。然后初始化整個圖，將分區中的每個社區成為聚合網絡中的一個節點，按照步驟一的方式迭代對網絡社區進行迭代歸類，直到滿足迭代結束條件為止。該算法在兩個基本階段對質量函數如模量度或CPM進行優化，直到評估函數不在變化為止。在每次迭代中，算法都會以任意預先定義的順序線性掃描頂點。對于每一個點v，會對它的所有鄰近社區進行檢查，并計算從當前社區移動到每個相鄰社區的模塊度增益值。一旦增益被計算出來，算法就會將該節點分配給一個能產生最大模塊增益的鄰近社區作為新社區，并更新以該節點為源和目標維護的相應社區結構。反之，如果所有的增益都是負的，頂點就留在它的當前共社區中。一旦所有頂點都以這種方式線性掃描，迭代就結束了。在一個階段結束后，該算法通過將一個個小的社區歸并為一個超結點來重新構造網絡，這時網絡中邊的權重為兩個結點內所有原始結點的邊權重之和;以及在兩個元頂點之間放置一條邊，其權重等于對應兩個社區之間的所有社區間邊的權重之和。這樣就形成了一個由多個子社區壓縮的圖G′（V′，E′，ω′），并將它作為下一階段的輸入，隨后，進行多次迭代計算，直到模塊度的值收斂。注意，每個階段代表社區檢測過程中形成的粗糙層次結構。

1.2 評價模型

Louvain算法是一個不斷迭代和合并的過程，在這個過程中是否需要進行下一次是由模塊度增益來確定的。在圖中每一種結構都對應著一個模塊度值，其計算方法如公式（1）所示：

當圖的結構發生變化，如一個節點a從當前社區C（i）移動到另外一個社區Qi 時，圖的結構就會發生變化，相應的模塊度也會發生變化，把這種變化稱為模塊度增益，用[?Q]表示，計算方法如公式（2）所示：

在維護的幾個數據集中，算法都可以讓QiC（j）的每個實例在O（1）時間內計算。因此，算法的時間復雜度為O（M）。雖然在迭代次數或相位數上沒有確定上限，但很明顯，該算法可以通過使用模塊增益來截止 （因為模塊是一個單調遞增的函數，直到終止）。在實踐中，該方法只需要幾十次迭代和更少的階段就能終止大多數真實網絡的輸入。

1.3 算法基本流程

Louvain社區發現是一個不斷移動節點，對節點和社區進行合并的過程，，其執行流程如下圖1所示。

2 基于Louvain的社交網絡分類

社交網絡是一個由若干個體構成的交互網絡，這些個體之間存在著不同的連接，有的個體之間保存在較為密切的聯系，而有的個體之間存在著較少的聯系，朋友之間的聯系用圖中節點之間的邊表示，節點之間的邊越多，則他們之間的關系越密切。一個大型的社交網絡通常是由若干小型網絡組成的，因此可以通過Louvain算法對社交網絡進行分類。本文在兩組社交網絡數據集上進行了實驗.其中一個是從Facebook上抓取的社交數據集，命名為socialship，另一個則是根據美國大學生足球聯賽而創建的一個復雜的社會網絡football。

2.1 實驗結果

socialship網絡是從facebook社交平臺上抓取的社交關系網絡，網絡中的成員來具有不同的學歷，在不同的年份參加了不同的假期活動，具有一定的社交關系。通過Louvain算法聚類分析后得到如圖1的結果。從聚類結果可以看出，socialship網絡主要被分成了8個社區，分類依據主要是成員的學歷、是否參加了相同的活動。分類效果較好，但仍然存在模糊的區域。

football網絡包含115個節點和616條邊，其中網絡中的結點代表足球隊，兩個結點之間的邊表示兩只球隊之間進行過一場比賽，參賽的115支大學生代表隊被分為12個聯盟。比賽的流程是聯盟內部的球隊先進行小組賽，然后再是聯盟之間球隊的比賽。通過聚類分析得到如圖2所示的結果。由圖可知115成員被很好地劃分成立12支球隊。

3 總結

本文對louvain算法的思想、流程、評價模型進行了分析，并應用該算法對社交網絡數據集進行分類。由于本次研究的網絡數據集較小，且是靜態網絡，社區結構相對簡單，因此得到了較好的實驗結果。在下一步的研究中，將試圖對louvain算法進行改進，用于更大的或動態的社交網絡社區發現。

參考文獻：

[1] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics：Theory and Experiment， 2008，2008（10）：P10008.

[2] M. E. J. Newman and M. Girvan， Phys. Rev. E69，026113 （2004）.

[3] 李沐南. Louvain算法在社區挖掘中的研究與實現[D]. 北京： 中國石油大學， 2016.

[4] 夏瑋，楊鶴標.改進的Louvain算法及其在推薦領域的研究[J].信息技術，2017（11）：125-128.

【通聯編輯：梁書】