基于節點屬性的重疊社區發現算法改進*

王夢迪，付順順

（中國人民公安大學 信息技術與網絡安全學院，北京 100038）

0 引 言

隨著復雜系統科學和信息技術的不斷發展，人們發現了越來越多的復雜網絡。這些網絡中，通常以節點表示個體，邊表示個體間關系[1]。大量研究表明，在復雜網絡中存在著一定的社區結構，它們具有相似的功能或屬性，如社會網絡中的家庭﹑朋友，蛋白質網絡中的相似功能團等。社區發現的目標就是從無標記的網絡中發現這樣的節點組合。目前，在信息網絡中，發現其中的社區結構，對用戶進行正確的輿論引導，營造健康的網絡環境，維護國家安全穩定[2]；在犯罪嫌疑人的信息網絡中，通過社區發現可以發現隱藏犯罪份子以及團伙的組織架構，給破案提供助益[3]；在商業方面，社區發現可用于個性化商品推薦[4]。早期網絡社區的研究主要基于“弱連接優勢理論”，使得研究人員認為網絡中的集群是由一些“信息虛線”連接而成，從而提出以圖分割﹑模塊度和中介中心性為基礎的模型，即通過移除能使節點集間相互隔離的邊來劃分社區[5-7]。上述模型的基礎是每個節點只能屬于一個社區。但真實的社區之間存在一定程度的重疊，即一個節點可以屬于多個社區。基于該思想，提出了派系過濾算法[8]﹑邊聚類LC算法[9]﹑標簽傳播算法[10]和混合隸屬度隨機塊模型[11]等。然而，大部分算法由于設定社區可重疊，可能使社區內部邊比外部邊少，從而導致非重疊區域的密度大于重疊區域這一不合理現象。

為了解決該問題，Jaewon通過改變以往社區發現算法中非重疊部分的鏈接密度高于重疊部分隱形假設，提出了社區隸屬模型（Community-Affiliation Graph Model，AGM）[12]。通過該模型不僅能有效解決上述不合理現象，而且能準確識別重疊社區劃分情況。然而，該算法主要存在以下兩點不足。一方面，在MCMC采樣階段，判定采樣結果是否能被接的過程中，僅考慮一個節點的隸屬改變之后相關社區的概率似然值的改變程度，沒有考慮該節點自身的節點屬性對社區的隸屬情況影響。另一方面，在計算社區似然值時運用的社區節點間生成邊的概率僅考慮社區所提供的概率，沒有引入節點間相似性對生成邊的影響[13]。針對上述問題，本文在原有的MCMC采樣過程中引入節點隸屬影響，同時在計算節點間生成邊概率時引入節點間相似性，以實現準確高效的社區識別。

1 基于社區隸屬模型AGM的重疊社區發現算法

基于社區隸屬模型AGM的社區發現算法是一種基于MCMC采樣算法的社區發現算法，核心概念定義如下[12]。

定義1：首先假定影響節點之間建立連接的主要因素是節點所屬的社區生成邊的概率P，則節點u﹑v之間生成一條邊的概率為：其中u﹑v屬于節點集V，k∈Cuv表示節點u﹑v同時所屬的社區。

定義2：基于定義1，當給定一個無向圖G(V,E)時，則圖G的似然函數為：

其中：B表示節點與社區之間關系的社區隸屬圖，常用形式為B(V,C,M)。如圖1所示，V表示網絡中所有節點的集合，C表示所有社區的集合，M表示社區與節點之間的關系集合。{Pc}表示社區內部節點之間生成邊的概率。

圖1 社區隸屬關系

定義3：更新{Pc}時，保持社區隸屬圖B不變，則：

