基于邊模式的社團(tuán)檢測(cè)算法

摘 要： 為了檢測(cè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，提出基于統(tǒng)計(jì)推理的邊模式社團(tuán)檢測(cè)方法，在計(jì)算機(jī)生成的網(wǎng)絡(luò)中和實(shí)際網(wǎng)絡(luò)檢測(cè)了算法的可行性和準(zhǔn)確性，并與現(xiàn)有的兩種基于邊模式的社團(tuán)檢測(cè)方法做了比較。實(shí)驗(yàn)表明，所提出的方法可以快速有效地檢測(cè)出重疊社團(tuán)，在性能上優(yōu)于后兩種方法。

關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò)； 社團(tuán)結(jié)構(gòu)； 邊模式； 網(wǎng)絡(luò)檢測(cè)

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2013）14?0031?04

Link model based detection algorithm of community structure in complex networks

GAO Hong?yan， QIAN Yu， LIU Fei

（Baoji University of Arts Science， Baoji 721016， China）

Abstract： The link model community detection method based on statistic inference is proposed in the paper to detect community structure of networks. The feasibility and accuracy of the algorithm were tested in both the synthetic networks and actual networks. It was compared with other two available community detection methods based on link model. It turns out that the proposed method can find out the overlapping communities rapidly and its performance is better than that of the previous methods.

Keywords： complex network； community structure； link model； network detection

0 引 言

對(duì)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和功能的研究近年來(lái)成了各學(xué)科專家探討的熱點(diǎn)問(wèn)題[1?2]。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中研究的最核心的問(wèn)題之一，社團(tuán)是將復(fù)雜網(wǎng)絡(luò)的點(diǎn)集按照一定的規(guī)則劃分的子集，在子集內(nèi)部，各點(diǎn)聯(lián)系相對(duì)緊密，而在各子集之間，點(diǎn)的聯(lián)系相對(duì)稀疏。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最重要的特性之一，揭示網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)對(duì)了解網(wǎng)絡(luò)結(jié)構(gòu)和功能非常重要[3]。到目前為止，人們提出了各種揭示社團(tuán)結(jié)構(gòu)的方法，大致基于譜分的思想，層次聚類法，基于優(yōu)化的思想。基于譜分的思想主要通過(guò)計(jì)算特殊矩陣的特征向量來(lái)進(jìn)行社團(tuán)的劃分[4?5]；層次聚類法又分分裂算法和凝聚算法，最經(jīng)典的就是GN算法和Newman快速算法。GN算法是通過(guò)不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊將網(wǎng)絡(luò)逐步細(xì)化若干個(gè)社團(tuán)[6]。Newman快速算法按照一定的規(guī)則向原始空網(wǎng)中添加邊來(lái)實(shí)現(xiàn)的[7]。基于優(yōu)化的思想有Kernighan?Lin算法[8]，極值優(yōu)化算法等等[9]，這些算法主要通過(guò)最優(yōu)化目標(biāo)函數(shù)來(lái)實(shí)現(xiàn)社團(tuán)劃分的。當(dāng)然，還有許多將兩種或以上算法結(jié)合起來(lái)的變種算法，如結(jié)合譜分析的凝聚算法等[10]。這些算法的一個(gè)共同特點(diǎn)就是劃分社團(tuán)時(shí)，將網(wǎng)絡(luò)中的點(diǎn)進(jìn)行劃分，它們都屬于基于點(diǎn)模式的社團(tuán)發(fā)現(xiàn)算法，當(dāng)然，由于點(diǎn)模式社團(tuán)發(fā)現(xiàn)由來(lái)已久，所以算法比較成熟。但是研究發(fā)現(xiàn)，這些算法只能將節(jié)點(diǎn)劃分到一個(gè)社團(tuán)當(dāng)中，對(duì)于那些存在著大量的重疊節(jié)點(diǎn)的社團(tuán)的檢測(cè)效果并不理想。而實(shí)際當(dāng)中，這種網(wǎng)絡(luò)卻大量存在，比如社會(huì)網(wǎng)中，個(gè)體由于不同的關(guān)系可能屬于不同的社團(tuán)，如：朋友關(guān)系，家庭關(guān)系，工作關(guān)系等。再如科學(xué)合作網(wǎng)，作者根據(jù)研究興趣可屬于不同的研究團(tuán)體。

