【文章內(nèi)容簡介】 小世界性，但聚集系數(shù)卻相當(dāng)小?？梢娨?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ò)模型[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)造過程如圖25所示!圖25 WS小世界模型隨機(jī)化重連過程 無標(biāo)度網(wǎng)絡(luò)模型盡管小世界模型能很好的刻畫現(xiàn)實(shí)世界的小世界性和高聚集性，但對(duì)小世界模型的理論分析表明其節(jié)點(diǎn)的度分布仍為指數(shù)分布形式。實(shí)證結(jié)果卻表明對(duì)于大多數(shù)大規(guī)模真實(shí)網(wǎng)絡(luò)用冪率分布來描述它們的度分布更加精確。冪率分布相對(duì)于指數(shù)分布其圖形沒有峰值，大多數(shù)節(jié)點(diǎn)僅有少量連接，而少數(shù)節(jié)點(diǎn)擁有大量連接，不存在隨機(jī)網(wǎng)絡(luò)中的特征標(biāo)度，于是Barabasi等人稱這種度分布具有冪率特征的網(wǎng)絡(luò)為Scalefree網(wǎng)絡(luò)。為解釋Scalefree網(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é)果表明：經(jīng)過充分長時(shí)間的演化后BA網(wǎng)絡(luò)的度分布不再隨時(shí)間變化，度分布穩(wěn)定為指數(shù)為3的冪律分布。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ò)都是Scalefree網(wǎng)絡(luò)。如有的真實(shí)網(wǎng)絡(luò)度分布為指數(shù)分布截?cái)嘈问降鹊取?模塊性和等級(jí)網(wǎng)絡(luò)為了研究網(wǎng)絡(luò)的模塊性，我們需要相應(yīng)的工具和度量以確定一個(gè)網(wǎng)絡(luò)是否是模塊化的，并且能夠清晰的辨識(shí)一個(gè)給定的網(wǎng)絡(luò)中的模塊以及模塊之間的關(guān)系。當(dāng)然，模塊便是并不是一件容易的事，因?yàn)闊o標(biāo)度性質(zhì)和模塊性看起來似乎是矛盾的。模塊式如何構(gòu)成的呢？近期研究表明，模體（motif）可能是復(fù)雜網(wǎng)絡(luò)的基本模塊[79]。網(wǎng)絡(luò)的高聚類性表明網(wǎng)絡(luò)在局部可能包含各種由高度連接節(jié)點(diǎn)組成的子圖(subgraph)。子圖描繪了從局部層次刻畫一個(gè)給定網(wǎng)絡(luò)的互聯(lián)的特定模式。為理解這點(diǎn)，我們考慮了一個(gè)完全規(guī)則的放鴿子，他的子圖報(bào)刊很多正方形而不是三角形（圖26）。這些正方形子圖反映了方格子的基本特征結(jié)構(gòu)，而在有明顯隨機(jī)性連接的復(fù)雜網(wǎng)絡(luò)中時(shí)難以找到這種明顯的有序特征的。也就是說，復(fù)雜網(wǎng)絡(luò)可能包含各種各樣的子圖，這些子圖所占的比率明顯高于同一網(wǎng)絡(luò)的完全隨機(jī)化形式中這些子圖所占的比例。這些子圖被稱為模體。圖26 子圖和模體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ò)都是Scalefree網(wǎng)絡(luò)。如有的真實(shí)網(wǎng)絡(luò)度分布為指數(shù)分布截?cái)嘈问降鹊?。接下來的問題是：一個(gè)網(wǎng)絡(luò)中的不同模體之間是如何相互作用的？經(jīng)驗(yàn)表明，特定的模體類型聚集在一起形成大的模體簇，這可能也是大多數(shù)實(shí)際網(wǎng)絡(luò)中的一個(gè)通有特性[10]。為了說明許多實(shí)際系統(tǒng)中同時(shí)存在的模塊性、局部聚類和無標(biāo)度拓?fù)涮匦?，需要哪家社模塊以某種迭代的方式生成一個(gè)等級(jí)網(wǎng)絡(luò)（hierarchical network）。研究表明，一些網(wǎng)絡(luò)（如新陳代謝網(wǎng)絡(luò)）中的拓?fù)淠K確實(shí)是按等級(jí)組織起來的。需要注意的是，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ī)制。第3章 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的研究已經(jīng)有很長的歷史。它與計(jì)算機(jī)科學(xué)中的圖形分割（graph partition）和社會(huì)學(xué)中的分級(jí)聚類（hierarchical clustering）有著密切的關(guān)系。，前者主要包括KernighanLin算法和基于圖的Laplace矩陣特征向量的譜平分法(Spectral Bisection Method)；而后者則以著名的GN(GirvanNewman)算法為代表。 分級(jí)聚類分級(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]。 凝聚算法凝聚算法的基本思想是用某種方法計(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è)算法的流程也可以用世系圖或者樹狀圖來表示，如圖31所示。底部的各個(gè)圓代表了網(wǎng)絡(luò)中的各個(gè)幾點(diǎn)。當(dāng)水平虛線從樹的底端逐步上移，各個(gè)幾點(diǎn)也逐步聚合稱為更大的社團(tuán)，當(dāng)虛線移至頂部，即表示整個(gè)網(wǎng)絡(luò)就總體的稱為一個(gè)社團(tuán)。在該樹狀圖的任何一個(gè)位置用虛線斷開，就對(duì)應(yīng)著一種社團(tuán)結(jié)構(gòu)。圖31 凝聚方法通常采用樹狀圖來記錄算法的結(jié)果基于一系列相似性度量標(biāo)準(zhǔn)額凝聚方法已經(jīng)應(yīng)用于許多不同的網(wǎng)絡(luò)。一些網(wǎng)絡(luò)本身就有很多相似性度量標(biāo)準(zhǔn)。比如，在電影演員合作網(wǎng)絡(luò)中[1213]，如果兩個(gè)演員出現(xiàn)在同一部電影中，他們之間就有一條邊相連，這樣就可以用有多少電影演員同時(shí)出現(xiàn)在同一部電影中來度量節(jié)點(diǎn)的相似性[14]。而另外一些網(wǎng)絡(luò)雖然其本身沒有相似性的度量，但是可以利用相關(guān)系數(shù)、路徑長度或者一些矩陣的方法來設(shè)計(jì)一些適當(dāng)?shù)亩攘浚疚纳婕暗碾S機(jī)游走算法便可以算得上一種凝聚算法。 分裂算法相反的，在分裂算法中，一般是從所關(guān)注的網(wǎng)絡(luò)著手，試圖找到已連接的相似性最低的節(jié)點(diǎn)對(duì)，然后移除連接他們的邊。重復(fù)這個(gè)過程，就逐步把整個(gè)網(wǎng)絡(luò)分成越來越小的各個(gè)部分。同樣的，可以在任何情況下終止，并且把此狀態(tài)的網(wǎng)絡(luò)看做若干網(wǎng)絡(luò)社團(tuán)的集合。與凝聚方法類似，利用樹狀圖來表示分裂方法的流程，可以更好地描述整個(gè)網(wǎng)絡(luò)逐步分解為若干個(gè)越來越小的子群這一連續(xù)過程。 迭代二分法計(jì)算機(jī)科學(xué)中的一個(gè)典型問題，是將一個(gè)網(wǎng)絡(luò)分解成若干結(jié)點(diǎn)數(shù)基本相等的子網(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ù)。我們介紹兩個(gè)最具代表性的迭代二分法：一是KernighanLin算法，該算法使用貪婪策略對(duì)社區(qū)內(nèi)以及社區(qū)間的邊數(shù)進(jìn)行優(yōu)化，從而達(dá)到改進(jìn)網(wǎng)絡(luò)的初始分解的目的；另一個(gè)是基于圖的Laplace矩陣的特征向量的譜二分法(Spectral Bisection Method)。 KernighanLin 算法KernighanLin算法是一種試探優(yōu)化法。它基于貪婪算法原理將網(wǎng)絡(luò)劃分為兩個(gè)規(guī)模已知的社區(qū)。其基本思想是為網(wǎng)絡(luò)的劃分引進(jìn)一個(gè)增益函數(shù)Q，Q定義為兩個(gè)社區(qū)內(nèi)部的邊數(shù)減去連接兩個(gè)社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。整個(gè)算法可描述如下：首先，將網(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í)記錄交換以后的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)。KernighanLin算法最大的缺陷是要求事先知道兩個(gè)社區(qū)的規(guī)模，否則，就很可能不會(huì)得到正確的結(jié)果。這個(gè)缺陷使得它在實(shí)際網(wǎng)絡(luò)分析中難以應(yīng)用。而且，即使這個(gè)問題可以得到解決，它與所有的二分算法一樣，仍然面臨著如何事先知道網(wǎng)絡(luò)中的社區(qū)數(shù)目，以及二分要重復(fù)到哪一步停止的問題一個(gè)有n個(gè)結(jié)點(diǎn)的無向圖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．．．)?？梢詮睦碚撋献C明，不為零的特征值所對(duì)應(yīng)的特征向量的各元素中，同一個(gè)社區(qū)內(nèi)的結(jié)點(diǎn)對(duì)應(yīng)的元素是近似相等的。這就是譜平分法的理論基礎(chǔ)?？紤]網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的一種特殊情況：當(dāng)一個(gè)網(wǎng)絡(luò)中僅存在兩個(gè)社區(qū)，此時(shí)該網(wǎng)絡(luò)的Laplace矩陣L就對(duì)應(yīng)了兩個(gè)近似的對(duì)角矩陣塊。對(duì)一個(gè)實(shí)對(duì)稱矩陣而言，它的非退化的特征值對(duì)應(yīng)的特征向量總是正交的。因此，除了最小特征值0以外，矩陣L其他特征值對(duì)應(yīng)的特征向量總是包含正、負(fù)兩種元素。這樣，當(dāng)網(wǎng)絡(luò)由兩個(gè)社區(qū)構(gòu)成時(shí)，就可以根據(jù)非零特征值相應(yīng)的特征向量中的元素對(duì)應(yīng)網(wǎng)絡(luò)的結(jié)點(diǎn)進(jìn)行分類。其中，所有正元素對(duì)應(yīng)的那些結(jié)點(diǎn)都屬于同一個(gè)社區(qū)，而所有負(fù)元素對(duì)應(yīng)的結(jié)點(diǎn)則屬于另一個(gè)社區(qū)。因此，我們可以根據(jù)網(wǎng)絡(luò)的Laplace矩陣的第二小的特征值將其分為兩個(gè)社區(qū)。這就是譜平分法的基本思想。當(dāng)網(wǎng)絡(luò)的確是分成兩個(gè)社區(qū)時(shí)，用譜平分法可以得到非常好的效果。但是，當(dāng)網(wǎng)絡(luò)不滿足這個(gè)條件時(shí)，譜平分法的優(yōu)點(diǎn)就不能得到充分體現(xiàn)。事實(shí)上，第二小特征值可以作為衡量譜平分法效果的標(biāo)準(zhǔn)：它的值越小，平分的效果就越好。也稱為圖的代數(shù)連接度(Algebraic Connectivity)。一般情況下，計(jì)算一個(gè)矩陣的全部特征向量的時(shí)間復(fù)雜度為。但是在大多數(shù)情況下，實(shí)際網(wǎng)絡(luò)的Laplace矩陣是一個(gè)稀疏矩陣，因此，可以用Lanczos方法快速計(jì)算主要的特征向量。該方法的時(shí)間復(fù)雜度大致為，其