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

1、<p>　　本科畢業(yè)設(shè)計（論文）</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>　　班級

2、 </b></p><p><b>　　學(xué)號 </b></p><p><b>　　班內(nèi)序號 </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ò)是對于復(fù)雜系統(tǒng)的高度抽象，其中許多性質(zhì)如小世界性質(zhì)、無標(biāo)度性質(zhì)以及聚集性質(zhì)等等已經(jīng)得到了充分的研究。復(fù)雜網(wǎng)絡(luò)的研究是以系統(tǒng)的觀點來看待真實系統(tǒng)，如Internet網(wǎng)絡(luò)、電力網(wǎng)、新陳代謝網(wǎng)絡(luò)等。(大量的文獻(xiàn)表明，)復(fù)雜網(wǎng)絡(luò)通常會呈現(xiàn)出

4、社區(qū)結(jié)構(gòu)特性，而如何在實際網(wǎng)絡(luò)中高效地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)是近年來復(fù)雜網(wǎng)絡(luò)的研究熱點之一。社團(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ū)評估和確定方面的概念、理論、算法及應(yīng)用等。同樣的，文章中也討論了一種可以應(yīng)用于大型復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)的random walk算法，并且顯示了它和其他算法在社團(tuán)劃分上有相同的表現(xiàn)，

5、同時擁有更低的復(fù)雜度。</p><p>　　文章中將random walk算法應(yīng)用于對已知社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)的劃分以及比較其劃分的社團(tuán)結(jié)構(gòu)的結(jié)果。除此之外，文章中對于此類算法給出一定改進(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 模塊性與等級網(wǎng)絡(luò)12</p><p>　　第三章 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu) 14</p><p>　　3.1 分級聚類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ī)游走算法對復(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 對復(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 對未來的展望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é)點眾多、連接關(guān)系復(fù)雜的網(wǎng)絡(luò)。由于其靈活普適的描述能力, 能夠廣泛應(yīng)用于各科學(xué)領(lǐng)域?qū)?fù)雜系統(tǒng)進(jìn)行建模、分析, 近年來吸引了越來越多的人對其進(jìn)行研究。隨著研究

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

26、man 基于邊介數(shù)提出GN 算法以來, 國際上掀起一股社團(tuán)發(fā)現(xiàn)的研究熱潮, 來自生物、物理、計算機(jī)等各學(xué)科領(lǐng)域的研究者們帶來了許多新穎的思想和算法, 并廣泛應(yīng)用于各個學(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).任何一個網(wǎng)絡(luò)都可以看做是由一些節(jié)點按某種方式連接而構(gòu)成的一個系統(tǒng)。具體網(wǎng)絡(luò)的抽象圖表示，就是用抽象的點表示具體網(wǎng)絡(luò)中的節(jié)點，并用節(jié)點之間的連線表示具體網(wǎng)絡(luò)中節(jié)點間的連接關(guān)系。</p><p>　　實際網(wǎng)絡(luò)的圖表示法可以追溯到18世紀(jì)偉大的數(shù)學(xué)家歐拉(Euler)對著名的“Konigs

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

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

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

31、歐拉圖。事實上，今天人們關(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ā)展使人類社會大步邁入了網(wǎng)絡(luò)時代。從Internet到WWW，從大型電力網(wǎng)絡(luò)到全球交通網(wǎng)絡(luò)，從生物體中的大腦到各種新陳代謝網(wǎng)絡(luò)，從

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

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

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

35、性，網(wǎng)絡(luò)行為也具有復(fù)雜性。</p><p>　　許多真實系統(tǒng)都可以用網(wǎng)絡(luò)的形式加以描述，一個典型的網(wǎng)絡(luò)是由許多結(jié)點與連接結(jié)點之間的邊組成的。結(jié)點代表系統(tǒng)中的個體，邊則表示結(jié)點之間的作用關(guān)系。如WWW網(wǎng)絡(luò)可以看成是網(wǎng)頁之間通過超鏈接構(gòu)成的網(wǎng)絡(luò)；Internet網(wǎng)絡(luò)可以看作不同的計算機(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>　　這些真實網(wǎng)絡(luò)的普遍存在，促使來自不同學(xué)科領(lǐng)域的科學(xué)家共同致力于復(fù)雜網(wǎng)絡(luò)的研究。這些學(xué)科領(lǐng)域包括復(fù)雜性科學(xué)、數(shù)學(xué)、物理、生物和計算機(jī)等。復(fù)雜網(wǎng)絡(luò)的研究可以使人們更好地了解現(xiàn)實世界的復(fù)雜系統(tǒng)，為設(shè)計具有良好性能的網(wǎng)絡(luò)提供依據(jù)。同時復(fù)雜網(wǎng)絡(luò)的理論成果將會廣泛地應(yīng)用到生物、計算機(jī)等各個學(xué)科領(lǐng)域。</p><p>　　復(fù)雜網(wǎng)絡(luò)的研究大致可以描述為三個密切相關(guān)但又依次深入

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

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

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

40、的。每個社區(qū)內(nèi)部的結(jié)點間的連接相對非常緊密，但是各個社區(qū)之間的連接相對來說卻比較稀疏。揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，對于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性是很重要的。如社會網(wǎng)絡(luò)中的社區(qū)代表根據(jù)興趣和背景而形成的真實的社會團(tuán)體；引文網(wǎng)絡(luò)中的社區(qū)代表針對同一主題的相關(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)劃分算法所要劃分的網(wǎng)絡(luò)大致可分為兩類，一類是比較常見的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)(網(wǎng)絡(luò)中邊的權(quán)值為正實數(shù))；另一類是符號社會網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負(fù)向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法相應(yīng)分為兩大類，而對于第一類網(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ò)劃分為兩個大小已知的社區(qū)的二分法。其基本思想是為網(wǎng)絡(luò)的劃分引進(jìn)一個增益函數(shù)Q，增益函數(shù)定義為兩個社區(qū)內(nèi)部的邊數(shù)減去連接兩個社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。1990年，Pothen等基于圖的Laplace矩陣的譜特征提出一種將網(wǎng)絡(luò)劃分為兩個社區(qū)的二分法瞻目。該算法的理論基礎(chǔ)是不為零的特征值所對應(yīng)的特征向量的各元素中，同一個社區(qū)內(nèi)的結(jié)點對應(yīng)的元素是近似相等的。因此可以根據(jù)網(wǎng)絡(luò)的Laplace矩陣的第二

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

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

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