科學(xué)家們也提出了一些發(fā)現(xiàn)重疊社團(tuán)的方法，如派系過(guò)濾法[11]，基于模塊度的擴(kuò)展定義的思想，以及基于優(yōu)化的思想[12]。這些都是從點(diǎn)的角度來(lái)劃分社團(tuán)。本文另辟蹊蹺，將社團(tuán)定義為邊的劃分，而非點(diǎn)的劃分。這樣，與點(diǎn)關(guān)聯(lián)的邊可屬于多個(gè)社團(tuán)，點(diǎn)也就屬于多個(gè)社團(tuán)。

基于邊模式的社團(tuán)劃分由T.S.Evans首次提出，它通過(guò)構(gòu)造線圖實(shí)現(xiàn)社團(tuán)劃分[13]，后來(lái)，Ahn將在基于節(jié)點(diǎn)相似的的聚類算法基礎(chǔ)上提出了基于邊相似性的聚類方法[14]。本文在研究前人算法的基礎(chǔ)上，受任偉的簡(jiǎn)單概率算法啟發(fā)[15]，提出一種新的基于統(tǒng)計(jì)推理的邊模式社團(tuán)發(fā)現(xiàn)算法。

1 基于線圖的劃分方法

線圖是圖論中的一個(gè)概念，可以為任何一個(gè)圖G構(gòu)造線圖L（G），L（G）的一個(gè)節(jié)點(diǎn)對(duì)應(yīng)G的一邊， 當(dāng)G中兩邊相互鄰接時(shí)（既有公共頂點(diǎn)），其對(duì)應(yīng)線圖中相應(yīng)兩節(jié)點(diǎn)有邊相連。線圖的制作過(guò)程如圖1所示。

圖1 線圖的構(gòu)造過(guò)程

設(shè)原圖的鄰接矩陣為A，關(guān)聯(lián)矩陣為B，線圖的鄰接矩陣為C則三者存在以下關(guān)系：

（1）

（2）

式中：為圖A中節(jié)點(diǎn)i的度；為沖擊函數(shù)，當(dāng)i=j時(shí)，=1，否則=0。由此可知，任何圖都與G都和一線圖L（G）一一對(duì)應(yīng)，而且有以下性質(zhì)：

（1）若原圖是連通的，線圖也是；

（2），原圖的邊色數(shù)等于線圖的點(diǎn)色數(shù)。

那么可以通過(guò)對(duì)線圖邊的劃分實(shí)現(xiàn)對(duì)原圖點(diǎn)的劃分。而且，由于線圖本質(zhì)上也是基本圖，所以任何關(guān)于圖聚類的算法都可以應(yīng)用到線圖的社團(tuán)劃分中去。

文獻(xiàn)[13]將隨機(jī)游走思想應(yīng)用于線圖，提出兩種線圖上的隨機(jī)游走過(guò)程“邊?邊隨機(jī)游走”和“邊?節(jié)點(diǎn)?邊隨機(jī)游走”，對(duì)質(zhì)量函數(shù)Q進(jìn)行優(yōu)化，采用基于模塊度優(yōu)化的算法對(duì)線圖進(jìn)行社團(tuán)劃分。

2 基于邊相似性的聚類算法

該方法從考慮邊的鄰居信息（即與一條邊有共同節(jié)點(diǎn)的邊）出發(fā)。如果網(wǎng)絡(luò)中兩條邊有共同的鄰居信息或者相近的鄰居信息，則這兩條邊就被認(rèn)為是相似的，它們同屬一個(gè)社團(tuán)的概率就大一些。

對(duì)于無(wú)向，無(wú)權(quán)網(wǎng)絡(luò)，節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合用N（i）表示，節(jié)點(diǎn)i及鄰居節(jié)點(diǎn)集合用，認(rèn)為鄰居邊（即共享一個(gè)節(jié)點(diǎn)的邊）比相互獨(dú)立的邊相似性更強(qiáng)，所以計(jì)算邊相似性時(shí)，只考慮哪些鄰居邊。邊和邊的相似性有以下幾種定義方式：

（3）

（4）

（5）

