發(fā)布時(shí)間：2016-08-20 06:16

第 1 章   緒     論 

1.1  課題研究背景和意義 
用網(wǎng)絡(luò)的觀點(diǎn)來描述現(xiàn)實(shí)世界，最早可以追溯到 1736 年瑞典數(shù)學(xué)家歐拉對(duì)著名的數(shù)學(xué)問題“哥尼斯堡七橋問題”的研究，并由此開創(chuàng)了數(shù)學(xué)研究領(lǐng)域中的一個(gè)重要分支—圖論[1]（Graph Theory）的研究。隨著圖論研究的深入，隨機(jī)圖理論（Random Graph Theory）開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究[2]。因此越來越多的研究人員開始關(guān)注網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性及其與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間的關(guān)系，其中文獻(xiàn)[3]揭示了復(fù)雜網(wǎng)絡(luò)所具有的“小世界”和“無標(biāo)度”等特殊性質(zhì)。圖(Graph)作為一種描述網(wǎng)絡(luò)的統(tǒng)一工具，被廣泛應(yīng)用于研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)上的共性。通過圖的表示形式，可以將任何一個(gè)網(wǎng)絡(luò)看作是由若干個(gè)節(jié)點(diǎn)通過特定的方式連接在一起所構(gòu)成的圖，這種表述方法不僅有很好的體現(xiàn)節(jié)點(diǎn)間的連接關(guān)系，同時(shí)還能呈現(xiàn)出清晰的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，因此圖的表示形式已經(jīng)廣泛的應(yīng)用于對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行建模和分析的過程中。 近年來，復(fù)雜網(wǎng)絡(luò)理論已經(jīng)成為分析網(wǎng)絡(luò)關(guān)系復(fù)雜性等相關(guān)問題的重要方法之一。復(fù)雜網(wǎng)絡(luò)的一個(gè)重要的特性就是網(wǎng)絡(luò)所呈現(xiàn)的社區(qū)結(jié)構(gòu)，所謂的社區(qū)結(jié)構(gòu)可以理解為關(guān)聯(lián)個(gè)體的集合，而復(fù)雜網(wǎng)絡(luò)則是由若干個(gè)社區(qū)組成。對(duì)于“社區(qū)”這個(gè)概念，，通常情況下認(rèn)為[4][20]“社區(qū)內(nèi)部的節(jié)點(diǎn)之間的連接相對(duì)比較緊密，各個(gè)社區(qū)之間的連接相對(duì)比較稀疏”。隨著對(duì)復(fù)雜網(wǎng)絡(luò)物理意義和數(shù)學(xué)特性的深入研究，研究人員發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中蘊(yùn)含著許多豐富的資源和潛在的信息，有效的利用這些信息具有很極高的商業(yè)價(jià)值和研究意義。然而，隨著社交網(wǎng)絡(luò)，生物信息網(wǎng)等新生應(yīng)用網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，現(xiàn)有的社區(qū)發(fā)現(xiàn)算法已經(jīng)不能滿足網(wǎng)絡(luò)規(guī)模達(dá)到數(shù)十億個(gè)節(jié)點(diǎn)的處理需求，因此如何高效的對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)已經(jīng)成為一個(gè)重要問題。由于現(xiàn)有算法普遍為串行算法，在對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)時(shí)，算法的處理效率較差，無法高效的處理大量的中間計(jì)算過程，同時(shí)社區(qū)發(fā)現(xiàn)的精確度也得不到很好的保障。 
........

