基于最小割圖分割的社區(qū)發(fā)現(xiàn)算法

王亞珅，黃河燕，馮 沖

(北京理工大學 計算機學院北京市海量語言信息處理與云計算應用工程技術(shù)研究中心，北京 100081)

基于最小割圖分割的社區(qū)發(fā)現(xiàn)算法

王亞珅，黃河燕，馮 沖

(北京理工大學 計算機學院北京市海量語言信息處理與云計算應用工程技術(shù)研究中心，北京 100081)

該文證明了模塊度最大化問題可以被轉(zhuǎn)換成為原網(wǎng)絡(luò)上的最小割圖分割問題，并且基于該證明提出了一種高效的社區(qū)發(fā)現(xiàn)算法。同時，該文創(chuàng)新性地將模塊度理論與當今比較流行的統(tǒng)計推理模型相結(jié)合： 首先，這些統(tǒng)計推理模型被轉(zhuǎn)化為模塊度最大化問題中的零模型；其次，統(tǒng)計推理模型中的目標函數(shù)被修改并應用于本文的最優(yōu)化算法中。實驗結(jié)果顯示，無論是在真實世界網(wǎng)絡(luò)還是在人工生成網(wǎng)絡(luò)中，該文提出的算法均具有高效和穩(wěn)定的發(fā)現(xiàn)社區(qū)的能力。

社區(qū)發(fā)現(xiàn)；模塊度；最小割圖分割

1 引言

作為網(wǎng)絡(luò)的一種常見屬性，社區(qū)結(jié)構(gòu)(community structure)是一種對網(wǎng)絡(luò)節(jié)點的分割，其中，同一個社區(qū)中的節(jié)點聯(lián)系緊密，而隸屬于不同社區(qū)的節(jié)點之間聯(lián)系則相對松散[1-2]，社區(qū)發(fā)現(xiàn)(community detection)已經(jīng)在諸多領(lǐng)域體現(xiàn)出其應用價值[3-5]。為了解決社區(qū)發(fā)現(xiàn)問題，我們首先討論社區(qū)(community)的定義，學界目前存在很多全局化的社區(qū)定義，這些定義均將社區(qū)結(jié)構(gòu)視為整個網(wǎng)絡(luò)的一個屬性[6]。

(1) 最為直觀的社區(qū)定義與連接不同社區(qū)邊的數(shù)量(在有權(quán)網(wǎng)絡(luò)中，則為連接邊的加權(quán)和)有關(guān)，這個數(shù)量通常被稱為割規(guī)模(cut size)，旨在最小化割規(guī)模的問題一般被稱為“最小割圖分割(minimum-cut graph partitioning)”問題。

(2) 另一種社區(qū)的定義則是基于被廣泛使用的模塊度(modularity)概念[1,7]。模塊度衡量一個給定的圖分割與一個期望隨機圖(又稱為“零模型”)的圖分割之間的差異，旨在最大化模塊度的問題一般被稱為“模塊度最大化(modularity maximization)”問題。

本文研究的核心內(nèi)容是，探索模塊度最大化問題和最小割圖分割問題的內(nèi)在關(guān)系。目前，學界對此類問題的相關(guān)研究較少。文獻[8]針對生成一個特定網(wǎng)絡(luò)的似然函數(shù)最大化問題，證明了統(tǒng)計推理模型可以映射成為最小割圖分割問題。本文的研究正是受文獻[8]啟發(fā)，但是我們重點關(guān)注的是模塊度最大化問題，證明模塊度最大化問題可以被轉(zhuǎn)化成為原網(wǎng)絡(luò)上的最小割圖分割問題，并應用多層次圖分割的Kernighan-Lin算法[9]來解決上述最小割圖分割問題。

本文另外一個貢獻在于，創(chuàng)新性地將模塊度理論和統(tǒng)計推理算法(例如隨機塊模型[10-11]及其度修正變體[12])相結(jié)合。統(tǒng)計推理算法首先假設(shè)了一些用于產(chǎn)生社區(qū)結(jié)構(gòu)的潛在概率模型，進而估計模型的參數(shù)。實際上，基于模塊度的算法和此類基于統(tǒng)計推理模型的算法均可以視為最優(yōu)化問題，因此我們嘗試證明二者之間的聯(lián)系。所以，統(tǒng)計推理模型在本文提出的算法中扮演著重要角色：

(1) 在證明過程中，統(tǒng)計推理模型可以被轉(zhuǎn)化成為模塊度最大化問題中的零模型(null model)[12]。

(2) 統(tǒng)計推理算法的核心思想是通過最大化似然函數(shù)(likelihood)來產(chǎn)生一個合理的目標函數(shù)，因此，我們修改這個目標函數(shù)以應用于我們的最優(yōu)化策略中。