在這三個(gè)相似度的表達(dá)式中，節(jié)點(diǎn)k的信息并沒有出現(xiàn)，這是因?yàn)楣?jié)點(diǎn)k的引進(jìn)不能帶來(lái)任何信息量。得到邊相似矩陣后，采用層次聚類法最其進(jìn)行社團(tuán)劃分，層次聚類法又分single?linkage，complete?linkage和average?linkage，single?linkage的類間距離為兩個(gè)類中對(duì)象間距離的最小值，complete?linkage的兩個(gè)類中對(duì)象間距離距離的最大值，average?linkage的類間距離為兩個(gè)類中對(duì)象間距離的平均值。層次聚類的關(guān)鍵是如何確定最佳劃分。文獻(xiàn)[14]引入一個(gè)類似于節(jié)點(diǎn)劃分的模塊的參量—?jiǎng)澐置芏菵來(lái)確定聚類何時(shí)結(jié)束。對(duì)于一個(gè)含M條邊，N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，該網(wǎng)絡(luò)的一個(gè)劃分，所劃分的社團(tuán)個(gè)數(shù)為C，子集中的邊數(shù)，與這些邊相關(guān)聯(lián)的節(jié)點(diǎn)數(shù)，注意有這樣的關(guān)系：，則社團(tuán)C的邊密度：

（6）

而劃分密度為的平均值。

（7）

此處，劃分密度克服的模塊的受精度限制的缺點(diǎn)，它可檢測(cè)出任意規(guī)模的社團(tuán)。

3 基于統(tǒng)計(jì)推理的邊模式社團(tuán)發(fā)現(xiàn)算法

統(tǒng)計(jì)推理指的是根據(jù)一組觀察數(shù)據(jù)和一個(gè)假設(shè)的模型推導(dǎo)出數(shù)據(jù)集的特性。如果數(shù)據(jù)集是網(wǎng)絡(luò)圖，假設(shè)節(jié)點(diǎn)連接情況的模型必須和網(wǎng)絡(luò)的真實(shí)拓?fù)浣Y(jié)構(gòu)相符合。

3.1 模型的定義

將網(wǎng)絡(luò)中邊的社團(tuán)劃分想象為圖中的邊涂色問(wèn)題，同一社團(tuán)中的邊，給涂上同一種顏色，不同社團(tuán)的邊，給涂上不同的顏色。所以可以定義這樣的模型，該模型是一個(gè)具有N個(gè)節(jié)點(diǎn)的無(wú)向網(wǎng)絡(luò)，該網(wǎng)絡(luò)的邊假設(shè)被圖上了K種顏色，即被劃分給了K個(gè)社團(tuán)，用參數(shù)來(lái)表征模型中邊的顏色特性，它表示與節(jié)點(diǎn)i相連的邊為顏色z的概率。為位于節(jié)點(diǎn)i和節(jié)點(diǎn)j的z色邊的邊數(shù)的均值，而節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的實(shí)際z色邊數(shù)服從關(guān)于的泊松分布。這意味著網(wǎng)絡(luò)可以是多圖——即網(wǎng)絡(luò)中一對(duì)節(jié)點(diǎn)之間可有多條邊。盡管大多數(shù)實(shí)際網(wǎng)絡(luò)只有單邊，但引進(jìn)多邊可大大降低模型的復(fù)雜性，而且由于的值本來(lái)就很小，所以引進(jìn)的誤差也是微乎其微的。隨著模型的建立，邊社團(tuán)也伴隨而生，對(duì)于某個(gè)z值，若節(jié)點(diǎn)i和節(jié)點(diǎn)j有大的，，則連接i，j的邊為z色的概率就大，這些邊就屬于社團(tuán)z。

3.2 檢測(cè)重疊社團(tuán)

根據(jù)定義的模型，直接生成相應(yīng)的網(wǎng)絡(luò)。由于相互獨(dú)立且服從泊松分布的隨機(jī)變量的和仍服從泊松分布，所以節(jié)點(diǎn)i，j之間的邊的所有顏色的均值為，i，j之間邊的實(shí)際顏色服從關(guān)于的泊松分布，由此生成鄰接矩陣為A的網(wǎng)絡(luò)的概率為：

（8）

式中：A為鄰接矩陣；第二部分為包含自環(huán)的情況。

這里，根據(jù)統(tǒng)計(jì)推理的思想，觀察數(shù)據(jù)就是網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，即網(wǎng)絡(luò)的鄰接矩陣，假設(shè)的模型為第3.1節(jié)定義的帶參數(shù)的模型，那么現(xiàn)在的任務(wù)就是根據(jù)觀察數(shù)據(jù)，假設(shè)模型推導(dǎo)出模型的參數(shù)，這樣就可以得到網(wǎng)絡(luò)中邊的顏色劃分，及社團(tuán)劃分。為了得到參數(shù)，采用數(shù)理統(tǒng)計(jì)中的最大似然法求解。即求式（8）左邊達(dá)到最大值時(shí)的參數(shù)值。對(duì)式（8）進(jìn)行簡(jiǎn)化，重新排列，得到簡(jiǎn)化的似然函數(shù)如下：

