【正文】 圖52 Risk的關(guān)系網(wǎng)絡(luò) 對(duì)復(fù)雜網(wǎng)絡(luò)的劃分在劃分復(fù)雜網(wǎng)絡(luò)過(guò)程中，我們分別對(duì)空手道俱樂(lè)部社團(tuán)以及Risk的關(guān)系網(wǎng)絡(luò)進(jìn)行劃分，依次得到如圖53，圖54的結(jié)果：圖53 算法所劃分出的空手道俱樂(lè)部的社團(tuán)結(jié)構(gòu)圖54 算法所劃分出的Risk社團(tuán)結(jié)構(gòu)根據(jù)所得出的算法結(jié)果，我們重新對(duì)空手道俱樂(lè)部，以及Risk社團(tuán)結(jié)構(gòu)進(jìn)行劃分，得出如圖55，圖56的結(jié)果：圖55 算法所劃分出的空手道俱樂(lè)部的社團(tuán)結(jié)構(gòu) 圖56 算法所劃分出的Risk網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)如圖55所示，對(duì)于空手道俱樂(lè)部的復(fù)雜網(wǎng)絡(luò)，隨機(jī)游走算法非常有效的將網(wǎng)絡(luò)劃分為兩個(gè)與實(shí)際情況幾乎完全一致的社團(tuán)（只有節(jié)點(diǎn)3被錯(cuò)誤的歸類(lèi)）。然而，我們從圖中可以看到，節(jié)點(diǎn)3處于兩個(gè)社團(tuán)的交界處，而且都分別通過(guò)四條邊與兩個(gè)社團(tuán)相連，因此，它本身就有一定的歧義性。對(duì)于Risk網(wǎng)絡(luò)雖然在幾次劃分的社團(tuán)結(jié)構(gòu)的過(guò)程中，有所錯(cuò)誤與偏差，但是我們?cè)诮?jīng)過(guò)多次劃分后，仍然可以得到完全正確的Risk網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，這對(duì)于算法的有效性上給予了很好的證明。 隨機(jī)游走算法的復(fù)雜度在隨機(jī)游走的過(guò)程中，我們可以看到隨機(jī)游走算法的復(fù)雜度，假設(shè)隨機(jī)游走的長(zhǎng)度被定義為l，那么我們定義隨機(jī)游走的復(fù)雜度為O(ln)。由于上文我們已經(jīng)介紹過(guò)復(fù)雜網(wǎng)絡(luò)中隨機(jī)游走步數(shù)設(shè)為有限的幾步就可以了，因此我們可以有效的將復(fù)雜度設(shè)為O(n)，但是在我們進(jìn)行矩陣融合的過(guò)程中，即使用我們形容的平均長(zhǎng)度融合的過(guò)程中，使得我們形容的復(fù)雜度最終成為。這種復(fù)雜度使得此類(lèi)算法不適用于對(duì)于大型的復(fù)雜網(wǎng)絡(luò)的劃分。因此我們需要將復(fù)雜度降低到我們可以接受的程度，此類(lèi)改進(jìn)將在下一章進(jìn)行介紹。第6章 基于隨機(jī)游走算法的程序優(yōu)化如上文介紹，我們?cè)诮y(tǒng)計(jì)隨機(jī)游走算法的復(fù)雜度時(shí)，我們得到通過(guò)相似度矩陣的最大值來(lái)融合矩陣的方式，但是的復(fù)雜度使隨機(jī)游走的算法并不適用于超大型的網(wǎng)絡(luò)，除此之外我們上兩章節(jié)介紹的隨機(jī)游走算法只是基于無(wú)權(quán)值網(wǎng)絡(luò)，并不適用于有權(quán)值的網(wǎng)絡(luò)，這也是我們需要改進(jìn)的地方。 隨機(jī)游走算法的復(fù)雜度的優(yōu)化在上文中我們可以看到，導(dǎo)致復(fù)雜度變高的主要是在每次遍歷的過(guò)程中都要需要相似度矩陣的最大值，如圖61所示：圖61 在每次隨機(jī)游走后都尋找矩陣中的最大值這導(dǎo)致隨機(jī)游走算法的復(fù)雜度上升為，為了降低此算法的復(fù)雜度，我們提出一種新的融合方式，即設(shè)定一個(gè)相似度元素的臨界值i，我們將所有的社團(tuán)間相似度的值大于i的社團(tuán)進(jìn)行融合，從而得到我們需要的最終結(jié)果。如圖62所示：圖62 改進(jìn)后的找尋下一對(duì)要融合的社團(tuán)算法改進(jìn)后我們，我們可以看到我們不必再每次隨機(jī)游走后在相似度矩陣中去尋找新得到的相似度矩陣的最大值元素S[i][j]，因此我們可以看到經(jīng)過(guò)我們改進(jìn)的算法復(fù)雜度，在很大程度上的減少了。以最壞的打算，我們需要n1次選擇融合，我們也可以將算法的復(fù)雜度從減少到O(n)。作為總結(jié)，我們提出這一隨機(jī)游走算法的改進(jìn)，可以很有效率的將大型復(fù)雜網(wǎng)絡(luò)進(jìn)行劃分，但是由于我們未知大型復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的劃分，所以我們對(duì)于這種改進(jìn)后的隨機(jī)游走算法對(duì)大型復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分的準(zhǔn)確度仍是未知的。 隨機(jī)游走算法的應(yīng)用于加權(quán)網(wǎng)絡(luò)我們上文中介紹的隨機(jī)游走算法在尋找節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j時(shí)，只是對(duì)于無(wú)權(quán)值的網(wǎng)絡(luò)來(lái)說(shuō)的。正如我們上面章節(jié)所述，在選擇節(jié)點(diǎn)i的所有所有鄰居節(jié)點(diǎn)時(shí)，我們是等概率的隨機(jī)的去選擇節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中的一個(gè)鄰居節(jié)點(diǎn)j。但是我們忽略了有權(quán)網(wǎng)絡(luò)中邊的權(quán)重對(duì)于我們一次隨機(jī)游走同屬于一個(gè)社團(tuán)的影響。因此，在選擇節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j時(shí)，我們要加入邊的權(quán)重的影響，假設(shè)節(jié)點(diǎn)i對(duì)鄰居節(jié)點(diǎn)j的邊的權(quán)重為x（i，j），那么我們將不再是等概率的隨機(jī)選擇節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，相反的，我們是通過(guò)權(quán)重的計(jì)算來(lái)重新給點(diǎn)每個(gè)鄰居節(jié)點(diǎn)被選擇的概率p，如公式61所示 （61）同時(shí)我們可以看到，所有的鄰居節(jié)點(diǎn)的概率p的和其實(shí)為1，在重新選擇鄰居節(jié)點(diǎn)時(shí)，我們便按照我們公式61計(jì)算出的各自節(jié)點(diǎn)的概率來(lái)選擇隨機(jī)游走過(guò)程中的下一個(gè)節(jié)點(diǎn)。在算法實(shí)現(xiàn)過(guò)程中，也進(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é)到了很多東西。首先是通過(guò)這次畢設(shè)中對(duì)復(fù)雜網(wǎng)絡(luò)算法的研究，讓我初步了解了復(fù)雜玩了過(guò)的基本概念和原理，同時(shí)也學(xué)到了使用比較優(yōu)化的復(fù)雜網(wǎng)絡(luò)社團(tuán)查找算法來(lái)劃分復(fù)雜網(wǎng)絡(luò)的社團(tuán)，并且在學(xué)習(xí)這些算法的過(guò)程中也體會(huì)到了不同算法之間的聯(lián)系與差異。并通過(guò)C語(yǔ)言來(lái)實(shí)現(xiàn)次我主要學(xué)習(xí)的隨機(jī)游走算法，在算法的實(shí)現(xiàn)過(guò)程中也遇到了不少問(wèn)題，但最后都一一解決，并實(shí)現(xiàn)了預(yù)期的功能。最后我還通過(guò)學(xué)習(xí)，實(shí)現(xiàn)了對(duì)于隨機(jī)游走算法方面的改進(jìn)，使得隨機(jī)游走算法的復(fù)雜度降低，能夠夠有效率的劃分復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。同時(shí)使得隨機(jī)游走算法可以應(yīng)用于有權(quán)的隨機(jī)網(wǎng)絡(luò)中。在整個(gè)畢設(shè)過(guò)程中，我遇到了不少挑戰(zhàn)，其中最大的就是對(duì)于隨機(jī)游走算法的理解與實(shí)現(xiàn)。由于初次接觸隨機(jī)游走算法，一些細(xì)節(jié)把握的不是很準(zhǔn)確，在實(shí)現(xiàn)過(guò)程中經(jīng)常遇到困難。但在明確了隨機(jī)游走算法的基本原理，以及實(shí)現(xiàn)方式后才有所改善。其次是C語(yǔ)言開(kāi)發(fā)能力，這成了我開(kāi)發(fā)過(guò)程中的另一大阻礙，但在一段時(shí)間的摸索后，基本能夠熟練運(yùn)用C語(yǔ)言進(jìn)行開(kāi)發(fā)。當(dāng)然，目前所做的一些開(kāi)發(fā)工作還有很多地方需要改進(jìn)，例如隨機(jī)游走算法優(yōu)化還不夠徹底，不夠深入；對(duì)于復(fù)雜網(wǎng)絡(luò)的知識(shí)還掌握的不很熟練，在后面的學(xué)習(xí)和工作中還需要進(jìn)一步學(xué)習(xí)。 對(duì)未來(lái)的展望在此次畢設(shè)的過(guò)程中，我也對(duì)復(fù)雜網(wǎng)絡(luò)有了初步的了解，理解了復(fù)雜網(wǎng)絡(luò)在當(dāng)今各個(gè)研究領(lǐng)域中的重要的應(yīng)用。同時(shí)，由于越來(lái)越強(qiáng)大的計(jì)算機(jī)技術(shù)，學(xué)科之間的相互交叉，以及還原論和整體論相結(jié)合為特色的復(fù)雜性科學(xué)的興起，都使得復(fù)雜網(wǎng)絡(luò)的研究在現(xiàn)今社會(huì)有了突破性的進(jìn)展。長(zhǎng)期以往，通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)等分別通信科學(xué)、電力科學(xué)、生命科學(xué)和社會(huì)學(xué)等不同學(xué)科之間的共性和處理他們的樸實(shí)方法。從20世紀(jì)末開(kāi)始，復(fù)雜網(wǎng)絡(luò)研究正滲透到數(shù)理學(xué)科、生命學(xué)科和工程學(xué)科等眾多不同的領(lǐng)域，對(duì)于復(fù)雜網(wǎng)絡(luò)的定量與定性特性的科學(xué)理解，已經(jīng)成為網(wǎng)絡(luò)時(shí)代科學(xué)研究中的一個(gè)極為重要的挑戰(zhàn)性課題。在未來(lái)的時(shí)間里，對(duì)于大型復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分的算法，一定會(huì)出現(xiàn)復(fù)雜度更低，劃分效果更好地算法。在此篇論文中，我們對(duì)于復(fù)雜網(wǎng)絡(luò)劃分算法的研究仍然停留在一個(gè)較為淺顯的層次中，只有在以后的學(xué)習(xí)中加深對(duì)于復(fù)雜網(wǎng)絡(luò)的理解，才能夠?qū)φ撐闹械碾S機(jī)游走算法有進(jìn)一步更好地改進(jìn)。除此之外希望在以后的研究生生活中，能夠更好地學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)相關(guān)的知識(shí)，加深相關(guān)發(fā)面的了解，提出更好地算法。參考文獻(xiàn)[1] Barabasu A L..The New Science of : Persus .[2] Watts D J. The 39。new39。 science of networks. Annual Review of :243270.[3] 王丹,:5759.[4] 汪小凡,李翔,:146.[5] Watts D J. Strogatz S H. Colective dynamics of 39。smallworld39。 (6684). 1998:440442.[6] Barabasi, Albert. Emergence of scaling in random networks. (5439),1999:509521.[7] 劉濤,陳忠,:16.[8] 駱志剛,丁凡,蔣曉舟,:4751.[9] :5861.[10] Kashtan N, Itzkovitz S,Milo R, Alon U. Topological Generalizations of network motifs. Phys. Rev. :101114.[11] Scott J. Social Network Analysis:A handbook. London: Sage .[12] Marcgiori M, Latora V. Harmony in the smallworld. Physica :539549.[13] Amaral L A N,Scala A. Classes of smallworld networks. Proc. Natl, Acad. :1114911152[14] Breiger R L,Boorman S A, Arabie P. An algorithm for clustering relations data with applications to social network analysis and parison with multidimensional scaling. Journal of Mathematical Psychology1975:328383.[15] Karsten Steinhaeuser,Nitesh V,Chawla: Identifying and evaluating munity structure in plex Recognition .[16] BingJing Cai, HaiYing Wang,HuiRu Zheng,Hui Improved Random Walk Based Clustering Algorithm for Community Detection in Complex :21622167. 致謝我對(duì)能夠來(lái)到的實(shí)驗(yàn)室感到非常的榮幸，并非常高興能在這里繼續(xù)自己的研究生學(xué)習(xí)。對(duì)于本次畢業(yè)設(shè)計(jì)和論文寫(xiě)作，我非常感謝老師幫我融入了泛在實(shí)驗(yàn)室的科研氛圍，使我能夠很快的適應(yīng)實(shí)驗(yàn)室生活。并在隨機(jī)游走算法的理解以及實(shí)現(xiàn)上給與我很多的幫助。我還要感謝同學(xué)的幫助。他們?cè)谖已芯繌?fù)雜網(wǎng)絡(luò)以及隨機(jī)游走算法的過(guò)程中給予了我多的鼓勵(lì)和幫助。尤其是在我實(shí)現(xiàn)隨機(jī)游走算法的過(guò)程中給予了我很多啟發(fā)性的幫助。最后，我還要感謝我的家人，沒(méi)有他們長(zhǎng)久以來(lái)的支持和鼓勵(lì)，我不可能順利完成大學(xué)學(xué)業(yè)。謹(jǐn)以此文獻(xiàn)給我的家人。35