復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的研究畢業(yè)論文

1、<p>　　本科畢業(yè)設(shè)計(jì)（論文）</p><p>　　題目:復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的研究</p><p><b>　　姓名 </b></p><p>　　學(xué)院 信息與通信工程</p><p><b>　　專業(yè)</b></p><p><b>　　班級(jí)

2、 </b></p><p><b>　　學(xué)號(hào) </b></p><p><b>　　班內(nèi)序號(hào) </b></p><p><b>　　指導(dǎo)教師 </b></p><p>　　2012年6月復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的研究</p>&

3、lt;p><b>　　摘 要</b></p><p>　　近些年，隨著WS小世界網(wǎng)絡(luò)模型和BA無標(biāo)度網(wǎng)絡(luò)模型的提出，國內(nèi)外掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。復(fù)雜網(wǎng)絡(luò)是對(duì)于復(fù)雜系統(tǒng)的高度抽象，其中許多性質(zhì)如小世界性質(zhì)、無標(biāo)度性質(zhì)以及聚集性質(zhì)等等已經(jīng)得到了充分的研究。復(fù)雜網(wǎng)絡(luò)的研究是以系統(tǒng)的觀點(diǎn)來看待真實(shí)系統(tǒng)，如Internet網(wǎng)絡(luò)、電力網(wǎng)、新陳代謝網(wǎng)絡(luò)等。(大量的文獻(xiàn)表明，)復(fù)雜網(wǎng)絡(luò)通常會(huì)呈現(xiàn)出

4、社區(qū)結(jié)構(gòu)特性，而如何在實(shí)際網(wǎng)絡(luò)中高效地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)是近年來復(fù)雜網(wǎng)絡(luò)的研究熱點(diǎn)之一。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)普遍存在的拓?fù)涮匦灾?，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)也是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)性問題。</p><p>　　在文章中討論了一些復(fù)雜網(wǎng)絡(luò)以及關(guān)于社區(qū)評(píng)估和確定方面的概念、理論、算法及應(yīng)用等。同樣的，文章中也討論了一種可以應(yīng)用于大型復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)的random walk算法，并且顯示了它和其他算法在社團(tuán)劃分上有相同的表現(xiàn)，

5、同時(shí)擁有更低的復(fù)雜度。</p><p>　　文章中將random walk算法應(yīng)用于對(duì)已知社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)的劃分以及比較其劃分的社團(tuán)結(jié)構(gòu)的結(jié)果。除此之外，文章中對(duì)于此類算法給出一定改進(jìn)，使該算法在復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分上擁有了更高的準(zhǔn)確度以及較低的復(fù)雜度。</p><p>　　關(guān)鍵詞 復(fù)雜網(wǎng)絡(luò)，社團(tuán)發(fā)現(xiàn)算法，random walk，復(fù)雜度</p><p>　　Ve

6、rifying Platform of Cognitive Radio Network</p><p><b>　　ABSTRACT</b></p><p>　　In recent years，as the WS small-world network model and BA scale—free network model was proposed，the stu

7、dy on complex networks is achieving a climax at home and abroad now．Complex network is the highly abstract of the complex system, many of the properties, such as small world nature, scale-free property and gathered prope

8、rties and so on, have got fully research. The study on complex networks treats the real systems such as the Internet，electricity</p><p>　　networks and metabolic networks with the viewpoint of system science．

9、(Lots of literatures show that community structure exists in many real networks．How to find such communities effectively is one of focuses of many recent researches in the branch of complex networks．Community structure i

10、s one of the common topological characteristics of complex networks. Community detection has become a fundamental problem in the research field of complex networks.</p><p>　　In the article, the author discus

11、ses some complex networks as well as the theory, method and application about the evaluating and identifying of the community. Similarly,in this context we also discuss the "random walk" algorithm that can be

12、used in a large, complex network to identify the community and show that it performs as well as other methods at the division of complex networks, but at lower computational complexity.</p><p>　　In the artic

13、le the algorithm is applied to the division of complex networks that has knowing the community structure and compare the results of the classification of the community structure. In addition, the article gives certain im

14、provement to such algorithm, so that the algorithm in the community division of complex network has the higher accuracy and lower complexity.</p><p>　　KEYWORDS the complex network, community detection, rand

15、om walk, complexity目錄</p><p><b>　　第一章緒論1</b></p><p>　　1.1 復(fù)雜網(wǎng)絡(luò)的研究背景1</p><p>　　1.1.1 從七橋問題開始1</p><p>　　1.1.2 復(fù)雜網(wǎng)絡(luò)近代的研究2</p><p>　　1.2 復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)

16、構(gòu)研究的現(xiàn)狀3</p><p>　　1.3 本文的研究內(nèi)容以及文章結(jié)構(gòu)6</p><p>　　第二章復(fù)雜網(wǎng)絡(luò)的基本概念以及網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ?</p><p>　　2.1 復(fù)雜網(wǎng)絡(luò)的基本概念7</p><p>　　2.1.1 網(wǎng)絡(luò)的圖表示7</p><p>　　2.1.2 平均路徑長度8</p>

17、<p>　　2.1.3 聚類系數(shù)8</p><p>　　2.1.4 精準(zhǔn)度9</p><p>　　2.1.5 復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)定義9</p><p>　　2.2 網(wǎng)絡(luò)拓?fù)浠灸Ｐ秃托再|(zhì)10</p><p>　　2.2.1 小世界模型10</p><p>　　2.2.2 無標(biāo)度網(wǎng)絡(luò)模型11<

18、;/p><p>　　2.2.3 模塊性與等級(jí)網(wǎng)絡(luò)12</p><p>　　第三章 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu) 14</p><p>　　3.1 分級(jí)聚類14</p><p>　　3.1.1 凝聚算法14</p><p>　　3.1.2 分裂算法15</p><p>　　3.2 迭代二分法15&

19、lt;/p><p>　　3.2.1 Kernighan-Lin 算法15</p><p>　　3.2.2 譜平分法16</p><p>　　3.3 其他經(jīng)典算法17</p><p>　　3.3.1 GN（Girvan-Newman）算法17</p><p>　　3.3.2 Newman快速算法17</p&g

20、t;<p>　　3.3.3 Radicchi算法17</p><p>　　第四章 基于隨機(jī)游走的社團(tuán)發(fā)現(xiàn)算法19</p><p>　　4.1 隨機(jī)游走算法的基本原理19</p><p>　　4.1.1 隨機(jī)游走算法的相似度矩陣獲取19</p><p>　　4.1.2 隨機(jī)游走算法的矩陣融合20</p>&

21、lt;p>　　4.1.3 矩陣元素融合方式21</p><p>　　4.2 隨機(jī)游走算法的代碼編譯過程22</p><p>　　4.2.1 隨機(jī)游走算法的相似度矩陣的獲取22</p><p>　　4.2.2 隨機(jī)游走算法的相似度矩陣融合23</p><p>　　第五章 隨機(jī)游走算法在社團(tuán)劃分中的應(yīng)用25</p>

22、<p>　　5.1 隨機(jī)游走算法對(duì)復(fù)雜網(wǎng)絡(luò)的劃分25</p><p>　　5.1.1 已知社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)25</p><p>　　5.1.2 對(duì)復(fù)雜網(wǎng)絡(luò)的劃分26</p><p>　　5.2 隨機(jī)游走算法的復(fù)雜度28</p><p>　　第六章 基于隨機(jī)游走算法的程序優(yōu)化29</p><p>　

23、　6.1 隨機(jī)游走算法的復(fù)雜度的優(yōu)化29</p><p>　　6.2 隨機(jī)游走算法的應(yīng)用于加權(quán)網(wǎng)絡(luò)30</p><p>　　第七章總結(jié)與展望31</p><p><b>　　7.1 總結(jié)31</b></p><p>　　7.2 對(duì)未來的展望31</p><p><b>　　參考

24、文獻(xiàn)34</b></p><p><b>　　致謝35</b></p><p><b>　　第一章 緒 論</b></p><p>　　復(fù)雜網(wǎng)絡(luò)一般指節(jié)點(diǎn)眾多、連接關(guān)系復(fù)雜的網(wǎng)絡(luò)。由于其靈活普適的描述能力, 能夠廣泛應(yīng)用于各科學(xué)領(lǐng)域?qū)?fù)雜系統(tǒng)進(jìn)行建模、分析, 近年來吸引了越來越多的人對(duì)其進(jìn)行研究。隨著研究

25、的深入, 人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)均具有社團(tuán)結(jié)構(gòu),即整個(gè)網(wǎng)絡(luò)由若干個(gè)社團(tuán)組成, 社團(tuán)之間的連接相對(duì)稀疏、社團(tuán)內(nèi)部的連接相對(duì)稠密。社團(tuán)發(fā)現(xiàn)則是利用圖拓?fù)浣Y(jié)構(gòu)中所蘊(yùn)藏的信息從復(fù)雜網(wǎng)絡(luò)中解析出其模塊化的社團(tuán)結(jié)構(gòu), 該問題的深入研究有助于以一種分而治之的方式研究整個(gè)網(wǎng)絡(luò)的模塊、功能及其演化, 更準(zhǔn)確地理解復(fù)雜系統(tǒng)的組織原則、拓?fù)浣Y(jié)構(gòu)與動(dòng)力學(xué)特性, 具有十分重要的意義。</p><p>　　自2002 年Girvan 和New

