【正文】 實(shí)際應(yīng)用中，大多數(shù)圖分割方法均基于迭代二分法：首先將圖按要求分割成2個(gè)子圖，然后再分別對(duì)這2個(gè)子圖進(jìn)行分割，如此迭代下去直至獲得所要求的子圖個(gè)數(shù)。 KernighanLin 算法KernighanLin算法是一種試探優(yōu)化法。其基本思想是為網(wǎng)絡(luò)的劃分引進(jìn)一個(gè)增益函數(shù)Q，Q定義為兩個(gè)社區(qū)內(nèi)部的邊數(shù)減去連接兩個(gè)社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。在此基礎(chǔ)上，考慮所有可能的結(jié)點(diǎn)對(duì)，其中每個(gè)結(jié)點(diǎn)對(duì)的結(jié)點(diǎn)分別來自兩個(gè)社區(qū)。規(guī)定每個(gè)結(jié)點(diǎn)只能交換一次。需要注意的是，在結(jié)點(diǎn)對(duì)交換的過程中，Q值并不一定總是單調(diào)增加的。當(dāng)交換完畢后，便找到上述交換過程中所記錄的最大的Q值。KernighanLin算法最大的缺陷是要求事先知道兩個(gè)社區(qū)的規(guī)模，否則，就很可能不會(huì)得到正確的結(jié)果。而且，即使這個(gè)問題可以得到解決，它與所有的二分算法一樣，仍然面臨著如何事先知道網(wǎng)絡(luò)中的社區(qū)數(shù)目，以及二分要重復(fù)到哪一步停止的問題一個(gè)有n個(gè)結(jié)點(diǎn)的無向圖G的Laplace矩陣是一個(gè)維的對(duì)稱矩陣L。如果這兩個(gè)結(jié)點(diǎn)之間有邊連接，則值為1，否則為0?？梢詮睦碚撋献C明，不為零的特征值所對(duì)應(yīng)的特征向量的各元素中，同一個(gè)社區(qū)內(nèi)的結(jié)點(diǎn)對(duì)應(yīng)的元素是近似相等的?？紤]網(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ì)角矩陣塊。因此，除了最小特征值0以外，矩陣L其他特征值對(duì)應(yīng)的特征向量總是包含正、負(fù)兩種元素。其中，所有正元素對(duì)應(yīng)的那些結(jié)點(diǎn)都屬于同一個(gè)社區(qū)，而所有負(fù)元素對(duì)應(yīng)的結(jié)點(diǎn)則屬于另一個(gè)社區(qū)。這就是譜平分法的基本思想。但是，當(dāng)網(wǎng)絡(luò)不滿足這個(gè)條件時(shí)，譜平分法的優(yōu)點(diǎn)就不能得到充分體現(xiàn)。也稱為圖的代數(shù)連接度(Algebraic Connectivity)。但是在大多數(shù)情況下，實(shí)際網(wǎng)絡(luò)的Laplace矩陣是一個(gè)稀疏矩陣，因此，可以用Lanczos方法快速計(jì)算主要的特征向量。這樣，計(jì)算的速度可以得到很大程度的提高。換句話說，當(dāng)網(wǎng)絡(luò)很明顯地分成兩個(gè)社區(qū)時(shí)，該算法的速度非常快，否則該算法就未必很有效。邊的介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過該邊的最短路徑的數(shù)目。GN算法的基本流程如下：(i) 計(jì)算網(wǎng)絡(luò)中的所有邊的介數(shù)；(ii) 找到介數(shù)最高的邊并將它從網(wǎng)絡(luò)中移除；(iii) 重復(fù)步驟(ii)，直到每個(gè)節(jié)點(diǎn)就是一個(gè)退化社區(qū)為止。 Newman快速算法由于GN 算法的時(shí)間復(fù)雜度較大，所以對(duì)大規(guī)模的復(fù)雜網(wǎng)絡(luò)的分析效果并不理想。此算法總的時(shí)間復(fù)雜度為。該算法與GN 算法相同，都是基于去邊，但不是根據(jù)邊介數(shù)選擇要去除的邊，而是引進(jìn)了邊聚集系數(shù)的新指標(biāo)。顯然，對(duì)于稀疏圖，其計(jì)算速度要比GN算法快一個(gè)數(shù)量級(jí)。若一個(gè)三角環(huán)包含一條連接不同社區(qū)的邊，則該三角環(huán)中的另兩條邊中的某一條仍然連接這兩個(gè)社區(qū)的可能性將很大。上式中的分母表示包含該邊的最大可能的三角環(huán)的個(gè)數(shù)。Radicchi 算法的不足是該算法依賴于網(wǎng)絡(luò)中的三角環(huán)，如果網(wǎng)絡(luò)中三角環(huán)很少，那么該算法將失去意義。這意味著Radicchi 算法更加適合于社會(huì)網(wǎng)絡(luò)。 隨機(jī)游走算法的基本原理在上一章節(jié)對(duì)各種社團(tuán)發(fā)現(xiàn)算法的介紹和比較后，我們?cè)诖颂岢鲆环N完全基于隨機(jī)游走來實(shí)現(xiàn)社團(tuán)劃分的算法。我們通過記錄在每次隨機(jī)游走過程中的軌跡來作為節(jié)點(diǎn)間屬于同一個(gè)社團(tuán)的證據(jù)。 隨機(jī)游走算法的相似度矩陣獲取隨機(jī)游走的基本思想是進(jìn)行多次一段較短步數(shù)的隨機(jī)游走，并且把在同一次隨機(jī)游走過程中經(jīng)歷的節(jié)點(diǎn)作為他們同屬于一個(gè)社團(tuán)的證據(jù)。算法的過程中，我們首先定義的矩陣S，把矩陣中的每一個(gè)元素S[i][j]都賦值為0。在隨機(jī)游走算法的過程中，我們從節(jié)點(diǎn)i開始進(jìn)行隨機(jī)游走，隨機(jī)游走即從節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)中等概率的找到它的一個(gè)鄰居節(jié)點(diǎn)，作為隨機(jī)游走的下一個(gè)節(jié)點(diǎn)。根據(jù)得到的集合C，我們隨機(jī)的選擇集合C中不相等的元素i，j，來作為相似度矩陣S的行號(hào)和列號(hào)，即S[i][j]。以此遍歷復(fù)雜網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，得到n個(gè)集合C，并最終得出矩陣S的值。S[i][j]值越大，表示i，j屬于一個(gè)社團(tuán)的可能性便越大。在融合矩陣的過程中，把每次融合的節(jié)點(diǎn)數(shù)進(jìn)行記錄到新的集合C中，在矩陣融合結(jié)束后，集合C中記錄的便是復(fù)雜網(wǎng)絡(luò)最終的社團(tuán)結(jié)構(gòu)的劃分。這種方式的普遍觀念是根據(jù)相似度矩陣中的元素的相似度的大小來進(jìn)行融合。融合矩陣的算法在圖42中給出。矩陣在相應(yīng)行（列）融合的過程中也在不斷地進(jìn)行變化。 矩陣元素融合方式在此我們提醒讀者關(guān)于我們討論的在融合社團(tuán)過程中，為相似矩陣計(jì)算的新的距離的方法。如果我們假設(shè)社團(tuán)i和社團(tuán)j要被融合，讓作為新的新的社團(tuán)結(jié)構(gòu)到某個(gè)社團(tuán)k的距離。 隨機(jī)游走算法的代碼編譯過程 隨機(jī)游走算法的相似度矩陣的獲取在算法實(shí)現(xiàn)過程中，生成所有節(jié)點(diǎn)的哈希表以及所有邊的哈希表。圖43 算法中對(duì)于點(diǎn)和邊的哈希表中元素的定義同時(shí)我們使用qsort函數(shù)來獲取按邊的起點(diǎn)的序號(hào)排列的新的邊的哈希表。獲得新的邊的哈希表之后，我們?cè)诿看坞S機(jī)游走過程中，以節(jié)點(diǎn)i作為一次隨機(jī)游走的起點(diǎn)，每次從對(duì)應(yīng)的邊的哈希表中找到以節(jié)點(diǎn)i作為起點(diǎn)的邊，在這些邊中獲得相應(yīng)邊的終點(diǎn)，即節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，從這些節(jié)點(diǎn)中等概的選取一個(gè)節(jié)點(diǎn)j作為隨機(jī)游走過程中下一次的節(jié)點(diǎn)。其次，第一，隨機(jī)游走算法是基于大型復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分，為了以后更好地應(yīng)用于大型復(fù)雜網(wǎng)絡(luò)中，以及減少算法的復(fù)雜度方面；第二，所得到的相似度矩陣式系數(shù)矩陣。矩陣定義如圖44圖44 算法中對(duì)于矩陣的定義最終通過每次隨機(jī)游走獲得的集合C，在已知的鏈表中進(jìn)行相對(duì)應(yīng)的處理，得到相似度矩陣S。） 隨機(jī)游走算法的相似度矩陣融合通過上一小節(jié)，我們得到了需要的相似度矩陣S，我們現(xiàn)階段的工作便是將相似度矩陣進(jìn)行融合。在融合后刪除Maxcol行以及Maxcol列。在每次融合的過程中，我們定義了另外一個(gè)帶行指針數(shù)組的鏈表來G存儲(chǔ)我們?nèi)诤线^程中結(jié)果，即每次融合社團(tuán)i和社團(tuán)j之后，帶行指針數(shù)組的鏈表G相應(yīng)的改變，將Maxcol中的鏈表移動(dòng)到到Maxcol后，刪除Maxcol中的鏈表。圖46 記錄矩陣融合過程中的社團(tuán)結(jié)構(gòu)在矩陣S中沒有非零元素后，完成最終的矩陣融合。第五章 隨機(jī)游走算法在社團(tuán)劃分中的應(yīng)用本章主要介紹隨機(jī)游走算法應(yīng)用于已知社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)的劃分，并得出劃分結(jié)果和比較劃分的準(zhǔn)確度。 隨機(jī)游走算法對(duì)復(fù)雜網(wǎng)絡(luò)的劃分 已知社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò) 空手道俱樂部的關(guān)系網(wǎng)絡(luò)20世紀(jì)70年代初期，Zachary用來兩年的時(shí)間來觀察美國(guó)一所大學(xué)中的空手道俱樂部成員間的相互社會(huì)關(guān)系。事有湊巧，在他調(diào)查過程中，該俱樂部的主管與校長(zhǎng)之間因是否太高俱樂部收費(fèi)的問題產(chǎn)生了政治。圖51中的節(jié)點(diǎn)1和節(jié)點(diǎn)33分別代表了俱樂部的主管和校長(zhǎng)，而方形和圓形的節(jié)點(diǎn)也分別代表了分裂后的小俱樂部中的各個(gè)社團(tuán)的成員。圖52 Risk的關(guān)系網(wǎng)絡(luò) 對(duì)復(fù)雜網(wǎng)絡(luò)的劃分在劃分復(fù)雜網(wǎng)絡(luò)過程中，我們分別對(duì)空手道俱樂部社團(tuán)以及Risk的關(guān)系網(wǎng)絡(luò)進(jìn)行劃分，依次得到如圖53，圖54的結(jié)果：圖53 算法所劃分出的空手道俱樂部的社團(tuán)結(jié)構(gòu)圖54 算法所劃分出的Risk社團(tuán)結(jié)構(gòu)根據(jù)所得出的算法結(jié)果，我們重新對(duì)空手道俱樂部，以及Risk社團(tuán)結(jié)構(gòu)進(jìn)行劃分，得出如圖55，圖56的結(jié)果：圖55 算法所劃分出的空手道俱樂部的社團(tuán)結(jié)構(gòu) 圖56 算法所劃分出的Risk網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)如圖55所示，對(duì)于空手道俱樂部的復(fù)雜網(wǎng)絡(luò)，隨機(jī)游走算法非常有效的將網(wǎng)絡(luò)劃分為兩個(gè)與實(shí)際情況幾乎完全一致的社團(tuán)（只有節(jié)點(diǎn)3被錯(cuò)誤的歸類）。對(duì)于Risk網(wǎng)絡(luò)雖然在幾次劃分的社團(tuán)結(jié)構(gòu)的過程中，有所錯(cuò)誤與偏差，但是我們?cè)诮?jīng)過多次劃分后，仍然可以得到完全正確的Risk網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，這對(duì)于算法的有效性上給予了很好的證明。由于上文我們已經(jīng)介紹過復(fù)雜網(wǎng)絡(luò)中隨機(jī)游走步數(shù)設(shè)為有限的幾步就可以了，因此我們可以有效的將復(fù)雜度設(shè)為O(n)，但是在我們進(jìn)行矩陣融合的過程中，即使用我們形容的平均長(zhǎng)度融合的過程中，使得我們形容的復(fù)雜度最終成為。因此我們需要將復(fù)雜度降低到我們可以接受的程度，此類改進(jìn)將在下一章進(jìn)行介紹。 隨機(jī)游走算法的復(fù)雜度的優(yōu)化在上文中我們可以看到，導(dǎo)致復(fù)雜度變高的主要是在每次遍歷的過程中都要需要相似度矩陣的最大值，如圖61所示：圖61 在每次隨機(jī)游走后都尋找矩陣中的最大值這導(dǎo)致隨機(jī)游走算法的復(fù)雜度上升為，為了降低此算法的復(fù)雜度，我們提出一種新的融合方式，即設(shè)定一個(gè)相似度元素的臨界值i，我們將所有的社團(tuán)間相似度的值大于i的社團(tuán)進(jìn)行融合，從而得到我們需要的最終結(jié)果。以最壞的打算，我們需要n1次選擇融合，我們也可以將算法的復(fù)雜度從減少到O(n)。 隨機(jī)游走算法的應(yīng)用于加權(quán)網(wǎng)絡(luò)我們上文中介紹的隨機(jī)游走算法在尋找節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j時(shí)，只是對(duì)于無權(quán)值的網(wǎng)絡(luò)來說的。但是我們忽略了有權(quán)網(wǎng)絡(luò)中邊的權(quán)重對(duì)于我們一次隨機(jī)游走同屬于一個(gè)社團(tuán)的影響。在算法實(shí)現(xiàn)過程中，也進(jìn)行了相應(yīng)的改進(jìn)如圖63所示圖63 改進(jìn)后的求相應(yīng)節(jié)點(diǎn)概率的算法實(shí)現(xiàn)第七章 總結(jié)與展望 總結(jié)本次畢業(yè)設(shè)計(jì)讓我收獲很多，畢設(shè)中，我遇到了很多挑戰(zhàn)，也讓我發(fā)現(xiàn)了自身的一些不足，學(xué)到了很多東西。并通過C語言來實(shí)現(xiàn)次我主要學(xué)習(xí)的隨機(jī)游走算法，在算法的實(shí)現(xiàn)過程中也遇到了不少問題，但最后都一一解決，并實(shí)現(xiàn)了預(yù)期的功能。同時(shí)使得隨機(jī)游走算法可以應(yīng)用于有權(quán)的隨機(jī)網(wǎng)絡(luò)中。由于初次接觸隨機(jī)游走算法，一些細(xì)節(jié)把握的不是很準(zhǔn)確，在實(shí)現(xiàn)過程中經(jīng)常遇到困難。其次是C語言開發(fā)能力，這成了我開發(fā)過程中的另一大阻礙，但在一段時(shí)間的摸索后，基本能夠熟練運(yùn)用C語言進(jìn)行開發(fā)。 對(duì)未來的展望在此次畢設(shè)的過程中，我也對(duì)復(fù)雜網(wǎng)絡(luò)有了初步的了解，理解了復(fù)雜網(wǎng)絡(luò)在當(dāng)今各個(gè)研究領(lǐng)域中的重要的應(yīng)用。長(zhǎng)期以往，通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)等分別通信科學(xué)、電力科學(xué)、生命科學(xué)和社會(huì)學(xué)等不同學(xué)科之間的共性和處理他們的樸實(shí)方法。在未來的時(shí)間里，對(duì)于大型復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分的算法，一定會(huì)出現(xiàn)復(fù)雜度更低，劃分效果更好地算法。除此之外希望在以后的研究生生活中，能夠更好地學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)相關(guān)的知識(shí)，加深相關(guān)發(fā)面的了解，提出更好地算法。new39。smallworld39。對(duì)于本次畢業(yè)設(shè)計(jì)和論文寫作，我非常感謝老師幫我融入了泛在實(shí)驗(yàn)室的科研氛圍，使我能夠很快的適應(yīng)實(shí)驗(yàn)室生活。我還要感謝同學(xué)的幫助。尤其是在我實(shí)現(xiàn)隨機(jī)游走算法的過程中給予了我很多啟發(fā)性的幫助。謹(jǐn)以此文獻(xiàn)給我的家人