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

第 1 章   緒     論 

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

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

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

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

2.2  圖的著色理論

圖著色問題[34]作為圖論中的經(jīng)典問題，具有廣泛的實際應用背景，許多實際問題，例如任務調(diào)度問題[36]，存儲問題[37]等都可以抽象成圖著色問題，同時圖著色問題也是一種組合優(yōu)化問題，由于圖的著色問題具有廣泛的應用性，因此對圖的著色問題進行深入的研究具有重要意義[22]。圖著色問題可以分為兩種問題，一是求圖的著色數(shù)問題，另一種是給定著色數(shù) k，要求對圖中的節(jié)點或邊進行著色。圖著色主要優(yōu)化的目標是使用最少的著色數(shù)，而著色數(shù)與圖的規(guī)模，節(jié)點度，最大節(jié)點度以及孤點個數(shù)有著緊密的關(guān)系 在圖著色算法中，對圖的節(jié)點著色算法是目前解決圖著色問題最主要的方法之一。對于無向圖來說，用 n 種顏色為圖中所有節(jié)點進行著色，要求相鄰節(jié)點之間著色情況不同，并且盡可能少的使用不同顏色為所有節(jié)點著色，這個過程成為圖的節(jié)點著色過程。節(jié)點著色算法主要利用了極大獨立集的思想，規(guī)定每個同色集合中兩兩節(jié)點不相鄰，同色節(jié)點集實際上是一個獨立集，當我們用一種顏色上色時，為了盡可能擴大顏色 1 的頂點數(shù)，到達顏色數(shù)使用最少的目的，實際上就是找到圖的一個極大獨立集并為他上顏色1，用第 2 種顏色上色時，同樣選擇另一個極大獨立集著色，當所有節(jié)點著色完畢，所用的著色數(shù)即所選的極大獨立集的個數(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é)點狀態(tài)更新機制 ......... 17 
3.5  動態(tài)負載劃分 ........... 19 
3.6  本章小結(jié) ......... 19 
第 4 章   基于 OPENMP 的并行社區(qū)發(fā)現(xiàn)算法設(shè)計 ........ 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  改進的圖數(shù)據(jù)結(jié)構(gòu) ...... 22 
4.3  算法設(shè)計 ......... 23
4.4  算法復雜度分析 ....... 29 
4.5  本章小結(jié) ......... 30 
第 5 章   實驗和測試分析 ........... 31
5.1  實驗平臺 ......... 31 
5.2  算法實現(xiàn) ......... 31 
5.3  實驗數(shù)據(jù)集 ..... 33 
5.4  對比算法 ......... 33 
5.5  實驗結(jié)果和分析 ....... 34 

第 5 章   實驗和測試分析 

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

總結(jié) 

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

本文編號：98625