復雜網(wǎng)絡中的重疊社團發(fā)現(xiàn)問題研究.pdf

1、近年來復雜網(wǎng)絡的研究受到了越來越廣泛的關注，在計算機科學、物理學、生物學、數(shù)學乃至社會學和管理學等領域都產(chǎn)生了重大的意義和深遠的影響。過去由于技術上的限制，科學家的研究往往都停留在只有幾十、幾百個節(jié)點的小網(wǎng)絡上，研究方法大多是比較直觀的圖論方法。然而，隨著信息技術的高速發(fā)展，科學家所面臨的網(wǎng)絡數(shù)據(jù)規(guī)模呈現(xiàn)爆炸式的增長，獲取上億規(guī)模的網(wǎng)絡已經(jīng)變得非常容易。在大規(guī)模網(wǎng)絡數(shù)據(jù)的驅動下，網(wǎng)絡科學得到了長足的發(fā)展，并在未來擁有更大的發(fā)展?jié)摿?。社團

2、結構是復雜網(wǎng)絡所特有的一種中觀結構，在真實世界中，它往往對應著不同網(wǎng)絡的不同功能或結構單元。由于社團結構不僅是網(wǎng)絡的一種壓縮表示形式，更為網(wǎng)絡的其他分析挖掘提供了中觀尺度的分析視角，因而在大規(guī)模復雜網(wǎng)絡的各項研究中，社團結構研究是一項非常重要而基礎的工作。社團的重疊是真實世界網(wǎng)絡中常見的一種現(xiàn)象，例如一個人可以屬于多個興趣小組、一個蛋白質可以屬于多個蛋白復合體等等，因此發(fā)現(xiàn)網(wǎng)絡中的重疊社團結構更能準確地獲取網(wǎng)絡中真實的中觀結構信息。但是

3、，目前常見的各種重疊社團發(fā)現(xiàn)算法往往面臨著復雜度較高或準確率較低等問題。此外，重疊社團發(fā)現(xiàn)中重疊程度的控制及結果的穩(wěn)定性等問題也仍然有待解決。
　　本研究主要內容包括：⑴提出一種可控重疊程度的重疊社團發(fā)現(xiàn)算法。利用邊圖發(fā)現(xiàn)重疊社團是一種重要的研究思路，然而簡單的邊圖重疊社團發(fā)現(xiàn)方法并不能保證高質量的結果。本文在邊圖重疊社團發(fā)現(xiàn)思想的基礎上，進一步發(fā)現(xiàn)，盡管每條邊都可以通過邊圖下社團發(fā)現(xiàn)獲得社團標簽，但是處于社團之間的邊用于標識節(jié)點

4、的社團標簽時可能帶來噪音干擾。由此，我們提出一種在邊圖社團發(fā)現(xiàn)結果的基礎上迭代刪除社團間邊標簽的算法----CDAEO算法，一方面可以實現(xiàn)重疊社團發(fā)現(xiàn)結果準確率的提升，另一方面利用算法中的參數(shù)可以在一定范圍內調節(jié)社區(qū)團間的交叉重疊程度。⑵提出一種基于非重疊社團的節(jié)點中介度指標----社團中介度（communitybetweenness），并利用該指標設計了一種基于節(jié)點分裂的重疊社團發(fā)現(xiàn)算法一CBS算法。在社會網(wǎng)絡分析的研究中具有高中介度

5、的邊被認為是網(wǎng)絡中具有“橋”屬性的邊，著名的GN算法通過反復割斷中介度高的邊而達到非重疊社團發(fā)現(xiàn)的目的。之后有學者將GN算法延伸到分裂中介度較高的節(jié)點，從而發(fā)現(xiàn)重疊社團。盡管這些方法可以在許多真實網(wǎng)絡中得到有意義的社團結構，但是由于中介度指標的計算復雜度太高從而限制了它們在大網(wǎng)絡上的應用。針對這一問題，提出一種基于非重疊社團結構的局部中介度指標，即僅在一對社團的范圍內計算社團間節(jié)點的中介度，從而將中介度的計算限制在一個有意義的局部網(wǎng)絡之

6、內，大幅降低了中介度計算的時間復雜度，進而得到一種高效的重疊社團發(fā)現(xiàn)算法。⑶提出一種基于重疊節(jié)點條件的重疊社團發(fā)現(xiàn)算法----CONA算法。本文認為一個節(jié)點從非重疊節(jié)點變?yōu)橹丿B節(jié)點應該滿足社團結構的模塊化程度不被破壞這一基本條件，即社團結構的模塊化函數(shù)值至少不會降低?；谶@一發(fā)現(xiàn)，在選取EQ函數(shù)為重疊社團模塊度量函數(shù)的基礎上，我們通過理論推導得出了非重疊社團間及社團內的潛在重疊節(jié)點應滿足的條件，并利用該推導結果設計了一種高效的重疊社團發(fā)

7、現(xiàn)算法。實驗表明，該方法在巨型網(wǎng)絡上具有明顯的速度優(yōu)勢，而結果質量方面也往往優(yōu)于或至少近似于同類其他算法。⑷提出一種基于均衡多標簽傳播的重疊社團發(fā)現(xiàn)算法(BMLPA)。標簽傳播算法(LPA)是一個著名的接近線性時間復雜度的快速非重疊社團發(fā)現(xiàn)算法，其算法過程非常簡單明了。Steve將LPA延伸為可發(fā)現(xiàn)重疊社團結構的COPRA算法，繼承了LPA快速的優(yōu)良特性，但是也遺傳了LPA結果穩(wěn)定性差的問題。本文提出一種均衡多標簽傳播算法，不僅可以在某