簡言之，本文提出的算法首先通過執(zhí)行多層次最小割圖分割算法，得到一個包含眾多社區(qū)結(jié)構(gòu)的候選集合；然后使用度修正隨機塊模型的目標函數(shù)，從候選集合中選擇目標函數(shù)值最大的社區(qū)結(jié)構(gòu)作為最終結(jié)果。據(jù)悉，我們首創(chuàng)性地探尋模塊度理論、統(tǒng)計推理模型和傳統(tǒng)圖聚類/圖分割算法三者之間的內(nèi)在聯(lián)系，雖然本文算法在時間復雜度方面依然有很大提升空間(文獻[8]也面臨同樣挑戰(zhàn))，但是本文算法在真實世界網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)的實驗中均得到了很高的準確率和穩(wěn)定性。

本文的內(nèi)容組織如下： 第二節(jié)將總結(jié)相關(guān)工作；第三節(jié)重點分析度修正隨機塊模型的原理；在第四節(jié)中，我們將詳細分析模塊度最大化算法和最小割圖分割算法之間的關(guān)系，并提出我們的算法；第五節(jié)和第六節(jié)將闡述實驗和相關(guān)結(jié)果及結(jié)論。

2 相關(guān)工作

作為聚類質(zhì)量的評價指標，模塊度被文獻[1]引入到社區(qū)發(fā)現(xiàn)研究中，并憑借其直觀高效的特點，逐漸成為社區(qū)發(fā)現(xiàn)研究的常用度量方式。文獻[7]提出的貪婪的基于模塊度的社區(qū)發(fā)現(xiàn)算法CNM，已成為當今使用最為普遍的算法。該算法從嵌套的堆棧中迭代地選擇和合并能夠產(chǎn)生最大模塊度增益的最優(yōu)節(jié)點對，直至沒有此類節(jié)點對能夠提高模塊度為止。此后，作為CNM的變體，一系列針對有權(quán)重網(wǎng)絡(luò)和有向網(wǎng)絡(luò)的計算模塊度的算法相繼被提出；此外，基于其他理論的諸多算法也被提出，例如計算網(wǎng)絡(luò)圖的Laplacian特征向量的算法[13]等。近年來，包括隨機塊模型[10]及其度修正變體[11]在內(nèi)的統(tǒng)計推理算法，憑借其優(yōu)良的性能吸引著越來越多的研究興趣。

不難發(fā)現(xiàn)，社區(qū)發(fā)現(xiàn)與圖分割/圖聚類有著密切關(guān)系，但是二者之間依然存在著一定差異[6]。圖分割是人工智能領(lǐng)域被深入研究的課題[14-16]，旨在將網(wǎng)絡(luò)中的節(jié)點劃分成一些指定規(guī)模(并不要求規(guī)模相等)的分組，并且確保分組之間連接邊的數(shù)量最小。其中有兩類算法占據(jù)著主導地位： 基于網(wǎng)絡(luò)圖Laplacian特征向量的譜二分析法，以及使用貪婪策略不斷優(yōu)化社區(qū)外部連接邊和內(nèi)部連接邊進而不斷改善初始劃分的Kernighan-Lin算法[16]及其多層次變體[9](見圖1)。目前，學界已有不少利用(歸一化)最小割圖分割算法進行社區(qū)發(fā)現(xiàn)的研究[17]，但是對于模塊度最大化與最小割圖分割的關(guān)系的研究尚屬少數(shù)[18]。文獻[18]意在證明歸一化模塊度最大化問題可以轉(zhuǎn)換為RatioCut譜聚類問題，但是無法精確證明二者之間的等價關(guān)系。

3 度修正的隨機塊模型

原始的隨機塊模型是一個用于網(wǎng)絡(luò)社區(qū)的產(chǎn)生式模型，但是由于忽略了節(jié)點度的多樣性，導致其很難被應用于真實世界網(wǎng)絡(luò)。為了解決上述問題，度修正隨機塊模型(degree-corrected stochastic block model)[12]為每個節(jié)點i添加了一個參數(shù)θi用于控制節(jié)點i的度的期望值，這使其能夠適應任何度分布。

對于網(wǎng)絡(luò)G(V,E),V和E分別表示該網(wǎng)絡(luò)全部n個節(jié)點的集合和全部m條邊的集合，k表示社區(qū)的數(shù)量。Aij表示G(V,E)的鄰接矩陣的元素，其值等同于節(jié)點i和節(jié)點j之間邊的數(shù)量，且Aii=0。ωrs是一個k×k維對稱矩陣的元素，控制著社區(qū)r和社區(qū)s之間的連接邊。我們將Aij的期望值設(shè)定為θiθjωgigj[12]，其中g(shù)i表示節(jié)點i所隸屬的社區(qū)。綜上所述，生成網(wǎng)絡(luò)G(V,E)的似然度函數(shù)為式(1)。

