基于局部近鄰傳播及用戶特征的社區(qū)識別算法

郭昆，郭文忠，邱啟榮，張岐山

(1. 福州大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院, 福建 福州 350108； 2. 福州大學(xué) 管理學(xué)院, 福建 福州 350108)

1 引言

近年來，以微博、Facebook、Youtube和Twitter等為代表的社交網(wǎng)絡(luò)服務(wù)（SNS, social network service）在世界范圍內(nèi)得到迅速發(fā)展，越來越多人開始通過社交網(wǎng)絡(luò)進(jìn)行在線聊天、購物、聚會等活動。在社交網(wǎng)絡(luò)中識別具有相近的年齡、背景、興趣等特征的用戶組成的社區(qū)，不僅在理論上是對復(fù)雜網(wǎng)絡(luò)聚類研究的進(jìn)一步深化和發(fā)展，在實踐上對基于社交網(wǎng)絡(luò)的搜索、推薦等商業(yè)應(yīng)用也具有重要意義。因此，基于社交網(wǎng)絡(luò)的社區(qū)識別已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的一個研究熱點。

廣義上，社交網(wǎng)絡(luò)上的社區(qū)識別可以看作是一種復(fù)雜網(wǎng)絡(luò)上的聚類[1]或圖上的社區(qū)識別[2]。但社交網(wǎng)絡(luò)也有一些其自身獨有的特點。首先，社交網(wǎng)絡(luò)通常具有龐大的用戶群，例如，F(xiàn)acebook和騰訊微博的用戶數(shù)量均達(dá)到億級。這對社交網(wǎng)絡(luò)上的社區(qū)識別算法的時間和空間復(fù)雜度提出了更加嚴(yán)格的要求，通常要求算法的復(fù)雜度降低至接近線性才能有效處理具有億級節(jié)點的網(wǎng)絡(luò)，而目前具有線性復(fù)雜度的算法還不多見[2]。其次，社交網(wǎng)絡(luò)具有顯著的動態(tài)性，網(wǎng)絡(luò)內(nèi)部節(jié)點及節(jié)點之間的聯(lián)系經(jīng)常隨時間、地點而不斷變化，這意味著任何一次數(shù)據(jù)采樣只能得到某一個時間段某一部分用戶和用戶關(guān)聯(lián)信息的樣本數(shù)據(jù)。目前，多數(shù)復(fù)雜網(wǎng)絡(luò)聚類算法均假設(shè)數(shù)據(jù)分析在一個完整的網(wǎng)絡(luò)上進(jìn)行，當(dāng)部分節(jié)點和邊的信息缺失時，數(shù)據(jù)分析的準(zhǔn)確性將受到不同程度的影響。最后，社交網(wǎng)絡(luò)的一個顯著特點是每個用戶節(jié)點都包含描述用戶的年齡、性別、愛好等詳細(xì)特征的信息。當(dāng)采樣得到的網(wǎng)絡(luò)數(shù)據(jù)中的節(jié)點或邊信息不完整時，充分利用節(jié)點自身包含的特征信息幫助判斷節(jié)點相似性是一種簡單有效的提高社區(qū)識別精度的方法。目前，在社交網(wǎng)絡(luò)分析領(lǐng)域，多數(shù)方法基于網(wǎng)絡(luò)拓?fù)溆嬎愎?jié)點相似度，同時考慮節(jié)點特征相似度的研究成果還不多見。

針對上述社交網(wǎng)絡(luò)的特殊性以及現(xiàn)有復(fù)雜網(wǎng)絡(luò)聚類方法在處理這些問題時存在的不足，本文提出以近鄰傳播聚類為主要手段，通過放松代表點約束以及引入局部近鄰傳播機制，并利用節(jié)點特征信息輔助社區(qū)識別，設(shè)計一種具有線性復(fù)雜度且能夠有效處理邊結(jié)構(gòu)不完整的社交網(wǎng)絡(luò)的高效社區(qū)識別算法。

2 相關(guān)工作

目前，復(fù)雜網(wǎng)絡(luò)聚類或圖上的社區(qū)識別方法根據(jù)采用的求解策略，主要可以分為基于優(yōu)化的方法和啟發(fā)式方法。

基于優(yōu)化的方法通過設(shè)置目標(biāo)函數(shù)并迭代逼近函數(shù)最優(yōu)值實現(xiàn)社區(qū)識別。譜方法[3]將社區(qū)識別問題轉(zhuǎn)換為放松的二次型優(yōu)化問題，通過求Laplacian矩陣的特征向量得到網(wǎng)絡(luò)的近似最優(yōu)劃分。KL（Kernighan-Lin）算法[4]早期用于圖的劃分，優(yōu)化目標(biāo)為極小化社區(qū)內(nèi)連接數(shù)與社區(qū)間連接數(shù)之差。FN（Fast Newman）算法[5]、GA（Guimera-Amaral）算法[6]和EO（extremal optimization）算法[7]均以Newman和Girvan提出的模塊度（modularity，又稱Q函數(shù)）為優(yōu)化目標(biāo)。模塊度的定義為

其中，e是一個對稱矩陣，其元素eij表示社區(qū)i和社區(qū)j之間的邊占全部邊的比例，Trace(e)表示矩陣的跡，表示與社區(qū)i內(nèi)部節(jié)點相連的邊數(shù)。由于模塊度能夠同時描述社區(qū)內(nèi)部高內(nèi)聚、社區(qū)之間低耦合的特性，具有清晰的物理含義，除了作為算法優(yōu)化目標(biāo)之外，它也成為評價算法性能的重要指標(biāo)?；赑otts模型的算法[8]借助物理學(xué)中轉(zhuǎn)子自旋態(tài)的概念，通過最小化描述系統(tǒng)能量的Hamilton算子實現(xiàn)網(wǎng)絡(luò)的最優(yōu)劃分。淦文燕[9]等提出基于拓?fù)鋭輬龅母叩蛣澐秩后w的方法。何東曉[10]等提出一種將聚類融合與遺傳算法（GA, genetic algorithm）結(jié)合的社區(qū)挖掘算法。葉鎮(zhèn)清[11]等提出一種新的模塊度Qd并采用迭代聚類法實現(xiàn)其最優(yōu)化。林旺群[12]等提出新的基于層次社區(qū)樹的社區(qū)結(jié)構(gòu)模型，并構(gòu)建相應(yīng)的并行化社區(qū)發(fā)現(xiàn)算法。楊博[13]等提出基于局部搜索和模擬退火（SA, simulated annealing）的能夠同時處理同配及異配網(wǎng)絡(luò)的社區(qū)挖掘算法。韓毅[14]等提出一種基于密度估計的特征簇發(fā)現(xiàn)算法，能夠發(fā)現(xiàn)社區(qū)間的層次結(jié)構(gòu)。在這一類方法中，精確求解算法通常具有超線性的時間復(fù)雜度，需要將復(fù)雜度降低為線性，而近似求解算法需要克服收斂速度慢及易陷入局部最優(yōu)解的問題，以適應(yīng)象社交網(wǎng)絡(luò)這樣的大規(guī)模網(wǎng)絡(luò)的數(shù)據(jù)分析。

