【正文】 方式，即在以任意節(jié)點i 為起點進行有限步數(shù)的隨機游走，在有限的步數(shù)內，相比于在不同的社團間的隨機游走，該隨機游走是有更大的可能性是停留在同一個社團內部的。第四章 基于隨機游走的社團發(fā)現(xiàn)算法本章主要介紹一種基于圖論的隨機游走（random walk）算法[1516]，主要介紹了該隨機游走算法的基本原理，以及隨機游走算法的編譯實現(xiàn)方式。實證研究表明，社會網(wǎng)絡中三角環(huán)的數(shù)量比較大，而在非社會網(wǎng)絡中，三角環(huán)的數(shù)量則相對較少。Radicchi 算法每一步去除的是網(wǎng)絡中邊聚集系數(shù)最小的邊，每次去除后，再重新計算每一條邊的邊聚集系數(shù)，如此進行下去，直至網(wǎng)絡中不存在任何邊。但是由于連接不同社區(qū)的邊非常稀少，將一條邊的邊聚集系數(shù)定義為包含該邊的三角環(huán)所占比例： （31）其中，分別表示節(jié)點i 和j 的度，表示網(wǎng)絡中實際包含該邊的三角環(huán)的個數(shù)。Radicchi 等考慮網(wǎng)絡中的三角環(huán)(即邊數(shù)為3 的閉合路徑)。整個算法的運行時間為。整個算法完成后可得到一個社區(qū)結構分解的樹狀圖，再通過選擇在不同位置斷開可得到不同的網(wǎng)絡社區(qū)結構，在這些社區(qū)結構中，選擇一個對應著局部最大的Q值，就得到最好的網(wǎng)絡社區(qū)結構。Newman 在GN 算法的基礎上提出了一種快速算法，它是基于貪婪算法思想的一種凝聚算法。缺點：在不知道社區(qū)數(shù)目的情況下，此算法也不能確定迭代的合適步數(shù)。它為區(qū)分一個社區(qū)內部邊和外部邊連接提供了一個度量準則。 其他經(jīng)典算法 GN（GirvanNewman）算法GN 算法是一種分裂方法，它通過迭代從網(wǎng)絡中移除介數(shù)(Betweenness)最大的邊將整個網(wǎng)絡分解為各個社區(qū)。但是，如果不能很快將從其它特征值中分離出來，該算法就可能在一定程度上有所減慢。該方法的時間復雜度大致為，其中，m表示網(wǎng)絡中邊的條數(shù)。一般情況下，計算一個矩陣的全部特征向量的時間復雜度為。事實上，第二小特征值可以作為衡量譜平分法效果的標準：它的值越小，平分的效果就越好。當網(wǎng)絡的確是分成兩個社區(qū)時，用譜平分法可以得到非常好的效果。因此，我們可以根據(jù)網(wǎng)絡的Laplace矩陣的第二小的特征值將其分為兩個社區(qū)。這樣，當網(wǎng)絡由兩個社區(qū)構成時，就可以根據(jù)非零特征值相應的特征向量中的元素對應網(wǎng)絡的結點進行分類。對一個實對稱矩陣而言，它的非退化的特征值對應的特征向量總是正交的。這就是譜平分法的理論基礎。L矩陣所有的行與列的和都為0，因此，該矩陣總有一個特征值為0，其對應的特征向量為l=(1，1，1．．．)。其中，L的對角線上的元素是結點i的度，而其他非對角線上的元素則表示結點i和結點j的連接關系。這個缺陷使得它在實際網(wǎng)絡分析中難以應用。這時對應的社區(qū)結構就認為是該網(wǎng)絡實際的社區(qū)結構。不過，即使某一步的交換會使Q值有所下降，但是仍然可能在其后的步驟中出現(xiàn)一個更大的Q值。重復這個交換過程，直到某個社區(qū)內所有的結點都被交換一次為止。對每個結點對，計算如果交換這兩個結點的話可能得到的Q的增益，然后交換最大的△Q對應的結點對，同時記錄交換以后的Q值。整個算法可描述如下：首先，將網(wǎng)絡中的結點隨機地劃分為已知規(guī)模的兩個社區(qū)。它基于貪婪算法原理將網(wǎng)絡劃分為兩個規(guī)模已知的社區(qū)。我們介紹兩個最具代表性的迭代二分法：一是KernighanLin算法，該算法使用貪婪策略對社區(qū)內以及社區(qū)間的邊數(shù)進行優(yōu)化，從而達到改進網(wǎng)絡的初始分解的目的；另一個是基于圖的Laplace矩陣的特征向量的譜二分法(Spectral Bisection Method)。圖分割問題(GPP)可應用于并行計算機的處理器合理分配進程。與凝聚方法類似，利用樹狀圖來表示分裂方法的流程，可以更好地描述整個網(wǎng)絡逐步分解為若干個越來越小的子群這一連續(xù)過程。重復這個過程，就逐步把整個網(wǎng)絡分成越來越小的各個部分。而另外一些網(wǎng)絡雖然其本身沒有相似性的度量，但是可以利用相關系數(shù)、路徑長度或者一些矩陣的方法來設計一些適當?shù)亩攘?，本文涉及的隨機游走算法便可以算得上一種凝聚算法。一些網(wǎng)絡本身就有很多相似性度量標準。在該樹狀圖的任何一個位置用虛線斷開，就對應著一種社團結構。底部的各個圓代表了網(wǎng)絡中的各個幾點。這個過程可以中止與任何一點，此時這個網(wǎng)絡的組成就認為是若干個社團。根據(jù)往網(wǎng)絡中添加邊還是移除邊，該類算法又可以分為兩類：凝聚算法（agglomerative method）和分裂算法（division method）[11]。前者主要包括KernighanLin算法和基于圖的Laplace矩陣特征向量的譜平分法(Spectral Bisection Method)；而后者則以著名的GN(GirvanNewman)算法為代表。第3章 復雜網(wǎng)絡中的社團結構網(wǎng)絡社團結構的研究已經(jīng)有很長的歷史。需要注意的是，ER隨機圖和BA無標度網(wǎng)絡都不具有等級拓撲，在這兩類網(wǎng)絡中的節(jié)點系數(shù)C(k)與該節(jié)點的度k無關。為了說明許多實際系統(tǒng)中同時存在的模塊性、局部聚類和無標度拓撲特性，需要哪家社模塊以某種迭代的方式生成一個等級網(wǎng)絡（hierarchical network）。如有的真實網(wǎng)絡度分布為指數(shù)分布截斷形式等等。之后，許多學者對這一模型進行了改進，如非線性擇優(yōu)連接、加速增長、重繞邊的局域事件、逐漸老化、適應性競爭等等。這些子圖被稱為模體。這些正方形子圖反映了方格子的基本特征結構，而在有明顯隨機性連接的復雜網(wǎng)絡中時難以找到這種明顯的有序特征的。子圖描繪了從局部層次刻畫一個給定網(wǎng)絡的互聯(lián)的特定模式。模塊式如何構成的呢？近期研究表明，模體（motif）可能是復雜網(wǎng)絡的基本模塊[79]。 模塊性和等級網(wǎng)絡為了研究網(wǎng)絡的模塊性，我們需要相應的工具和度量以確定一個網(wǎng)絡是否是模塊化的，并且能夠清晰的辨識一個給定的網(wǎng)絡中的模塊以及模塊之間的關系。需要注意的是，絕大多數(shù)而不是所有的真實網(wǎng)絡都是Scalefree網(wǎng)絡。BA模型的提出是復雜網(wǎng)絡研究中的又一重大突破，標志著人們對客觀網(wǎng)絡世界認識的深入。他們不僅給出了BA模型的生成算法并進行了模擬分析，而且還利用統(tǒng)計物理中的平均場方法給出了模型的解析解。為解釋Scalefree網(wǎng)絡的形成機制，Barabasi和Albert提出了著名的BA模型[6]。實證結果卻表明對于大多數(shù)大規(guī)模真實網(wǎng)絡用冪率分布來描述它們的度分布更加精確。他們通過將規(guī)則網(wǎng)絡中的每條邊以概率p隨機連接到網(wǎng)絡中的一個新節(jié)點上，構造出一種介于規(guī)則網(wǎng)絡和隨機網(wǎng)絡之間的網(wǎng)絡（簡稱WS網(wǎng)絡），它同時具有較小的平均路徑長度和較大的聚集系數(shù)，而規(guī)則網(wǎng)絡和隨機網(wǎng)絡則分別是WS網(wǎng)絡在p為0和1時的特例?？梢娨?guī)則網(wǎng)絡和隨機網(wǎng)絡并不能很好展現(xiàn)真實網(wǎng)絡的性質，這說明現(xiàn)實世界既不是完全確定的也不是完全隨機的。然而，規(guī)則網(wǎng)絡雖具有聚集性，平均最短路徑卻較大。隨機網(wǎng)絡模型的提出是網(wǎng)絡研究中的重大成果，但它仍不能很好的刻畫實際網(wǎng)絡的性質，人們又相繼提出了一些新的網(wǎng)絡模型。在這些社區(qū)內部，結點之間的聯(lián)系非常緊密，而社區(qū)之間的聯(lián)系就稀疏的多。每個群內的結點之間的連接非常緊密，而群之間的連接卻相對比較稀疏，如圖24所示。隨著對網(wǎng)絡性質的物理意義和數(shù)學特性的深入研究，人們發(fā)現(xiàn)許多實際網(wǎng)絡都具有一個共同性質——社團結構。對于社團劃分的準確的計算如下所示，假設一個復雜網(wǎng)絡已經(jīng)分成數(shù)個社團，對于每個社團i，遍歷i中所有的節(jié)點并找出每個節(jié)點最常發(fā)生的真實的標簽，這個標簽便被稱作社團中節(jié)點v的預期的標簽。以上所述算法最終目的均是把網(wǎng)絡劃分為若干個相互分離的社區(qū)，但是現(xiàn)實中很多網(wǎng)絡并不存在絕對的彼此獨立的社區(qū)結構，相反它們是由許多彼此重疊且相互關聯(lián)的社區(qū)構成。而這個節(jié)點間的實際存在的邊數(shù)為和總的可能的邊數(shù)(1)/2之比就定義為節(jié)點i的聚類系數(shù)，即 （23）從幾何特點上看，上式的一個等價定義為 （24）其中，與節(jié)點i相連的三元組是指包括節(jié)點i的三個節(jié)點，并且至少存在從節(jié)點i到其他兩個節(jié)點的兩條邊（圖23）。一般的，假設網(wǎng)絡中的一個節(jié)點i有條邊將他和其他節(jié)點相連，這個節(jié)點就稱為節(jié)點i的鄰居。圖22 一個簡單網(wǎng)絡的直徑和平局路徑長度 聚類系數(shù)聚集系數(shù)C用來描述網(wǎng)絡中節(jié)點的聚集情況，即網(wǎng)絡有多緊密。它描述了網(wǎng)絡中節(jié)點間的分離程度，即網(wǎng)絡有多小。圖21 不同類型網(wǎng)絡的例子(a) 單一類型節(jié)點和邊的無向網(wǎng)絡 (b)不同類型節(jié)點和邊的無向網(wǎng)絡 (c)節(jié)點和邊權重變化的無向網(wǎng)絡 (d)有向網(wǎng)絡 平均路徑長度網(wǎng)絡研究中一般定義兩節(jié)點i和j間的距離為連接兩個節(jié)點的最短路徑的邊數(shù)，網(wǎng)絡的直徑為任意兩點間的距離的最大值，記為D，即 （21）網(wǎng)絡的平均路徑長度L則定義為任意兩個節(jié)點對之間距離的平均值，即 （22）其中N為網(wǎng)絡節(jié)點數(shù)。圖21給出了幾種不同類型的網(wǎng)絡的例子。當然無權網(wǎng)絡也可以看做每條邊權值都為1的等權網(wǎng)絡。如果任意點對（i，j）和（j，i）對應同一條邊，則該網(wǎng)絡稱為無向網(wǎng)絡（），否則稱為有向網(wǎng)絡。節(jié)點數(shù)記為N = | V |，邊數(shù)記為M = | E |。在這里先介紹復雜網(wǎng)絡的這幾種性質，其他性質后面會陸續(xù)介紹。實際上，Watts和Strogatz提出小世界網(wǎng)絡模型的初衷就是建立一個既具有類似于隨機圖的較少的平均路徑長度，又具有類似于規(guī)則網(wǎng)絡的較大的聚類系數(shù)的網(wǎng)絡模型。第6章 主要介紹了在random walk算法基礎上的改進，使random walk算法能夠實現(xiàn)：對有權的復雜網(wǎng)絡的社團結構的劃分；減少算法的復雜度。找到并且分析這些子群，有助于我們更好地理解網(wǎng)絡的全局行為第4章 主要提出了基于圖論的隨機游走（random walk）算法，研究隨機游走算法的基本原理，以及對隨機游走算法的編譯。大多數(shù)的實際網(wǎng)絡都具有社團結構。第3章 主要針對Internet 中的拓撲結構提出來一些模型。具體內容如下：第2章 介紹了一些復雜網(wǎng)絡的圖表示、度分布、平均最短路徑和社區(qū)結構等基本概念和基本性