（9）

式（9）很難直接微分求解，這里采用Jensen不等式對(duì)其進(jìn)行簡(jiǎn)化：此處，為任意正數(shù)集，為概率且滿足當(dāng)滿足有：

（10）

此處概率只要滿足條件即可。在不等式（10）中，只要選擇合適的值，就能取到等號(hào)，假設(shè)給定的最佳真值，則的最佳真值由下式給出：

（11）

同樣，給定的最佳真值， 對(duì)式（10）進(jìn)行微分得到的值。

（12）

對(duì)式（12）求和，并重新排列，得到下列關(guān)系：

（13）

聯(lián)合式（12），式（13）得到：

（14）

最大化似然函數(shù)現(xiàn)在簡(jiǎn)化為同步求解式（11）和式（14），可采用EM算法求解，即給隨機(jī)設(shè)置一組初始值，將其值代入式（11）得到，再將所得代入式（14）得到的值，這樣來(lái)回迭代，在迭代的過(guò)程中，似然值單調(diào)增加，當(dāng)似然值達(dá)到最大值時(shí)所對(duì)應(yīng)的即為假設(shè)的模型的最佳真值，為了防止似然值陷入局部最大值，可采取重復(fù)計(jì)算取最大值的方法。最終得到參數(shù)值就是邊（i，j）被涂為z色的概率，它恰恰就是進(jìn)行社團(tuán)劃分所需要的參數(shù)。進(jìn)一步，當(dāng)，則節(jié)點(diǎn)i就屬于社團(tuán)z。

3.3 算法復(fù)雜度分析

算法的存儲(chǔ)空間主要取決于存儲(chǔ)系數(shù)所需的空間，此算法中有兩個(gè)參數(shù)和。要求的空間復(fù)雜度為，而 要求的存儲(chǔ)空間復(fù)雜度為，m，n和K分別為網(wǎng)絡(luò)中邊數(shù)，節(jié)點(diǎn)數(shù)，劃分的社團(tuán)數(shù)。因?yàn)閙通常遠(yuǎn)遠(yuǎn)大于n，所以存儲(chǔ)空間主要由參數(shù)決定為。對(duì)于時(shí)間復(fù)雜度，算法迭代一次為，總運(yùn)行時(shí)間取決于達(dá)到最大似然值前的迭代次數(shù)。

4 實(shí) 驗(yàn)

在此使用真實(shí)的網(wǎng)絡(luò)檢測(cè)該的算法。

4.1 人工合成網(wǎng)絡(luò)

計(jì)算機(jī)生成的網(wǎng)絡(luò)是一個(gè)包含n=10 000個(gè)節(jié)點(diǎn)，被劃分成2個(gè)重疊社團(tuán)的網(wǎng)絡(luò)。將x個(gè)節(jié)點(diǎn)放置在第一個(gè)社團(tuán)當(dāng)中，y個(gè)節(jié)點(diǎn)放置在第二個(gè)社團(tuán)中，剩下n-x-y個(gè)節(jié)點(diǎn)放置在兩個(gè)社團(tuán)當(dāng)中，并與兩個(gè)社團(tuán)其他節(jié)點(diǎn)連接的邊數(shù)的均值相等。設(shè)置每個(gè)節(jié)點(diǎn)的度均值為k。

做三組測(cè)試：

（1）固定重疊的節(jié)點(diǎn)數(shù)z=500，x=y=4 750，觀察算法隨k的變化情況。當(dāng)k趨于10時(shí)，網(wǎng)絡(luò)中無(wú)邊，故無(wú)社團(tuán)結(jié)構(gòu)，當(dāng)k變大時(shí)，可以直接檢測(cè)出社團(tuán)結(jié)構(gòu)；

（2）固定z=500，k=10，改變x和y；

（3）固定k=10，x=y，改變z。

實(shí)驗(yàn)結(jié)果顯示，算法在相當(dāng)一段參數(shù)范圍內(nèi)執(zhí)行結(jié)果良好。算法的準(zhǔn)確性隨著K的增加而增加。當(dāng)k>10時(shí)，執(zhí)行結(jié)果與真實(shí)網(wǎng)絡(luò)幾乎一致，隨著z的增加，x，y比例的失衡，算法的準(zhǔn)確性下降。

4.2 Zachary俱樂(lè)部網(wǎng)