26、man 基于邊介數(shù)提出GN 算法以來, 國際上掀起一股社團(tuán)發(fā)現(xiàn)的研究熱潮, 來自生物、物理、計(jì)算機(jī)等各學(xué)科領(lǐng)域的研究者們帶來了許多新穎的思想和算法, 并廣泛應(yīng)用于各個(gè)學(xué)科領(lǐng)域的具體問題中。</p><p>　　1.1復(fù)雜網(wǎng)絡(luò)研究背景</p><p>　　1.1.1 從七橋問題開始</p><p>　　近年來復(fù)雜網(wǎng)絡(luò)研究的興起，使得人們開始廣泛關(guān)注網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性及其與

27、網(wǎng)絡(luò)行為之間的關(guān)系，要研究各種不同的復(fù)雜網(wǎng)絡(luò)在結(jié)構(gòu)上的共性，首先需要有一種描述網(wǎng)絡(luò)的統(tǒng)一工具。這種工具在數(shù)學(xué)上成為圖(graph).任何一個(gè)網(wǎng)絡(luò)都可以看做是由一些節(jié)點(diǎn)按某種方式連接而構(gòu)成的一個(gè)系統(tǒng)。具體網(wǎng)絡(luò)的抽象圖表示，就是用抽象的點(diǎn)表示具體網(wǎng)絡(luò)中的節(jié)點(diǎn)，并用節(jié)點(diǎn)之間的連線表示具體網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接關(guān)系。</p><p>　　實(shí)際網(wǎng)絡(luò)的圖表示法可以追溯到18世紀(jì)偉大的數(shù)學(xué)家歐拉(Euler)對(duì)著名的“Konigs

28、berg 七橋問題”的研究。Konigsberg 是東普魯士（現(xiàn)俄羅斯）的一個(gè)城鎮(zhèn)，城中有一條橫貫城區(qū)的河流，河中有兩座島，兩岸和兩島間共有七座橋，一個(gè)人能否在一次散步中走過所有的七座橋，而且每座橋只經(jīng)過一次，最后返回原地？</p><p>　　1736年，歐拉仔細(xì)的研究了這個(gè)問題。他用數(shù)學(xué)抽象法，將被河流分隔開的四塊陸地抽象為四個(gè)點(diǎn)，分別用A、B、C和D表示，而將七座橋抽象為連接四個(gè)點(diǎn)的七條線，分別用a、b、c

29、、d、e、f、g表示，這樣就得到了四個(gè)點(diǎn)和七條線構(gòu)成的一個(gè)圖，如圖（圖1-1）所示。</p><p><b>　　圖1-1 七橋問題</b></p><p>　　于是歐拉考慮如果一筆畫出圖1-1，則七橋問題迎刃而解?？梢韵胂?，能一筆畫出的圖形，一定只有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)（這里要求起點(diǎn)和終點(diǎn)重合），中間經(jīng)過的每一點(diǎn)總是包含進(jìn)去的一條線和出去的一條線，這樣除了終點(diǎn)和起點(diǎn)外

30、，每一點(diǎn)都只能有偶數(shù)條線與之相連。因此，如果要求起點(diǎn)和終點(diǎn)重合的話，那么能夠一筆畫出的圖形中所有的點(diǎn)都必然有偶數(shù)條線與之相連。從圖1-1中四個(gè)點(diǎn)看，每個(gè)點(diǎn)都是有三條或五條線通過，所以不能一筆畫出這個(gè)圖形，就是說不重復(fù)的一次走遍七座橋是據(jù)對(duì)不可能的。</p><p>　　歐拉的七橋問題的抽象和論證思想，開創(chuàng)了數(shù)學(xué)中的一個(gè)分支----圖論（graph theory）的研究。因此，歐拉被公認(rèn)為圖論只父，而圖1-1被稱為

31、歐拉圖。事實(shí)上，今天人們關(guān)于復(fù)雜網(wǎng)絡(luò)的研究與歐拉當(dāng)年關(guān)于七橋問題的研究在某種程度上是一脈相承的，即網(wǎng)絡(luò)結(jié)構(gòu)域網(wǎng)絡(luò)心智密切相關(guān)。</p><p>　　1.1.2 復(fù)雜網(wǎng)絡(luò)近代的研究</p><p>　　20世紀(jì)90年代以來，以Internet為代表的信息技術(shù)的迅猛發(fā)展使人類社會(huì)大步邁入了網(wǎng)絡(luò)時(shí)代。從Internet到WWW，從大型電力網(wǎng)絡(luò)到全球交通網(wǎng)絡(luò)，從生物體中的大腦到各種新陳代謝網(wǎng)絡(luò)，從

32、科研合作網(wǎng)絡(luò)到各種經(jīng)濟(jì)、政治和社會(huì)關(guān)系網(wǎng)絡(luò)等，可以說；人們已經(jīng)生活在一個(gè)充滿著各種各樣的復(fù)雜網(wǎng)絡(luò)的世界中。人類社會(huì)的網(wǎng)絡(luò)化是一把“雙刃劍”：它既給人類社會(huì)生產(chǎn)與生活帶來了極大便利，提高了人類生產(chǎn)效率和生活質(zhì)量，但也給人類社會(huì)生活帶來了一定的負(fù)面沖擊，如傳染病和計(jì)算機(jī)病毒的快速傳播以及大規(guī)模的停電事故等。因此，人類社會(huì)的日益網(wǎng)絡(luò)化需要人類對(duì)各種人工和自然的復(fù)雜網(wǎng)絡(luò)的行為有更好的認(rèn)識(shí)。</p><p>　　長期以來，

33、通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)等分別是通信科學(xué)、電力科學(xué)、生命科學(xué)、社會(huì)學(xué)等不同學(xué)科的研究對(duì)象，而復(fù)雜網(wǎng)絡(luò)理論所要研究的則是各種看上去互不相同的復(fù)雜網(wǎng)絡(luò)之間的共性和處理它們的普適方法。從20世紀(jì)末開始，復(fù)雜網(wǎng)絡(luò)研究正滲透到數(shù)理學(xué)科、生命學(xué)科和工程學(xué)科等眾多不同的領(lǐng)域，對(duì)復(fù)雜網(wǎng)絡(luò)的定量與定性特征的科學(xué)理解，已成為網(wǎng)絡(luò)時(shí)代科學(xué)研究的一個(gè)極其重要的挑戰(zhàn)性課題，甚至被稱為“網(wǎng)絡(luò)的新科學(xué)(new science of networks)”

34、[1,2] 。</p><p>　　傳歐拉七橋問題之后的近兩百年中，數(shù)學(xué)家們一直致力于對(duì)簡單的規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)進(jìn)行抽象的數(shù)學(xué)研究。隨著近年來計(jì)算機(jī)存儲(chǔ)能力和處理數(shù)據(jù)能力的增強(qiáng)，以及一些大規(guī)模系統(tǒng)的數(shù)據(jù)庫的建立，人們重新獲得了真實(shí)網(wǎng)絡(luò)的特征數(shù)據(jù)，發(fā)現(xiàn)大多數(shù)真實(shí)網(wǎng)絡(luò)既不是規(guī)則的，也不是隨機(jī)的，而是呈現(xiàn)一定規(guī)律的復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)之所以復(fù)雜，不僅在于網(wǎng)絡(luò)規(guī)模的巨大，網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜而且網(wǎng)絡(luò)在時(shí)間、空間上都具有動(dòng)態(tài)的復(fù)雜

35、性，網(wǎng)絡(luò)行為也具有復(fù)雜性。</p><p>　　許多真實(shí)系統(tǒng)都可以用網(wǎng)絡(luò)的形式加以描述，一個(gè)典型的網(wǎng)絡(luò)是由許多結(jié)點(diǎn)與連接結(jié)點(diǎn)之間的邊組成的。結(jié)點(diǎn)代表系統(tǒng)中的個(gè)體，邊則表示結(jié)點(diǎn)之間的作用關(guān)系。如WWW網(wǎng)絡(luò)可以看成是網(wǎng)頁之間通過超鏈接構(gòu)成的網(wǎng)絡(luò)；Internet網(wǎng)絡(luò)可以看作不同的計(jì)算機(jī)通過光纜連接構(gòu)成的網(wǎng)絡(luò)；科學(xué)家合作網(wǎng)絡(luò)可以看作不同的科學(xué)家合作關(guān)系構(gòu)成的網(wǎng)絡(luò)；基因調(diào)控網(wǎng)絡(luò)可以看作是不同的基因通過調(diào)控與被調(diào)控關(guān)系構(gòu)成

