一種新的復(fù)雜網(wǎng)絡(luò)層次社團(tuán)發(fā)現(xiàn)算法_圖文

1、一種新的復(fù)雜網(wǎng)絡(luò)層次社團(tuán)發(fā)現(xiàn)算法張劍(北京郵電大學(xué)計算機學(xué)院,北京 100876摘要:網(wǎng)絡(luò)結(jié)構(gòu)廣泛存在于自然界和人們的現(xiàn)實生活之中,近來研究表明復(fù)雜網(wǎng)絡(luò)呈現(xiàn)出層次社團(tuán)結(jié)構(gòu),網(wǎng)絡(luò)中節(jié)點被分成社團(tuán),社團(tuán)又可以劃分成更小的社團(tuán),這些不同的層次劃分從不同維度展示復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特性。本文針對復(fù)雜網(wǎng)絡(luò)中的層次社團(tuán)結(jié)構(gòu)提出一種新的基于聚類的層次社團(tuán)劃分算法,該算法通過有效合并策略能對不同規(guī)模的網(wǎng)絡(luò)進(jìn)行自適應(yīng)計算。人工和實際網(wǎng)絡(luò)的試驗結(jié)果均表明:該算法能得到復(fù)雜網(wǎng)絡(luò)中合理的層次社團(tuán)劃分。關(guān)鍵詞:可能性矩陣;概率矩陣;層次結(jié)構(gòu);社團(tuán)發(fā)現(xiàn)中圖分類號:TP312A Novel Algorithm for Hiera

2、rchical Community StructureDetection in Complex NetworksZHANG Jian(School of Computer Science,Beijing University of Posts and Telecommunications, Beijing 100876 Abstract: Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of sc

3、ience. Recent studies suggest that network often exhibit hierarchical organization, where vertices divide into groups that further subdivided into groups of groups, and so forth over multiple scales. In this paper, we introduce a novel algorithm that searches for the hierarchical structure. The meth

4、od iteratively combines the similar communities with the elaborate design of community similarity and combination threshold. The experiments on artificial and real networks show that the method is able to obtain reasonable hierarchical structure solutions.Key words: similarity matrix; possibility ma

5、trix; hierarchical structure; community detection0引言隨著對實際網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和物理意義的深入研究,人們逐漸發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)除了典型的“無尺度”1,“小世界”2以及“高聚集系數(shù)”3等特征,現(xiàn)實世界中的網(wǎng)絡(luò)還具有第四個重要特性,即:存在“社區(qū)結(jié)構(gòu)”4或“社團(tuán)結(jié)構(gòu)”。更進(jìn)一步研究發(fā)現(xiàn),平面化的網(wǎng)絡(luò)社團(tuán)劃分并不能掩蓋實際網(wǎng)絡(luò)結(jié)構(gòu)的非平面模塊結(jié)構(gòu):社團(tuán)是嵌套的,小社團(tuán)組成稍大社團(tuán),稍大社團(tuán)反過來組成更大社團(tuán),例如大公司組織架構(gòu),生物組織功能結(jié)構(gòu)等。在社團(tuán)發(fā)現(xiàn)基礎(chǔ)上引入層次結(jié)構(gòu),社團(tuán)結(jié)構(gòu)會更豐富,并能幫助分析研究人員更清楚地了解復(fù)雜系統(tǒng)的組織結(jié)構(gòu)特征。應(yīng)用于

6、生物,金融以及社會網(wǎng)絡(luò)分析中的層次聚類算法由來已久,其基本思想就是根據(jù)結(jié)點之間的相似程度遞歸地將結(jié)點合并和分裂。本文所要介紹的算法是基于合并型的層次聚類算法,算法分別采用相似性矩陣和概率矩陣來衡量節(jié)點和社團(tuán)間的相似性,這種具備自適應(yīng)特性的社團(tuán)合并策略對于人工網(wǎng)絡(luò)和實際網(wǎng)絡(luò)的層次社團(tuán)劃分都取得了滿意的結(jié)果。1介紹由Girvan和Newman5提出的一種新社團(tuán)發(fā)現(xiàn)算法-GN算法,是基于從網(wǎng)絡(luò)中不斷移除邊的思想,作為一種分裂型算法,GN算法的執(zhí)行過程就可以反映網(wǎng)絡(luò)的層次結(jié)構(gòu)。該算法的主要思想是:根據(jù)社團(tuán)的定義,社團(tuán)之間的邊的數(shù)目很少,可以認(rèn)為是社團(tuán)之間的“瓶頸”。作者簡介:張劍(1986-,男,碩士

7、,主要研究方向:復(fù)雜網(wǎng)絡(luò)可視化與數(shù)據(jù)挖掘. E-mail: zj.cst.bupt如果從一個社團(tuán)的結(jié)點到達(dá)另一個結(jié)點就必須經(jīng)過至少一條這樣的“瓶頸”邊。因此這些邊的流量與社團(tuán)內(nèi)部的邊相比較高。如果找到這樣的一些邊從網(wǎng)絡(luò)中移除就可以把網(wǎng)絡(luò)劃分為社團(tuán)。Girvan 和Newman 提出的算法在很多情況下都可以取得較好的效果,但是這種算法也有兩個重要的缺點,第一個是像其它算法一樣這個算法也沒有給出應(yīng)該把網(wǎng)絡(luò)劃分為幾個社團(tuán)的衡量方法。該算法另一個缺點就是速度較慢。如果共移除m 條邊,算法將花費O(mN的時間,最壞情況下為O(N 3 。在此之后出現(xiàn)了此算法的改進(jìn)算法,其主要思路是在計算邊介數(shù)時應(yīng)用一些優(yōu)

8、化模型來提高算法效率。合并層次聚類算法的一般步驟如下:1計算N 個結(jié)點兩兩之間的相似度; 2構(gòu)造N 個成員社團(tuán)C 1,C 2,C 3,C N ,每一類的高度都為0; 3找到最近的社團(tuán)C i , C j ,合并C i ,C j ,社團(tuán)個數(shù)減少1,以被合并的兩個類的間距作為上層的高度; 4計算新生成的社團(tuán)與本層中其它社團(tuán)的相似度,如果滿足條件算法終止,否則轉(zhuǎn)到3。各種合并型聚類算法的步驟基本相同,差別在于數(shù)據(jù)之間的相似度量標(biāo)準(zhǔn)的定義和社團(tuán)間距離的定義。本文所提的算法即合并型的層次聚類,算法分別采用相似性矩陣和概率矩陣來衡量節(jié)點和社團(tuán)間相似性,并對算法的優(yōu)劣從人工網(wǎng)絡(luò)和實際網(wǎng)絡(luò)分別進(jìn)行實驗對比,均取

9、得滿意結(jié)果。2 迭代層次社團(tuán)發(fā)現(xiàn)算法本章首先介紹算法中的相關(guān)函數(shù)定義,再介紹算法的詳細(xì)實現(xiàn)。 (A 0111000101110011010001110000000001100001010000110 1.00.40.50.50.20.0010.0010.4 1.00.40.40.0010.20.20.50.4 1.00.50.20.0010.0010.50.40.5 1.00.20.0010.0010.20.0010.20.2 1.00.250.250.0010.20.0010.0010.25 1.00.3330.0010.20.0010.0010.250.333 1.010.0040.001

10、0.00410.250.0010.251 (B (C (D圖1 (A簡單網(wǎng)絡(luò)圖;(B鄰接矩陣;(C相似性矩陣;(D概率矩陣如圖所示,圖1 (A由7個節(jié)點和10條邊組成的簡單網(wǎng)絡(luò). 考慮節(jié)點1和5間的節(jié)點相似性(N1= 2, 3, 4, N5= 2, 6, 7,相似度為0.2;(B 圖A 所示網(wǎng)絡(luò)的鄰接矩陣. (C 圖A 相似性矩陣. 同時也是概率矩陣000,(,0.5,(,0.001,0.25PM MAX PM i j MIN PM i j =. 第一次迭代運行結(jié)束后所得到的社團(tuán):1123123,1,2,3,4,5,6,7P C C C C C C =;(D11121212,(,0.25,(,

11、0.001,0.125.,1,2,3,4,5,6,7PM MAX PM i j MIN PM i j P C C C C =.2.1 相似性矩陣計算任意一對節(jié)點間相似性,用以構(gòu)造相似性矩陣。衡量節(jié)點間相似性的辦法很多,在經(jīng)過大量試驗后,我們選擇了一個測量網(wǎng)絡(luò)拓?fù)渲丿B的基本方法678,將其定義為兩節(jié)點公有的鄰接點與兩節(jié)點所有的鄰接點的比值。這種衡量方法是在圖中較小的局部空間內(nèi)衡量節(jié)點間的相似度。 1(|,(|i j ij i j N N SM i j i j N N = 在節(jié)點相似度基本上構(gòu)造SM 矩陣,矩陣行列索引與節(jié)點編號一致?？紤]到節(jié)點i 的度可能通過,i j K A i j =計算。|i

12、 j N N 即為第i 行和第j 行數(shù)據(jù)所構(gòu)造的向量進(jìn)行“與”運算; |i j N N 即為第i 行和第j 行數(shù)據(jù)所構(gòu)造的向量進(jìn)行“并”運算即可得。2.2 可能性矩陣在合并社團(tuán)過程中,我們需要衡量社團(tuán)間的連接緊密程度。這里我們引用概率矩陣來衡量社團(tuán)間的連接緊密程序。在諸多方法比較之后,我們定義可能性矩陣公式如下:|11|,1,j i i j C C m n C C PM i j SM m n = 注意到分母,SM m n 的值可能為0,在實驗中我們選擇一個極小值(0.001來代替0.2.3 迭代層次社團(tuán)發(fā)現(xiàn)算法IHCD算法思想沿用層次聚類思想,通過引入相似性矩陣來表示節(jié)點間連接緊密程度,用概率

13、矩陣來衡量社團(tuán)間連接緊密程度,其算法主要包括以下兩個基本步驟:(i 根據(jù)鄰接矩陣計算相似性矩陣(ii 迭代合并連接度緊密的社團(tuán)結(jié)構(gòu)算法1是IHCD 的基本框架,通過每一次的迭代過程,我們都能得到一種社團(tuán)劃分,即相應(yīng)的層次結(jié)構(gòu)。概率矩陣是基于上次迭代后得到的社團(tuán)劃分結(jié)果以及相似性矩陣計算而來。整個過程結(jié)束的條件是所有節(jié)點處于同一社團(tuán)。IHCD 算法的關(guān)鍵在于社團(tuán)合并,在經(jīng)過大量試驗和對比后我們發(fā)現(xiàn),采取一種自適應(yīng)的方式來合并社團(tuán)更有效。對于某種社團(tuán)劃分t P 得到的概率矩陣t PM , 合并閾值(,(,/2MAX PM i j MIN PM i j =,如果社團(tuán)i 和社團(tuán)j 的相似度,PM i

14、j >,算法將i 與j 合并。Algorithm 1 Main framework of IHCD-Iteration Hierarchical Community Detection1. procedure2. calculate similarity matrix SM based on the adjacent matrix A3. initialize graph partition 0P with each node is a community4. set t = 05. while (|1t P > do6. calculate possibility matrix

15、t PM based on t P and SM7. combine communities to construct partition 1t P +8. t=t+19. end while10. end procedure算法2給出了合并社團(tuán)的詳細(xì)描述,其過程可看作是算法1中第7行的具體操作策略。Algorithm 2 Combine Communities1. procedure2. set (,(,/2MAX PM i j MIN PM i j =3. for each community i set isCombinedi = false4. set m = 05. initiali

16、ze graph partition 0P6. for each i C in t P do7. if (isCombinedi = false do8. add i C to m C in 1t P +9. isCombinedi = true10. for j C in t P (j>ido 11. if ( isCombinedj = false and ,PM i j > do12. add j C to m C in 1t P +13. isCombinedj = true14. end if15. end for 16. m+17. end if18. end for1

17、9. end procedure合并過程截止條件是所有節(jié)點劃歸到同一社團(tuán)。很顯然我們在每次迭代過程中能得到一種社團(tuán)結(jié)構(gòu)劃分,這種劃分也構(gòu)成了層次網(wǎng)絡(luò)的每一層。為了找出有意義的層次結(jié)構(gòu),我們需要較好地設(shè)計合并策略,對值的設(shè)計可以有很多種方式,最簡單的方式是將值從0到1按0.1逐級遞增,將網(wǎng)絡(luò)從不同顆粒度逐級合并。這里我們設(shè)置值選取概率矩陣所有值的中間值,即最大與最小值求平均。試驗結(jié)果表明這種社團(tuán)合并策略能達(dá)到最快的社團(tuán)層次收斂,并且能得到有意義的層次社團(tuán)結(jié)構(gòu),其它合并策略也可引用,將留作今后討論。 3 試驗為了進(jìn)一步驗證IHCD 實驗效果,我們進(jìn)行了兩組試驗,包括人工網(wǎng)絡(luò)和實際網(wǎng)絡(luò)實驗,實驗環(huán)境

18、:OS Windows XP, Frequency 2.40GHz and 2G RAM Pentium Processor 。3.1 人工網(wǎng)絡(luò)實驗采用的數(shù)據(jù)是由Girvan 與Newman 數(shù)據(jù)集的擴(kuò)展,如圖2所示。網(wǎng)絡(luò)由1024個節(jié)點組成,所有節(jié)點被劃分成64個社團(tuán),每個社團(tuán)包含16個節(jié)點。在最里層社團(tuán)(由16個節(jié)點組成,每個結(jié)點有K1條邊與其內(nèi)部結(jié)點相連,在第二層有K2條邊與64個節(jié)點組成的社團(tuán)相連,第三層有K3條邊與256個節(jié)點所組成的第三層社團(tuán)相連接,另外,每個節(jié)點有K4條邊隨機地與網(wǎng)絡(luò)中其他節(jié)點相連。這樣,網(wǎng)絡(luò)的三層結(jié)構(gòu)便呈現(xiàn)出來,如圖2(A 灰度圖所示:其中最里層包含64個社團(tuán)(

19、圖中高亮部分,次外層包含16個社團(tuán),最外層包括四個社團(tuán)。通過實驗我們希望IHCD 能將網(wǎng)絡(luò)的三層結(jié)構(gòu)呈現(xiàn)出來:最外層包含四個大社團(tuán),中間層包含16個子社團(tuán),最里層包含64個小社團(tuán)。K1, K2, K3和K4分別用來控制社團(tuán)度。K1值越大表明最內(nèi)部社團(tuán)連接越緊密,這里我們選擇設(shè)置K2=K3=K4=5, K1取值范圍從5到13. K1值越小,表明最內(nèi)部社團(tuán)結(jié)構(gòu)越模糊,試驗算法能否從中找出有效社團(tuán)。 (A (B圖2 (A三層網(wǎng)絡(luò)結(jié)構(gòu)灰度圖;(B試驗結(jié)果如圖所示,圖2(A是一個具有三層層次結(jié)構(gòu)的網(wǎng)絡(luò)灰度圖。最外層的社團(tuán)結(jié)構(gòu)由四個均包含256個結(jié)點的社團(tuán)組成,次外層由16個均包含64個節(jié)點組成的社團(tuán),最

20、里層由64個均包含16個結(jié)點組成的社團(tuán)來表示。圖2(B是層次網(wǎng)絡(luò)的實驗結(jié)果,圖釋分別表示K1-K2-K3-K4。試驗結(jié)果如圖2(B所示。在多數(shù)情況下,IHCD能準(zhǔn)備地顯示出三層體系結(jié)構(gòu):最內(nèi)層(包含64個社團(tuán)結(jié)構(gòu),次外層(包含16個社團(tuán)結(jié)構(gòu),第三層(包含4個社團(tuán)結(jié)構(gòu)。我們同樣發(fā)現(xiàn):隨著K1值減少,最里層節(jié)點間聯(lián)系變得較為松散。因此,IHCD難以準(zhǔn)確尋找64個社團(tuán)。特別地,當(dāng)K1=13時,IHCD迭代四次即可準(zhǔn)備找出三層社團(tuán)結(jié)構(gòu)。當(dāng)K1=5時,IHCD算法通過6次迭代過程顯示出其層次結(jié)構(gòu)。3.2實際網(wǎng)絡(luò)為驗證IHCD的有效性,我們使用經(jīng)常使用的一個典型的網(wǎng)絡(luò):空手道俱樂部5(Karate 俱樂部

21、網(wǎng)絡(luò)來進(jìn)行實驗,這個網(wǎng)絡(luò)是在社會網(wǎng)絡(luò)分析中經(jīng)常用到的一個經(jīng)典的具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)。它反應(yīng)了美國一所大學(xué)中空手道俱樂部成員之間的相互關(guān)系。20世紀(jì)70年代, Zachary通過對這個網(wǎng)絡(luò)的觀察,發(fā)現(xiàn)該俱樂部的主管和教練之間因是否應(yīng)該提高俱樂部的收費產(chǎn)生了分歧,結(jié)果該俱樂部形成了以主管和教練為中心的兩個社團(tuán)。如圖3所示,結(jié)點1和結(jié)點33分別代表主管和教練,方形和圓形分別代表了以主管和教練為中心的社團(tuán)。 (A(B圖3 (AKarate俱樂部網(wǎng)絡(luò);(B北美大學(xué)足球聯(lián)盟網(wǎng)絡(luò)實驗二是北美大學(xué)足球聯(lián)盟網(wǎng)絡(luò)5。其中包括115個結(jié)點,代表所有隊伍,隊伍間比賽用一條邊相連。在該網(wǎng)絡(luò)中,每個結(jié)點代表了北美2000年

22、橄欖球賽季的參加比賽的高校代表隊,連接兩個結(jié)點之間的邊則表示相應(yīng)的兩支球隊之間至少曾有過一場比賽。整個賽季被事先劃分成了12個區(qū)域(conferences,每個區(qū)域平均包含有10-12支球隊。被劃分在同中國科技論文在線 為如圖所示的 12 個社區(qū)。 一個區(qū)域內(nèi)的高校之間的常規(guī)賽要明顯多于區(qū)域之間的比賽， 因此， 該網(wǎng)絡(luò)很自然地被劃分 (A (B (C (D (E 圖 4 (A迭代次數(shù)與相應(yīng) Q 值衡量標(biāo)準(zhǔn)間關(guān)系的結(jié)果示意圖。 (B(C通過 Q 值局部最優(yōu)得到的 Karate 網(wǎng) 絡(luò)的兩層結(jié)構(gòu)。(D(E通過局部 Q 值最優(yōu)得到的兩層結(jié)構(gòu)的足球網(wǎng)絡(luò)圖。 兩實驗在 IHCD 算法經(jīng)過 7 次迭代運算

23、后結(jié)束。 我們使用較簡單的方式從諸多社團(tuán)劃分 中選擇有意義的層次社團(tuán)結(jié)構(gòu)。通過計算 Q 值，我們選擇局部 Q 值最優(yōu)解來得到有意義的 社團(tuán)結(jié)構(gòu)。圖 4（A）顯示不同次迭代劃分得到的社團(tuán)個數(shù)及其對應(yīng)的 Q 值。對 Karate 網(wǎng)絡(luò) 而言，在第六次迭代時得到最真實的社團(tuán)劃分結(jié)果（如圖 4（C）所示），這兩個社團(tuán)從更 低粒度可被進(jìn)一步劃分為 5 個社團(tuán)（如圖 4（B）所示），同樣的結(jié)果也在其他研究中被發(fā) 現(xiàn)59.對足球網(wǎng)絡(luò)而言，IHCD 在第三次迭代時將其劃分為 12 個社團(tuán)（如圖 4（D）所示。 同時，這些社團(tuán)可進(jìn)一步在第 6 次迭代后高粒度劃分為 5 個區(qū)（如圖 4（E）。對于這些 -6- 中

24、國科技論文在線 4 結(jié)論 真實網(wǎng)絡(luò)而言， IHCD 不僅能反正網(wǎng)絡(luò)的真實結(jié)構(gòu)， 同時能發(fā)現(xiàn)社團(tuán)間隱藏的其他真實情況。 本文給出了層次社團(tuán)發(fā)現(xiàn)算法 IHCD 的兩個主要過程。 第一階段是計算網(wǎng)絡(luò)相似性矩陣 并初始化各個節(jié)點自成社團(tuán)，第二階段即迭代地合并相似的社團(tuán)。在經(jīng)過一系列實驗后，我 們設(shè)計一個簡單并有效的方法來衡量社團(tuán)相似并決定合并條件。 對人工網(wǎng)絡(luò)的實驗結(jié)果表明 算法可以通過少量的迭代過程準(zhǔn)確地找到內(nèi)在的層次結(jié)構(gòu)， 對真實網(wǎng)絡(luò)的實驗結(jié)果表明算法 可以找到真實存在的社團(tuán)結(jié)構(gòu)， 并能找到其他有意義的層次結(jié)構(gòu)。 算法的相應(yīng)改進(jìn)策略包括 設(shè)計更合理的合并策略以及相似性計算， 包括其應(yīng)用于大規(guī)模網(wǎng)絡(luò)

25、， 這些均有待在今后進(jìn)一 步探討。 參考文獻(xiàn) (References 1 Barabasi, A.L. and R. Albert, Emergence of scaling in random networks, in Science. Department of Physics, University of Notre Dame, Notre Dame, 1999，46556, USA. p. 509-512. 2 Watts, D.J. and S.H. Strogatz. Collective Dynamics of Small-World Networks. Nature. 1998. p. 440-422. 3 Newman, M.E.J. The structure and function of complex networks. S