一種基于聚集系數(shù)的復(fù)雜網(wǎng)絡(luò)社團劃分算法

王學(xué)凱 馬英紅

山東師范大學(xué)管理科學(xué)與工程學(xué)院 山東 250014

0 引言

復(fù)雜網(wǎng)絡(luò)的特征和性質(zhì)在近些年來已經(jīng)成為研究的熱點。對社團結(jié)構(gòu)的研究對于理解和分析網(wǎng)絡(luò)結(jié)構(gòu)及其功能有著至關(guān)重要的作用已廣泛應(yīng)用到生物學(xué)、計算機科學(xué)、社會學(xué)等領(lǐng)域中。社團結(jié)構(gòu)是指其社團內(nèi)部節(jié)點連接緊密，社團之間連接相對稀疏的一種結(jié)構(gòu)。許多研究人員從不同角度出發(fā)提出了劃分社團算法，例如Kernighan-Lin算法，Kernighan算法是一種基于貪婪算法原理將網(wǎng)絡(luò)分割為兩個大小已知的社團的二分法，但該算法必須已知網(wǎng)絡(luò)社團的確切規(guī)模才能得以應(yīng)用；基于Laplace圖特征值的譜平分法，利用網(wǎng)絡(luò)結(jié)構(gòu)的Laplace矩陣中不為零的特征值所對應(yīng)的特征向量，和同一個社團內(nèi)的節(jié)點對應(yīng)的元素近似相等的原理對網(wǎng)絡(luò)社團進行劃分，在規(guī)模為n個節(jié)點的網(wǎng)絡(luò)中，該算法的復(fù)雜度為O(n3)；GN算法通過從網(wǎng)絡(luò)中移除介數(shù)最大的邊將整個網(wǎng)絡(luò)分成越來越小的部分，其不足在于對網(wǎng)絡(luò)社團劃分優(yōu)劣沒有一個定量描述。Newman等人經(jīng)過研究提出了一種度量網(wǎng)絡(luò)社團劃分質(zhì)量的標準，成功地解決了這個問題。Wu和Huberman提出了基于電阻網(wǎng)絡(luò)電壓譜的快速分割算法，該方法須已知分屬于不同社團的兩個節(jié)點。Newman義了模塊度Q，用來衡量網(wǎng)絡(luò)劃分質(zhì)量，Q值越大，說明劃分結(jié)果越好。Clauset等通過節(jié)點的局部信息，提出局部模塊度，該方法的優(yōu)點是計算量比較小。在很多情況下，研究人員關(guān)注的是網(wǎng)絡(luò)的局部社團結(jié)構(gòu)。例如，在社會網(wǎng)絡(luò)中搜索時通常只關(guān)心某個人所在的社團，此時就不需要耗時尋找網(wǎng)絡(luò)的全局社團結(jié)構(gòu)，而只需搜索網(wǎng)絡(luò)中某個節(jié)點所在的局部社團。

本文提出一種局部社團劃分的新算法，通過搜索鄰居節(jié)點以及計算有關(guān)節(jié)點聚集系數(shù)，選擇符合條件的節(jié)點加入局部社團，最終獲得待求節(jié)點所在的社團。局部社團對鄰居節(jié)點的吸引力取決于社團對該節(jié)點的重要程度。節(jié)點的聚集系數(shù)就是表征某節(jié)點鄰居之間連接的緊密程度，因此通過考察某局部社團存在前后其鄰居節(jié)點聚集系數(shù)的變化情況來確定社團和節(jié)點之間的關(guān)系。利用該算法尋找到某個節(jié)點的社團后，從網(wǎng)絡(luò)中社團外的任一節(jié)點開始尋找其社團，重復(fù)此過程，即可得到網(wǎng)絡(luò)的全局社團結(jié)構(gòu)。

1 相關(guān)概念

在一個無向無權(quán)網(wǎng)絡(luò)G=＜V,E＞中，具有n個節(jié)點，m條邊，eij表示節(jié)點i和節(jié)點j之間的連邊，V={i|i∈n}，E={eij|i,j∈n且i≠j} 。

(1) 鄰居節(jié)點集合

節(jié)點i的鄰居節(jié)點集合：Ni={j|節(jié)點i和節(jié)點j 直接相連}；社團Ψ的鄰居節(jié)點集合：

n表示社團Ψ具有的節(jié)點的個數(shù)。

(2) 聚集系數(shù)

