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