1.2  國內(nèi)外研究現(xiàn)狀 
復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)技術(shù)已經(jīng)廣泛應(yīng)用于社會(huì)學(xué)、生物醫(yī)學(xué)、計(jì)算機(jī)科學(xué)等諸多領(lǐng)域。例如在生物醫(yī)學(xué)研究中，識(shí)別癌癥患者蛋白質(zhì)功能組。在社會(huì)學(xué)研究中，通過社區(qū)發(fā)現(xiàn)分析人際交往的關(guān)系網(wǎng)絡(luò)等等。 復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的研究最早可以追溯到社會(huì)學(xué)中的研究工作[5]，大量的研究表明，實(shí)際網(wǎng)絡(luò)中所蘊(yùn)含的社區(qū)結(jié)構(gòu)往往具有特殊的功能。社區(qū)發(fā)現(xiàn)實(shí)際上就是通過網(wǎng)絡(luò)中不同節(jié)點(diǎn)的連接關(guān)系，將它們劃分到不同的社區(qū)中，因此對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)具有很高的應(yīng)用價(jià)值。隨著對(duì)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題研究的不斷深入，研究人員通過圖論等相關(guān)成熟理論來解決社區(qū)發(fā)現(xiàn)問題，產(chǎn)生了大量不同類型的社區(qū)發(fā)現(xiàn)算法。根據(jù)處理網(wǎng)絡(luò)方式的不同，復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法可以分為兩類：基于全局信息的社區(qū)發(fā)現(xiàn)算法和基于局部信息的社區(qū)發(fā)現(xiàn)算法。全局社區(qū)發(fā)現(xiàn)算法主要采用了圖論中圖劃分的思想，通過對(duì)整個(gè)網(wǎng)絡(luò)的劃分形成社區(qū)結(jié)構(gòu)，代表算法有 GN 算法[4]，KL 算法[18]等經(jīng)典算法，這類算法通常算法復(fù)雜度比較高，并且基于全局信息考慮的社區(qū)發(fā)現(xiàn)算法并不適合對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)。局部社區(qū)發(fā)現(xiàn)算法主要通過盡可能少的網(wǎng)絡(luò)局部信息實(shí)現(xiàn)社區(qū)結(jié)構(gòu)的劃分。局部社區(qū)發(fā)現(xiàn)算法的基本思路是：首先選擇初始節(jié)點(diǎn)的社區(qū)擴(kuò)展集，然后根據(jù)局部的評(píng)判標(biāo)準(zhǔn)選擇初始節(jié)點(diǎn)進(jìn)行社區(qū)合并等操作。經(jīng)典算法包括基于模塊度優(yōu)化的 LM[38]算法，基于拉普拉斯矩陣譜分析的社區(qū)發(fā)現(xiàn)算法和基于標(biāo)簽傳播思想 RAK[14]算法，其中 LM 算法結(jié)合了模塊度優(yōu)化與層次聚類的思想，能夠快速，準(zhǔn)確的對(duì)不同規(guī)模的復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)，并且社區(qū)發(fā)現(xiàn)結(jié)果具有一定的層次結(jié)構(gòu)特性，該算法是當(dāng)前社區(qū)發(fā)現(xiàn)算法研究中重要的參考對(duì)象。
.........

第 2 章   相關(guān)工作和技術(shù) 