① 節(jié)點的聚集系數(shù)

節(jié)點i的聚集系數(shù)Ci定義為：Ci=Ei/Ti,,Ci∈[0,1]。

其中，設(shè)節(jié)點i的度是ki，Ei表示節(jié)點i的k個鄰居節(jié)點之間實際的連接邊數(shù)，Ti表示節(jié)點i的k個鄰居節(jié)點之間可能形成的最大連接數(shù)，Ti=ki(ki-1)/2。當(dāng)Ci=1時，表示節(jié)點i的所有鄰居節(jié)點之間都相互連接，節(jié)點i和它的鄰居節(jié)點之間形成了全局耦合網(wǎng)絡(luò)，連接緊密。

② 邊的聚集系數(shù)

邊eij的聚集系數(shù)：Ci,j=|Nij|/(ki+kj-|Nij|-2)，

式中Nij=Ni∩Nj，表示節(jié)點i和節(jié)點j的公共鄰居集合，|Nij|表示以eij為邊組成的實際三角形的數(shù)量。邊的集聚系數(shù)Ci,j∈[0,1]，它表示被這條邊所連接的兩個節(jié)點的連接強度，值越大，強度就越強，表示這兩個節(jié)點在同一個社團的可能性就越大。

(3) 社團的度

在社團Ψ 中，Din(Ψ)表示社團的內(nèi)度，Dout(Ψ)表示社團的外度，n表示社團Ψ內(nèi)節(jié)點的個數(shù)，表示節(jié)點i和社團Ψ內(nèi)部節(jié)點連接度，表示節(jié)點i和社團Ψ外部節(jié)點連接度，其中對?i∈Ψ。

① 社團的內(nèi)度

社團Ψ的內(nèi)度為：

② 社團的外度

設(shè)社團Ψ的外度為：

③ 節(jié)點的內(nèi)外度差：

2 算法描述

本文提出的算法從待求節(jié)點開始到最終劃分出全部社團為止。首先將待求節(jié)點加入到一個空社團，即得到一個局部社團，通過鄰居節(jié)點的度和聚集系數(shù)等相關(guān)比較計算，不斷地添加鄰居節(jié)點，直到發(fā)現(xiàn)沒有符合條件的節(jié)點時，即刻停止便可獲得一個社團。在剩余網(wǎng)絡(luò)中重復(fù)運行，最終將網(wǎng)絡(luò)劃分為若干個社團。為方便算法的描述，在確定社團時可以根據(jù)以下定義提出以下約定：

(1) 若社團外的某一節(jié)點i有一半以上連接與該社團相連，那么這個節(jié)點也在社團中。

(2) 在與社團連接的所有邊中，若存在一條邊eij滿足以下條件，那么節(jié)點j也屬于該社團。該條件是邊eij的聚集系數(shù)是在與社團連接的所有邊中是最大的，其中節(jié)點i是該社團內(nèi)的一點，j是該社團的鄰居節(jié)點，并且與節(jié)點j相連的其它邊的聚集系數(shù)小于等于該邊的聚集系數(shù)。

(3) 要求社團的內(nèi)度大于社團的外度。

(4) 計算所形成初步社團中每一個節(jié)點的內(nèi)外度差，優(yōu)化社團結(jié)構(gòu)。

具體算法過程如下描述：

輸入：一個無向無權(quán)網(wǎng)絡(luò)G=＜V,E＞，V是網(wǎng)絡(luò)中節(jié)點集合，E是網(wǎng)絡(luò)中邊的集合。

輸出：網(wǎng)絡(luò)的社團結(jié)構(gòu)。

① 初始社團Ψi為空。

② 選取剩余網(wǎng)絡(luò)中度數(shù)最大的節(jié)點i作為社團Ψi的初始節(jié)點。令Ψi←Ψi+i ，V←V-i，建立社團Ψi的鄰居集合NΨi。

