基于標簽傳播的半監(jiān)督社區(qū)發(fā)現(xiàn)算法研究

魏芳芳 睢世杰 睢世凱

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

關(guān)鍵詞：社區(qū)發(fā)現(xiàn); 半監(jiān)督; 標簽信息;標簽傳播

DOI：10. 11907/rjdk. 191234 開放科學（資源服務(wù)）標識碼（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-），女，碩士，國家開放大學信息化部研究實習員，研究方向為網(wǎng)絡(luò)信息采集與整合。

0 引言

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

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

圖1 LFR基準網(wǎng)絡(luò)

3 評價標準

3.1 模塊度函數(shù)

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

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

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

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

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

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

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

3.2 標準化互斥信息

標準化互斥信息代表了網(wǎng)絡(luò)中兩種不同的社區(qū)劃分差異性，如果從一種社區(qū)劃分到另一種劃分所需的信息量較大，則兩個劃分差異性比較大;反之，則兩個劃分差異性較小[18-20]。基于此，本文使用[NMI]作為社區(qū)發(fā)現(xiàn)算法好壞的評價標準。

假設(shè)混合矩陣[N]，其中行表示真實社區(qū)，列表示算法發(fā)現(xiàn)的社區(qū)。[Nij]表示真實社區(qū)[ci]與算法發(fā)現(xiàn)的社區(qū)[cj]中節(jié)點交集中節(jié)點數(shù)目。[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]表示網(wǎng)絡(luò)中存在的實際社區(qū)數(shù)，[CB]表示算法發(fā)現(xiàn)的社區(qū)數(shù)，[Ni.]表示[N]中第[i]行的和，[N.j]表示[N]中第[j]列的和，[NMI（A，B）]的變動區(qū)間為[0，1]。如果算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與真實社區(qū)結(jié)構(gòu)一致，則[NMI]值趨近于1;反之，[NMI]值趨近于0。

4 實驗分析

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

圖2 真實網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)實驗結(jié)果

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

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

圖3 LFR基準網(wǎng)絡(luò)上的實驗結(jié)果

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

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

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

5 結(jié)語

本文提出半監(jiān)督社區(qū)發(fā)現(xiàn)算法S_LPA，驗證了網(wǎng)絡(luò)中少量標簽信息有助于指導社區(qū)發(fā)現(xiàn)的設(shè)想。隨著標簽信息增多，NMI值不斷增大;相對其它算法，S_LPA算法在karate網(wǎng)絡(luò)和dolphins網(wǎng)絡(luò)的NMI值均高于CNM、InfoMap、LPA算法，在LRF網(wǎng)絡(luò)上準確度高出約20%;提高參數(shù)u后，S_LPA算法可識別出其它算法不能識別的社區(qū)結(jié)構(gòu)。因此該算法具有較強的適用性，尤其是對于社區(qū)結(jié)構(gòu)不明顯的網(wǎng)絡(luò)，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] 潘瀟，王斌君. 基于社交網(wǎng)絡(luò)的犯罪團伙發(fā)現(xiàn)算法研究[J]. 軟件導刊，2018，17（12）：77-80+86.

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

[7] 趙中英，李超. 大數(shù)據(jù)環(huán)境下復雜社會網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法研究綜述[J]. 軟件導刊，2016，15（12）：164-167.

[8] 沈海燕，李星毅. 一種新的基于標簽傳播的重疊社區(qū)發(fā)現(xiàn)算法[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] 楊曉波，陳楚湘，王至婉. 基于節(jié)點相似性的LFM社團發(fā)現(xiàn)算法[J]. 復雜系統(tǒng)與復雜性科學，2017，14（3）：85-90.

[20] 睢世凱，基于局部標簽信息的半監(jiān)督社區(qū)發(fā)現(xiàn)算法研究[D]. 成都：電子科技大學，2015.

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

（責任編輯：江 艷）