2.1  復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)理論
從圖論的角度來說，復(fù)雜網(wǎng)絡(luò)是一個(gè)由大量節(jié)點(diǎn)通過復(fù)雜的連接關(guān)系互相連接形成的圖，因此復(fù)雜網(wǎng)絡(luò)的研究核心主要是通過圖的表示形式揭示復(fù)雜網(wǎng)絡(luò)功能和結(jié)構(gòu)之間的內(nèi)在關(guān)系。通過圖的表示形式可以反映出網(wǎng)絡(luò)中不同類型的節(jié)點(diǎn)，例如在社交網(wǎng)絡(luò)中，圖中的節(jié)點(diǎn)代表不同的個(gè)體，而邊表示不同人之間的熟悉程度。根據(jù)網(wǎng)絡(luò)是否存在權(quán)值及節(jié)點(diǎn)間的指代關(guān)系，又將圖分為有權(quán)或無權(quán)，無向或有向圖。 社區(qū)發(fā)現(xiàn)技術(shù)的研究最早源于社會(huì)學(xué)的研究工作[5]，本文根據(jù) Fortunato[6]的綜述文獻(xiàn)，對(duì)現(xiàn)有算法進(jìn)行了詳細(xì)的總結(jié)與比較，將現(xiàn)有研究方法分為以下幾類：2002 年 Newman 和 Girvan 提出的模塊度[7]  這個(gè)社區(qū)評(píng)價(jià)標(biāo)準(zhǔn)以后，才真正意義上的推動(dòng)了復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)的研究。在此之后產(chǎn)生了大量基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)算法，這些算法的主要思想是將社區(qū)發(fā)現(xiàn)問題轉(zhuǎn)化成優(yōu)化問題，將模塊度定義為評(píng)價(jià)社區(qū)劃分好壞的質(zhì)量函數(shù)，通過比較模塊度數(shù)值獲取最優(yōu)的社區(qū)劃分結(jié)構(gòu)。根據(jù)層次聚類的思想，模塊度優(yōu)化算法主要分為兩類，第一類算法采用凝聚法，算法自下而上執(zhí)行，代表算法有 Fast-GN[7]算法、CNM[8]算法。Fast-GN 算法將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)看作一個(gè)獨(dú)立的社區(qū)，對(duì)產(chǎn)生最大模塊度的兩個(gè)節(jié)點(diǎn)進(jìn)行聚類，算法是一個(gè)貪心迭代的過程，最終的社區(qū)結(jié)構(gòu)可以表示成一個(gè)樹狀圖，算法的時(shí)間復(fù)雜度為O m mn 。CNM 算法采用了更高效的堆數(shù)據(jù)結(jié)構(gòu)對(duì)模塊度值進(jìn)行存儲(chǔ)，提高算法的執(zhí)行效率并減少對(duì)存儲(chǔ)空間的需求。隨后 Blondel[38]結(jié)合了模塊度優(yōu)化與層次聚類思想提出了 Louvain  method 算法，算法具有計(jì)算速度快，社區(qū)發(fā)現(xiàn)結(jié)果準(zhǔn)確性高等特性，是目前基于優(yōu)化模塊度最好的算法。第二類算法采用分裂法，算法自上而下執(zhí)行.代表算法為 Newman 最早提出的 GN[4]算法，算法通過刪除網(wǎng)絡(luò)中邊介數(shù)最大的邊，實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)，但是算法的復(fù)雜度較高3O n ，并且只能處理無權(quán)網(wǎng)絡(luò)。隨著對(duì)模塊度研究的深入，研究人員發(fā)現(xiàn)模塊度優(yōu)化方法不能發(fā)現(xiàn)小于一定粒度的社區(qū)結(jié)構(gòu)[10][11]，Duan[12]應(yīng)用不同相關(guān)性度量方法，改進(jìn)了以模塊度為標(biāo)準(zhǔn)的質(zhì)量函數(shù)，有效的克服了社區(qū)發(fā)現(xiàn)過程中模塊度分辨率問題。 
............

2.2  圖的著色理論

