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

1、一種新的復(fù)雜網(wǎng)絡(luò)層次社團(tuán)發(fā)現(xiàn)算法張劍(北京郵電大學(xué)計(jì)算機(jī)學(xué)院,北京 100876摘要:網(wǎng)絡(luò)結(jié)構(gòu)廣泛存在于自然界和人們的現(xiàn)實(shí)生活之中,近來(lái)研究表明復(fù)雜網(wǎng)絡(luò)呈現(xiàn)出層次社團(tuán)結(jié)構(gòu),網(wǎng)絡(luò)中節(jié)點(diǎn)被分成社團(tuán),社團(tuán)又可以劃分成更小的社團(tuán),這些不同的層次劃分從不同維度展示復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特性。本文針對(duì)復(fù)雜網(wǎng)絡(luò)中的層次社團(tuán)結(jié)構(gòu)提出一種新的基于聚類(lèi)的層次社團(tuán)劃分算法,該算法通過(guò)有效合并策略能對(duì)不同規(guī)模的網(wǎng)絡(luò)進(jìn)行自適應(yīng)計(jì)算。人工和實(shí)際網(wǎng)絡(luò)的試驗(yàn)結(jié)果均表明:該算法能得到復(fù)雜網(wǎng)絡(luò)中合理的層次社團(tuán)劃分。關(guān)鍵詞:可能性矩陣;概率矩陣;層次結(jié)構(gòu);社團(tuán)發(fā)現(xiàn)中圖分類(lèi)號(hào):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引言隨著對(duì)實(shí)際網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和物理意義的深入研究,人們逐漸發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)除了典型的“無(wú)尺度”1,“小世界”2以及“高聚集系數(shù)”3等特征,現(xiàn)實(shí)世界中的網(wǎng)絡(luò)還具有第四個(gè)重要特性,即:存在“社區(qū)結(jié)構(gòu)”4或“社團(tuán)結(jié)構(gòu)”。更進(jìn)一步研究發(fā)現(xiàn),平面化的網(wǎng)絡(luò)社團(tuán)劃分并不能掩蓋實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)的非平面模塊結(jié)構(gòu):社團(tuán)是嵌套的,小社團(tuán)組成稍大社團(tuán),稍大社團(tuán)反過(guò)來(lái)組成更大社團(tuán),例如大公司組織架構(gòu),生物組織功能結(jié)構(gòu)等。在社團(tuán)發(fā)現(xiàn)基礎(chǔ)上引入層次結(jié)構(gòu),社團(tuán)結(jié)構(gòu)會(huì)更豐富,并能幫助分析研究人員更清楚地了解復(fù)雜系統(tǒng)的組織結(jié)構(gòu)特征。應(yīng)用于

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

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

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