啟發(fā)式方法通過設(shè)置啟發(fā)規(guī)則來尋找最優(yōu)社區(qū)劃分。GN（Girvan-Newman）算法[15]以社區(qū)間連接的邊介數(shù)（betweeness）應(yīng)大于社區(qū)內(nèi)連接的邊介數(shù)為啟發(fā)規(guī)則，通過不斷刪除具有最大邊介數(shù)的邊來發(fā)現(xiàn)社區(qū)。WH（Wu- Huberman）算法[16]將復(fù)雜網(wǎng)絡(luò)建模為電路系統(tǒng)來設(shè)計啟發(fā)規(guī)則：當(dāng)在不同社區(qū)中分別選取2個節(jié)點作為正負(fù)極后，由于社區(qū)間電阻遠(yuǎn)大于簇內(nèi)電阻，相同社區(qū)節(jié)點勢能應(yīng)相近，而相異社區(qū)節(jié)點勢能應(yīng)有顯著差別。CPM（clique percolation method）算法[17]的啟發(fā)規(guī)則為：網(wǎng)絡(luò)社區(qū)由多個相鄰的k-團（k-clique）組成，每個k-團唯一屬于一個社區(qū)，但不同社區(qū)的k-團可能共享相鄰節(jié)點，通過建立團-團重疊矩陣可以計算出重疊網(wǎng)絡(luò)社區(qū)的結(jié)構(gòu)?；跇?biāo)簽傳播（label propaga-tion）的算法[18]采用標(biāo)簽描述節(jié)點的社區(qū)信息，其啟發(fā)規(guī)則為：不斷在節(jié)點及其近鄰間傳遞標(biāo)簽信息，經(jīng)過多次迭代后，屬于同一個社區(qū)的節(jié)點的標(biāo)簽將趨于一致?；陔S機游走的算法[19]將社區(qū)結(jié)構(gòu)的識別過程建模為圖上的隨機游走，其啟發(fā)規(guī)則為：當(dāng)網(wǎng)絡(luò)存在明顯社區(qū)結(jié)構(gòu)時，隨機游走 agent在社區(qū)內(nèi)節(jié)點間游走的概率要大于在社區(qū)間節(jié)點間游走的概率。對于此類方法，如何設(shè)計能夠準(zhǔn)確描述復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)特征的啟發(fā)規(guī)則、提高算法的普適性仍是其面臨的主要挑戰(zhàn)。

目前，將網(wǎng)絡(luò)拓?fù)涮卣髋c節(jié)點自身特征相結(jié)合進(jìn)行社區(qū)識別的研究主要見于社交媒體分析（social media analysis），其典型代表是主題建模（topic modeling）。主題建模的目標(biāo)是通過分析在一個用戶群體之間交流的文本、圖片等多媒體數(shù)據(jù)之間存在的相關(guān)性找出從屬于不同主題的用戶子群[19～22]。雖然與社交網(wǎng)絡(luò)中的社區(qū)識別存在相似性，但是，主題建模的目標(biāo)是建立隱藏在用戶交流數(shù)據(jù)背后的主題模型，其社區(qū)劃分以主題為中心，而不以用戶為中心，一個用戶可以加入多個主題群，當(dāng)主題變動時社區(qū)也隨之變化，因此，不能直接將主題建模方法應(yīng)用于社交網(wǎng)絡(luò)中的社區(qū)識別。不過，受到主題建模思想的啟發(fā)，已經(jīng)有學(xué)者開始將網(wǎng)絡(luò)拓?fù)涮卣髋c節(jié)點特征結(jié)合應(yīng)用于描述節(jié)點的綜合相似度，從而更好地在社交網(wǎng)絡(luò)中識別社區(qū)。例如，Yoshida設(shè)計了一種考慮節(jié)點特征相似度的復(fù)合相似度，在具有不同邊缺失比的復(fù)雜網(wǎng)絡(luò)上的實驗取得良好效果[23]，但其采用的譜方法具有較高的時間復(fù)雜度。McAuley[24]等提出同時考慮節(jié)點的拓?fù)湎嗨贫群吞卣飨嗨贫鹊纳缃蝗ψ幽Ｐ?，并?yīng)用于設(shè)計在個人社交網(wǎng)絡(luò)中識別不同的社交圈子的算法。但由于采用了基于統(tǒng)計的方法，算法的時間開銷較大?？傮w而言，這方面的研究還處于起步階段。

3 近鄰傳播

近鄰傳播（AP, affinity propagation）算法是一種通過在近鄰節(jié)點間傳播消息實現(xiàn)聚類的方法[25]，是圈信任傳播（loopy belief propagation）[26]在聚類方面的最新應(yīng)用。AP算法通過多次迭代使簇中心點（或代表點）逐漸顯現(xiàn)，因此不需要預(yù)先輸入簇數(shù)參數(shù)。此外，AP算法不要求節(jié)點具有對稱相似度，因此能夠適應(yīng)相似性測度不滿足三角不等式的應(yīng)用。

AP算法需要輸入相似度矩陣S。矩陣元素s(i,k)表示點xk與點xi的相似度。文獻(xiàn)[25]采用2個節(jié)點之間的歐式距離作為其相似度，即s(i,k)=-|xi-xk|2。相似度矩陣S的主對角線元素s(k,k)具有特別含義：它表示節(jié)點xk適合作為代表點的程度。s(k,k)的值越大，節(jié)點k被選為代表點的可能性就越大。AP算法中將所有的s(k,k)設(shè)為一個共同值p。因此，p是AP算法的一個非常重要參數(shù)，直接影響到最終生成的簇的數(shù)量。