其中，ki是節(jié)點i的度；κs是社區(qū)s所有節(jié)點度的總和；mrs是連接社區(qū)r和社區(qū)s的邊的數(shù)量，其定義如式(3)所示。

其中，δgigj是KroneckerDelta。將θ和ω的值帶入式(1)，經(jīng)過適當改寫，我們便得到了只依賴于社區(qū)結(jié)構(gòu)輪廓的似然函數(shù)，并取對數(shù)得

因為統(tǒng)計推理算法通常被用作評估社區(qū)發(fā)現(xiàn)算法的基準算法，所以我們不妨利用式(4)作為判別社區(qū)劃分是否合理的目標函數(shù)

4 基于最小割圖分割的社區(qū)發(fā)現(xiàn)算法

文獻[1]所定義的模塊度概念，被廣為認可和使用，而近來來關(guān)于社區(qū)發(fā)現(xiàn)的研究也大多集中在模塊度最大化問題。本章將證明，模塊度最大化問題可以被轉(zhuǎn)化成原網(wǎng)絡(luò)最小割圖分割問題。

給定以下條件：

(1) 一個擁有n個節(jié)點和m條邊的網(wǎng)絡(luò)G(V,E),V和E分別代表上文所定義的節(jié)點集合和邊集合；

(2) 包含k個社區(qū)的一個劃分P=P1,…,Pk；

(3) 一個在原網(wǎng)絡(luò)節(jié)點集合V上的隨機網(wǎng)絡(luò)分布為G。

隨機網(wǎng)絡(luò)分布G有很多選擇方式[19]，具體如下。

(1)Erd?s-Renyi模型： 原始的隨機塊模型與Erd?s和Renyi提出的隨機圖模型[20]有密切的內(nèi)在聯(lián)系[12]，但是這個模型極易產(chǎn)生不符合實際的網(wǎng)絡(luò)(度分布服從泊松分布)，甚至產(chǎn)生沒有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)。

(2)Chung-Lu模型： 為了避免上述問題，模塊度經(jīng)常使用另外一種固定度期望序列使之與被觀察網(wǎng)絡(luò)一致的模型來定義。這種意義下，度修正的隨機塊模型與Chung和Lu所研究的模型[21]有關(guān)。

為了簡化描述，我們定義

為劃分P所對應的割規(guī)模。我們首先考慮最簡單的情況——二分問題(即k=2)，式(6)可以被改寫成

對于式(8)中隨機網(wǎng)絡(luò)分布G的選定，我們將分別考察原始隨機塊模型及其度修正變體。

4.1 將原始隨機塊模型作為G的情況

重寫式(8)得

如果我們使用w12來表示社區(qū)1和社區(qū)2之間的邊的數(shù)量期望值，那么

考慮到

其中，n1和n2分別表示社區(qū)1和社區(qū)2中節(jié)點的數(shù)量，則

因此模塊度最大化問題可以被進一步重寫為

至此，式(6)所代表的原始問題，已經(jīng)被轉(zhuǎn)化成了計算公式(15)。

4.2 將度修正的隨機塊模型作為G的情況

去掉式(8)中的常數(shù)項m，我們可以得到

在度修正隨機塊模型中，我們有

其中，w11和w22分別表示社區(qū)1和社區(qū)2內(nèi)部邊數(shù)量的期望值。并且有

相似地，可得

至此，式(6)所代表的原始問題，已經(jīng)被轉(zhuǎn)化成了計算式(21)。

式(21)與式(15)十分相似，原始的模塊度最大化問題也被映射成為一個帶有附加項的最小割圖分割問題。所以，綜合考慮式(15)和式(21)，本文首先固定隨機網(wǎng)絡(luò)分布G，執(zhí)行以社區(qū)結(jié)構(gòu)為自變量的最小化；然后，固定社區(qū)結(jié)構(gòu)，執(zhí)行以G為自變量的最小化。