9、得滿(mǎn)意結(jié)果。2 迭代層次社團(tuán)發(fā)現(xiàn)算法本章首先介紹算法中的相關(guān)函數(shù)定義,再介紹算法的詳細(xì)實(shí)現(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簡(jiǎn)單網(wǎng)絡(luò)圖;(B鄰接矩陣;(C相似性矩陣;(D概率矩陣如圖所示,圖1 (A由7個(gè)節(jié)點(diǎn)和10條邊組成的簡(jiǎn)單網(wǎng)絡(luò). 考慮節(jié)點(diǎn)1和5間的節(jié)點(diǎn)相似性(N1= 2, 3, 4, N5= 2, 6, 7,相似度為0.2;(B 圖A 所示網(wǎng)絡(luò)的鄰接矩陣. (C 圖A 相似性矩陣. 同時(shí)也是概率矩陣000,(,0.5,(,0.001,0.25PM MAX PM i j MIN PM i j =. 第一次迭代運(yùn)行結(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 相似性矩陣計(jì)算任意一對(duì)節(jié)點(diǎn)間相似性,用以構(gòu)造相似性矩陣。衡量節(jié)點(diǎn)間相似性的辦法很多,在經(jīng)過(guò)大量試驗(yàn)后,我們選擇了一個(gè)測(cè)量網(wǎng)絡(luò)拓?fù)渲丿B的基本方法678,將其定義為兩節(jié)點(diǎn)公有的鄰接點(diǎn)與兩節(jié)點(diǎn)所有的鄰接點(diǎn)的比值。這種衡量方法是在圖中較小的局部空間內(nèi)衡量節(jié)點(diǎn)間的相似度。 1(|,(|i j ij i j N N SM i j i j N N = 在節(jié)點(diǎn)相似度基本上構(gòu)造SM 矩陣,矩陣行列索引與節(jié)點(diǎn)編號(hào)一致?？紤]到節(jié)點(diǎn)i 的度可能通過(guò),i j K A i j =計(jì)算。|i

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

13、矩陣來(lái)衡量社團(tuán)間連接緊密程度,其算法主要包括以下兩個(gè)基本步驟:(i 根據(jù)鄰接矩陣計(jì)算相似性矩陣(ii 迭代合并連接度緊密的社團(tuán)結(jié)構(gòu)算法1是IHCD 的基本框架,通過(guò)每一次的迭代過(guò)程,我們都能得到一種社團(tuán)劃分,即相應(yīng)的層次結(jié)構(gòu)。概率矩陣是基于上次迭代后得到的社團(tuán)劃分結(jié)果以及相似性矩陣計(jì)算而來(lái)。整個(gè)過(guò)程結(jié)束的條件是所有節(jié)點(diǎn)處于同一社團(tuán)。IHCD 算法的關(guān)鍵在于社團(tuán)合并,在經(jīng)過(guò)大量試驗(yàn)和對(duì)比后我們發(fā)現(xiàn),采取一種自適應(yīng)的方式來(lái)合并社團(tuán)更有效。對(duì)于某種社團(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ì)描述,其過(guò)程可看作是算法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合并過(guò)程截止條件是所有節(jié)點(diǎn)劃歸到同一社團(tuán)。很顯然我們?cè)诿看蔚^(guò)程中能得到一種社團(tuán)結(jié)構(gòu)劃分,這種劃分也構(gòu)成了層次網(wǎng)絡(luò)的每一層。為了找出有意義的層次結(jié)構(gòu),我們需要較好地設(shè)計(jì)合并策略,對(duì)值的設(shè)計(jì)可以有很多種方式,最簡(jiǎn)單的方式是將值從0到1按0.1逐級(jí)遞增,將網(wǎng)絡(luò)從不同顆粒度逐級(jí)合并。這里我們?cè)O(shè)置值選取概率矩陣所有值的中間值,即最大與最小值求平均。試驗(yàn)結(jié)果表明這種社團(tuán)合并策略能達(dá)到最快的社團(tuán)層次收斂,并且能得到有意義的層次社團(tuán)結(jié)構(gòu),其它合并策略也可引用,將留作今后討論。 3 試驗(yàn)為了進(jìn)一步驗(yàn)證IHCD 實(shí)驗(yàn)效果,我們進(jìn)行了兩組試驗(yàn),包括人工網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)實(shí)驗(yàn),實(shí)驗(yàn)環(huán)境

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

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

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

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

22、橄欖球賽季的參加比賽的高校代表隊(duì),連接兩個(gè)結(jié)點(diǎn)之間的邊則表示相應(yīng)的兩支球隊(duì)之間至少曾有過(guò)一場(chǎng)比賽。整個(gè)賽季被事先劃分成了12個(gè)區(qū)域(conferences,每個(gè)區(qū)域平均包含有10-12支球隊(duì)。被劃分在同中國(guó)科技論文在線 為如圖所示的 12 個(gè)社區(qū)。 一個(gè)區(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通過(guò) Q 值局部最優(yōu)得到的 Karate 網(wǎng) 絡(luò)的兩層結(jié)構(gòu)。(D(E通過(guò)局部 Q 值最優(yōu)得到的兩層結(jié)構(gòu)的足球網(wǎng)絡(luò)圖。 兩實(shí)驗(yàn)在 IHCD 算法經(jīng)過(guò) 7 次迭代運(yùn)算

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

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