AP算法在節(jié)點之間傳播的消息分為支持度消息(responsibility)和適選度消息(availability)。前者由矩陣R=r(i,k)描述，r(i,k)表示節(jié)點i向節(jié)點k發(fā)送的消息，反映節(jié)點i在考慮其他潛在代表點后對節(jié)點k作為其代表點的支持程度。后者由矩陣A=a(i,k)描述，a(i,k)表示節(jié)點k向節(jié)點i發(fā)送的消息，反映節(jié)點k綜合了其他點對其支持度后向節(jié)點i表明自己作為節(jié)點i的代表點的適合程度。近鄰傳播過程即表現(xiàn)為2個消息矩陣的交替更新。每次更新后，通過計算決策矩陣E=R+A=e(i,k)確定節(jié)點i的代表點。消息更新公式如下。

4 結(jié)合局部近鄰傳播及用戶特征的社區(qū)識別

4.1 局部近鄰傳播與代表點約束放松

與互聯(lián)網(wǎng)、生物網(wǎng)絡(luò)等其他復(fù)雜網(wǎng)絡(luò)不同，社交網(wǎng)絡(luò)中的社區(qū)是通用戶與其近鄰（包括親戚、朋友、同事等）間的不斷交互逐漸產(chǎn)生并發(fā)展的。這與AP算法通過在近鄰間傳播消息，以使社區(qū)結(jié)構(gòu)自然涌現(xiàn)的設(shè)計思想存在相似性。但是，直接將AP算法應(yīng)用于社交網(wǎng)絡(luò)中的社區(qū)識別存在一些困難。首先，AP算法中的消息是在所有節(jié)點之間傳播的，而社交網(wǎng)絡(luò)中的用戶一般僅與其相近用戶傳遞信息。2個距離較遠(yuǎn)的用戶直接進(jìn)行消息傳遞的概率很低。其次，AP算法要求每個代表點必須選擇自身作為其代表點（又稱為代表點約束）。文獻(xiàn)[27]發(fā)現(xiàn)這限制了其聚類精度的進(jìn)一步提高，并提出放松這一約束以得到更低的聚類錯誤率。最后，AP算法的時間復(fù)雜度為O(n2)，n為網(wǎng)絡(luò)節(jié)點數(shù)。當(dāng)應(yīng)用于像社交網(wǎng)絡(luò)這樣規(guī)模較大的數(shù)據(jù)集時，其時間開銷較大。

通過將消息傳播范圍局限于節(jié)點的直接近鄰，一方面使算法的運行過程更符合社交網(wǎng)絡(luò)中社區(qū)的形成與發(fā)展過程，從而有可能得到具有更高內(nèi)聚的社區(qū)；另一方面，更重要的是，由于每個節(jié)點發(fā)送和接收的消息數(shù)由O(n)下降為O(dmax)，dmax為節(jié)點最大度，算法的時間復(fù)雜度將下降為O(dmaxn)，具體參見4.5節(jié)的分析。此時，消息更新公式應(yīng)修改為

其中，NB(i)和NB(k)分別表示節(jié)點i和節(jié)點k的近鄰節(jié)點集。

從另一方面來看，將消息傳播范圍限制于節(jié)點近鄰也會導(dǎo)致近鄰消息不能充分在全網(wǎng)節(jié)點之間傳播。但是，正如前面指出的，針對社交網(wǎng)絡(luò)這種特殊的復(fù)雜網(wǎng)絡(luò)，遠(yuǎn)程節(jié)點之間的聯(lián)系遠(yuǎn)少于近鄰節(jié)點之間的聯(lián)系。因此，可以預(yù)期遠(yuǎn)程節(jié)點之間交換的消息對社區(qū)生成過程的影響很小。這一假設(shè)也在實驗中得到了驗證，具體實驗結(jié)果的分析參見第5節(jié)。

在生成代表點時，放松代表點約束，即允許代表點選擇其自身以外的其他節(jié)點作為其代表點，能夠進(jìn)一步提高聚類的精確度。但是，帶來的問題是可能導(dǎo)致代表點間出現(xiàn)循環(huán)代表，形成圈結(jié)構(gòu)。例如，節(jié)點1的代表點為節(jié)點2，節(jié)點2的代表點為節(jié)點3，而節(jié)點3的代表點又是節(jié)點1，如圖1所示。

圖1 代表點的圈結(jié)構(gòu)

代表點之間的這種圈結(jié)構(gòu)將使近鄰傳播過程陷入無限循環(huán)。一個可行的解決方案是從某個節(jié)點位置切斷其與代表點的連接，使圈變?yōu)槁窂剑瑫r修改路徑上除最末代表點外所有其他節(jié)點的代表點。圖1中的圈結(jié)構(gòu)從節(jié)點1處切斷后重新調(diào)整的結(jié)果如圖2所示。

圖2 消除圈結(jié)構(gòu)后的代表點

4.2 考慮用戶特征的相似度

由于社交網(wǎng)絡(luò)規(guī)模龐大且變化頻繁，在進(jìn)行數(shù)據(jù)采樣時通常只能得到網(wǎng)絡(luò)的部分信息。這樣，在進(jìn)行數(shù)據(jù)分析時，由于部分節(jié)點及邊信息的缺失，單純依賴于網(wǎng)絡(luò)拓?fù)溆嬎愎?jié)點相似度的方法可能造成分析結(jié)果的不準(zhǔn)確。借鑒文獻(xiàn)[23]的思想，利用社交網(wǎng)絡(luò)通常包含用戶特征描述信息的優(yōu)點，將基于網(wǎng)絡(luò)拓?fù)涞南嗨贫扰c基于用戶特征的相似度相結(jié)合，設(shè)計一種新的組合相似度，其計算公式如下

其中，st(i,j)描述節(jié)點的拓?fù)湎嗨贫?，其實質(zhì)上是計算2個節(jié)點的近鄰集的Jaccard相似度。sp(i,j)描述2個節(jié)點的特征向量ri和rj的相似度，這里采用余弦公式計算。節(jié)點的特征向量是一個二值向量，ri=(rik)，當(dāng)節(jié)點i具有特征k時，rik=1，否則rik=0。最后，節(jié)點的組合相似度根據(jù)式(8)計算，其中，加權(quán)系數(shù)調(diào)整拓?fù)湎嗨贫群吞卣飨嗨贫仍诮M合相似度中所占的比重。

4.3 算法總體框架

在網(wǎng)絡(luò)規(guī)模較大且消息傳播范圍僅限于節(jié)點直接近鄰時，即使有參數(shù)p的約束，一次局部近鄰傳播仍可能產(chǎn)生過多的代表點，使網(wǎng)絡(luò)被劃分成大量規(guī)模極小的社區(qū)。此時，通過將生成的代表點及代表點間的連接邊看作一個新的超網(wǎng)（super network），在這個網(wǎng)絡(luò)上再次運行局部近鄰傳播生成新的代表點，可以實現(xiàn)社區(qū)數(shù)量的進(jìn)一步壓縮。這個過程可以迭代進(jìn)行，直到生成的代表點不再發(fā)生變化。