36、的網(wǎng)絡(luò)。</p><p>　　這些真實(shí)網(wǎng)絡(luò)的普遍存在，促使來自不同學(xué)科領(lǐng)域的科學(xué)家共同致力于復(fù)雜網(wǎng)絡(luò)的研究。這些學(xué)科領(lǐng)域包括復(fù)雜性科學(xué)、數(shù)學(xué)、物理、生物和計(jì)算機(jī)等。復(fù)雜網(wǎng)絡(luò)的研究可以使人們更好地了解現(xiàn)實(shí)世界的復(fù)雜系統(tǒng)，為設(shè)計(jì)具有良好性能的網(wǎng)絡(luò)提供依據(jù)。同時(shí)復(fù)雜網(wǎng)絡(luò)的理論成果將會(huì)廣泛地應(yīng)用到生物、計(jì)算機(jī)等各個(gè)學(xué)科領(lǐng)域。</p><p>　　復(fù)雜網(wǎng)絡(luò)的研究大致可以描述為三個(gè)密切相關(guān)但又依次深入

37、的方面：大量的真實(shí)網(wǎng)絡(luò)的實(shí)證研究，分析真實(shí)網(wǎng)絡(luò)的統(tǒng)計(jì)特性；構(gòu)建符合真實(shí)網(wǎng)絡(luò)統(tǒng)計(jì)性質(zhì)的網(wǎng)絡(luò)演化模型，研究網(wǎng)絡(luò)的形成機(jī)制和內(nèi)在機(jī)理；研究網(wǎng)絡(luò)上的動(dòng)力學(xué)行為，如網(wǎng)絡(luò)的魯棒性和同步能力，網(wǎng)絡(luò)的擁塞及網(wǎng)絡(luò)上的傳播行為等。</p><p>　　1967年，美國哈佛大學(xué)社會(huì)心里學(xué)家Milgram做了一個(gè)實(shí)驗(yàn)，在美國將一封信通過熟人找熟人的方式傳遞到目標(biāo)者，發(fā)現(xiàn)平均最短經(jīng)過6人就可到達(dá)，這就是著名的“六度分離(six degre

38、e of separation)”現(xiàn)象，它揭示了社會(huì)網(wǎng)絡(luò)的小世界特性。而在萬維網(wǎng)中，平均只需點(diǎn)擊19次超級(jí)鏈接，就可以從任意一個(gè)網(wǎng)頁到達(dá)其它網(wǎng)頁。</p><p>　　近年來，隨著大型數(shù)據(jù)庫的建立和計(jì)算機(jī)存儲(chǔ)與運(yùn)算能力的迅速提高，復(fù)雜網(wǎng)絡(luò)的研究進(jìn)程大大加快。人們對(duì)社會(huì)系統(tǒng)、大型基礎(chǔ)性設(shè)施和生物系統(tǒng)中大量的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)庫進(jìn)行了系統(tǒng)的分析，尋找呈現(xiàn)表象的內(nèi)在機(jī)制和模式，試圖發(fā)現(xiàn)支配和影響這些復(fù)雜系統(tǒng)的動(dòng)力學(xué)和演化規(guī)律

39、的內(nèi)在本質(zhì)。復(fù)雜網(wǎng)絡(luò)的理論及實(shí)證研究的發(fā)展將會(huì)對(duì)網(wǎng)絡(luò)安全、網(wǎng)絡(luò)控制、疾病傳播的控制與防御、社會(huì)中人的行為動(dòng)力學(xué)的研究和生物網(wǎng)絡(luò)的演化機(jī)制研究等產(chǎn)生重要影響。</p><p>　　1.2 復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)研究的現(xiàn)狀</p><p>　　隨著對(duì)網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同性質(zhì)，即社區(qū)結(jié)構(gòu)。也就是說，整個(gè)網(wǎng)絡(luò)是由若干個(gè)“社區(qū)"或“組’’構(gòu)成

40、的。每個(gè)社區(qū)內(nèi)部的結(jié)點(diǎn)間的連接相對(duì)非常緊密，但是各個(gè)社區(qū)之間的連接相對(duì)來說卻比較稀疏。揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，對(duì)于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性是很重要的。如社會(huì)網(wǎng)絡(luò)中的社區(qū)代表根據(jù)興趣和背景而形成的真實(shí)的社會(huì)團(tuán)體；引文網(wǎng)絡(luò)中的社區(qū)代表針對(duì)同一主題的相關(guān)論文；萬維網(wǎng)中的社區(qū)就是討論相關(guān)主題的若干網(wǎng)站；而生物化學(xué)網(wǎng)絡(luò)或者電子電路中的網(wǎng)絡(luò)社區(qū)可以是某一類功能單元。發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社區(qū)有助于我們更加有效地理解和開發(fā)這些網(wǎng)絡(luò)。</p>

41、<p>　　在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的研究中，社區(qū)結(jié)構(gòu)劃分算法所要?jiǎng)澐值木W(wǎng)絡(luò)大致可分為兩類，一類是比較常見的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)(網(wǎng)絡(luò)中邊的權(quán)值為正實(shí)數(shù))；另一類是符號(hào)社會(huì)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負(fù)向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法相應(yīng)分為兩大類，而對(duì)于第一類網(wǎng)絡(luò)又提出了許多不同的社區(qū)結(jié)構(gòu)劃分算法，劃分第一類網(wǎng)絡(luò)社區(qū)的傳統(tǒng)算法可分為兩大類，第一類是基于圖論的算法，比如K—L算法、譜平分法、隨機(jī)游走算

42、法和派系過濾等；第二類是層次聚類算法，比如基于相似度度量的凝聚算法和基于邊介數(shù)度量的分裂算法等。最近幾年從其他不同的角度又提出了許多劃分第一類網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法，大致可劃分如下：基于電阻網(wǎng)絡(luò)性質(zhì)的算法、基于信息論的算法、基于PCA的算法和最大化模塊度算法等。下面簡要介紹一下幾種具有代表性的算法。</p><p>　　1970年，Kernighan和Lin提出一種試探優(yōu)化法劃分網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，簡稱K-L算法。它是

43、一種基于貪婪算法原理將網(wǎng)絡(luò)劃分為兩個(gè)大小已知的社區(qū)的二分法。其基本思想是為網(wǎng)絡(luò)的劃分引進(jìn)一個(gè)增益函數(shù)Q，增益函數(shù)定義為兩個(gè)社區(qū)內(nèi)部的邊數(shù)減去連接兩個(gè)社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。1990年，Pothen等基于圖的Laplace矩陣的譜特征提出一種將網(wǎng)絡(luò)劃分為兩個(gè)社區(qū)的二分法瞻目。該算法的理論基礎(chǔ)是不為零的特征值所對(duì)應(yīng)的特征向量的各元素中，同一個(gè)社區(qū)內(nèi)的結(jié)點(diǎn)對(duì)應(yīng)的元素是近似相等的。因此可以根據(jù)網(wǎng)絡(luò)的Laplace矩陣的第二

44、小特征值將其分為兩個(gè)社區(qū)。2001年，Girvan和Newman提出了一種基于邊介數(shù)的分裂算法，簡稱GN算法。該算法的基本思想是不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊。邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過每條邊的最短路徑數(shù)目。該算法的復(fù)雜度非常高，2003年Tyler等在GN算法的基礎(chǔ)上提出了一種新的算法圓1，它可以顯著提高計(jì)算速度，但也降低了計(jì)算的準(zhǔn)確性。GN算法是以網(wǎng)絡(luò)中的每一個(gè)結(jié)點(diǎn)i為源結(jié)點(diǎn)，來計(jì)算它到其他結(jié)點(diǎn)的最短路徑，并以這些最短路徑經(jīng)過每條邊的

45、次數(shù)作為該邊的介數(shù)。而</p><p>　　2003年，Wu和Huberman基于電阻網(wǎng)絡(luò)的性質(zhì)提出了W_H算法，其主要思路為將網(wǎng)絡(luò)中每條邊想象成電阻為單位值的導(dǎo)線，且在網(wǎng)絡(luò)中任意選擇的兩個(gè)結(jié)點(diǎn)上加上單位值的電位差。Wu和Huberman認(rèn)為，如果網(wǎng)絡(luò)可以分解成兩個(gè)社區(qū)，那么電位譜在連接兩個(gè)社區(qū)的邊的兩端會(huì)產(chǎn)生一個(gè)較大的間隙。因此，首先確定電位譜的最大間隙處的某個(gè)電位值，然后根據(jù)每個(gè)結(jié)點(diǎn)處的電位是否大于該值而確定

46、結(jié)點(diǎn)屬于哪個(gè)社區(qū)。該算法的一個(gè)重要特點(diǎn)是可以用來確定包含指定結(jié)點(diǎn)的社區(qū)，而無須計(jì)算出所有的社區(qū)。2004年，Newman提出一種基于貪婪法思想的凝聚算法，并稱這種算法為快速算法。該算法是在使得模塊度不斷增加的基礎(chǔ)上進(jìn)行，即每次合并沿著使模塊度增多最大和減小最少的方向進(jìn)行。算法總的復(fù)雜度為O((m+n)n)，對(duì)于稀疏網(wǎng)絡(luò)則為O()，其中n為網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù)，m為網(wǎng)絡(luò)中邊的條數(shù)。在Newman快速算法的基礎(chǔ)上，Clauset、Newman