我們可以執(zhí)行下述在社區(qū)發(fā)現(xiàn)研究中常用的貪婪策略[7]來完成對社區(qū)規(guī)模n1和n2的選擇。假設(shè)我們并不區(qū)分社區(qū)的類別，即我們只需要將所有節(jié)點劃分進兩個不同的社區(qū)，而并不關(guān)心某個節(jié)點具體屬于哪個社區(qū)。如果網(wǎng)絡(luò)中節(jié)點總數(shù)n是偶數(shù)，那么有n/2+1種對兩個社區(qū)的規(guī)模的選擇方式： 一種極端的選擇方式將所有節(jié)點放入某一個社區(qū)中，另一種極端的選擇方式將所有節(jié)點均分到兩個社區(qū)中，其他的選擇方式介于上述兩種極端選擇方式之間。相似地，如果n是奇數(shù)，則會有(n+1)/2種對兩個社區(qū)規(guī)模的選擇方式。上述所有選擇構(gòu)成一個單一參數(shù)(參數(shù)為社區(qū)規(guī)模)的候選集合；對于每個選擇均對應一個標準的最小割圖分割問題，因此很多啟發(fā)式算法[14-16]可以應用于此，本文使用多層次的Kernighan-Lin算法[9]解決該最小割圖分割問題，并得到相應候選解(即候選的社區(qū)結(jié)構(gòu))。此時，因為這里使模塊度全局最大的候選解應同樣滿足使式(4)取得最大值，所以我們將每個候選解帶入式(4)并計算，從計算得到的目標值中選擇最大值對應的候選解作為最終結(jié)果。上述將網(wǎng)絡(luò)劃分為兩個社區(qū)的算法可以很簡單地擴展到多社區(qū)劃分的情況，方法如下： 我們首先使用上述算法將網(wǎng)絡(luò)分成兩個網(wǎng)絡(luò)，然后遞歸地將各個子網(wǎng)絡(luò)繼續(xù)劃分成兩個社區(qū)，以此類推[13]；對于某個子圖，如果其任何劃分都不增加整個網(wǎng)絡(luò)的模塊度，那么這個子圖將被保留成為一個社區(qū)而不再被繼續(xù)分割。

基于文獻[9]中的分析，本文提出的算法將包含n個節(jié)點和m條邊的網(wǎng)絡(luò)劃分成兩個社區(qū)的時間復雜度為O(n2)；當劃分為k個社區(qū)的時候，只需要執(zhí)行d次上述計算即可，其中d是樹狀圖的深度(在二分樹中，log2k≤d≤k)。因為本文提出的算法是一個創(chuàng)新性的嘗試和證明，所以與現(xiàn)有算法(如算法[7])相比，其計算時間并不具備優(yōu)勢，依然有很大改進空間(這種降低時間復雜度的挑戰(zhàn)同樣也是文獻[8]所面臨的)。因此在降低時間復雜度方面對算法進行改進，將是未來工作的方向之一；但是實驗結(jié)果顯示，該算法對于發(fā)現(xiàn)社區(qū)結(jié)構(gòu)具有很高的準確率。

5 實驗和結(jié)果分析

本節(jié)中，我們在真實世界網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)上，分別測試本文算法(記為MC)的性能并與其他算法進行比較，實驗證明其取得了良好的實驗結(jié)果。其中，真實世界網(wǎng)絡(luò)可以體現(xiàn)算法在現(xiàn)實條件下的性能，而人工生成網(wǎng)絡(luò)可以在已知社區(qū)結(jié)構(gòu)設(shè)定和受控條件下測試算法發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的能力。本文實驗部分修改和應用基于多層次圖分割策略的圖分割工具包METIS-5.1.0*http://glaros.dtc.umn.edu/gkhome/metis/metis/download，主要采用的度量方法是歸一化互信息(normalizedmutualinformation,NMI)[22]及其變體(variantnormalizedmutualinformation，VNMI)。

本文實驗所使用的網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)均已知，這使得我們可以度量被算法所正確劃分的節(jié)點的數(shù)量。所以，本文重點關(guān)注： 真實的社區(qū)結(jié)構(gòu)和算法所產(chǎn)生的社區(qū)結(jié)構(gòu)之間的差異。將上述兩種社區(qū)結(jié)構(gòu)均視為隨機變量(分別記為A和B)，NMI定義如下：

5.1 真實世界網(wǎng)絡(luò)實驗

我們將本文算法應用在了一系列不同規(guī)模的真實世界網(wǎng)絡(luò)，算法均產(chǎn)生了與先驗知識一致的社區(qū)結(jié)構(gòu)。這里，我們重點介紹其中三個真實世界網(wǎng)絡(luò)的實驗細節(jié)。