綜合前面的分析，提出一種結(jié)合局部近鄰傳播及考慮用戶特征的相似度的新算法 LAP（local affinity propagation），其總體框架如下。

1) 應(yīng)用近鄰傳播求網(wǎng)絡(luò)G的代表點集，消息更新公式采用修改后的式(4)和式(5)。

2) 若當(dāng)前得到的代表點與上次得到的代表點不一致，則建立由新的代表點及代表點間的連接邊組成的超網(wǎng)G'，返回步驟1)繼續(xù)執(zhí)行。

3) 否則，消除代表點中可能存在的圈結(jié)構(gòu)，輸出得到的社區(qū)，算法結(jié)束。

4.4 算法實現(xiàn)

LAP算法的具體實現(xiàn)如下。

算法1 LAP算法

輸入：網(wǎng)絡(luò)G=(V,E,R)，V為節(jié)點集，E為邊集，R為節(jié)點特征向量集，最大迭代次數(shù)maxIter，穩(wěn)定迭代次數(shù)convIter，p，α

輸出：社區(qū)集Setc={C1,…,Ck}，k為社區(qū)數(shù)

算法最外層的WHILE循環(huán)反復(fù)執(zhí)行局部近鄰傳播，直至生成的代表點不再變化。步驟3至步驟14的FOR循環(huán)是局部近鄰傳播的實現(xiàn)。這里，由于消息傳播的范圍限制為節(jié)點的直接近鄰，不再需要保留支持度矩陣R和適選度矩陣A，而只需要為每個節(jié)點i保留一個支持度向量ri和一個適選度向量ai，以存儲節(jié)點接收到和準(zhǔn)備發(fā)送的消息。這樣，算法的空間復(fù)雜度可以大幅度下降。步驟 17的判斷決定外層的WHILE循環(huán)何時可以結(jié)束，若生成的代表點仍變化，步驟20通過修剪原始網(wǎng)絡(luò)G得到只是包含代表點及其連接邊的超網(wǎng)G'，為下一次迭代做準(zhǔn)備。在根據(jù)指示向量v確定節(jié)點所屬的社區(qū)時，需要先消除向量v中可能存在的圈結(jié)構(gòu)，步驟16調(diào)用過程RemoveCircle完成這一操作。算法最后返回根據(jù)指示向量v建立的以各個代表點為中心的社區(qū)集。

過程RemoveCircle的具體實現(xiàn)如下。

RemoveCircle過程

輸入：節(jié)點指示向量v=(vi)

針對每個節(jié)點i，過程 RemoveCircle首先判斷節(jié)點i的代表點是否是其自身的代表，如果是，則散列表H為空，不存在圈結(jié)構(gòu)。否則，從節(jié)點i到其真實代表點存在一條路徑。這里，真實代表點有2種情況：一是最終找到以一個以其自身為代表的代表點，此時不存在圈結(jié)構(gòu)，只需要執(zhí)行步驟11至步驟15將路徑上的所有節(jié)點的代表點都修改為該代表點即可；二是找到一個已經(jīng)在路徑中出現(xiàn)過的代表點，此時出現(xiàn)圈結(jié)構(gòu)，在步驟11至步驟 15中必須將該節(jié)點連同路徑上的所有結(jié)構(gòu)的代表點都修改為一個指定的代表點（過程RemoveCircle中設(shè)為發(fā)現(xiàn)的重復(fù)節(jié)點）。2種情況的處理如圖3所示。

圖3 圈結(jié)構(gòu)的處理

可以證明，過程RemoveCircle能夠消除代表點中存在的圈結(jié)構(gòu)。

定理1 經(jīng)過過程RemoveCircle處理后的代表點集合不存在圈結(jié)構(gòu)。

1)ex的代表點為其自身。此時，不存在圈結(jié)構(gòu)，也不需要過程RemoveCircle處理。

2)ex的代表點ey∈P。此時，由于P中的代表點統(tǒng)一指向一個代表點ek，不存在圈結(jié)構(gòu)，過程RemoveCircle按第一種情況處理，將ex的代表點修改為ek。

3)ex的代表點ey∈E-P且ex≠ey。此時，設(shè)從ex開始到其最終代表點的路徑上的節(jié)點構(gòu)成集合。若集合Q不存在圈結(jié)構(gòu)，則過程 RemoveCircle按第一種情況處理，將所有節(jié)點的代表點修改為eq。若集合Q存在圈結(jié)構(gòu)，根據(jù)其真實代表點et是否在集合P中又可以分為2種情況。

a)et?P。此時，集合Q的處理與集合P的處理無關(guān)，過程RemoveCircle按第二種情況處理集合Q，將所有節(jié)點的代表點修改為et，2個集合都不再存在圈結(jié)構(gòu)。

b)et∈P。此時，過程RemoveCircle仍按第二種情況處理集合Q，只是真實代表點變?yōu)閑t在集合P中的真實代表點es，即將集合Q中所有節(jié)點的代表點修改為es，集合Q的圈結(jié)構(gòu)消除，且不會影響集合P中的節(jié)點。

由上述分析可知，在消除新的圈結(jié)構(gòu)時不會造成已經(jīng)處理過的節(jié)點重新產(chǎn)生圈結(jié)構(gòu)。這樣，當(dāng)依次處理完剩余的所有代表點后，代表點集合E不再存在圈結(jié)構(gòu)。

證畢。

4.5 算法復(fù)雜度分析

性質(zhì)1 LAP算法具有近似線性的時間復(fù)雜度和線性的空間復(fù)雜度。

