胡章榮

摘要：社區(qū)發(fā)現(xiàn)常用來了解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)，挖掘社區(qū)成員之間內(nèi)在的關(guān)聯(lián)關(guān)系，當(dāng)今檢測(cè)大型網(wǎng)絡(luò)中社區(qū)最廣泛使用的方法之一是Louvain算法。Louvain是一種用于識(shí)別大型網(wǎng)絡(luò)中的社區(qū)的簡(jiǎn)單，高效且易于實(shí)現(xiàn)的方法，它揭示了社區(qū)的層次結(jié)構(gòu)，并允許在社區(qū)中進(jìn)行縮放以發(fā)現(xiàn)子社區(qū)。本文分析了Louvain算法的基本思想，并用該算法對(duì)兩個(gè)社交網(wǎng)絡(luò)進(jìn)行分類，得到了較好的分類結(jié)果。

關(guān)鍵詞：社區(qū)發(fā)現(xiàn);Louvain算法;社交網(wǎng)絡(luò)

中圖分類號(hào)：? TP311? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）23-0197-02

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

1 Louvain 算法

1.1 算法思想

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

1.2 評(píng)價(jià)模型

Louvain算法是一個(gè)不斷迭代和合并的過程，在這個(gè)過程中是否需要進(jìn)行下一次是由模塊度增益來確定的。在圖中每一種結(jié)構(gòu)都對(duì)應(yīng)著一個(gè)模塊度值，其計(jì)算方法如公式（1）所示：

當(dāng)圖的結(jié)構(gòu)發(fā)生變化，如一個(gè)節(jié)點(diǎn)a從當(dāng)前社區(qū)C（i）移動(dòng)到另外一個(gè)社區(qū)Qi 時(shí)，圖的結(jié)構(gòu)就會(huì)發(fā)生變化，相應(yīng)的模塊度也會(huì)發(fā)生變化，把這種變化稱為模塊度增益，用[?Q]表示，計(jì)算方法如公式（2）所示：

在維護(hù)的幾個(gè)數(shù)據(jù)集中，算法都可以讓QiC（j）的每個(gè)實(shí)例在O（1）時(shí)間內(nèi)計(jì)算。因此，算法的時(shí)間復(fù)雜度為O（M）。雖然在迭代次數(shù)或相位數(shù)上沒有確定上限，但很明顯，該算法可以通過使用模塊增益來截止 （因?yàn)槟K是一個(gè)單調(diào)遞增的函數(shù)，直到終止）。在實(shí)踐中，該方法只需要幾十次迭代和更少的階段就能終止大多數(shù)真實(shí)網(wǎng)絡(luò)的輸入。

1.3 算法基本流程

Louvain社區(qū)發(fā)現(xiàn)是一個(gè)不斷移動(dòng)節(jié)點(diǎn)，對(duì)節(jié)點(diǎn)和社區(qū)進(jìn)行合并的過程，，其執(zhí)行流程如下圖1所示。

2 基于Louvain的社交網(wǎng)絡(luò)分類

社交網(wǎng)絡(luò)是一個(gè)由若干個(gè)體構(gòu)成的交互網(wǎng)絡(luò)，這些個(gè)體之間存在著不同的連接，有的個(gè)體之間保存在較為密切的聯(lián)系，而有的個(gè)體之間存在著較少的聯(lián)系，朋友之間的聯(lián)系用圖中節(jié)點(diǎn)之間的邊表示，節(jié)點(diǎn)之間的邊越多，則他們之間的關(guān)系越密切。一個(gè)大型的社交網(wǎng)絡(luò)通常是由若干小型網(wǎng)絡(luò)組成的，因此可以通過Louvain算法對(duì)社交網(wǎng)絡(luò)進(jìn)行分類。本文在兩組社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn).其中一個(gè)是從Facebook上抓取的社交數(shù)據(jù)集，命名為socialship，另一個(gè)則是根據(jù)美國(guó)大學(xué)生足球聯(lián)賽而創(chuàng)建的一個(gè)復(fù)雜的社會(huì)網(wǎng)絡(luò)football。

2.1 實(shí)驗(yàn)結(jié)果

socialship網(wǎng)絡(luò)是從facebook社交平臺(tái)上抓取的社交關(guān)系網(wǎng)絡(luò)，網(wǎng)絡(luò)中的成員來具有不同的學(xué)歷，在不同的年份參加了不同的假期活動(dòng)，具有一定的社交關(guān)系。通過Louvain算法聚類分析后得到如圖1的結(jié)果。從聚類結(jié)果可以看出，socialship網(wǎng)絡(luò)主要被分成了8個(gè)社區(qū)，分類依據(jù)主要是成員的學(xué)歷、是否參加了相同的活動(dòng)。分類效果較好，但仍然存在模糊的區(qū)域。

football網(wǎng)絡(luò)包含115個(gè)節(jié)點(diǎn)和616條邊，其中網(wǎng)絡(luò)中的結(jié)點(diǎn)代表足球隊(duì)，兩個(gè)結(jié)點(diǎn)之間的邊表示兩只球隊(duì)之間進(jìn)行過一場(chǎng)比賽，參賽的115支大學(xué)生代表隊(duì)被分為12個(gè)聯(lián)盟。比賽的流程是聯(lián)盟內(nèi)部的球隊(duì)先進(jìn)行小組賽，然后再是聯(lián)盟之間球隊(duì)的比賽。通過聚類分析得到如圖2所示的結(jié)果。由圖可知115成員被很好地劃分成立12支球隊(duì)。

3 總結(jié)

本文對(duì)louvain算法的思想、流程、評(píng)價(jià)模型進(jìn)行了分析，并應(yīng)用該算法對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行分類。由于本次研究的網(wǎng)絡(luò)數(shù)據(jù)集較小，且是靜態(tài)網(wǎng)絡(luò)，社區(qū)結(jié)構(gòu)相對(duì)簡(jiǎn)單，因此得到了較好的實(shí)驗(yàn)結(jié)果。在下一步的研究中，將試圖對(duì)louvain算法進(jìn)行改進(jìn)，用于更大的或動(dòng)態(tài)的社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)。

參考文獻(xiàn)：

[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算法在社區(qū)挖掘中的研究與實(shí)現(xiàn)[D]. 北京： 中國(guó)石油大學(xué)， 2016.

[4] 夏瑋，楊鶴標(biāo).改進(jìn)的Louvain算法及其在推薦領(lǐng)域的研究[J].信息技術(shù)，2017（11）：125-128.

【通聯(lián)編輯：梁書】