基于標簽傳播的半監督社區發現算法研究

魏芳芳 睢世杰 睢世凱

摘 要：近年來，許多關于社區發現的優秀算法被提出并取得了較好的社區劃分效果。但是到目前為止，沒有任何一種算法能夠同時在時間復雜度和準確度方面取得較好的表現。現實網絡中往往存在一些有利于指導社區發現的標簽信息，如must-link信息、cannot-link信息等。因此提出基于少量標簽信息傳播、拓撲結構的半監督社區發現算法S_LPA，分別在karate網絡、dolphins網絡、LFR基準網絡上進行測試。實驗結果表明，該算法S_LPA時間復雜度為O（m），相對其它算法，S_LPA在karate網絡和dolphins網絡的NMI值高于CNM、InfoMap、LPA算法，在LRF網絡上準確度高出約20%;提高參數u后，S_LPA算法可識別其它算法不能識別的社區結構。

關鍵詞：社區發現; 半監督; 標簽信息;標簽傳播

DOI：10. 11907/rjdk. 191234 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）007-0092-04

Semi-supervised Community Detection Based on Label Propagation

WEI Fang-fang1，SUI Shi-jie2， SUI Shi-kai3

（1. The Open University of China Information Department，Beijing 100039，China;

2. Fujian Nanwei Software Co.， Ltd.， Fuzhou 350000，China;

3. School of Computer Science and Engineering， University of Electronic Science and Technology of China， Chengdu 610054，China）

Abstract：In recent years， many algorithms about community detection have been proposed and achieved good results， but they belong to unsupervised learning and none of them can play a role in both time complexity and accuracy. In fact， many information in the network， like must-link information or cannot-link information， can help guide the community detection. So we propose the semi-supervised algorithm S_LPA based on label propagation， and combine the small information of the network with the topological structure. The S_LPA verifies that a small amount of label information in the network is helpful to guide community discovery. With the increase of label information， the NMI value increases continuously. The time complexity of S_LPA proposed in this paper is O（m）. Compared with other algorithms， the NMI value of S_LPA in karate networks and dolphins networks is higher than that of CNM， dolphins networks， InfoMap， LPA algorithm， and the accuracy is about 20% higher in LRF network; after improving the parameter u， S_LPA algorithm can also identify community structures that other algorithms can not recognize.

Key Words：community detection; semi-supervised; label information; label propogation

基金項目：國家開放大學校級項目（G18F0023Y）

作者簡介：魏芳芳（1991-），女，碩士，國家開放大學信息化部研究實習員，研究方向為網絡信息采集與整合。

0 引言

許多復雜系統可以被描述成復雜網絡的形式[1-2]。社區結構是網絡統計特征的體現。至今還沒有關于社區結構的規范性定義，廣義上社區結構的特點是不同社區的邊連接較少，社區自身的邊連接較多 [3]。如何發現有價值的社區結構并應用于復雜網絡具有重要意義。國內外關于社區發現的算法很豐富[4-8]。Girvan &Newman[9-10]提出GN算法，該算法通過計算網絡各邊的邊介數，刪除網絡中邊介數最大的邊，使算法準確率和復雜度均較高，但如果未知社區個數，則難以確定GN算法終止時間;Xie等[11]提出基于新規則和標簽傳播的算法LPA，該算法可提高計算效率和社區檢測效果;Wu 等[12]提出BMLPA算法，在算法初始化標簽時，快速生成粗糙核，對LAP算法進行改進;Liu[13]將標簽傳播和BRIM算法結合進行社區發現，BRIM算法能夠通過在二分網絡中遞歸地誘導兩類節點之間的劃分，從而生成更好的社區結構;Taher等[14]將公共鄰域相似性融入InfoMap算法，得到的加權單模網絡可以用隨機游走技術進行聚類。

改進的benchmark網絡模型LFR benchmark網絡更符合真實網絡的結構特征，具有社區大小和節點度數不均勻性的特征。圖1展示了[n=600]，[=40]，[max（k）=50]，[τ2=2]，[τ1=1]，[u=0.1]，[min（C）=50]，[max（C）=120]的LFR benchmark網絡結構。其中[n]為網絡節點總數，[]為網絡節點平均度，[max（k）]為網絡節點最大度，[τ2]為度分布的指數冪，[τ1]為社區大小的指數冪，[u]為混合系數，[min（C）]為社區大小的最小值，[max（C）]為社區大小的最大值[18-19]。

圖1 LFR基準網絡

3 評價標準

3.1 模塊度函數

模塊度是評價社區發現算法準確率的重要指標，模塊度值越大，社區發現效果越好;模塊度值越小，則社區發現效果越差[20-21]。