③ 計算社團Ψi的鄰居集合NΨi中的每個節(jié)點的度，如果節(jié)點的度有一半或者以上的與社團Ψi相連，將把這些節(jié)點并入到社團中；在剩余的鄰居節(jié)點中計算每個節(jié)點與社團連接邊的聚集系數(shù)，找到與邊的聚集系數(shù)最大的對應(yīng)的那個鄰居節(jié)點并計算與該節(jié)點連接的其他邊的聚集系數(shù)，比較與社團連接的聚集系數(shù)，如果與社團連接的聚集系數(shù)是最大的，那么將該節(jié)點加入到社團中，否則，計算找到聚集系數(shù)為第二大、第三大...的邊，并計算與該邊對應(yīng)的鄰居節(jié)點連接的其他邊的聚集系數(shù)，如果是最大加入社團中，直到?jīng)]有符合條件的節(jié)點為止。Ψi←Ψi+Vi，V←V-Vi，并更新鄰居集合NΨi，直到Ψi的鄰居集合中不再有新的節(jié)點加入。重復(fù)②③形成所有社團結(jié)構(gòu)。

④ 比較③中形成的社團的內(nèi)度和外度，如果內(nèi)度大于外度，則進行步驟⑤，否則將小度社團與鄰居社團中內(nèi)度最大的社團合并后進行步驟⑤。

⑤ 計算所形成的初始社團中每一個節(jié)點的內(nèi)外度差δ，如果δ≤0，計算該節(jié)點的鄰居節(jié)點屬于不同社團的鄰居數(shù)并加入具有最大鄰居數(shù)的社團；如果δ＞0，則節(jié)點所屬的社團不變。

⑥ 輸出所有社團。

3 實驗與分析

為了驗證該算法的可行性以及劃分的精確性，本次試驗選擇了Zachary空手道俱樂部成員網(wǎng)絡(luò)和Dolphin social network經(jīng)典網(wǎng)絡(luò)進行劃分。

(1) Zachary空手道俱樂部成員網(wǎng)絡(luò)

Zachary空手道俱樂部網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)在社會學(xué)分析中常用的經(jīng)典問題之一。20世紀70年代初，Zachary用了兩年時間觀察美國一所大學(xué)空手道俱樂部成員間的相互社會關(guān)系，基于這些成員在俱樂部內(nèi)部和外部的社會關(guān)系，Zachary構(gòu)造了該網(wǎng)絡(luò)。Zachary空手道俱樂部網(wǎng)絡(luò)由34個節(jié)點和78條邊組成，節(jié)點代表俱樂部的成員，邊代表成員之間的關(guān)系。將本文提出的算法應(yīng)用于該網(wǎng)絡(luò)，得到的劃分結(jié)果如圖1所示。

圖1 Zachary俱樂部網(wǎng)絡(luò)

(2) Dolphin social network網(wǎng)絡(luò)

Lusseau在1994年-2001年研究了生活在新西蘭的62只海豚，通過觀察它們之間的聯(lián)系情況，構(gòu)建了海豚社會網(wǎng)絡(luò)。在他觀察期間，隨著一只關(guān)鍵海豚的離開，這個群體分成了兩個小群體，利用本文中的算法將該網(wǎng)絡(luò)劃分成3個社團結(jié)構(gòu)，圖2是利用本文的算法對該網(wǎng)絡(luò)劃分的結(jié)果。

5 結(jié)術(shù)語

復(fù)雜網(wǎng)絡(luò)社團研究中，存在著許多種社團發(fā)現(xiàn)的算法，本文提出了一種基于聚集系數(shù)的局部社團劃分最終求出整個網(wǎng)絡(luò)的社團劃分，該算法用時少，劃分準確，并通過實驗得到的理想結(jié)果證明其劃分的準確性，該算法同樣可以應(yīng)用于數(shù)據(jù)挖掘的多個領(lǐng)域，在今后的研究中，應(yīng)結(jié)合新的理論成果和技術(shù)方法尋找新的更有效的算法。

圖2 海豚網(wǎng)絡(luò)的社團結(jié)構(gòu)

[1] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell Syst Tech J.1970.

[2] Kleinberg J. Authoritative sources in a hyperlinked environment[J].JACM.1999.

[3] Girvan M, Newman M E J. Community structure in social and biological networks[J].Proc Natl Acad Sci USA.2002.

[4] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J].Phys Rev.2004.

[5] Wu F, Huberman B A. Finding communities in linear time： A physics approach[J]. Eur Phys J B, 2004.

[6] Newman M E J,Girvan M. Finding and evaluating community structure in networks[J].Phys Rev.2004.

[7] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J].Phys Rev.2004.

[8] Zachary W. An information flow model for conflict and fission in small groups[J].J Anth Res.1977.

[9] Lusseau D, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, can geographic isolation explain this unique trait[J].Behavioral Ecology and Sociobiology.2003.