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

魏芳芳 睢世杰 睢世凱

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

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

DOI：10. 11907/rjdk. 191234 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

基金項(xiàng)目：國(guó)家開放大學(xué)校級(jí)項(xiàng)目（G18F0023Y）

作者簡(jiǎn)介：魏芳芳（1991-），女，碩士，國(guó)家開放大學(xué)信息化部研究實(shí)習(xí)員，研究方向?yàn)榫W(wǎng)絡(luò)信息采集與整合。

0 引言

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

改進(jìn)的benchmark網(wǎng)絡(luò)模型LFR benchmark網(wǎng)絡(luò)更符合真實(shí)網(wǎng)絡(luò)的結(jié)構(gòu)特征，具有社區(qū)大小和節(jié)點(diǎn)度數(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é)點(diǎn)總數(shù)，[]為網(wǎng)絡(luò)節(jié)點(diǎn)平均度，[max（k）]為網(wǎng)絡(luò)節(jié)點(diǎn)最大度，[τ2]為度分布的指數(shù)冪，[τ1]為社區(qū)大小的指數(shù)冪，[u]為混合系數(shù)，[min（C）]為社區(qū)大小的最小值，[max（C）]為社區(qū)大小的最大值[18-19]。

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

3 評(píng)價(jià)標(biāo)準(zhǔn)

3.1 模塊度函數(shù)

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

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

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

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

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

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

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

3.2 標(biāo)準(zhǔn)化互斥信息

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

圖3 LFR基準(zhǔn)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

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

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

圖4 NMI隨標(biāo)簽信息增加變化的量

5 結(jié)語(yǔ)

本文提出半監(jiān)督社區(qū)發(fā)現(xiàn)算法S_LPA，驗(yàn)證了網(wǎng)絡(luò)中少量標(biāo)簽信息有助于指導(dǎo)社區(qū)發(fā)現(xiàn)的設(shè)想。隨著標(biāo)簽信息增多，NMI值不斷增大;相對(duì)其它算法，S_LPA算法在karate網(wǎng)絡(luò)和dolphins網(wǎng)絡(luò)的NMI值均高于CNM、InfoMap、LPA算法，在LRF網(wǎng)絡(luò)上準(zhǔn)確度高出約20%;提高參數(shù)u后，S_LPA算法可識(shí)別出其它算法不能識(shí)別的社區(qū)結(jié)構(gòu)。因此該算法具有較強(qiáng)的適用性，尤其是對(duì)于社區(qū)結(jié)構(gòu)不明顯的網(wǎng)絡(luò)，S_LPA依然可進(jìn)行有效識(shí)別。

參考文獻(xiàn)：

[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ò)的犯罪團(tuán)伙發(fā)現(xiàn)算法研究[J]. 軟件導(dǎo)刊，2018，17（12）：77-80+86.

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

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

[8] 沈海燕，李星毅. 一種新的基于標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)算法[J]. 軟件導(dǎo)刊，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é)點(diǎn)相似性的LFM社團(tuán)發(fā)現(xiàn)算法[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2017，14（3）：85-90.

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

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

（責(zé)任編輯：江 艷）