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

王學(xué)凱 馬英紅

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

0 引言

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

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

1 相關(guān)概念

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

(1) 鄰居節(jié)點(diǎn)集合

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

n表示社團(tuán)Ψ具有的節(jié)點(diǎn)的個(gè)數(shù)。

(2) 聚集系數(shù)

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

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

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

② 邊的聚集系數(shù)

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

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

(3) 社團(tuán)的度

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

① 社團(tuán)的內(nèi)度

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

② 社團(tuán)的外度

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

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

2 算法描述

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

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

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

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

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

具體算法過程如下描述：

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

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

① 初始社團(tuán)Ψi為空。

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

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

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

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

⑥ 輸出所有社團(tuán)。

3 實(shí)驗(yàn)與分析

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

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

Zachary空手道俱樂部網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)在社會(huì)學(xué)分析中常用的經(jīng)典問題之一。20世紀(jì)70年代初，Zachary用了兩年時(shí)間觀察美國一所大學(xué)空手道俱樂部成員間的相互社會(huì)關(guān)系，基于這些成員在俱樂部內(nèi)部和外部的社會(huì)關(guān)系，Zachary構(gòu)造了該網(wǎng)絡(luò)。Zachary空手道俱樂部網(wǎng)絡(luò)由34個(gè)節(jié)點(diǎn)和78條邊組成，節(jié)點(diǎn)代表俱樂部的成員，邊代表成員之間的關(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)建了海豚社會(huì)網(wǎng)絡(luò)。在他觀察期間，隨著一只關(guān)鍵海豚的離開，這個(gè)群體分成了兩個(gè)小群體，利用本文中的算法將該網(wǎng)絡(luò)劃分成3個(gè)社團(tuán)結(jié)構(gòu)，圖2是利用本文的算法對(duì)該網(wǎng)絡(luò)劃分的結(jié)果。

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

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

圖2 海豚網(wǎng)絡(luò)的社團(tuán)結(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.