說明 首先分析 LAP算法的時間復(fù)雜度。設(shè)n=|V|，m=|E|。步驟1中的相似度向量的計算的時間復(fù)雜度為O(dmaxn)。算法最外層的 WHILE循環(huán)的次數(shù)取決于代表點需要多長時間達(dá)到穩(wěn)定。在極端情況下，每個節(jié)點都選擇自身作為其代表點，從而得到n個單節(jié)點社區(qū)。通過設(shè)置參數(shù)p為遠(yuǎn)小于0的值可以避免這種情況的發(fā)生。此時，每次生成的社區(qū)至少包含2個節(jié)點，因而每次WHILE循環(huán)生成的代表點數(shù)均減少一半。這樣，最外層的WHILE循環(huán)的次數(shù)為O(logn)。步驟3至步驟14的第一層FOR循環(huán)的次數(shù)為O(maxIter)。步驟4至步驟9的第二層FOR循環(huán)的次數(shù)為O(n)。步驟5至步驟8的最內(nèi)層FOR循環(huán)的次數(shù)與節(jié)點的最大度成正比，設(shè)節(jié)點最大度為dmax，則該循環(huán)的次數(shù)為O(dmax)。步驟 10和步驟 11的時間復(fù)雜度分別為O(dmax)和O(convIter)。由于采用了散列表，過程RemoveCircle的時間復(fù)雜度為O(nlp)，lp為節(jié)點到其真實代表點的最大路徑長度。步驟20和步驟22的時間開銷分別為O(m)和O(n)。綜上可得，LAP算法總的時間復(fù)雜度O(dmaxn+lognmaxIter(n+dmax+convIter)+nlp+m)。社交網(wǎng)絡(luò)具有稀疏圖的特征，因此dmax＜＜n，convIter≤maxIter，n≤m，lp＜＜n，從而可以將 LAP算法的時間復(fù)雜度簡化為O(maxIternlogn+m)。由此可知，LAP算法具有近似線性的時間復(fù)雜度。

接下來分析算法的空間復(fù)雜度。由于采用近鄰傳播，步驟1中只需要存儲每個節(jié)點的相似度向量，其空間開銷為O(dmaxn)。同樣，在向近鄰傳播消息過程中只需要為每個節(jié)點保存其支持度向量和適選度向量，其空間代價為O(dmaxn)。步驟11要求保存最近convIter次代表點集，需要的空間為O(convItern)。指示向量需要的空間為O(n)。過程RemoveCircle中存儲散列表和路徑需要的空間為O(n)。因此，LAP算法總的空間復(fù)雜度為O(dmaxn+convItern)。由于dmax，convIter＜＜n，LAP算法的空間復(fù)雜度可以簡化為O(n)。由此可知，LAP算法具有線性空間復(fù)雜度。

5 實驗及分析

為了驗證本文提出的新算法的性能，分別選擇人工生成的數(shù)據(jù)集和真實數(shù)據(jù)集，與 AP算法和Yoshida提出的算法（以下簡稱為NEM算法）進(jìn)行實驗對比。人工數(shù)據(jù)集利用Lancichinetti等提出的LFR基準(zhǔn)程序生成[28]。LFR能夠根據(jù)輸入的參數(shù)生成不同數(shù)據(jù)量、不同度分布及不同簇數(shù)的仿真數(shù)據(jù)集。真實數(shù)據(jù)集采用斯坦福大學(xué)的網(wǎng)絡(luò)數(shù)據(jù)集SNAP中的ego-Facebook數(shù)據(jù)集[24]。ego-Facebook數(shù)據(jù)集提供了社交網(wǎng)絡(luò) Facebook中以用戶為中心的好友圈子及好友的特征信息。實驗數(shù)據(jù)集的詳細(xì)描述如表1所示。

表1 實驗數(shù)據(jù)集

表1中，參數(shù)N、μ、k、c和Nr分別表示數(shù)據(jù)集大小、節(jié)點平均外部度與內(nèi)部度之比、節(jié)點度、真實社區(qū)數(shù)和特征數(shù)。真實數(shù)據(jù)集中的348、3 437和107代表相應(yīng)編號節(jié)點的近鄰組成的社交圈子數(shù)據(jù)集。在人工數(shù)據(jù)集方面，由于LFR不能生成節(jié)點的特征信息，采用以下步驟生成每個節(jié)點的仿真特征。

步驟 1將Nr個特征組成的特征集R劃分成Nr/c個互不相交的特征子集，每個特征子集對應(yīng)一個社區(qū)。

步驟2設(shè)與社區(qū)Ci對應(yīng)的特征子集為Ri，社區(qū)Ci中各節(jié)點的特征以概率0.9從Ri中選擇，以概率0.1從R-Ri中選擇。

通過這種方式，既保證各社區(qū)節(jié)點的特征具有較高的一致性，又允許不同社區(qū)節(jié)點的特征存在一定程度的重疊。所有算法均采用Java語言實現(xiàn)，并在硬件配置為Intel i5-2520M 2.50 GHz CPU，8 GB RAM，軟件配置為Microsoft Windows7, JDK 7.0的平臺上進(jìn)行測試。

實驗比較了LAP算法與AP算法和NEM算法在不同數(shù)據(jù)量及不同邊保留比例時的模塊度、NMI(normalized mutual information)[28]、運行時間和社區(qū)數(shù)等指標(biāo)的數(shù)值。這里，通過保留原始數(shù)據(jù)中不同比例的邊來模擬真實采樣中難以獲得全部關(guān)聯(lián)邊信息的情況。為了克服隨機性對算法測試的影響，所有實驗結(jié)果均取 20次運行結(jié)果的平均值。各算法的參數(shù)設(shè)置如表2所示。

表2 算法參數(shù)的設(shè)置

AP算法對參數(shù)p非常敏感，需要根據(jù)不同的數(shù)據(jù)集調(diào)整參數(shù)p的值以達(dá)到最優(yōu)聚類效果。實驗中根據(jù)不同數(shù)據(jù)集取使聚類質(zhì)量達(dá)到最高的p值。而LAP算法對p值變化不敏感，在一個較大范圍內(nèi)改變p值得到的社區(qū)數(shù)基本保持不變，因此實驗時采用固定值p=-1.0。NEM 算法需要輸入社區(qū)數(shù)k，實驗中將k設(shè)為數(shù)據(jù)集的真實社區(qū)數(shù)，以使算法達(dá)到最佳性能。其他參數(shù)均取原作者論文中的推薦值。

5.1 人工數(shù)據(jù)集上的實驗結(jié)果

5.1.1 邊完整時的實驗結(jié)果

本小節(jié)描述數(shù)據(jù)集中的邊是完整時的實驗結(jié)果。圖4顯示了算法的模塊度隨數(shù)據(jù)量的變化。