定義[A]是網絡鄰接矩陣，[ki]是節點[vi]的度，[m]是邊數，則模塊度[Q]為兩點間邊數與隨機網絡中邊數的差值，其計算公式如式（2）所示。

[Q=12mij[Aij-kikj2m]δ（Ci，Cj）]? ? ? ? （2）

[δ（Ci，Cj）]為二值函數，如果節點[vi]和[vj]同屬一個社區，則[δ=1]，否則[δ=0]。

令[Bij=Aij-kikj2m]，定義矩陣[D]，其中[Dic]表示節點[vi]是否屬于社區[c]，則模塊度[Q]如公式（3）所示。

[Q=12mTr（DTBD）]? ? ? ? （3）

如果社區劃分效果與隨機網絡一致，則[Q=0]。如果社區劃分效果非常好，則[Q]值偏大。一般而言，[Q]的取值區間為[0.3，0.7]。

3.2 標準化互斥信息

標準化互斥信息代表了網絡中兩種不同的社區劃分差異性，如果從一種社區劃分到另一種劃分所需的信息量較大，則兩個劃分差異性比較大;反之，則兩個劃分差異性較小[18-20]?；诖?，本文使用[NMI]作為社區發現算法好壞的評價標準。

假設混合矩陣[N]，其中行表示真實社區，列表示算法發現的社區。[Nij]表示真實社區[ci]與算法發現的社區[cj]中節點交集中節點數目。[NMI]如公式（4）所示。

[NMI（A，B）=-2i=1CAj=1CBNijlog（NijN/Ni.N.j）i=1CANi.log（Ni./N）+j=1CBN.jlog（N.j/N）] （4）

其中，[CA]表示網絡中存在的實際社區數，[CB]表示算法發現的社區數，[Ni.]表示[N]中第[i]行的和，[N.j]表示[N]中第[j]列的和，[NMI（A，B）]的變動區間為[0，1]。如果算法發現的社區結構與真實社區結構一致，則[NMI]值趨近于1;反之，[NMI]值趨近于0。

4 實驗分析

首先，本文將S_LPA算法在真實網絡上進行實驗，并與傳統CNM算法、InfoMap算法和LPA算法對比。為了衡量社區發現準確度，本文分別采用模塊度[Q]值和標準化互斥信息[NMI]作為評價標準。S_LPA初始化時，將隨機選擇網絡中20%的節點對作為先驗信息，并標注上must-link先驗信息和cannot-link先驗信息。本文將LPA算法和S_LPA算法運行10次，以其結果均值作為最終結果，如圖4所示。

圖2 真實網絡社區發現實驗結果

從圖2可以看出，如果以模塊度值[Q]作為社區發現準確度衡量標準，以上4種算法均可很好地識別出網絡社區結構。而基于模塊度優化的CNM算法準確度最高，其[Q]值遠遠高于其它幾種算法。但也可以看出，雖然S_LPA算法的[Q]值不是最高，但也可以得到一個較好的社區劃分結果。如果以標準化互斥信息[NMI]作為社區發現準確度評價標準，S_LPA算法準確度明顯高于其它幾種算法。[NMI]作為衡量真實社區結構與算法找到的社區結構間差異的標準，更能反映算法優劣。所以總的來說，S_LPA算法在真實網絡上的社區發現效果優于其它幾種算法。

其次，本文將S_LPA算法在LFR 基準網絡上進行實驗，并與傳統CNM算法、InfoMap算法和LPA算法對比。由于在生成LFR 基準網絡的過程中，每個節點均有自己的社區歸屬，本文將[NMI]作為社區發現的準確度評價標準。在實驗過程中，將產生混合系數[u]從0.1到0.9的9組數據集測試網絡，其中[u]值越大代表網絡社區結構越不明顯。在S_LPA起始階段，本文將隨機選擇網絡20%的節點對作為先驗信息，并為其隨機標上must-link先驗信息和cannot-link先驗信息。由于LPA算法和S_LPA算法的隨機性，本文分別將LPA算法和S_LPA算法運行10次，并將其結果計算平均值作為最終社區發現結果，實驗結果如圖3所示。

圖3 LFR基準網絡上的實驗結果

從圖3可以看出，當[u0.8]時，網絡社區結構不明顯，LPA算法和CNM算法均不能很好地識別出網絡社區結構，而S_LPA算法和InfoMap算法卻有不錯的表現。但當[u]值很小時，尤其是當[u=0.1]時，網絡社區結構非常明顯，但InfoMap社區發現準確度不高。故在LFR 基準網絡測試中，S_LPA算法社區發現準確度高于其它3種算法。