47、和Moore等人采用堆的數(shù)據(jù)結(jié)構(gòu)來計(jì)算和更新網(wǎng)絡(luò)的模塊度，提出了一種新的貪婪算法，稱為CNM算法。該算法的復(fù)雜度只有O(n)，已接近線性復(fù)雜性，可用來分析大型復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)。同樣為了最大化網(wǎng)</p><p>　　2005年，Pons和Latapy提出一種利用隨機(jī)游走劃分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法，算法的初始條件為每個(gè)結(jié)點(diǎn)為一個(gè)單獨(dú)的社區(qū)，然后逐步合并可使結(jié)點(diǎn)和它所在社區(qū)之間的平方距離均值達(dá)到最小的兩個(gè)社區(qū)。每一步都要更新社

48、區(qū)之間的距離，其中兩個(gè)結(jié)點(diǎn)之間的距離對(duì)應(yīng)于它們的相似度，即在一個(gè)離散的隨機(jī)游走過程中，它們之間的方向轉(zhuǎn)移概率。</p><p>　　以上所述算法最終目的均是把網(wǎng)絡(luò)劃分為若干個(gè)相互分離的社區(qū)，但是現(xiàn)實(shí)中很多網(wǎng)絡(luò)并不存在絕對(duì)的彼此獨(dú)立的社區(qū)結(jié)構(gòu)，相反它們是由許多彼此重疊且相互關(guān)聯(lián)的社區(qū)構(gòu)成。比如，每個(gè)人根據(jù)不同的分類方法都會(huì)屬于多個(gè)不同的社區(qū)(如學(xué)校、家庭、不同的興趣小組等)。在這種情況下，很難單獨(dú)的將這些社區(qū)劃分出

49、來。因此，Palla等人提出了一種派系過濾算法(clique Percolation Method)來分析這種互相重疊的社區(qū)結(jié)構(gòu)。盡管復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題得到了大量的研究，但還存在一些尚未解決的基本問題，如社區(qū)概念雖然大量使用，但卻缺少嚴(yán)格的數(shù)學(xué)定義；大多數(shù)社區(qū)發(fā)現(xiàn)算法雖然性能優(yōu)越，但所需計(jì)算量卻很大。這說明復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的研究還需要付出大量的努力。</p><p>　　1.3本文的研究內(nèi)容以及文章結(jié)構(gòu)&

50、lt;/p><p>　　本課題主要研究復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)劃分。首先，針對(duì)無權(quán)的復(fù)雜網(wǎng)絡(luò)，提出了隨機(jī)游走的概念，在此基礎(chǔ)上提出一種有效的劃分社區(qū)結(jié)構(gòu)的算法。實(shí)驗(yàn)結(jié)果表明該算法是可行且有效的。最后把這種算法推廣到加權(quán)的大型復(fù)雜網(wǎng)絡(luò)中，并把算法應(yīng)用實(shí)際的加權(quán)網(wǎng)絡(luò)數(shù)據(jù)中，驗(yàn)證了推廣算法的可行性和有效性。綜上所述，本文主要研究內(nèi)容共分為兩個(gè)部分：第一部分提出了一種基于隨機(jī)游走的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法；第二部分把此算法推廣到

51、加權(quán)的復(fù)雜網(wǎng)絡(luò)中。具體內(nèi)容如下：</p><p>　　介紹了一些復(fù)雜網(wǎng)絡(luò)的圖表示、度分布、平均最短路徑和社區(qū)結(jié)構(gòu)等基本概念和基本性質(zhì)。介紹一些基本的網(wǎng)絡(luò)拓?fù)淠Ｐ图捌湫再|(zhì)，包括規(guī)則網(wǎng)絡(luò)、隨機(jī)圖、小世界網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)等。</p><p>　　主要針對(duì)Internet 中的拓?fù)浣Y(jié)構(gòu)提出來一些模型。介紹復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)及其搜索算法。大多數(shù)的實(shí)際網(wǎng)絡(luò)都具有社團(tuán)結(jié)構(gòu)。也就是說，一個(gè)大的網(wǎng)絡(luò)可以分成

52、若干個(gè)字裙，在這些子群的內(nèi)部的連接較為緊密，但是各個(gè)子群間的連接卻較為稀疏。找到并且分析這些子群，有助于我們更好地理解網(wǎng)絡(luò)的全局行為</p><p>　　主要提出了基于圖論的隨機(jī)游走（random walk）算法，研究隨機(jī)游走算法的基本原理，以及對(duì)隨機(jī)游走算法的編譯。</p><p>　　主要介紹了random walk 算法對(duì)已知社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)的劃分，并比較劃分社團(tuán)結(jié)構(gòu)的

53、準(zhǔn)確度；同時(shí)給出算法的復(fù)雜度的分析。</p><p>　　主要介紹了在random walk算法基礎(chǔ)上的改進(jìn)，使random walk算法能夠?qū)崿F(xiàn)：對(duì)有權(quán)的復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的劃分；減少算法的復(fù)雜度。</p><p>　　第二章 復(fù)雜網(wǎng)絡(luò)的基本概念以及網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ?lt;/p><p>　　2.1復(fù)雜網(wǎng)絡(luò)的基本概念</p><p>　　近年來

54、，人們在刻畫復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性上提出了許多概念和方法，其中有三個(gè)基本的概念：平均路徑長度（average path length）、聚類系數(shù)（clustering coefficient）和度分布（degree distribution）。實(shí)際上，Watts和Strogatz提出小世界網(wǎng)絡(luò)模型的初衷就是建立一個(gè)既具有類似于隨機(jī)圖的較少的平均路徑長度，又具有類似于規(guī)則網(wǎng)絡(luò)的較大的聚類系數(shù)的網(wǎng)絡(luò)模型。另一方面，Barabasi和Albert

55、 提出的無標(biāo)度網(wǎng)絡(luò)模型，則是基于許多實(shí)際網(wǎng)絡(luò)的度分布具有冪律(power-law)形式的事實(shí)。在這里先介紹復(fù)雜網(wǎng)絡(luò)的這幾種性質(zhì)，其他性質(zhì)后面會(huì)陸續(xù)介紹。</p><p>　　2.1.1網(wǎng)絡(luò)的圖表示</p><p>　　一個(gè)具體網(wǎng)絡(luò)可以抽象為一個(gè)由點(diǎn)集V和邊集E組成的圖G =（V，E）。節(jié)點(diǎn)數(shù)記為N = | V |，邊數(shù)記為M = | E |。E中每條邊都有V種的一堆點(diǎn)與之相對(duì)應(yīng)。如果任意點(diǎn)

56、對(duì)（i，j）和（j，i）對(duì)應(yīng)同一條邊，則該網(wǎng)絡(luò)稱為無向網(wǎng)絡(luò)（），否則稱為有向網(wǎng)絡(luò)。如果給沒調(diào)表都賦予相應(yīng)的權(quán)值，那么該網(wǎng)絡(luò)就被稱為加權(quán)網(wǎng)絡(luò)（），否則為無權(quán)網(wǎng)絡(luò)。當(dāng)然無權(quán)網(wǎng)絡(luò)也可以看做每條邊權(quán)值都為1的等權(quán)網(wǎng)絡(luò)。此外，一個(gè)網(wǎng)絡(luò)中還可能包含多種不同類型的節(jié)點(diǎn)。圖2-1給出了幾種不同類型的網(wǎng)絡(luò)的例子。在圖論中，沒有重邊</p><p>　　和自環(huán)的圖稱為簡單圖（simple graph）[4] 。</p>

57、<p>　　圖2-1 不同類型網(wǎng)絡(luò)的例子</p><p>　　單一類型節(jié)點(diǎn)和邊的無向網(wǎng)絡(luò) (b)不同類型節(jié)點(diǎn)和邊的無向網(wǎng)絡(luò)</p><p>　　(c)節(jié)點(diǎn)和邊權(quán)重變化的無向網(wǎng)絡(luò) (d)有向網(wǎng)絡(luò)</p><p>　　2.1.2 平均路徑長度</p><p>　　網(wǎng)絡(luò)研究中一般定義兩節(jié)點(diǎn)i和j間的距離為連接兩個(gè)節(jié)點(diǎn)的最短路徑的邊

58、數(shù)，網(wǎng)絡(luò)的直徑為任意兩點(diǎn)間的距離的最大值，記為D，即</p><p><b>　　（2-1）</b></p><p>　　網(wǎng)絡(luò)的平均路徑長度L則定義為任意兩個(gè)節(jié)點(diǎn)對(duì)之間距離的平均值，即</p><p><b>　　（2-2）</b></p><p>　　其中N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。網(wǎng)絡(luò)的平均路徑長度也成為網(wǎng)

