《基於改進的GN算法的社區發現技術》是楊立文撰寫的一篇論文。
基本介紹
- 中文名：基於改進的GN算法的社區發現技術
- 論文來源：吉林大學
- 發表時間：2012
- 作者：楊立文
- 分類號：TP391.3
論文摘要,引文格式,
論文摘要
近年來，複雜網路已經成為科學研究中非常重要的研究領域。典型的複雜網路包括社會網路、生物網路、交通網路和信息網路等。這些網路都具有較強的社區結構，因此發現社區結構有助於我們了解網路的其他特性，從而幫助我們開發和利用這些網路。另外，隨著複雜網路尤其是英特網的迅速發展，所要處理的信息量不斷增加，這使得搜尋信息的操作變得尤為複雜，所以如何能夠快速搜尋到所需信息成為搜尋的關鍵問題，而社區發現技術正是解決這個問題的有效方法。目前，大多數已知的社區發現算法都是串列的，普遍存在速度慢、效率低的缺陷。然而，隨著多核技術的發展，以及在面臨所處理的信息越來越多的實際情況下，並行社區發現算法會比串列社區發現算法獲得更快的效率，可以有效地克服串列算法的局限性。針對上述問題，本文採用並行化策略對經典社區發現算法，即傳統的GN (Givern-Newman)算法進行了改進。這兩種並行策略分別為粗粒度並行策略和細粒度並行策略，均與計算邊介數（full-betweenness,betweenness）相關。第一種方法，即粗粒度並行，分別從不同的源節點出發，並行的計算每條邊的邊介數（betweenness），然後將每條邊的從所有不同的源節點出發計算出的邊介數（betweenness）累加起來，得到的這個累加和就是每條邊的相對於所有源節點的邊介數（full-betweenness）。第二種方法，即細粒度並行，是在計算每條邊的相對於一個源節點的邊介數（betweenness）的時候，採用並行的搜尋方法以及並行的回溯求和方法。從理論上分析，傳統的GN算法是一種基於重複移除邊的疊代的社區發現算法，我們提出的兩種方法都可以減少每次疊代的計算時間。然後，本文選擇對粗粒度並行算法加以實現，通過實驗對比以粗粒度方式並行的GN算法相對於傳統的GN算法的加速效果。實驗結果表明粗粒度並行的方法在四核處理器上具有明顯的加速效果，並且不會影響算法的準確性。
引文格式
楊立文. 基於改進的GN算法的社區發現技術[D].吉林大學,2012.