47、和Moore等人采用堆的數(shù)據(jù)結(jié)構(gòu)來計算和更新網(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)的算法，算法的初始條件為每個結(jié)點為一個單獨的社區(qū)，然后逐步合并可使結(jié)點和它所在社區(qū)之間的平方距離均值達(dá)到最小的兩個社區(qū)。每一步都要更新社

48、區(qū)之間的距離，其中兩個結(jié)點之間的距離對應(yīng)于它們的相似度，即在一個離散的隨機(jī)游走過程中，它們之間的方向轉(zhuǎn)移概率。</p><p>　　以上所述算法最終目的均是把網(wǎng)絡(luò)劃分為若干個相互分離的社區(qū)，但是現(xiàn)實中很多網(wǎng)絡(luò)并不存在絕對的彼此獨立的社區(qū)結(jié)構(gòu)，相反它們是由許多彼此重疊且相互關(guān)聯(lián)的社區(qū)構(gòu)成。比如，每個人根據(jù)不同的分類方法都會屬于多個不同的社區(qū)(如學(xué)校、家庭、不同的興趣小組等)。在這種情況下，很難單獨的將這些社區(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)越，但所需計算量卻很大。這說明復(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)劃分。首先，針對無權(quán)的復(fù)雜網(wǎng)絡(luò)，提出了隨機(jī)游走的概念，在此基礎(chǔ)上提出一種有效的劃分社區(qū)結(jié)構(gòu)的算法。實驗結(jié)果表明該算法是可行且有效的。最后把這種算法推廣到加權(quán)的大型復(fù)雜網(wǎng)絡(luò)中，并把算法應(yīng)用實際的加權(quán)網(wǎng)絡(luò)數(shù)據(jù)中，驗證了推廣算法的可行性和有效性。綜上所述，本文主要研究內(nèi)容共分為兩個部分：第一部分提出了一種基于隨機(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>　　主要針對Internet 中的拓?fù)浣Y(jié)構(gòu)提出來一些模型。介紹復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)及其搜索算法。大多數(shù)的實際網(wǎng)絡(luò)都具有社團(tuán)結(jié)構(gòu)。也就是說，一個大的網(wǎng)絡(luò)可以分成

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

53、準(zhǔn)確度；同時給出算法的復(fù)雜度的分析。</p><p>　　主要介紹了在random walk算法基礎(chǔ)上的改進(jìn)，使random walk算法能夠?qū)崿F(xiàn)：對有權(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)計特性上提出了許多概念和方法，其中有三個基本的概念：平均路徑長度（average path length）、聚類系數(shù)（clustering coefficient）和度分布（degree distribution）。實際上，Watts和Strogatz提出小世界網(wǎng)絡(luò)模型的初衷就是建立一個既具有類似于隨機(jī)圖的較少的平均路徑長度，又具有類似于規(guī)則網(wǎng)絡(luò)的較大的聚類系數(shù)的網(wǎng)絡(luò)模型。另一方面，Barabasi和Albert

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

56、對（i，j）和（j，i）對應(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ò)。此外，一個網(wǎng)絡(luò)中還可能包含多種不同類型的節(jié)點。圖2-1給出了幾種不同類型的網(wǎng)絡(luò)的例子。在圖論中，沒有重邊</p><p>　　和自環(huán)的圖稱為簡單圖（simple graph）[4] 。</p>

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

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

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

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

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

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

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

64、</b></p><p><b>　　（2-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é)和社會</p><p>　　的每一個角落。隨著對網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實際<

