第 1 章   緒     論 

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

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

第 2 章   相關工作和技術 

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

2.2  圖的著色理論

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

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

第 3 章   基于模塊度的社區(qū)發(fā)現并行化方法研究 ........... 11 
3.1  模塊度優(yōu)化函數 ....... 11 
3.2 LM 算法社區(qū)發(fā)現算法 ....... 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  本章小結 ......... 19 
第 4 章   基于 OPENMP 的并行社區(qū)發(fā)現算法設計 ........ 20 
4.1  并行 LM 社區(qū)發(fā)現算法 ..... 20 
4.1.1  算法思想和執(zhí)行流程 ............ 20 
4.2  數據結構 ......... 21 
4.2.1  傳統(tǒng)的圖數據結構 ...... 21 
4.2.2  改進的圖數據結構 ...... 22 
4.3  算法設計 ......... 23
4.4  算法復雜度分析 ....... 29 
4.5  本章小結 ......... 30 
第 5 章   實驗和測試分析 ........... 31
5.1  實驗平臺 ......... 31 
5.2  算法實現 ......... 31 
5.3  實驗數據集 ..... 33 
5.4  對比算法 ......... 33 
5.5  實驗結果和分析 ....... 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，內存：32G。 網絡環(huán)境：實驗室與計算節(jié)點之間通過千兆以太網互相連接，通過 SSH 與 VNC 遠程登錄計算節(jié)點。本文提出的并行社區(qū)發(fā)現算法 P-LM 是基于 Open MP 共享內存編程方式實現的，算法通過 GCC 編譯器編譯后，可以通過 Linux 命令行的方式控制算法不同階段的執(zhí)行方式，實現了一個可以對不同類型的大規(guī)模網絡數據集進行計算與分析的工具。 如圖 5.1 所示，通過輸入控制選項—f，輸出輸入數據的基本信息。例如輸入數據的節(jié)點數，邊數，最大節(jié)點度，平均節(jié)點度，特殊節(jié)點個數等基本信息。 如圖 5.2 所示，通過輸入控制選項—cp，對輸入數據進行粗粒度預處理過程，也就是將網絡中孤點以及節(jié)點度為 1 的特殊節(jié)點進行優(yōu)先，并且對網絡中的節(jié)點進行重新編號。這樣做記錄了下一階段算法進行著色過程時網絡中節(jié)點數與邊數，并且我們發(fā)現由于部分節(jié)點進行了社區(qū)合并，使得網絡的平均節(jié)點度發(fā)生了變化。 
.........

總結 

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

本文編號：98625