第一個實驗網(wǎng)絡(luò)是“KarateClub”網(wǎng)絡(luò)[23]，該網(wǎng)絡(luò)表示一所美國大學中擁有34個成員的空手道俱樂部中的人際關(guān)系交互情況。由于一次爭吵，這個俱樂部的成員被劃分成為兩個部分，因此這個網(wǎng)絡(luò)為二分算法提供了良好的實驗素材。圖2展示了本文算法在“KarateClub”網(wǎng)絡(luò)上的實驗結(jié)果。結(jié)果顯示，本文算法準確地識別出了已知社區(qū)結(jié)構(gòu)，除了錯分位于兩個社區(qū)邊界的編號為10的節(jié)點——該節(jié)點在很多其他的算法中也經(jīng)常被錯誤分類[12]，主要因為該節(jié)點連接到兩個社區(qū)的邊的數(shù)量相同。第二個實驗網(wǎng)絡(luò)是“BottlenoseDolphins”網(wǎng)絡(luò)。圖3 展示了本文算法在 “BottlenoseDolphins”網(wǎng)絡(luò)的實驗結(jié)果。該網(wǎng)絡(luò)包含了位于新西蘭的62只海豚，是通過觀察它們之間交互的頻繁程度而建立的網(wǎng)絡(luò)[24]。本文算法首先將這個網(wǎng)絡(luò)分成兩個大的子網(wǎng)絡(luò)，其中較大的一個隨后又被分成兩個較小的子網(wǎng)絡(luò)。

圖2 “Karate Club”網(wǎng)絡(luò)實驗結(jié)果

圖3 “Bottlenose Dolphins”網(wǎng)絡(luò)實驗結(jié)果

第三個網(wǎng)絡(luò)是“AmericanPoliticalBlogs”網(wǎng)絡(luò)。“AmericanPoliticalBlogs”網(wǎng)絡(luò)[25]由2004年美國總統(tǒng)大選期間政治類博客及其鏈接信息組成，這些博客中的前758個是支持共和黨的，而剩下的732個博客是支持民主黨的。表1顯示，本文算法應用于全部1 490個節(jié)點的情況下，NMI值只有0.500 502(錯分164個節(jié)點)；但是如果去掉原圖中225個孤立節(jié)點而只考慮原圖的聯(lián)系密切的主要部分節(jié)點(1 265個節(jié)點)及其連接，NMI值上升到0.720 525，這與文獻[12]的實驗結(jié)果十分接近。

表1 “American Political Blogs”網(wǎng)絡(luò)實驗結(jié)果

5.2 人工生成網(wǎng)絡(luò)實驗

為了與其他(基準)算法進行比較，我們將本文算法分別應用到基于度修正隨機塊模型(DCM)[12]和Lancichinetti-Fortunato-Radicchi(LFR)基準[26]所產(chǎn)生的人工生成網(wǎng)絡(luò)上。

5.2.1 DCM人工生成網(wǎng)絡(luò)實驗

效仿文獻[12]，本文按照如下的定義來選擇ωrs，從而產(chǎn)生基于DCM的人工生成網(wǎng)絡(luò)。

在第一組DCM人工生成網(wǎng)絡(luò)實驗中，每個網(wǎng)絡(luò)均含有100 000個節(jié)點，以及兩個等規(guī)模的社區(qū)，并且每個社區(qū)的度的平均期望值均為20。在選定社區(qū)結(jié)構(gòu)、所有節(jié)點度的期望值(公式(2)中的θi)和ωrs的取值之后，我們按照如下方法來生成網(wǎng)絡(luò)： 首先對于每對社區(qū)r和s，產(chǎn)生一個服從泊松分布(均值為ωrs)的邊的數(shù)量值，然后根據(jù)θi將所有邊附著在節(jié)點i上。本文提出的MC、原始隨機塊模型(記為SBM)和度修正隨機塊模型(記為DCM)被應用在第一組實驗網(wǎng)絡(luò)上進行性能對比。對于SBM和DCM這兩個模型，我們均采用隨機設(shè)定(后綴為R)和種植設(shè)定(后綴為P)分別進行初始化，分別進行10次獨立運行，并從中選擇最好的結(jié)果展示出來。

圖4將NMI值作為參數(shù)λ的函數(shù)值，每個數(shù)據(jù)點代表了在100個等條件生成網(wǎng)絡(luò)上的平均值。圖4(a)顯示，隨著λ從0開始逐漸增長，雖然因為此時的網(wǎng)絡(luò)還處于比較隨機的狀態(tài)，所有的算法均未能產(chǎn)生比較合理的社區(qū)結(jié)構(gòu)，但是本文算法性能優(yōu)于其他算法，一方面是因為最小割圖分割思想有效地將社區(qū)發(fā)現(xiàn)問題還原到了圖論問題的本質(zhì)，另一方面是因為本文算法引入的窮舉策略，能夠遍歷當前參數(shù)設(shè)定條件下所有可能的社區(qū)劃分。值得注意的是，本文的算法為每個候選社區(qū)結(jié)構(gòu)均計算“目標值”[見式(4)]，但是只有擁有最大“目標值”的社區(qū)結(jié)構(gòu)才會被選中成為最終結(jié)果，所以在最終結(jié)果的NMI值和所有候選的社區(qū)結(jié)構(gòu)中最大的NMI值之間存在一個“間距”： 通過實驗我們發(fā)現(xiàn)，當λ的取值接近于0的時候，上述“間距”比較大；而當λ繼續(xù)增加，“間距”開始下降。這種現(xiàn)象很直觀地解釋了以下問題： 當網(wǎng)絡(luò)中社區(qū)劃分越明確，傳統(tǒng)圖分割算法對于社區(qū)劃分結(jié)果的置信度越高；同時，這種“間距”下降，也證明了本文引入度修正隨機塊模型的似然函數(shù)的有效性。此外，當λ超過中值，MC和DCM的曲線基本重合，說明我們的結(jié)果達到了當前最優(yōu)的基準效果。而對于未進行度修正的SBM，即使λ的取值已經(jīng)超過中值，也依然未能產(chǎn)生合理的社區(qū)結(jié)構(gòu)。