網絡中少量標簽信息能夠有效指導社區發現過程。為驗證少量標簽信息的作用，本文將S_LPA算法在社區結構不明顯、[u=0.9]的LFR 基準網絡上進行實驗，并將網絡中含有先驗信息的節點比例從0%逐漸增大至30%。從圖4可以看出，隨著網絡中含有先驗信息的節點比例增大，社區發現準確度NMI值逐漸增大，所以可以得出網絡中少量標簽信息可有效指導社區發現過程的結論。

圖4 NMI隨標簽信息增加變化的量

5 結語

本文提出半監督社區發現算法S_LPA，驗證了網絡中少量標簽信息有助于指導社區發現的設想。隨著標簽信息增多，NMI值不斷增大;相對其它算法，S_LPA算法在karate網絡和dolphins網絡的NMI值均高于CNM、InfoMap、LPA算法，在LRF網絡上準確度高出約20%;提高參數u后，S_LPA算法可識別出其它算法不能識別的社區結構。因此該算法具有較強的適用性，尤其是對于社區結構不明顯的網絡，S_LPA依然可進行有效識別。

參考文獻：

[1] HARENBERG S，BELLO G，GJELTEMA，et al. Community detection in large-scale networks： a survey and empirical evaluation[J]. Wiley Interdisciplinary Reviews Computational Statistics，2015，6（6）：426-439.

[2] WANG T， QIAN X， WANG X. Label propagation based community detection algorithm with dpark[C]. International Conference on Computational Social Networks， 2015：116-127.

[3] LU Z， SUN X， WEN Y， et al. Algorithms and applications for community detection in weighted networks[J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（11）：2916-2926.

[4] XIE J， KELLEY S， SZYMANSKI B K. Overlapping community detection in networks： the state-of-the-art and comparative study[J]. ACM Computing Surveys （CSUR）， 2013， 45（4）：1-35.

[5] 潘瀟，王斌君. 基于社交網絡的犯罪團伙發現算法研究[J]. 軟件導刊，2018，17（12）：77-80+86.

[6] 李衛疆，謝志勇，余正濤. 一種基于節點相似度的標簽傳播算法[J]. 軟件導刊，2018，17（02）：63-67.

[7] 趙中英，李超. 大數據環境下復雜社會網絡的社區發現方法研究綜述[J]. 軟件導刊，2016，15（12）：164-167.

[8] 沈海燕，李星毅. 一種新的基于標簽傳播的重疊社區發現算法[J]. 軟件導刊，2015，14（04）：59-62.

[9] EATON E，MANSBACH R. A spin-glass model for semi-supervised community detection[C]. Twenty-Sixth AAAI Conference on Artificial Intelligence，2012：900-906.

[10] ZHANG Z Y，SUN K D，WANG S Q. Enhanced community structure detection in complex networks with partial background information[J]. Scientific Reports，2013，3（11）：32-41.

[11] XIE J，SZYMANSKI B K. Community detection using a neighborhood strength driven label propagation algorithm[C]. IEEE Network Science Workshop，2011：1-8.

[12] 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.

[13] LIU X，MURATA T. Community detection in large-scale bipartite networks[J].? Transactions of the Japanese Society for Artificial Intelligence， 2010， 1（1）：50-57.

[14] ALZAHRANI T，HORADAM K J，BOZTAS S. Community detection in bipartite networks using random walks[C].? Proceedings of the 5th Workshop on Complex Networks CompleNet， 2014：157-163.

[15] WU Z， LIU Y， NIU J. A novel graph-based method to study community evolutions in social interactions[C]. 2015 IEEE Conference on Ubiquitous Intelligence and Computing ， 2016：62-67.

[16] XIE J， SZYMANSKI B K. Towards linear time overlapping community detection in social networks[C]. Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining， 2012：25-36.

[17] HUANG Z， WANG Z， ZHANG Z. Detecting overlapping and hierarchical communities in complex network based on maximal cliques[C]. Chinese National Conference on Social Media Processing， 2015：184-191.

[18] ZHANG P. Evaluating accuracy of community detection using the relative normalized mutual information[J]. Computer Science， 2015（11）：1-7.

[19] 楊曉波，陳楚湘，王至婉. 基于節點相似性的LFM社團發現算法[J]. 復雜系統與復雜性科學，2017，14（3）：85-90.

[20] 睢世凱，基于局部標簽信息的半監督社區發現算法研究[D]. 成都：電子科技大學，2015.

[21] 陳東明，王云開，黃新宇，等. 基于社團密合度的復雜網絡社團發現算法[J]. 東北大學學報：自然科學版，2019，40（2）：186-191.

（責任編輯：江 艷）