65、/p><p>　　網(wǎng)絡(luò)都具有一個共同性質(zhì)——社團(tuán)結(jié)構(gòu)。也就是說，網(wǎng)絡(luò)是由若干個“群(Group)"或“團(tuán)(Cluster)”構(gòu)成的。每個群內(nèi)的結(jié)點之間的連接非常緊密，而群之間的連接卻相對比較稀疏，如圖2-4所示。圖中的空手道俱樂部網(wǎng)絡(luò)包含兩個社團(tuán)，分別對應(yīng)圖中不同節(jié)點形狀的部分。在這些社區(qū)內(nèi)部，結(jié)點之間的聯(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ò)，其特點是每個節(jié)點的近鄰數(shù)目都相同，如一維鏈、二維晶格、完全圖等。隨機(jī)網(wǎng)絡(luò)模型的提出是網(wǎng)絡(luò)研究中的重大成果，但它仍不能很好的刻畫實際網(wǎng)絡(luò)的性質(zhì)，人們又相繼提出了一些新的網(wǎng)絡(luò)模型。</p><p>　　2.2.1 小世界模型</p>

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

68、型[6]，它是復(fù)雜網(wǎng)絡(luò)研究中的重大突破。他們通過將規(guī)則網(wǎng)絡(luò)中的每條邊以概率p隨機(jī)連接到網(wǎng)絡(luò)中的一個新節(jié)點上，構(gòu)造出一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的網(wǎng)絡(luò)（簡稱WS網(wǎng)絡(luò)），它同時具有較小的平均路徑長度和較大的聚集系數(shù)，而規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)則分別是WS網(wǎng)絡(luò)在p為0和1時的特例。模型構(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)實世界的小世界性和高聚集性，但對小世界模型的理論分析表明其節(jié)點的度分布仍為指數(shù)分布形式。實證結(jié)果卻表明對于大多數(shù)大規(guī)模真實網(wǎng)絡(luò)用冪率分布來描述它們的度分布更加精確。</p><p>　　冪率分布相對于指數(shù)分布其圖形沒有峰值，大多數(shù)節(jié)點僅有少量連接，而少數(shù)節(jié)點擁有大量連接，不存在隨機(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ò)模型沒有考慮真實網(wǎng)絡(luò)的兩個重要性質(zhì)：增長性和擇優(yōu)連接性，前者意味著網(wǎng)絡(luò)中不斷有新的節(jié)點加入進(jìn)來，后者則意味著新的節(jié)點進(jìn)來后優(yōu)先選擇網(wǎng)絡(luò)中度數(shù)大的節(jié)點進(jìn)行連接。他們不僅給出了BA模型的生成算法并進(jìn)行了模擬分析，而且還利用統(tǒng)計物理中的平均場方法給出了模型的解析解。結(jié)果表

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

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

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

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

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

76、k）。研究表明，一些網(wǎng)絡(luò)（如新陳代謝網(wǎng)絡(luò)）中的拓?fù)淠K確實是按等級組織起來的。</p><p>　　需要注意的是，ER隨機(jī)圖和BA無標(biāo)度網(wǎng)絡(luò)都不具有等級拓?fù)?，在這兩類網(wǎng)絡(luò)中的節(jié)點系數(shù)C(k)與該節(jié)點的度k無關(guā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ī)科學(xué)中的圖形分割（graph partition）和社會學(xué)中的分級聚類（hierarchical clustering）有著密切的關(guān)系。，前者主要包括Kernighan-Lin算法和基于圖的Laplace矩陣特征向量的譜平分法(Spectral Bisection Method)；而后者則以著名的GN(Girvan-Newman)算法為代表。</p><p><b>　　3.1

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

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

80、就總體的稱為一個社團(tuán)。在該樹狀圖的任何一個位置用虛線斷開，就對應(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]，如果兩個演員出現(xiàn)在同一部電影中，他們之間就有一條邊相連，這樣就可以用有多少電影演員

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

96、通過選擇在不同位置斷開可得到不同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，在這些社區(qū)結(jié)構(gòu)中，選擇一個對應(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)。整個算法的運(yùn)行時間為。顯然，對于稀疏圖，其計算速度要比GN算法快一個數(shù)量級。</p>

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

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

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

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

101、通過記錄在每次隨機(jī)游走過程中的軌跡來作為節(jié)點間屬于同一個社團(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é)點作為他們同屬于一個社團(tuán)的證據(jù)。這個信息在經(jīng)過所有的隨機(jī)游走過程后

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

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

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

105、<p>　　現(xiàn)在我們通過隨機(jī)游走得到了一個相似度矩陣S，我們下一步的工作便是將相似度矩陣進(jìn)行融合，在融合的過程中不斷得到新的社團(tuán)結(jié)構(gòu)。在融合矩陣的過程中，把每次融合的節(jié)點數(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)驗性的選取平均值來作為融合結(jié)果最好的值（在下一小節(jié)我們進(jìn)行討論），根據(jù)相應(yīng)的算法，其復(fù)雜度可以為也可以為O(n)，具體介紹將在下一章具體介紹。</p><p>　　4.1.3 矩陣元素融合方式</p><p>　　在此我們提醒讀者關(guān)于我們討論的在融合社團(tuán)過程中，為相似矩陣計算的新的距離的方法。在融合矩陣之前，我們首先應(yīng)該了解那種算法方式是最有效率