另外一組基于DCM人工生成網(wǎng)絡(luò)的實驗采用的生成網(wǎng)絡(luò)更加復雜和貼近現(xiàn)實網(wǎng)絡(luò)。社區(qū)規(guī)模與度的平均期望值與上一組實驗相同，不同之處在于，本組實驗設(shè)定社區(qū)1的度分布服從冪律分布——復雜網(wǎng)絡(luò)的顯著特征之一，并且取冪指數(shù)γ=2.8；設(shè)定社區(qū)2的度分布為均值為20的泊松分布。圖4(b)證明了本文算法具有良好的穩(wěn)定性：MC在λ很小的情況(即網(wǎng)絡(luò)社區(qū)劃分不明確，甚至是幾乎隨機的網(wǎng)絡(luò))下依然能夠體現(xiàn)出不錯的性能。這是因為MC能夠僅僅依靠節(jié)點的度信息對絕大部分節(jié)點進行分類。相反地，在λ≤0.2的情況下，DCM的正確率幾乎為0，僅略微優(yōu)于原始的SBM。當λ處于插值的中值階段(0.5≤λ≤0.7)時，DCM性能優(yōu)于本文提出的MC，但是在λ取其他值時，MC依然優(yōu)于DCM。換言之，當每條邊都有幾乎相同概率從隨機網(wǎng)絡(luò)和種植網(wǎng)絡(luò)中選擇的時候，DCM準確率的提升速度要快于MC的準確率。特別地，本組實驗社區(qū)1中更為接近現(xiàn)實復雜網(wǎng)絡(luò)中度的冪律分布，使SBM的性能遠差于其在上一組實驗的性能，這是因為SBM產(chǎn)生的網(wǎng)絡(luò)中，節(jié)點的度服從泊松分布，而泊松分布不符合真實世界網(wǎng)絡(luò)，因此SBM無法有效擬合觀測網(wǎng)絡(luò)。比較上述兩組DCM人工生成網(wǎng)絡(luò)實驗，我們不難發(fā)現(xiàn)，現(xiàn)實網(wǎng)絡(luò)更有助于本文算法發(fā)揮其性能優(yōu)勢。

圖4 基于DCM的人工合成網(wǎng)絡(luò)的實驗

5.2.2LFR人工生成網(wǎng)絡(luò)實驗

為了測試算法在一系列大跨度、寬范圍的結(jié)構(gòu)化網(wǎng)絡(luò)特征下的性能，我們使用LFR基準網(wǎng)絡(luò)進行實驗。LFR綜合考慮了度和社區(qū)規(guī)模的多樣性，是社區(qū)發(fā)現(xiàn)研究領(lǐng)域經(jīng)常被使用的比較符合現(xiàn)實網(wǎng)絡(luò)特征的基準網(wǎng)絡(luò)。

本文主要討論下述三個主要的用于生成網(wǎng)絡(luò)的參數(shù)，對不同算法的性能影響： (a)聚合參數(shù)μ，類似于上述DCM人工生成網(wǎng)絡(luò)實驗中的參數(shù)λ；(b)節(jié)點度的平均值〈k〉；(c)網(wǎng)絡(luò)所包含的節(jié)點總數(shù)N。

首先，本文與文獻[28]進行對比實驗。我們使用相同的實驗網(wǎng)絡(luò)設(shè)定，實驗包括兩種不同的網(wǎng)絡(luò)規(guī)模(1 000個節(jié)點和5 000個節(jié)點)，度的平均值為20。圖5(a)呈現(xiàn)了本文算法的實驗曲線，每個數(shù)據(jù)點均代表100個等條件網(wǎng)絡(luò)實驗結(jié)果的平均值。其中，后綴S和B分別表示較小的社區(qū)規(guī)模(每個社區(qū)包含10～50個節(jié)點)和較大的社區(qū)規(guī)模(每個社區(qū)包含20～100個節(jié)點)。通過實驗結(jié)果對比，本文算法比文獻[28]所分析的算法更有競爭力；相似地，當μ由0.6增長為0.7的時候，曲線出現(xiàn)了快速下降。