59、絡(luò)的特征路徑長度（characteristic path length）。它描述了網(wǎng)絡(luò)中節(jié)點(diǎn)間的分離程度，即網(wǎng)絡(luò)有多小。復(fù)雜網(wǎng)絡(luò)研究中一個(gè)重要的發(fā)現(xiàn)是絕大多數(shù)大規(guī)模真實(shí)網(wǎng)絡(luò)的平均路徑長度比想象的小得多，稱之為“小世界效應(yīng)”這一提法來源于著名的Milgram“小世界”試驗(yàn)[4] 。</p><p>　　圖2-2 一個(gè)簡單網(wǎng)絡(luò)的直徑和平局路徑長度</p><p>　　2.1.3 聚類系數(shù)<

60、;/p><p>　　聚集系數(shù)C用來描述網(wǎng)絡(luò)中節(jié)點(diǎn)的聚集情況，即網(wǎng)絡(luò)有多緊密。比如在社會(huì)網(wǎng)絡(luò)中，你朋友的朋友可能也是你的朋友或者你的兩個(gè)朋友可能彼此也是朋友。一般的，假設(shè)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i有條邊將他和其他節(jié)點(diǎn)相連，這個(gè)節(jié)點(diǎn)就稱為節(jié)點(diǎn)i的鄰居。顯然，在這個(gè)節(jié)點(diǎn)之間最多可能有(-1)/2條邊。而這個(gè)節(jié)點(diǎn)間的實(shí)際存在的邊數(shù)為和總的可能的邊數(shù)(-1)/2之比就定義為節(jié)點(diǎn)i的聚類系數(shù)，即</p><p>

61、<b>　?。?-3）</b></p><p>　　從幾何特點(diǎn)上看，上式的一個(gè)等價(jià)定義為</p><p><b>　?。?-4）</b></p><p>　　其中，與節(jié)點(diǎn)i相連的三元組是指包括節(jié)點(diǎn)i的三個(gè)節(jié)點(diǎn)，并且至少存在從節(jié)點(diǎn)i到其他兩個(gè)節(jié)點(diǎn)的兩條邊（圖2-3）。[5]</p><p>　　圖2-

62、3 以節(jié)點(diǎn)i為頂點(diǎn)之一的三元組的兩種可能形式</p><p><b>　　2.1.4 精準(zhǔn)度</b></p><p>　　精準(zhǔn)度是用來粗略的衡量社團(tuán)發(fā)現(xiàn)算法對(duì)于劃分復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的準(zhǔn)確度的參數(shù)。以上所述算法最終目的均是把網(wǎng)絡(luò)劃分為若干個(gè)相互分離的社區(qū)，但是現(xiàn)實(shí)中很多網(wǎng)絡(luò)并不存在絕對(duì)的彼此獨(dú)立的社區(qū)結(jié)構(gòu)，相反它們是由許多彼此重疊且相互關(guān)聯(lián)的社區(qū)構(gòu)成。給定一個(gè)由n個(gè)節(jié)

63、點(diǎn)組成的復(fù)雜網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)v都賦予一個(gè)真實(shí)的標(biāo)簽來表示其屬于的社團(tuán)。對(duì)于社團(tuán)劃分的準(zhǔn)確的計(jì)算如下所示，假設(shè)一個(gè)復(fù)雜網(wǎng)絡(luò)已經(jīng)分成數(shù)個(gè)社團(tuán)，對(duì)于每個(gè)社團(tuán)i，遍歷i中所有的節(jié)點(diǎn)并找出每個(gè)節(jié)點(diǎn)最常發(fā)生的真實(shí)的標(biāo)簽，這個(gè)標(biāo)簽便被稱作社團(tuán)中節(jié)點(diǎn)v的預(yù)期的標(biāo)簽。而精確度的公式也如下所示：</p><p><b>　　（2-6）</b></p><p><b>　　其中

64、</b></p><p><b>　?。?-7）</b></p><p>　　2.1.5 復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)定義</p><p>　　近幾年來，復(fù)雜網(wǎng)絡(luò)的研究正處于蓬勃發(fā)展的階段，其思想已經(jīng)充斥到科學(xué)和社會(huì)</p><p>　　的每一個(gè)角落。隨著對(duì)網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實(shí)際<

65、/p><p>　　網(wǎng)絡(luò)都具有一個(gè)共同性質(zhì)——社團(tuán)結(jié)構(gòu)。也就是說，網(wǎng)絡(luò)是由若干個(gè)“群(Group)"或“團(tuán)(Cluster)”構(gòu)成的。每個(gè)群內(nèi)的結(jié)點(diǎn)之間的連接非常緊密，而群之間的連接卻相對(duì)比較稀疏，如圖2-4所示。圖中的空手道俱樂部網(wǎng)絡(luò)包含兩個(gè)社團(tuán)，分別對(duì)應(yīng)圖中不同節(jié)點(diǎn)形狀的部分。在這些社區(qū)內(nèi)部，結(jié)點(diǎn)之間的聯(lián)系非常緊密，而社區(qū)之間的聯(lián)系就稀疏的多。</p><p>　　圖2-4 空手道

66、俱樂部復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)</p><p>　　2.2網(wǎng)絡(luò)拓?fù)浠灸Ｐ秃托再|(zhì)</p><p>　　最簡單的網(wǎng)絡(luò)模型為規(guī)則網(wǎng)絡(luò)，其特點(diǎn)是每個(gè)節(jié)點(diǎn)的近鄰數(shù)目都相同，如一維鏈、二維晶格、完全圖等。隨機(jī)網(wǎng)絡(luò)模型的提出是網(wǎng)絡(luò)研究中的重大成果，但它仍不能很好的刻畫實(shí)際網(wǎng)絡(luò)的性質(zhì)，人們又相繼提出了一些新的網(wǎng)絡(luò)模型。</p><p>　　2.2.1 小世界模型</p>

67、<p>　　實(shí)證結(jié)果表明，大多數(shù)的真實(shí)網(wǎng)絡(luò)具有小世界性（較小的最短路徑）和聚集性（相對(duì)較大的聚集系數(shù)）。然而，規(guī)則網(wǎng)絡(luò)雖具有聚集性，平均最短路徑卻較大。隨機(jī)圖則正好相反，具有小世界性，但聚集系數(shù)卻相當(dāng)小。</p><p>　　可見規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)并不能很好展現(xiàn)真實(shí)網(wǎng)絡(luò)的性質(zhì)，這說明現(xiàn)實(shí)世界既不是完全確定的也不是完全隨機(jī)的。Watts和Strogatz在1998年提出了一個(gè)兼具小世界性和高聚集性的網(wǎng)絡(luò)模

68、型[6]，它是復(fù)雜網(wǎng)絡(luò)研究中的重大突破。他們通過將規(guī)則網(wǎng)絡(luò)中的每條邊以概率p隨機(jī)連接到網(wǎng)絡(luò)中的一個(gè)新節(jié)點(diǎn)上，構(gòu)造出一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的網(wǎng)絡(luò)（簡稱WS網(wǎng)絡(luò)），它同時(shí)具有較小的平均路徑長度和較大的聚集系數(shù)，而規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)則分別是WS網(wǎng)絡(luò)在p為0和1時(shí)的特例。模型構(gòu)造過程如圖2-5所示!</p><p>　　圖2-5 WS小世界模型隨機(jī)化重連過程</p><p>　　2.2.2

69、 無標(biāo)度網(wǎng)絡(luò)模型</p><p>　　盡管小世界模型能很好的刻畫現(xiàn)實(shí)世界的小世界性和高聚集性，但對(duì)小世界模型的理論分析表明其節(jié)點(diǎn)的度分布仍為指數(shù)分布形式。實(shí)證結(jié)果卻表明對(duì)于大多數(shù)大規(guī)模真實(shí)網(wǎng)絡(luò)用冪率分布來描述它們的度分布更加精確。</p><p>　　冪率分布相對(duì)于指數(shù)分布其圖形沒有峰值，大多數(shù)節(jié)點(diǎn)僅有少量連接，而少數(shù)節(jié)點(diǎn)擁有大量連接，不存在隨機(jī)網(wǎng)絡(luò)中的特征標(biāo)度，于是Barabasi等人稱

70、這種度分布具有冪率特征的網(wǎng)絡(luò)為Scale-free網(wǎng)絡(luò)。為解釋Scale-free網(wǎng)絡(luò)的形成機(jī)制，Barabasi和Albert提出了著名的BA模型[6]。他們認(rèn)為以前的網(wǎng)絡(luò)模型沒有考慮真實(shí)網(wǎng)絡(luò)的兩個(gè)重要性質(zhì)：增長性和擇優(yōu)連接性，前者意味著網(wǎng)絡(luò)中不斷有新的節(jié)點(diǎn)加入進(jìn)來，后者則意味著新的節(jié)點(diǎn)進(jìn)來后優(yōu)先選擇網(wǎng)絡(luò)中度數(shù)大的節(jié)點(diǎn)進(jìn)行連接。他們不僅給出了BA模型的生成算法并進(jìn)行了模擬分析，而且還利用統(tǒng)計(jì)物理中的平均場方法給出了模型的解析解。結(jié)果表