圖著色問題[34]作為圖論中的經(jīng)典問題，具有廣泛的實(shí)際應(yīng)用背景，許多實(shí)際問題，例如任務(wù)調(diào)度問題[36]，存儲(chǔ)問題[37]等都可以抽象成圖著色問題，同時(shí)圖著色問題也是一種組合優(yōu)化問題，由于圖的著色問題具有廣泛的應(yīng)用性，因此對(duì)圖的著色問題進(jìn)行深入的研究具有重要意義[22]。圖著色問題可以分為兩種問題，一是求圖的著色數(shù)問題，另一種是給定著色數(shù) k，要求對(duì)圖中的節(jié)點(diǎn)或邊進(jìn)行著色。圖著色主要優(yōu)化的目標(biāo)是使用最少的著色數(shù)，而著色數(shù)與圖的規(guī)模，節(jié)點(diǎn)度，最大節(jié)點(diǎn)度以及孤點(diǎn)個(gè)數(shù)有著緊密的關(guān)系 在圖著色算法中，對(duì)圖的節(jié)點(diǎn)著色算法是目前解決圖著色問題最主要的方法之一。對(duì)于無向圖來說，用 n 種顏色為圖中所有節(jié)點(diǎn)進(jìn)行著色，要求相鄰節(jié)點(diǎn)之間著色情況不同，并且盡可能少的使用不同顏色為所有節(jié)點(diǎn)著色，這個(gè)過程成為圖的節(jié)點(diǎn)著色過程。節(jié)點(diǎn)著色算法主要利用了極大獨(dú)立集的思想，規(guī)定每個(gè)同色集合中兩兩節(jié)點(diǎn)不相鄰，同色節(jié)點(diǎn)集實(shí)際上是一個(gè)獨(dú)立集，當(dāng)我們用一種顏色上色時(shí)，為了盡可能擴(kuò)大顏色 1 的頂點(diǎn)數(shù)，到達(dá)顏色數(shù)使用最少的目的，實(shí)際上就是找到圖的一個(gè)極大獨(dú)立集并為他上顏色1，用第 2 種顏色上色時(shí)，同樣選擇另一個(gè)極大獨(dú)立集著色，當(dāng)所有節(jié)點(diǎn)著色完畢，所用的著色數(shù)即所選的極大獨(dú)立集的個(gè)數(shù)。 

..............

第 3 章   基于模塊度的社區(qū)發(fā)現(xiàn)并行化方法研究 ........... 11 
3.1  模塊度優(yōu)化函數(shù) ....... 11 
3.2 LM 算法社區(qū)發(fā)現(xiàn)算法 ....... 13 
3.2.1  算法思想 ............ 13 
3.2.2  算法執(zhí)行流程 .... 13 
3.3  并行作業(yè)劃分 ........... 15
3.4  基于模塊度的節(jié)點(diǎn)狀態(tài)更新機(jī)制 ......... 17 
3.5  動(dòng)態(tài)負(fù)載劃分 ........... 19 
3.6  本章小結(jié) ......... 19 
第 4 章   基于 OPENMP 的并行社區(qū)發(fā)現(xiàn)算法設(shè)計(jì) ........ 20 
4.1  并行 LM 社區(qū)發(fā)現(xiàn)算法 ..... 20 
4.1.1  算法思想和執(zhí)行流程 ............ 20 
4.2  數(shù)據(jù)結(jié)構(gòu) ......... 21 
4.2.1  傳統(tǒng)的圖數(shù)據(jù)結(jié)構(gòu) ...... 21 
4.2.2  改進(jìn)的圖數(shù)據(jù)結(jié)構(gòu) ...... 22 
4.3  算法設(shè)計(jì) ......... 23
4.4  算法復(fù)雜度分析 ....... 29 
4.5  本章小結(jié) ......... 30 
第 5 章   實(shí)驗(yàn)和測(cè)試分析 ........... 31
5.1  實(shí)驗(yàn)平臺(tái) ......... 31 
5.2  算法實(shí)現(xiàn) ......... 31 
5.3  實(shí)驗(yàn)數(shù)據(jù)集 ..... 33 
5.4  對(duì)比算法 ......... 33 
5.5  實(shí)驗(yàn)結(jié)果和分析 ....... 34 

第 5 章   實(shí)驗(yàn)和測(cè)試分析 