定義4：采用MCMC采樣方法，對社區隸屬圖B(V,C,M)隨機做出刪除﹑增加和交換中的一種生成新圖B'(V ',C ',M ')，并以概率min(1,L(B',{Pc})/L(B,{Pc}))來決定是否接受該次變換。其中，刪除表示隨機的選擇有隸屬關系的節點u與社區C對(u,C)∈M，并將之從M中刪除；增加表示隨機選擇無隸屬關系的節點u與社區C對(u,C)?M，將其增加到M中；交換表示隨機的選擇兩個社區C1﹑C2和一個節點u，(u,C1)∈M，(u,C2)?M，將(u,C1)從M中移除，(u,C2)添加到M中，如圖2所示。

圖2 MCMC過程

基于社區隸屬模型AGM的社區發現算法的核心思想：首先給定復雜網絡G(V,E)，然后通過最優鄰居節點法隨機初始化社區隸屬圖B(V,C,M)，最后采用MCMC方法對隸屬圖B(V,C,M)進行不斷變換。當社區隸屬圖B對應的似然函數值最大時，得到的節點與社區之間的對應情況就是社區劃分結果。

基于社區隸屬模型AGM的社區發現算法進行實際應用時主要存在以下問題：MCMC采樣階段，判定采樣結果是否能被接的過程中，僅考慮一個節點的隸屬改變之后相關社區的概率似然值的改變程度，沒有考慮該節點自身的節點屬性對社區隸屬情況的影響；在計算社區似然值時運用的社區節點間生成邊的概率pc僅考慮社區所提供的概率，沒有引入節點間相似性對生成邊的影響。

2 基于改進MCMC方法的重疊社區發現算法

基于上述分析，提出了在原有的MCMC采樣過程中引入節點隸屬影響，同時在計算節點間生成邊概率時引入節點間相似性，以實現準確高效的社區識別。

2.1 節點相似度構建

在復雜網絡中，節點間相似性不僅與該節點的屬性相關，還與該節點所處的局部網絡環境相關。本文計算節點間相似度的方法是采用同鄰居算法（Common Neighbors）。它是局部信息中最簡單的相似性算法，表示的是若兩個節點連接的相同節點數越多，則這兩個節點相似程度越高。CN算法概念為：對于網絡中的任一節點u，定義u的鄰居節點集為φ(u)，那么兩個節點u和v的節點相似性Suv就定義為它們的共同鄰居節點數量比上兩個節點的全部鄰節點數量[13]，即：

相應地，式（1）改進為：

相應地，式（2）改進為：

相應地，式（3）改進如下：

2.2 節點影響力構建

當某一節點的多個鄰居節點屬于該社區時，則可以認為該節點在社區的重要程度可能性越大，同時屬于該社區的可能性越高。節點u與社區C之間的影響情況可表示為：

其中φ(u)表示u的鄰居節點，C表示社區C包含的節點，|C|表示社區C包含的節點個數。

基于改進MCMC方法的重疊社區算法詳細步驟如下：

輸入：復雜網絡G(V,E)，最大迭代次數maxIter

For i=1 to maxIter do

使用STMCMC方法，在社區隸屬圖前一狀態Bi中采樣，獲得新狀態Bi+1

3 實驗結果與分析

3.1 算法的評估指標

在基于AGM模型的社區發現算法中，用準確發現社區數U﹑平衡誤差率BER和F1分數作為指標來評估算法[3,14]。假定算法發現的社區集為則準確發現社區數U﹑平衡誤差率BER和F1分數的公式分別為：

3.2 實驗數據

為了測試改進后的算法性能，利用斯坦福大學提供的四種真實世界網絡數據[13]——amaon商品關系網絡﹑DBLP科學合著網絡﹑Youtube用戶關注網絡和LiveJournal社交網絡進行社區發現實驗。每種網絡的數據規模如表1所示。

由于斯坦福提供的數據的社區結構已知，為了提高效率，從每個數據集中隨機抽出50﹑100﹑150﹑200﹑300﹑500﹑1000個社區用做測試，抽取的數據包括社區成員節點以及與該社區成員相連接的其他節點。當然，為了保證這種實驗方式的合理性﹑科學性，首先要求隨機抽取，其次保證所抽節點集的節點度符合冪率分布，最后基于文獻[15]可知，當社區個數達到1000時，各項實驗指標會趨于穩定。具體地，所抽數據包含的節點個數及邊數如表2所示。

表2 實驗抽取數據

3.3 實驗結果與分析

鑒于MCMC方法的隨機性，最終選擇結果為選取的每組數據進行50次運算后的平均值。

從圖3﹑圖4可以看出，算法在DBLP科學合著網絡和Amaon商品關系網絡中具有相似背景或者功用等，能導致社區節點之間聯系緊密的網絡社區劃分效果較為優異。同時可以得出，在DBLP科學合著網絡中，改進算法的性能比原算法提高約14%；在Amazon商品關系網絡中，改進算法性能也提高的將近10%。從圖6可以看出，算法在LiveJournal社交網絡中也能做出有效的社區劃分，并且算法改進后各項評估指標也較改進之前提高了9%左右。但是，從圖5來看，改進前與改進后的算法在Youtube社區內部之間聯系不太緊密的網絡中，社區劃分效果都不明顯。綜上所述，此類算法能很好地適用于社區節點之間聯系緊密的網絡中，且改進后的算法明顯提高了社區發現的精確性和可靠性。

圖3 在Amazon商品網絡中的相關實驗數據

圖4 在DBLP科學合著網絡中的相關實驗數據

圖5 在Youtube用戶關注網絡中的相關實驗數據

圖6 在LiveJournal社交網絡中的相關實驗數據

4 結 語

本文分析基于AGM模型的社區發現算法的特點和不足，考慮節點相似性和影響力對生成邊的影響，經過理論分析和在真實數據集上的測試可以得出結論，改進后的算法可以明顯提高社區發現的精確性和可靠性。下一步，將更多考慮MCMC采樣的優化方案，并考慮引入MapReduce﹑MPI等并行計算框架，以期實現算法的并行化。

[1] 程學旗,沈華偉.復雜網絡的社區結構[J].復雜系統與復雜性科學,2011,8(01):57-70.

CHENG Xue-qi,SHEN Hua-wei.Community Structure in Complex Network[J].Science Technology of Complex Systems and Complexity,2011,8(01):57-70.

[2] 李玉翔.基于網絡社區的用戶興趣建模與推薦技術研究[D].鄭州:解放軍信息工程大學,2013.

LI Yu-xiang.Research on User Interest Modeling and Recommendation Technology Based on Internet Community[D].Zhengzhou:PLA Information Engineering University,2013.

[3] 劉巖,顧益軍,張大瀚.基于節點相似度的個人網絡社交圈發現算法改進研究[J].網絡安全技術與應用,2016(09):49-52.

LIU Yan,GU Yi-jun,ZHANG Da-han.Research on Improvement of Social Network Discovery Algorithm Based on Node Similarity[J].Network Security Technology and Application,2016(09):49-52.

[4] 陳晶,萬云.社交網絡中基于模塊度最大化的標簽傳播算法的研究[J].通信學報,2017,38(02):25-33.

CHEN Jing,WAN Yun.Study on Tag Propagation Algorithm Based on Modularity Maximization in Social Networks[J].Journal of Communication,2017,38(02):25-33.

[5] Fortunato S.Community Detection in Graphs[J].Physics Reports,2010,486(03-05):75-174

[6] 顧益軍,解易,張培晶.面向有組織犯罪分析的人際關系網絡節點重要性評價研究[J].中國人民公安大學學報:自然科學版,2013(04):66-68.

GU Yi-jun,XIE Yi,ZHANG Pei-jing.Study on the Importance of Network Node of Human Relationship Network for Organized Crime Analysis[J].Journal of Chinese People's Public Security University: Natural Science Edition,2013(04):66-68.

[7] 顧益軍,夏天.融合LDA與Text Rank的關鍵詞抽取研究[J].現代圖書情報技術,2014(07/08):41-47.

GU Yi-jun,XIA Tian.Keywords Extraction Using Fusion LDA and Text Rank[J].New Technology of Library and Information Service,2014(07/08):41-47.

[8] Gergely Palla,Imre Derényi,Illés Farkas,et al.Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[J].Nature,2005(435):814-818.

[9] Ahn Y Y,Bagrow J P,Lehmann S.Link Communities Reveal Multiscale Complexity in Networks[J].Nature,2010,466(7307):761.

[10] 張俊麗,常艷麗,師文.標簽傳播算法理論及其應用研究綜述[J].計算機應用研究,2013,30(01):21-25.

ZHANG Jun-li,CHANG Yan-li,SHI Wen.A Review of Tag Propagation Algorithms and Their Applications[J].Application Research of Computers,2013,30(01):21-25.

[11] 柴變芳,賈彩燕,于劍.基于統計推理的社區發現模型綜述[J].計算機科學,2012,39(08):1-7.

CHAI Bian-fang,JIA Cai-yan,YU Jian.A Survey of Community Discovery Models Based on Statistical Reasoning[J].Computer Science,2012,39(08):1-7.

[12] Yang J,Leskovec J.Community-Affiliation Graph Model for Overlapping Network Community Detection[C].IEEE International Conference on Data Mining,2012:1170-1175.

[13] 東昱曉,柯慶,吳斌.基于節點相似性的鏈接預測[J].計算機科學,2011,38(07):162-164.

DONG Yu-xiao,KE Qing,WU Bin.Link Prediction Based on Node Similarity[J].Computer Science,2011,38(07):162-164.

[14] Yang J,Leskovec J.Defining and Evaluating Network Communities Based on Ground-Truth[C].IEEE International Conference on Data Mining,Computer Society,2012:745-754.

[15] Yang J,Leskovec J.Overlapping Communities Explain Core-Periphery Organization of Networks[J].Proceedings of the IEEE,2014,102(12):1892-1902.