71、明：經(jīng)過充分長時(shí)間的演化后BA網(wǎng)絡(luò)的度分布不再隨時(shí)間變化，度分布穩(wěn)定為指數(shù)為3的冪律分布。</p><p>　　BA模型的提出是復(fù)雜網(wǎng)絡(luò)研究中的又一重大突破，標(biāo)志著人們對(duì)客觀網(wǎng)絡(luò)世界認(rèn)識(shí)的深入。之后，許多學(xué)者對(duì)這一模型進(jìn)行了改進(jìn)，如非線性擇優(yōu)連接、加速增長、重繞邊的局域事件、逐漸老化、適應(yīng)性競爭等等。需要注意的是，絕大多數(shù)而不是所有的真實(shí)網(wǎng)絡(luò)都是Scale-free網(wǎng)絡(luò)。如有的真實(shí)網(wǎng)絡(luò)度分布為指數(shù)分布截?cái)嘈问降鹊?/p>

72、。</p><p>　　2.2.3 模塊性和等級(jí)網(wǎng)絡(luò)</p><p>　　為了研究網(wǎng)絡(luò)的模塊性，我們需要相應(yīng)的工具和度量以確定一個(gè)網(wǎng)絡(luò)是否是模塊化的，并且能夠清晰的辨識(shí)一個(gè)給定的網(wǎng)絡(luò)中的模塊以及模塊之間的關(guān)系。當(dāng)然，模塊便是并不是一件容易的事，因?yàn)闊o標(biāo)度性質(zhì)和模塊性看起來似乎是矛盾的。</p><p>　　模塊式如何構(gòu)成的呢？近期研究表明，模體（motif）可能是復(fù)

73、雜網(wǎng)絡(luò)的基本模塊[7-9]。網(wǎng)絡(luò)的高聚類性表明網(wǎng)絡(luò)在局部可能包含各種由高度連接節(jié)點(diǎn)組成的子圖(subgraph)。子圖描繪了從局部層次刻畫一個(gè)給定網(wǎng)絡(luò)的互聯(lián)的特定模式。為理解這點(diǎn)，我們考慮了一個(gè)完全規(guī)則的放鴿子，他的子圖報(bào)刊很多正方形而不是三角形（圖2-6）。這些正方形子圖反映了方格子的基本特征結(jié)構(gòu)，而在有明顯隨機(jī)性連接的復(fù)雜網(wǎng)絡(luò)中時(shí)難以找到這種明顯的有序特征的。也就是說，復(fù)雜網(wǎng)絡(luò)可能包含各種各樣的子圖，這些子圖所占的比率明顯高于同一網(wǎng)

74、絡(luò)的完全隨機(jī)化形式中這些子圖所占的比例。這些子圖被稱為模體。</p><p>　　圖2-6 子圖和模體</p><p>　　BA模型的提出是復(fù)雜網(wǎng)絡(luò)研究中的又一重大突破，標(biāo)志著人們對(duì)客觀網(wǎng)絡(luò)世界認(rèn)識(shí)的深入。之后，許多學(xué)者對(duì)這一模型進(jìn)行了改進(jìn)，如非線性擇優(yōu)連接、加速增長、重繞邊的局域事件、逐漸老化、適應(yīng)性競爭等等。需要注意的是，絕大多數(shù)而不是所有的真實(shí)網(wǎng)絡(luò)都是Scale-free網(wǎng)絡(luò)。如有的

75、真實(shí)網(wǎng)絡(luò)度分布為指數(shù)分布截?cái)嘈问降鹊取?lt;/p><p>　　接下來的問題是：一個(gè)網(wǎng)絡(luò)中的不同模體之間是如何相互作用的？經(jīng)驗(yàn)表明，特定的模體類型聚集在一起形成大的模體簇，這可能也是大多數(shù)實(shí)際網(wǎng)絡(luò)中的一個(gè)通有特性[10]。</p><p>　　為了說明許多實(shí)際系統(tǒng)中同時(shí)存在的模塊性、局部聚類和無標(biāo)度拓?fù)涮匦?，需要哪家社模塊以某種迭代的方式生成一個(gè)等級(jí)網(wǎng)絡(luò)（hierarchical networ

76、k）。研究表明，一些網(wǎng)絡(luò)（如新陳代謝網(wǎng)絡(luò)）中的拓?fù)淠K確實(shí)是按等級(jí)組織起來的。</p><p>　　需要注意的是，ER隨機(jī)圖和BA無標(biāo)度網(wǎng)絡(luò)都不具有等級(jí)拓?fù)?，在這兩類網(wǎng)絡(luò)中的節(jié)點(diǎn)系數(shù)C(k)與該節(jié)點(diǎn)的度k無關(guān)。這點(diǎn)并不奇怪，因?yàn)樵谶@兩類網(wǎng)絡(luò)的構(gòu)造過程中并未包含有利于模塊涌現(xiàn)的機(jī)制。</p><p>　　復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)</p><p>　　網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的研究已經(jīng)

77、有很長的歷史。它與計(jì)算機(jī)科學(xué)中的圖形分割（graph partition）和社會(huì)學(xué)中的分級(jí)聚類（hierarchical clustering）有著密切的關(guān)系。，前者主要包括Kernighan-Lin算法和基于圖的Laplace矩陣特征向量的譜平分法(Spectral Bisection Method)；而后者則以著名的GN(Girvan-Newman)算法為代表。</p><p><b>　　3.1

78、分級(jí)聚類</b></p><p>　　分級(jí)聚類是尋找社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)的一類傳統(tǒng)算法，它是基于各個(gè)節(jié)點(diǎn)之間連接的相似性或者強(qiáng)度，把網(wǎng)絡(luò)自然地劃分為各個(gè)子群。根據(jù)往網(wǎng)絡(luò)中添加邊還是移除邊，該類算法又可以分為兩類：凝聚算法（agglomerative method）和分裂算法（division method）[11]。</p><p>　　3.1.1 凝聚算法</p>

79、<p>　　凝聚算法的基本思想是用某種方法計(jì)算出各節(jié)點(diǎn)對(duì)之間的相似性，然后從相似性最高的節(jié)點(diǎn)對(duì)開始，往一個(gè)節(jié)點(diǎn)數(shù)位n而邊的數(shù)目為0的原始空網(wǎng)絡(luò)中添加邊。這個(gè)過程可以中止與任何一點(diǎn)，此時(shí)這個(gè)網(wǎng)絡(luò)的組成就認(rèn)為是若干個(gè)社團(tuán)。從空?qǐng)D到最終圖的整個(gè)算法的流程也可以用世系圖或者樹狀圖來表示，如圖3-1所示。底部的各個(gè)圓代表了網(wǎng)絡(luò)中的各個(gè)幾點(diǎn)。當(dāng)水平虛線從樹的底端逐步上移，各個(gè)幾點(diǎn)也逐步聚合稱為更大的社團(tuán)，當(dāng)虛線移至頂部，即表示整個(gè)網(wǎng)絡(luò)

80、就總體的稱為一個(gè)社團(tuán)。在該樹狀圖的任何一個(gè)位置用虛線斷開，就對(duì)應(yīng)著一種社團(tuán)結(jié)構(gòu)。</p><p>　　圖3-1 凝聚方法通常采用樹狀圖來記錄算法的結(jié)果</p><p>　　基于一系列相似性度量標(biāo)準(zhǔn)額凝聚方法已經(jīng)應(yīng)用于許多不同的網(wǎng)絡(luò)。一些網(wǎng)絡(luò)本身就有很多相似性度量標(biāo)準(zhǔn)。比如，在電影演員合作網(wǎng)絡(luò)中[12-13]，如果兩個(gè)演員出現(xiàn)在同一部電影中，他們之間就有一條邊相連，這樣就可以用有多少電影演員

81、同時(shí)出現(xiàn)在同一部電影中來度量節(jié)點(diǎn)的相似性[14]。而另外一些網(wǎng)絡(luò)雖然其本身沒有相似性的度量，但是可以利用相關(guān)系數(shù)、路徑長度或者一些矩陣的方法來設(shè)計(jì)一些適當(dāng)?shù)亩攘?，本文涉及的隨機(jī)游走算法便可以算得上一種凝聚算法。</p><p>　　3.1.2 分裂算法</p><p>　　相反的，在分裂算法中，一般是從所關(guān)注的網(wǎng)絡(luò)著手，試圖找到已連接的相似性最低的節(jié)點(diǎn)對(duì)，然后移除連接他們的邊。重復(fù)這個(gè)過程

82、，就逐步把整個(gè)網(wǎng)絡(luò)分成越來越小的各個(gè)部分。同樣的，可以在任何情況下終止，并且把此狀態(tài)的網(wǎng)絡(luò)看做若干網(wǎng)絡(luò)社團(tuán)的集合。與凝聚方法類似，利用樹狀圖來表示分裂方法的流程，可以更好地描述整個(gè)網(wǎng)絡(luò)逐步分解為若干個(gè)越來越小的子群這一連續(xù)過程。</p><p><b>　　3.2 迭代二分法</b></p><p>　　計(jì)算機(jī)科學(xué)中的一個(gè)典型問題，是將一個(gè)網(wǎng)絡(luò)分解成若干結(jié)點(diǎn)數(shù)基本相等