5.1  實(shí)驗(yàn)平臺(tái) 
本文將實(shí)驗(yàn)平臺(tái)建立在吉林大學(xué)高性能中心計(jì)算的刀片服務(wù)器的計(jì)算節(jié)點(diǎn)上。具體的實(shí)驗(yàn)環(huán)境如下： 操作系統(tǒng)：Redhat Linux version 2.6.32-358.el6. x86_64； CPU：Intel(R) Xeon(R) E5-2670，16 核，主頻為 2.60GHz，內(nèi)存：32G。 網(wǎng)絡(luò)環(huán)境：實(shí)驗(yàn)室與計(jì)算節(jié)點(diǎn)之間通過千兆以太網(wǎng)互相連接，通過 SSH 與 VNC 遠(yuǎn)程登錄計(jì)算節(jié)點(diǎn)。本文提出的并行社區(qū)發(fā)現(xiàn)算法 P-LM 是基于 Open MP 共享內(nèi)存編程方式實(shí)現(xiàn)的，算法通過 GCC 編譯器編譯后，可以通過 Linux 命令行的方式控制算法不同階段的執(zhí)行方式，實(shí)現(xiàn)了一個(gè)可以對(duì)不同類型的大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行計(jì)算與分析的工具。 如圖 5.1 所示，通過輸入控制選項(xiàng)—f，輸出輸入數(shù)據(jù)的基本信息。例如輸入數(shù)據(jù)的節(jié)點(diǎn)數(shù)，邊數(shù)，最大節(jié)點(diǎn)度，平均節(jié)點(diǎn)度，特殊節(jié)點(diǎn)個(gè)數(shù)等基本信息。 如圖 5.2 所示，通過輸入控制選項(xiàng)—cp，對(duì)輸入數(shù)據(jù)進(jìn)行粗粒度預(yù)處理過程，也就是將網(wǎng)絡(luò)中孤點(diǎn)以及節(jié)點(diǎn)度為 1 的特殊節(jié)點(diǎn)進(jìn)行優(yōu)先，并且對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行重新編號(hào)。這樣做記錄了下一階段算法進(jìn)行著色過程時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)與邊數(shù)，并且我們發(fā)現(xiàn)由于部分節(jié)點(diǎn)進(jìn)行了社區(qū)合并，使得網(wǎng)絡(luò)的平均節(jié)點(diǎn)度發(fā)生了變化。 
.........

總結(jié) 

隨著信息技術(shù)的迅猛發(fā)展，現(xiàn)實(shí)世界中充滿著各種各樣的復(fù)雜網(wǎng)絡(luò)。由于復(fù)雜網(wǎng)絡(luò)中存在較強(qiáng)的社區(qū)結(jié)構(gòu)，因此對(duì)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的研究室人們可以更好地理解復(fù)雜網(wǎng)絡(luò)的數(shù)學(xué)意義與物理特征。 本文詳實(shí)的介紹了復(fù)雜網(wǎng)絡(luò)的相關(guān)知識(shí)以及并行社區(qū)發(fā)現(xiàn)算法的相關(guān)研究，在現(xiàn)有基于模塊度優(yōu)化的 LM 社區(qū)發(fā)現(xiàn)算法的基礎(chǔ)上，提出了一個(gè)面向大規(guī)模復(fù)雜網(wǎng)絡(luò)的并行社區(qū)發(fā)現(xiàn)算法（PLM），算法主要通過 Open MP 共享內(nèi)存思想實(shí)現(xiàn)并行的。不同于 LM串行算法順序選取節(jié)點(diǎn)計(jì)算模塊度增量，本文提出基于圖著色的并行作業(yè)劃分方法，對(duì)節(jié)點(diǎn)進(jìn)行著色處理，對(duì)不直接相鄰的節(jié)點(diǎn)并行計(jì)算它們的模塊度最大增量。還對(duì)根據(jù)模塊度進(jìn)行社區(qū)合并與信息更新的過程進(jìn)行了優(yōu)化，提出了節(jié)點(diǎn)狀態(tài)更新機(jī)制以及粗粒度的預(yù)處理過程。最后為了優(yōu)化并行算法的計(jì)算效率，提出了基于節(jié)點(diǎn)度的動(dòng)態(tài)負(fù)載劃分方法。
.........
參考文獻(xiàn)(略)  

本文編號(hào)：98625