Zachary俱樂(lè)部網(wǎng)是用來(lái)檢測(cè)算法的基準(zhǔn)網(wǎng)絡(luò)之一，代表了大學(xué)運(yùn)動(dòng)俱樂(lè)部的關(guān)系網(wǎng)，由34個(gè)節(jié)點(diǎn)組成。圖2 是由本文算法得到的交疊社團(tuán)劃分圖。由圖可知，劃分的社團(tuán)結(jié)構(gòu)很明顯，其中節(jié)點(diǎn)3，9 ，14， 20， 31為重疊節(jié)點(diǎn)，這些重疊節(jié)點(diǎn)代表了那些在兩個(gè)社團(tuán)中都有朋友的個(gè)體，在爭(zhēng)論中，他們很難決定站在哪一方，故將其劃為重疊節(jié)點(diǎn)是合理的。

圖2 Zachary俱樂(lè)部網(wǎng)絡(luò)

4.3 和其他算法比較

在此做了兩組比較，首先將提出的方法與文中提到的兩種邊模式社團(tuán)檢測(cè)做了比較，發(fā)現(xiàn)前兩種方法雖然定義了邊模式社團(tuán)，但卻用節(jié)點(diǎn)社團(tuán)的傳統(tǒng)方法對(duì)社團(tuán)進(jìn)行了檢測(cè)。其復(fù)雜度顯然要大于相對(duì)應(yīng)的傳統(tǒng)方法。提出的方法在效率和復(fù)雜性上要略好一些。

其次，將所提算法與簡(jiǎn)單概率算法進(jìn)行比較，發(fā)現(xiàn)二者復(fù)雜性相同，均采用模型假設(shè)和EM算法。二者的主要區(qū)別在于SPAEM定義的參數(shù)是基于節(jié)點(diǎn)的連接性。而本文算法基于邊的連接性。故在檢測(cè)重疊節(jié)點(diǎn)方面，本文算法要優(yōu)于SPAEM算法。

5 結(jié) 語(yǔ)

在該文中，綜述了現(xiàn)有的基于邊模式的設(shè)團(tuán)檢測(cè)算法，并提出了一種新的邊模式社團(tuán)檢測(cè)算法，該算法有嚴(yán)格的數(shù)學(xué)基礎(chǔ)，它是一種基于概率模型的邊社團(tuán)檢測(cè)算法，易于實(shí)現(xiàn)，該算法的缺點(diǎn)是必須預(yù)知社團(tuán)的個(gè)數(shù)，這是后面進(jìn)一步研究的內(nèi)容。由于復(fù)雜度的限制，它只能檢測(cè)中等規(guī)模的數(shù)據(jù)，需要進(jìn)一步的改進(jìn)。

參考文獻(xiàn)

[1] STROGATZ S H. Exploring complex networks [J]. Nature， 2001， 410： 268?276.

[2] BOCCALETTI S， LATORA V， MORENO Y， et al. Complex networks： structure and dynamics [J]. Physics Reports， 2006， 424（4/5）： 175?308.

[3] FORTUNATO Santo. Community detection in graphs [J]. Physics Reports， 2010， 486： 75?174.

[4] FIEDLER M. Algebraic connectivity of graphs [J]. Czech. Math. J.， 1973， 23： 298?304.

[5] POTHEN A， SIMON H， LIOU K?P. Partitioning sparse matrices with eigenvectors of graphs [J]. SIAM Journal on Matrix Analysis and Applications， 1990， 11（3）： 430?452.

[6] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [J]. Proc. Natl. Acad. Sci.， 2001， 99： 7821?7826.

[7] NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Phys. Rev. E， 2004， 69： 066133.

[8] KERNIGHAN B W， LIN S. An efficient heuristic procedure for partitioning graphs [J]. Bell System Technical Journal， 1970， 49： 291?307.

[9] DUCH J， ARENAS A. Community detection in complex networks using extreme optimization [EB/OL]. [2005?01?16]. http：//www. arxiv.org/pdf/cond?mat/0501368.

[10] DONETTI L， MU?OZ M A. Detecting network communities： a new systematic and efficient algorithm [EB/OL]. [2008?02?02]. http：//www.arxiv.org/pdf/cond?mat/0404652.

[11] PALLA G， DERéNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature， 2005， 435（7043）： 814?818.

[12] BAUMES J， GOLDBERG M K， KRISHNAMOORTHY M S， et al. Finding communities by clustering a graph into overlapping subgraphs [C]// Proceedings of IADIS AC. [S.l.]： IADIS ， 2005： 97?104.