圖5(b)和圖5(c)分別展示了節(jié)點度平均值〈k〉和節(jié)點總數(shù)N對算法性能的影響。通過實驗我們發(fā)現(xiàn)，節(jié)點數(shù)量對于算法性能的影響有限；然而節(jié)點度平均值卻對準確率有著顯著影響，在節(jié)點度的變化過程中，幾乎所有算法都遭受過NMI值的巨大損失，而大部分算法的NMI值在度平均值取值約為25的時候達到峰值。

圖5 基于LFR的人工生成網(wǎng)絡(luò)的實驗

6 總結(jié)

社區(qū)發(fā)現(xiàn)長久以來一直吸引著學者們的研究興趣，諸如基于模塊度算法、統(tǒng)計推理模型算法和基于傳統(tǒng)圖聚類/圖分割算法等不同類型算法被相繼提出。我們始終認為，在這些不同的理論之間一定存在某些內(nèi)在聯(lián)系。所以，本文進行了一個創(chuàng)新性的嘗試，旨在探索并發(fā)現(xiàn)這些理論之間的潛在聯(lián)系。本文證明了模塊度最大化問題可以被轉(zhuǎn)化成在原網(wǎng)絡(luò)上的最小割圖分割問題，因此所有高效的最小割圖分割算法均可以被應用于本文提出的算法中。此外，本文將模塊化理論和當今比較流行的統(tǒng)計推理模型進行充分結(jié)合，將后者轉(zhuǎn)化成為模塊度最大化問題中的零模型，并將其目標函數(shù)應用在我們的最優(yōu)化策略中?；谏鲜鲎C明和討論，本文提出了一種新的基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法。

我們在不同規(guī)模(節(jié)點數(shù)量級最高達到百萬級)的真實世界網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)上測試了本文提出的算法。實驗結(jié)果顯示，本文算法在發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的能力方面具備高效性和穩(wěn)定性；尤其是在諸如冪律分布此類有著強烈不均衡度分布的網(wǎng)絡(luò)中，本文算法依然表現(xiàn)出良好的性能。除了“大規(guī)?！碧匦?，現(xiàn)實社交網(wǎng)絡(luò)的另一個重要特征就是“動態(tài)”特性。因此，我們的后續(xù)研究將重點關(guān)注解決在線或者動態(tài)社區(qū)發(fā)現(xiàn)問題；同樣，我們將會繼續(xù)完善本文算法，以進一步降低其時間復雜度。

[1]NewmanMEJ,GirvanM.Findingandevaluatingcommunitystructureinnetworks[J].PhysicalReviewE, 2004, 69(2): 026113.

[2]Fortunato,S.Communitydetectioningraphs[J].PhysicsReports. 2010, 486(3): 75-174.

[3]ZhouTC,MaH,LyuMR,etal.User-Rec:auserrecommendationframeworkinsocialtaggingsystems[C]//Proceedingsof24thAAAIConferenceonArtificialIntelligence.Atlanta,USA:AAAIPress, 2010: 1486-1491.

[4]WengJ,LeeBS.EventDetectioninTwitter[C]//Proceedingsof5thInternationalAAAIConferenceonWeblogsandSocialMedia.Barcelona,Spain:AAAIPress, 2011: 401-408.

[5] 靳延安,李瑞軒,文坤梅,等. 社會標注及其在信息檢索中的應用研究綜述[J]. 中文信息學報,2010,(4): 52-62.

[6]PapadopoulosS,KompatsiarisY,VakaliA,etal.CommunitydetectioninSocialMedia[J].DataMiningandKnowledgeDiscovery, 2011, 24(3): 515-554.

[7]ClausetA,NewmanM,MooreC.Findingcommunitystructureinverylargenetworks[J].PhysicalReviewE, 2004, 70(6): 066111.

[8]NewmanMEJ.Communitydetectionandgraphpartitioning[J].EPL(EurophysicsLetters), 2013, 103(2): 28003.

[9]KarypisG,KumarV.Afastandhighqualitymultilevelschemeforpartitioningirregulargraphs[J].SIAMJournalonScientificComputing, 1998, 20(1): 359-392.

[10]CondonA,KarpRM.Algorithmsforgraphpartitioningontheplantedpartitionmodel[J].RandomStructuresandAlgorithms, 2001, 18(2): 116-140.