83、的子網(wǎng)，使得不同子網(wǎng)中的結(jié)點(diǎn)之間的連接數(shù)最少，稱為圖分割。圖分割問題(GPP)可應(yīng)用于并行計(jì)算機(jī)的處理器合理分配進(jìn)程。實(shí)際應(yīng)用中，大多數(shù)圖分割方法均基于迭代二分法：首先將圖按要求分割成2個(gè)子圖，然后再分別對(duì)這2個(gè)子圖進(jìn)行分割，如此迭代下去直至獲得所要求的子圖個(gè)數(shù)。</p><p>　　我們介紹兩個(gè)最具代表性的迭代二分法：一是Kernighan-Lin算法，該算法使用貪婪策略對(duì)社區(qū)內(nèi)以及社區(qū)間的邊數(shù)進(jìn)行優(yōu)化，從而達(dá)

84、到改進(jìn)網(wǎng)絡(luò)的初始分解的目的；另一個(gè)是基于圖的Laplace矩陣的特征向量的譜二分法(Spectral Bisection Method)。</p><p>　　3.2.1 Kernighan-Lin 算法</p><p>　　Kernighan-Lin算法是一種試探優(yōu)化法。它基于貪婪算法原理將網(wǎng)絡(luò)劃分為兩個(gè)規(guī)模已知的社區(qū)。其基本思想是為網(wǎng)絡(luò)的劃分引進(jìn)一個(gè)增益函數(shù)Q，Q定義為兩個(gè)社區(qū)內(nèi)部的邊

85、數(shù)減去連接兩個(gè)社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。整個(gè)算法</p><p><b>　　可描述如下：</b></p><p>　　首先，將網(wǎng)絡(luò)中的結(jié)點(diǎn)隨機(jī)地劃分為已知規(guī)模的兩個(gè)社區(qū)。在此基礎(chǔ)上，考慮所有可能的結(jié)點(diǎn)對(duì)，其中每個(gè)結(jié)點(diǎn)對(duì)的結(jié)點(diǎn)分別來自兩個(gè)社區(qū)。對(duì)每個(gè)結(jié)點(diǎn)對(duì)，計(jì)算如果交換這兩個(gè)結(jié)點(diǎn)的話可能得到的Q的增益，然后交換最大的△Q對(duì)應(yīng)的結(jié)點(diǎn)對(duì)，同時(shí)記錄交換以

86、后的Q值。規(guī)定每個(gè)結(jié)點(diǎn)只能交換一次。重復(fù)這個(gè)交換過程，直到某個(gè)社區(qū)內(nèi)所有的結(jié)點(diǎn)都被交換一次為止。需要注意的是，在結(jié)點(diǎn)對(duì)交換的過程中，Q值并不一定總是單調(diào)增加的。不過，即使某一步的交換會(huì)使Q值有所下降，但是仍然可能在其后的步驟中出現(xiàn)一個(gè)更大的Q值。當(dāng)交換完畢后，便找到上述交換過程中所記錄的最大的Q值。這時(shí)對(duì)應(yīng)的社區(qū)結(jié)構(gòu)就認(rèn)為是該網(wǎng)絡(luò)實(shí)際的社區(qū)結(jié)構(gòu)。</p><p>　　Kernighan-Lin算法最大的缺陷是要求

87、事先知道兩個(gè)社區(qū)的規(guī)模，否則，就很可能</p><p>　　不會(huì)得到正確的結(jié)果。這個(gè)缺陷使得它在實(shí)際網(wǎng)絡(luò)分析中難以應(yīng)用。而且，即使這個(gè)問題可以得到解決，它與所有的二分算法一樣，仍然面臨著如何事先知道網(wǎng)絡(luò)中的社區(qū)數(shù)目，以及二分要重復(fù)到哪一步停止的問題</p><p><b>　　3.2.2譜平分法</b></p><p>　　一個(gè)有n個(gè)結(jié)點(diǎn)的無向

88、圖G的Laplace矩陣是一個(gè)維的對(duì)稱矩陣L。其中，L的對(duì)角線上的元素是結(jié)點(diǎn)i的度，而其他非對(duì)角線上的元素則表示結(jié)點(diǎn)i和結(jié)點(diǎn)j的連接關(guān)系。如果這兩個(gè)結(jié)點(diǎn)之間有邊連接，則值為1，否則為0。L矩陣所有的行與列的和都為0，因此，該矩陣總有一個(gè)特征值為0，其對(duì)應(yīng)的特征向量為l=(1，1，1．．．)。可以從理論上證明，不為零的特征值所對(duì)應(yīng)的特征向量的各元素中，同一個(gè)社區(qū)內(nèi)的結(jié)點(diǎn)對(duì)應(yīng)的元素是近似相等的。這就是譜平分法的理論基礎(chǔ)。</p>

89、<p>　　考慮網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的一種特殊情況：當(dāng)一個(gè)網(wǎng)絡(luò)中僅存在兩個(gè)社區(qū)，此時(shí)該網(wǎng)絡(luò)的</p><p>　　Laplace矩陣L就對(duì)應(yīng)了兩個(gè)近似的對(duì)角矩陣塊。對(duì)一個(gè)實(shí)對(duì)稱矩陣而言，它的非退化</p><p>　　的特征值對(duì)應(yīng)的特征向量總是正交的。因此，除了最小特征值0以外，矩陣L其他特征</p><p>　　值對(duì)應(yīng)的特征向量總是包含正、負(fù)兩種元素。這樣，

90、當(dāng)網(wǎng)絡(luò)由兩個(gè)社區(qū)構(gòu)成時(shí)，就可以</p><p>　　根據(jù)非零特征值相應(yīng)的特征向量中的元素對(duì)應(yīng)網(wǎng)絡(luò)的結(jié)點(diǎn)進(jìn)行分類。其中，所有正元素</p><p>　　對(duì)應(yīng)的那些結(jié)點(diǎn)都屬于同一個(gè)社區(qū)，而所有負(fù)元素對(duì)應(yīng)的結(jié)點(diǎn)則屬于另一個(gè)社區(qū)。</p><p>　　因此，我們可以根據(jù)網(wǎng)絡(luò)的Laplace矩陣的第二小的特征值將其分為兩個(gè)社區(qū)。這就是譜平分法的基本思想。當(dāng)網(wǎng)絡(luò)的確是分成兩個(gè)社

91、區(qū)時(shí)，用譜平分法可以得到非常</p><p>　　好的效果。但是，當(dāng)網(wǎng)絡(luò)不滿足這個(gè)條件時(shí)，譜平分法的優(yōu)點(diǎn)就不能得到充分體現(xiàn)。事</p><p>　　實(shí)上，第二小特征值可以作為衡量譜平分法效果的標(biāo)準(zhǔn)：它的值越小，平分的效果就</p><p>　　越好。也稱為圖的代數(shù)連接度(Algebraic Connectivity)。</p><p>　　一

92、般情況下，計(jì)算一個(gè)矩陣的全部特征向量的時(shí)間復(fù)雜度為。但是在大</p><p>　　多數(shù)情況下，實(shí)際網(wǎng)絡(luò)的Laplace矩陣是一個(gè)稀疏矩陣，因此，可以用Lanczos方法快</p><p>　　速計(jì)算主要的特征向量。該方法的時(shí)間復(fù)雜度大致為，其中，m表示網(wǎng)絡(luò)中邊的條數(shù)。這樣，計(jì)算的速度可以得到很大程度的提高。但是，如果不能很快將從其它特征值中分離出來，該算法就可能在一定程度上有所減慢。換句話

93、說，當(dāng)網(wǎng)絡(luò)很明顯地分成兩個(gè)社區(qū)時(shí)，該算法的速度非?？?，否則該算法就未必很有效。</p><p>　　3.3 其他經(jīng)典算法</p><p>　　3.3.1 GN（Girvan-Newman）算法</p><p>　　GN 算法是一種分裂方法，它通過迭代從網(wǎng)絡(luò)中移除介數(shù)(Betweenness)最大的邊將整個(gè)網(wǎng)絡(luò)分解為各個(gè)社區(qū)。邊的介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過該邊的最短路徑的數(shù)

94、目。它為區(qū)分一個(gè)社區(qū)內(nèi)部邊和外部邊連接提供了一個(gè)度量準(zhǔn)則。</p><p>　　GN算法的基本流程如下：</p><p>　　(i) 計(jì)算網(wǎng)絡(luò)中的所有邊的介數(shù)；</p><p>　　(ii) 找到介數(shù)最高的邊并將它從網(wǎng)絡(luò)中移除；</p><p>　　(iii) 重復(fù)步驟(ii)，直到每個(gè)節(jié)點(diǎn)就是一個(gè)退化社區(qū)為止。</p><