從圖4可以看出，AP算法和LAP算法得到的社區(qū)劃分的模塊度隨著數(shù)據(jù)量的增加而逐漸提高。由于AP算法和LAP算法均通過節(jié)點之間的關(guān)聯(lián)邊來傳播近鄰消息，而當(dāng)數(shù)據(jù)量增大時網(wǎng)絡(luò)的邊數(shù)及每個節(jié)點的平均度也相應(yīng)增加，使消息能夠得到更充分地傳播，從而使社區(qū)計算得到的模塊度數(shù)值更大。LAP算法得到的模塊度在數(shù)據(jù)量較小時略低于AP算法，表明局部近鄰傳播策略在數(shù)據(jù)量較小時對算法性能有一定影響。但隨著網(wǎng)絡(luò)節(jié)點及邊的增加，這種影響迅速減小，而LAP采用的更有效的代表點選擇策略的優(yōu)勢則逐漸顯露。因此，當(dāng)數(shù)據(jù)量超過400時，LAP算法得到的模塊度已經(jīng)高于AP算法。圖4也反映了NEM算法得到的社區(qū)劃分的模塊度低于AP算法和LAP算法，且不同數(shù)據(jù)量的模塊度的波動較明顯，這可能與其采用具有隨機性的k均值算法對映射后的子空間向量進(jìn)行聚類有關(guān)。由于LFR基準(zhǔn)程序生成的仿真數(shù)據(jù)分組含真實社區(qū)信息，也對不同算法的NMI指標(biāo)進(jìn)行了實驗，結(jié)果如圖5所示。

圖4 模塊度隨數(shù)據(jù)集大小的變化（人工數(shù)據(jù)集）

圖5的實驗結(jié)果與圖4基本相似，但也存在一些不同之處。從圖5可以發(fā)現(xiàn)，AP算法得到的社區(qū)劃分在所有數(shù)據(jù)量下均非常接近于真實的社區(qū)結(jié)構(gòu)。LAP算法在數(shù)據(jù)量大于100時也能夠得到與真實社區(qū)的相近程度大于 80%的社區(qū)劃分。特別地，當(dāng)數(shù)據(jù)量達(dá)到1 000時，LAP算法得到的社區(qū)劃分的質(zhì)量與AP算法已經(jīng)基本相當(dāng)。這同樣可以由前述 LAP算法采用的局部近鄰傳播與代表點約束放松策略的影響來解釋。NEM算法的NMI值較低，反映其得到的社區(qū)劃分與真實社區(qū)存在較顯著的差別，而曲線較大幅度的波動亦反映了k均值算法對其性能的影響。

不同算法的運行時間隨數(shù)據(jù)集大小的變化反映在圖6中。

圖5 NMI隨數(shù)據(jù)集大小的變化（人工數(shù)據(jù)集）

圖6 運行時間隨數(shù)據(jù)集大小的變化（人工數(shù)據(jù)集）

圖6顯示，與AP算法和NEM算法相比，LAP算法的運行時間隨數(shù)據(jù)量的增加的幅度非常平緩。這主要有2個方面的原因：一是由第4節(jié)的分析可知LAP算法具有近似線性的時間復(fù)雜度，而AP算法和 NEM 算法的時間復(fù)雜度分別達(dá)到O(n2)和O(n3)，因此 LAP算法隨數(shù)據(jù)量增加的時間代價顯著小于2個對比算法；二是LAP算法采用的局部近鄰傳播及代表點約束放松策略使算法在數(shù)據(jù)量較大時仍保持較快的收斂速率，而AP算法在數(shù)據(jù)量增大時易出現(xiàn)不收斂現(xiàn)象，使算法的迭代次數(shù)大大增加，從而增加了算法的運行時間。

由于AP算法和LAP算法的社區(qū)均由聚類過程自動涌現(xiàn)，還將它們得到的社區(qū)數(shù)與真實社區(qū)數(shù)進(jìn)行了比較，結(jié)果如圖7所示。其中，由于NEM算法的社區(qū)數(shù)參數(shù)k設(shè)為真實社區(qū)數(shù)，將其作為比較的基準(zhǔn)。

由圖7可知，盡管AP算法和LAP算法的社區(qū)是在聚類過程中自動涌現(xiàn)的，最終得到的社區(qū)數(shù)與真實社區(qū)數(shù)仍比較接近。這表明在網(wǎng)絡(luò)中的邊結(jié)構(gòu)完整時，AP算法和LAP算法的具有較強的社區(qū)識別能力。由于LAP算法在不同數(shù)據(jù)集上均采用相同的p值，而AP算法需要調(diào)整p值以適應(yīng)不同數(shù)據(jù)集，LAP算法的適應(yīng)性顯然強于AP算法。

圖7 社區(qū)數(shù)隨數(shù)據(jù)集大小的變化（人工數(shù)據(jù)集）

5.1.2 邊不完整時的實驗結(jié)果

現(xiàn)實中采樣得到的數(shù)據(jù)通常無法涵蓋網(wǎng)絡(luò)中所有邊。通過按不同比例保留測試數(shù)據(jù)集中的邊，比較了各個算法在不同邊缺失情況下的性能，數(shù)據(jù)集取大小為400的人工數(shù)據(jù)集，其他參數(shù)設(shè)置同表2。模塊度的實驗結(jié)果如圖8所示。

圖8 不同邊保留比例時的模塊度（人工數(shù)據(jù)集）

圖8反映邊的減小對LAP算法和NEM算法的影響較小。這主要是由于2個算法在計算節(jié)點相似度時均同時考慮網(wǎng)絡(luò)拓?fù)浜凸?jié)點的特征相似度。當(dāng)網(wǎng)絡(luò)中的邊減小時，節(jié)點特征相似度對節(jié)點之間相似性的判斷起到主要作用。而LAP算法采用的新策略使其得到的社區(qū)的模塊度顯著高于NEM算法。AP算法需要根據(jù)網(wǎng)絡(luò)中的邊信息計算節(jié)點相似度矩陣。當(dāng)網(wǎng)絡(luò)中的邊大量減小時，其相似度矩陣將存在大量0值，從而對算法性能造成較大影響。邊的刪除導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化，因此LFR基準(zhǔn)程序提供的真實社區(qū)信息不再適用，故未對 NMI指標(biāo)進(jìn)行測試。但從圖5和圖4的相似性可以推測在不同邊保留比例下的NMI指標(biāo)值應(yīng)與圖8有相似結(jié)果。不同邊保留比例下運行時間的實驗結(jié)果如圖9所示。

圖9 不同邊保留比例的運行時間

圖9顯示算法的運行時間受邊數(shù)變化的影響較小，這主要是因為算法的時間復(fù)雜度主要與數(shù)據(jù)集規(guī)模相關(guān)。在數(shù)據(jù)集大小不變時，各算法的運行時間基本保持穩(wěn)定。只有 NEM 算法受其采用的k均值算法影響，運行時間的波動略大。與圖6中的實驗結(jié)果相一致，LAP算法由于具有近似線性的時間復(fù)雜度，運行速度最快。AP算法和NEM算法由于時間復(fù)雜度較高，運行速度顯著慢于LAP算法。