[11]AiroldiEM,BleiDM,FienbergSE,etal.Mixedmembershipstochasticblockmodels[J].TheJournalofMachineLearningResearch, 2008, 9: 1981-2014.

[12]KarrerB,NewmanMEJ.Stochasticblockmodelsandcommunitystructureinnetworks[J].PhysicalReviewE, 2011, 83(1): 016107.

[13]NewmanMEJ.Findingcommunitystructureinnetworksusingtheeigenvectorsofmatrices[J].PhysicalReviewE, 2006, 74(3): 036104.

[14]FjallstromP.Algorithmsforgraphpartitioning:asurvey[J].LinkopingElectronicArticlesinComputerandInformationScience, 1998, 3(10) 123-128.

[15]FiedlerM.Algebraicconnectivityofgraphs[J].CzechoslovakMathematicalJournal, 1973, 23 (98): 298-305.

[16]KernighanBW,LinS.Anefficientheuristicprocedureforpartitioninggraphs[J].BellSystemTechnicalJournal, 1970, 49: 291-307.

[17]FlakeGW,TarjanRE,TsioutsiouliklisK.Graphclusteringandminimumcuttrees[J].InternetMathematics, 2004, 1(4): 385-408.

[18]WhiteS,SmythP.Aspectralapproachtofindcommunitiesingraphs[C]//ProceedingsofSIAMConf.onDataMining. 2005: 76-84.

[19] 馬力,焦李成,白琳,等. 基于小世界模型的復合關(guān)鍵詞提取方法研究[J]. 中文信息學報,2009,(3)： 121-128.

[20]Erd?sP,RenyiA.Onrandomgraphs[J].Publ.Math, 1959, (6): 290-297.

[21]ChungF,LuL.Connectedcomponentsinrandomgraphswithgivenexpecteddegreesequences[J].AnnalsofCombinatorics, 2002, 6(2): 125-145.

[22]FredALN,JainAK.Robustdataclustering[C]//2003IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.Madison,Wisconsin,USA:IEEEPress, 2003:II-128-133.

[23]ZacharyWW.Aninformationflowmodelforconflictandfissioninsmallgroups[J].JournalofAnthropologicalResearch, 1977, 33(4): 452-473.

[24]LusseauD,SchneiderK,BoisseauOJ,etal.ThebottlenosedolphincommunityofDoubtfulSoundfeaturesalargeproportionoflong-lastingassociations[J].BehavioralEcologyandSociobiology, 2003, 54(4): 396-405.

[25]AdamicLA,GlanceN.Thepoliticalblogosphereandthe2004U.S.election[C]//Proceedingsof3rdInternationalWorkshoponLinkDiscovery.NewYork,NewYork,USA:ACMPress, 2005: 36-43.

[26]LancichinettiA,FortunatoS,RadicchiF.Benchmarkgraphsfortestingcommunitydetectionalgorithms[J].PhysicalReviewE, 2008, (78): 046110.

[27]ChungF,LuL.Theaveragedistancesinrandomgraphswithgivenexpecteddegrees[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica, 2002, 99(25): 15879-15882.

[28]LancichinettiA,FortunatoS.Communitydetectionalgorithms:Acomparativeanalysis[J].PhysicalReviewE, 2009, 80: 056117.

CommunityDetectionBasedonMinimum-CutGraphPartitioning

WANG Yashen, HUANG Heyan, FENG Chong

(Beijing Engineering Research Center of High Volume Language Information Processing and Cloud Computing Application, School of Computer, Beijing Institute of Technology, Beijing 100081, China)

This article demonstrated that modularity maximization issue could be transformed into minimum-cut graph partitioning problem, and proposed an efficient algorithm for detecting community structure. Meanwhile, we combined the modularity theory with popular statistical inference method in two aspects: (i) transforming such statistical model into null model in modularity maximization; (ii) adapting the objective function of statistical inference method for our optimization. The experiments we conducted show that the proposed algorithm is highly effective and stable in discovering community structure from both real-world networks and synthetic networks.

community detection; modularity; minimum-cut graph partitioning

王亞珅(1989—)，博士研究生，主要研究領(lǐng)域為短文本話題發(fā)現(xiàn)和信息檢索。

黃河燕(1963—)，通信作者，教授、博士生導師，主要研究領(lǐng)域為語言信息智能處理、社交網(wǎng)絡(luò)、文本大數(shù)據(jù)分析處理及云計算。

馮沖(1977—)，副研究員，主要研究領(lǐng)域為機器翻譯、信息抽取、網(wǎng)絡(luò)輿情和社會計算。

1003-0077(2017)03-0213-10

2015-04-07定稿日期： 2015-08-27

國家高技術(shù)研究發(fā)展計劃(863計劃)(2015AA015404)

TP391

： A