95、;p>　　缺點(diǎn)：在不知道社區(qū)數(shù)目的情況下，此算法也不能確定迭代的合適步數(shù)。</p><p>　　3.3.2 Newman快速算法</p><p>　　由于GN 算法的時(shí)間復(fù)雜度較大，所以對(duì)大規(guī)模的復(fù)雜網(wǎng)絡(luò)的分析效果并不理想。Newman 在GN 算法的基礎(chǔ)上提出了一種快速算法，它是基于貪婪算法思想的一種凝聚算法。此算法總的時(shí)間復(fù)雜度為。整個(gè)算法完成后可得到一個(gè)社區(qū)結(jié)構(gòu)分解的樹狀圖，再

96、通過選擇在不同位置斷開可得到不同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，在這些社區(qū)結(jié)構(gòu)中，選擇一個(gè)對(duì)應(yīng)著局部最大的Q值，就得到最好的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。</p><p>　　3.3.3Radicchi算法</p><p>　　該算法與GN 算法相同，都是基于去邊，但不是根據(jù)邊介數(shù)選擇要去除的邊，而是引進(jìn)了邊聚集系數(shù)的新指標(biāo)。整個(gè)算法的運(yùn)行時(shí)間為。顯然，對(duì)于稀疏圖，其計(jì)算速度要比GN算法快一個(gè)數(shù)量級(jí)。</p>

97、<p>　　Radicchi 等考慮網(wǎng)絡(luò)中的三角環(huán)(即邊數(shù)為3 的閉合路徑)。若一個(gè)三角環(huán)包含一條連接不同社區(qū)的邊，則該三角環(huán)中的另兩條邊中的某一條仍然連接這兩個(gè)社區(qū)的可能性將很大。但是由于連接不同社區(qū)的邊非常稀少，故包含一條給定的連接不同社區(qū)的邊的三角環(huán)不可能很多.因此，將一條邊的邊聚集系數(shù)定義為包含該邊的三角環(huán)所占比例：</p><p><b>　?。?-1）</b><

98、;/p><p>　　其中，，分別表示節(jié)點(diǎn)i 和j 的度，表示網(wǎng)絡(luò)中實(shí)際包含該邊的三角環(huán)的個(gè)數(shù)。上式中的分母表示包含該邊的最大可能的三角環(huán)的個(gè)數(shù)。</p><p>　　Radicchi 算法每一步去除的是網(wǎng)絡(luò)中邊聚集系數(shù)最小的邊，每次去除后，再重新計(jì)算每一條邊的邊聚集系數(shù)，如此進(jìn)行下去，直至網(wǎng)絡(luò)中不存在任何邊。</p><p>　　Radicchi 算法的不足是該算法依賴

99、于網(wǎng)絡(luò)中的三角環(huán)，如果網(wǎng)絡(luò)中三角環(huán)很少，那么該算法將失去意義。實(shí)證研究表明，社會(huì)網(wǎng)絡(luò)中三角環(huán)的數(shù)量比較大，而在非社會(huì)網(wǎng)絡(luò)中，三角環(huán)的數(shù)量則相對(duì)較少。這意味著Radicchi 算法更加適合于社會(huì)網(wǎng)絡(luò)。</p><p>　　第四章 基于隨機(jī)游走的社團(tuán)發(fā)現(xiàn)算法</p><p>　　本章主要介紹一種基于圖論的隨機(jī)游走（random walk）算法[15-16]，主要介紹了該隨機(jī)游走算法的基本原理，

100、以及隨機(jī)游走算法的編譯實(shí)現(xiàn)方式。</p><p>　　4.1 隨機(jī)游走算法的基本原理</p><p>　　在上一章節(jié)對(duì)各種社團(tuán)發(fā)現(xiàn)算法的介紹和比較后，我們在此提出一種完全基于隨機(jī)游走來實(shí)現(xiàn)社團(tuán)劃分的算法。該算法的主要實(shí)現(xiàn)原理是基于此種方式，即在以任意節(jié)點(diǎn)i 為起點(diǎn)進(jìn)行有限步數(shù)的隨機(jī)游走，在有限的步數(shù)內(nèi)，相比于在不同的社團(tuán)間的隨機(jī)游走，該隨機(jī)游走是有更大的可能性是停留在同一個(gè)社團(tuán)內(nèi)部的。我們

101、通過記錄在每次隨機(jī)游走過程中的軌跡來作為節(jié)點(diǎn)間屬于同一個(gè)社團(tuán)的證據(jù)。正式介于此類原理，我們提出了這種更簡單，更直接的劃分復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的隨機(jī)游走算法。</p><p>　　4.1.1 隨機(jī)游走算法的相似度矩陣獲取</p><p>　　隨機(jī)游走的基本思想是進(jìn)行多次一段較短步數(shù)的隨機(jī)游走，并且把在同一次隨機(jī)游走過程中經(jīng)歷的節(jié)點(diǎn)作為他們同屬于一個(gè)社團(tuán)的證據(jù)。這個(gè)信息在經(jīng)過所有的隨機(jī)游走過程后

102、被補(bǔ)充完整，并被用來作為一個(gè)基本的信息去劃分復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，算法的基本過程在圖4-1中顯示。</p><p>　　算法的過程中，我們首先定義的矩陣S，把矩陣中的每一個(gè)元素S[i][j]都賦值為0。在考慮算法的隨機(jī)游走的步數(shù)時(shí)，我們可以根據(jù)我們要處理的復(fù)雜網(wǎng)絡(luò)的半徑以及節(jié)點(diǎn)數(shù)n來自己給出隨機(jī)游走的步數(shù)（隨機(jī)游走的步數(shù)一般不會(huì)超過10）。在隨機(jī)游走算法的過程中，我們從節(jié)點(diǎn)i開始進(jìn)行隨機(jī)游走，隨機(jī)游走即從節(jié)點(diǎn)i的所

103、有鄰居節(jié)點(diǎn)中等概率的找到它的一個(gè)鄰居節(jié)點(diǎn)，作為隨機(jī)游走的下一個(gè)節(jié)點(diǎn)。在每一次隨機(jī)游走過程中，我們都會(huì)用一個(gè)集合C來存儲(chǔ)我們這一次隨機(jī)游走過程中所遍歷的節(jié)點(diǎn)i（集合C中的數(shù)據(jù)是不重復(fù)的，即使我們隨機(jī)游走的過程中經(jīng)過多次節(jié)點(diǎn)i，我們也只在集合C中記錄一次）。根據(jù)得到的集合C，我們隨機(jī)的選擇集合C中不相等的元素i，j，來作為相似度矩陣S的行號(hào)和列號(hào)，即S[i][j]。與此同時(shí)，S[i][j]中的元素對(duì)應(yīng)加1。以此遍歷復(fù)雜網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，得到

104、n個(gè)集合C，并最終得出矩陣S的值。</p><p>　　在完成矩陣S后，矩陣的每個(gè)元素S[i][j]表示節(jié)點(diǎn)i和節(jié)點(diǎn)j同屬于一次隨機(jī)游走的次數(shù)，即同屬于一個(gè)社團(tuán)的可能性的大小。S[i][j]值越大，表示i，j屬于一個(gè)社團(tuán)的可能性便越大。</p><p>　　圖4-1 隨機(jī)游走算法矩陣S的獲取</p><p>　　4.1.2 隨機(jī)游走算法的矩陣融合</p>

105、<p>　　現(xiàn)在我們通過隨機(jī)游走得到了一個(gè)相似度矩陣S，我們下一步的工作便是將相似度矩陣進(jìn)行融合，在融合的過程中不斷得到新的社團(tuán)結(jié)構(gòu)。在融合矩陣的過程中，把每次融合的節(jié)點(diǎn)數(shù)進(jìn)行記錄到新的集合C中，在矩陣融合結(jié)束后，集合C中記錄的便是復(fù)雜網(wǎng)絡(luò)最終的社團(tuán)結(jié)構(gòu)的劃分。</p><p>　　在融合矩陣的過程中，我們使用的是與Johnson 描述的凝聚算法相類似的一種技術(shù)。這種方式的普遍觀念是根據(jù)相似度矩陣中

106、的元素的相似度的大小來進(jìn)行融合。融合的方式為從最大的相似度開始融合，以后依次遞減類推，在融合結(jié)束后得出結(jié)果。融合矩陣的算法在圖4-2中給出。</p><p>　　圖4-2 隨機(jī)游走算法相似度矩陣S的融合</p><p>　　在矩陣融合的過程中，相似度矩陣S的尺寸在每一次的融合過程中不斷的減少。矩陣在相應(yīng)行（列）融合的過程中也在不斷地進(jìn)行變化。而在融合的過程中，幾種不同的方式可供我們選擇，有

107、最大值，最小值以及平均值的方式，在這里我們經(jīng)驗(yàn)性的選取平均值來作為融合結(jié)果最好的值（在下一小節(jié)我們進(jìn)行討論），根據(jù)相應(yīng)的算法，其復(fù)雜度可以為也可以為O(n)，具體介紹將在下一章具體介紹。</p><p>　　4.1.3 矩陣元素融合方式</p><p>　　在此我們提醒讀者關(guān)于我們討論的在融合社團(tuán)過程中，為相似矩陣計(jì)算的新的距離的方法。在融合矩陣之前，我們首先應(yīng)該了解那種算法方式是最有效率