5.2 真實數(shù)據(jù)集上的實驗結(jié)果

5.2.1 邊完整時的實驗結(jié)果

圖10顯示了不同算法在3個真實數(shù)據(jù)集上的得到的社區(qū)劃分的模塊度。

真實數(shù)據(jù)集中通常存在噪聲數(shù)據(jù)，這增加了社區(qū)識別的難度，因此圖 10中各算法的模塊度總體上要低于圖4中的結(jié)果。除了在348數(shù)據(jù)集上的模塊度略低于NEM算法外，LAP算法在所有其他數(shù)據(jù)集上的性能均優(yōu)于對比算法，再一次表明 LAP算法采用的局部近鄰傳播及代表點約束放松策略在數(shù)據(jù)集較大時具有較好的效果。由表1可知，348數(shù)據(jù)集的網(wǎng)絡(luò)規(guī)模較小，每個真實社區(qū)的規(guī)模也不大，且經(jīng)過計算該數(shù)據(jù)集的節(jié)點平均度為28，因此該數(shù)據(jù)集的社區(qū)結(jié)構(gòu)不顯著，導(dǎo)致各算法在該數(shù)據(jù)集上的識別效果均不理想。此外，雖然107數(shù)據(jù)集大于3 437數(shù)據(jù)集，但算法在3 437數(shù)據(jù)集上得到的模塊度卻高于107數(shù)據(jù)集。由于107數(shù)據(jù)集可能具有更復(fù)雜的內(nèi)部結(jié)構(gòu)（其節(jié)點具有更多的特征），這表明了在真實的應(yīng)用環(huán)境中，不僅網(wǎng)絡(luò)規(guī)模，網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)的復(fù)雜程度也對算法的性能產(chǎn)生影響。ego-Facebook數(shù)據(jù)集中的真實社區(qū)信息不完整，故無法測試NMI指標(biāo)。圖11顯示了不同算法在3個真實數(shù)據(jù)集上的運行時間。

圖10 不同真實數(shù)據(jù)集的模塊度

圖11 不同真實數(shù)據(jù)集的運行時間

與圖6的結(jié)果相似，圖11同樣表明AP算法和NEM 算法的時間復(fù)雜度隨數(shù)據(jù)量的增加而快速增加。與之相反，LAP算法的運行時間隨數(shù)據(jù)量的增加呈近似線性增長，且總是低于2個對比算法。其中，由于107數(shù)據(jù)集的復(fù)雜度較高，AP算法不能在maxIter次迭代內(nèi)收斂，大大增加了其運行時間。圖12顯示了各算法在不同數(shù)據(jù)集上得到的社區(qū)數(shù)。

圖12 不同數(shù)據(jù)集的社區(qū)數(shù)

圖12表明， LAP算法傾向于生成較多小規(guī)模的社區(qū)，這主要是由于當(dāng)p值固定時，LAP算法采用的局部近鄰傳播及代表點約束放松策略使算法的收斂速度加快。而AP算法和NEM算法由于可以分別通過調(diào)整參數(shù)p和參數(shù)k的值來匹配真實社區(qū)數(shù)，不存在這個問題。但是，由圖 13的結(jié)果可知，即使AP算法和NEM算法能夠生成正確的社區(qū)數(shù)，其生成的社區(qū)的模塊度仍然不如LAP算法。

5.2.2 邊不完整時的實驗結(jié)果

當(dāng)真實網(wǎng)絡(luò)中的邊存在缺失時，不同算法得到的模塊度如圖13所示。采用107數(shù)據(jù)集作為測試數(shù)據(jù)集，其他參數(shù)設(shè)置同表2。

圖13 不同邊保留比例時的模塊度（真實數(shù)據(jù)集）

圖13中的實驗結(jié)果與圖8存在相似性，AP算法和LAP算法的模塊度仍然高于NEM算法。但可以發(fā)現(xiàn)，在邊保留比例較低時，LAP算法和 NEM算法的性能受到一定影響。當(dāng)保留的邊數(shù)減少到一定程度時，網(wǎng)絡(luò)將分隔為多個獨立的連通分支，大量節(jié)點間的拓?fù)湎嗨贫冉咏?0，不能有效描述節(jié)點間的真實相似度。當(dāng)α=0.5時對算法性能產(chǎn)生一定影響。結(jié)合后面對參數(shù)α的實驗結(jié)果，此時可以通過減小α值使節(jié)點特征相似度發(fā)揮主導(dǎo)作用，起到一定彌補作用。不同邊保留比例時算法的運行時間如圖14所示。

圖14 不同邊保留比例的運行時間

圖14顯示的實驗結(jié)果與圖9基本一致，LAP算法具有最快的運行速度，其次是NEM算法，AP算法的運行速度最慢。但LAP算法在邊保留比例為80%處存在一個尖峰，這主要是由于此時LAP使用了較多的迭代次數(shù)才達(dá)到收斂，從而增加了運行時間。而在邊保留比例為 40%處，AP算法也存在一個低谷，這主要是由于此時AP算法在stableIter次迭代時即達(dá)到收斂，從而減小了運行時間，再次反映了真實數(shù)據(jù)集內(nèi)部結(jié)構(gòu)的復(fù)雜性對算法性能存在影響。

5.3 參數(shù)α的實驗結(jié)果

參數(shù)α決定了在計算節(jié)點相似度時拓?fù)湎嗨贫扰c特征相似度的相對比例。為了研究α值的變化對LAP算法性能的影響，在大小為400的人工數(shù)據(jù)集上測試了不同邊保留比例下不同α值的模塊度，實驗結(jié)果如圖15所示。

圖15 不同邊保留比例及α值的模塊度

從圖15可以看出，當(dāng)α=1.0時，邊保留比例的降低將導(dǎo)致模塊度的顯著下降，表明當(dāng)完全依賴拓?fù)湎嗨贫冗M(jìn)行社區(qū)識別時，算法性能受網(wǎng)絡(luò)邊缺失的影響較明顯。當(dāng)α取小于1.0的其他值時，節(jié)點的特征相似度參與到節(jié)點組合相似度的計算中，此時模塊度隨邊缺失程度變化的幅度較小，表明節(jié)點特征相似度對提高社區(qū)識別精度具有顯著作用。與圖13中的實驗結(jié)果類似，圖15也反映出算法的模塊度隨著邊保留比例的增大而逐漸提高。

6 結(jié)束語

針對社交網(wǎng)絡(luò)規(guī)模龐大、動態(tài)變化對社交網(wǎng)絡(luò)上的社區(qū)識別帶來的挑戰(zhàn)，本文提出一種新的將局部傳播近鄰消息、放松代表點約束，以及在結(jié)合網(wǎng)絡(luò)拓?fù)浼坝脩籼卣鞫攘抗?jié)點相似性等策略相結(jié)合的社區(qū)識別算法。通過理論分析和實驗檢驗，證明了提出的算法不僅具有較低的時間和空間復(fù)雜度，而且在采樣得到的網(wǎng)絡(luò)存在邊缺失時仍具有較好的識別精度，具有一定的實用意義。

在接下來的工作中，將進(jìn)一步考慮更多的節(jié)點近鄰選擇方法，比較不同方法對社區(qū)識別精度的影響，并考慮引入MapReduce、MPI等并行計算框架，實現(xiàn)算法的并行化，使算法具有更高的實用價值。

[1] 楊博, 劉大有, LIU J M等. 復(fù)雜網(wǎng)絡(luò)聚類方法[J]. 軟件學(xué)報, 2009,20(1): 54-66.YANG B, LIU D Y, LIU J M,et al. Complex network clustering algorithms[J]. Journal of Software, 2009, 20(1): 54-66.

[2] FORTUNATO S. Community detection in graphs[J]. Physics Reports,2010, 486(3-5): 75-174.

[3] SHIGA M, TAKIGAWA I, MAMITSUKA H. A spectral approach to clustering numerical vectors as nodes in a network[J]. Pattern Recognition, 2011, 44(2): 236-251.

[4] NEWMAN M E J. Detecting community structure in networks[J]. The European Physical Journal B - Condensed Matter, 2004, 38(2):321-330.

[5] GUIMERA R, SALES-PARDO M, AMARAL L A N. Modularity from fluctuations in random graphs and complex networks[J]. Physical Review E, 2004, 70(2): 025101.

[6] GUIMERA R. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028): 895-900.

[7] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical Review E, 2005,72(2):027104.

[8] SON S W, JEONG H, NOH J D. Random field ising model and community structure in complex networks[J]. The European Physical Journal B, 2006, 50(3): 431-437.

[9] 淦文燕, 赫南, 李德毅等. 一種基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J].軟件學(xué)報, 2009, 20(8): 2241-2254.GAN W Y, HAO N, LI Y D,et al. Community discovery method in networks based on topological potential[J]. Journal of Software, 2009,20(8): 2241-2254.

[10] 何東曉, 周栩, 王佐等. 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘—基于聚類融合的遺傳算法[J]. 自動化學(xué)報, 2010, 36(8): 1160-1170.HE D X, ZHOU X, WANG Z,et al. Community mining in complex networks — clustering combination based genetic algorithm[J]. Acta Automatica Sinica, 2010, 36(8): 1160-1170.

[11] YE Z Q, ZHANG K, HU S N,et al. A new definition of modularity for community detection in complex networks[J]. Chinese Physics Letters,2012, 29(9): 098901.

[12] 林旺群, 盧風(fēng)順, 丁兆云等. 基于帶權(quán)圖的層次化社區(qū)并行計算方法[J]. 軟件學(xué)報, 2012, 23(6): 1517-1530.LIN W Q, LU F S, DING Z Y,et al. Parallel computing hierachical community approach based on weighted-graph[J]. Journal of Software,2012, 23(6): 1517-1530.

[13] 楊博, 劉杰, 劉大有. 基于隨機網(wǎng)絡(luò)集成模型的廣義網(wǎng)絡(luò)社區(qū)挖掘算法[J]. 自動化學(xué)報, 2012, 38(5): 812-822.YANG B, LIU J, LIU D Y. A random network ensemble model based generalized network community mining algorithm[J]. Acta Automatica Sinica, 2012, 38(5): 812-822.

[14] 韓毅, 方濱興, 賈焰等. 基于密度估計的社會網(wǎng)絡(luò)特征簇挖掘方法[J]. 通信學(xué)報, 2012, 33(5): 38-48.HAN Y, FANG B X, JIA Y,et al. Mining characteristic clusters: a density estimation approach[J]. Journal on Communications, 2012, 33(5):38-48.

[15] GIRVAN M., NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.

[16] WU F, HUBERMAN B A. Finding communities in linear time: a physics approach[J]. The European Physical Journal B-Condensed Matter, 2004,38(2): 331-338.

[17] PALLA G, DERENYI I, FARKAS I,et al. Uncovering the overlapping community structure of complex networks in nature and society[J].Nature, 2005,435(7043): 814-818.

[18] WU Z H, LIN Y F, GREGORY S,et al. Balanced multi-label propagation for overlapping community detection in social networks[J]. Journal of Computer Science and Technology, 2012, 27(3): 468-479.

[19] 金弟, 楊博, 劉杰等. 復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測—基于隨機游走的蟻群算法[J]. 軟件學(xué)報, 2012, 23(3): 451-464.JIN D, YANG B, LIU J,et al. Ant colony optimization based on random walk for community detection in complex networks[J].Journal of Software, 2012, 23(3): 451-464.

[20] WANG X, MOHANTY N, MCCALLUM A. Group and topic discovery from relations and their attributes[J]. Advances in Neural Information Processing Systems, 2006, 18:1449.

[21] MOSER F, GE R, ESTER M. Joint cluster analysis of attribute and relationship data without a-priori specification of the number of clusters[A]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD'07)[C]. 2007. 510-519.

[22] YAN L, ALEXANDRU N M, WOJCIECH G. Topic-link LDA: joint models of topic and author community[A]. Proceedings of the 26th Annual International Conference on Machine Learning[C]. 2009.665-672.

[23] YOSHIDA T. Toward finding hidden communities based on user profiles[A]. Proceedings of the 2010 IEEE International Conference on Data Mining Workshops (ICDE'10)[C]. 2010. 380-387.

[24] MCAULEY J., LESKOVEC J. Learning to discover social circles in ego networks[A]. Proceedings of the 26th Annual Conference on Neural Information Processing Systems 2012[C]. 2012. 548-556.

[25] BRENDAN J F, DELBERT D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[26] JUDEA P. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[M]. Morgan Kaufmann, 1988.

[27] SUMEDHA M L, WEIGT M. Unsupervised and semi-supervised clustering by message passing: soft-constraint affinity propagation[J].The European Physical Journal B, 2008, 66(1):125-135.

[28] LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80(1):1-8.

[29] LANCICHINETTI A., FORTUNATO S., KERTéSZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11(3): 033015.