杜長江　王志曉　邢貞明

(中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，徐州，221116)

引　　言

隨著社交網(wǎng)絡(luò)的興起，社會網(wǎng)絡(luò)引起了研究人員的重視。社區(qū)結(jié)構(gòu)不僅反映了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，同時也被認(rèn)為是能體現(xiàn)真實(shí)社會網(wǎng)絡(luò)功能的一個重要屬性[1-2]，因此社區(qū)發(fā)現(xiàn)算法的研究有很重要的理論價值和現(xiàn)實(shí)意義[1,3-4]。比如針對互聯(lián)網(wǎng)用戶進(jìn)行社區(qū)劃分，可根據(jù)用戶所在社區(qū)提供特定服務(wù)，有很大的商業(yè)價值。

近年來，研究人員提出了很多富有成效的社區(qū)發(fā)現(xiàn)算法。經(jīng)典的基于圖劃分的KL (Kernighan-Lin)算法[5]和譜平分算法[6]，前者基于貪婪原理[5,7]，后者則利用拉普拉斯矩陣[6,8]的特征向量，都可將網(wǎng)絡(luò)劃分成兩個社區(qū)。但是這兩種方法有很大的局限性，適用于社區(qū)數(shù)目已知的網(wǎng)絡(luò)。基于層次聚類的GN(Girvan-Newman)算法[9]，Newman和Girvanc采用分裂思想，構(gòu)造出分層樹，可將網(wǎng)絡(luò)劃分為多個社區(qū)，一定程度上克服了KL算法[5]和譜平分算法[6]的缺陷，但是該算法復(fù)雜度較高[10]，而且社區(qū)數(shù)量不確定，依賴于在分層樹上選取的劃分位置[1]。2014年，Jiang等人[7]提出了基于優(yōu)化的貪心算法的社區(qū)發(fā)現(xiàn)算法(Algorithm based on greedy surprise optimization, AGSO)及其改進(jìn)版本FAGSO(Fast-AGSO)算法，該算法在實(shí)驗(yàn)中展現(xiàn)出了比社區(qū)發(fā)現(xiàn)的幾種重要算法更好的效果，包括BGLL(Blondel-Guillaume-Lambiotte-Lefebvre)[11]、CNM (Clauset-Newman-Moore)[12]、OSLOM(Order statistics local optimization method)[13]等。不同于傳統(tǒng)的算法，Raghavan等人[14]首次將標(biāo)簽傳播思想引入到社區(qū)發(fā)現(xiàn)領(lǐng)域，提出標(biāo)簽傳播算法(Label propagation algorithm，LPA)，綜合考慮了網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)本身的傳播特性,且具有較高的效率，適用于大規(guī)模網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)[15]。

然而上述算法均是針對非重疊社區(qū)，即網(wǎng)絡(luò)中的一個節(jié)點(diǎn)只能屬于一個社區(qū)[1]。但很顯然，社會網(wǎng)絡(luò)中一個節(jié)點(diǎn)屬于多個社區(qū)的情況是普遍存在的，比如，一個人在不同的領(lǐng)域扮演不同的角色、在論壇中參與不同社區(qū)的話題討論等。所以，重疊社區(qū)更符合復(fù)雜網(wǎng)絡(luò)的實(shí)際意義[1,16]。2005年，Palla等人[17]提出了基于團(tuán)過濾的重疊社區(qū)發(fā)現(xiàn)算法(Clique percolation method，CPM)。該方法假設(shè)社區(qū)由一系列相互連接的團(tuán)(完全子圖)構(gòu)成，通過搜索融合相鄰的團(tuán)來劃分社區(qū)。由于方法需要設(shè)置團(tuán)的初始規(guī)模K，因此劃分結(jié)果受到參數(shù)K的影響。作為經(jīng)典重疊社區(qū)發(fā)現(xiàn)算法，該算法常被當(dāng)作基準(zhǔn)算法與其他算法比較[18]。2007年，Steve等人[19]在GN算法的基礎(chǔ)上進(jìn)行改進(jìn)給出了CONGA(Cluster-overlap Newman Grivan algorithm)算法使其可用于重疊社區(qū)發(fā)現(xiàn),并在其基礎(chǔ)是進(jìn)一步引入局部中介度的概念，進(jìn)一步提出了CONGO算法(Cluster-overlap Newman Grivan optimization)[20]。

隨著現(xiàn)實(shí)網(wǎng)絡(luò)規(guī)模的不斷增加，這些傳統(tǒng)的方法由于時間復(fù)雜度高，在實(shí)際的應(yīng)用中有很大的限制[21]?？紤]到標(biāo)簽傳播算法LPA是一種高效率的社區(qū)發(fā)現(xiàn)算法[1,21]，很多學(xué)者對其進(jìn)行了改進(jìn)以應(yīng)用于重疊社區(qū)發(fā)現(xiàn)。2010年，Steve等人[22]在單一標(biāo)簽的基礎(chǔ)上引入了多標(biāo)簽的概念，提出了基于標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)算法 (Community overlap propagation algorithm，COPRA)，該算法不僅能發(fā)現(xiàn)重疊社區(qū)，且保留了LPA算法時間復(fù)雜度低的特點(diǎn)，其在大規(guī)模網(wǎng)絡(luò)上的實(shí)驗(yàn)表明COPRA效率遠(yuǎn)高于CPM和CNOGO算法； 2012 年，Wu等人[23]對其進(jìn)行改進(jìn)并提出了基于均衡多標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法(Balanced multi-label propagation algorithm， BMLPA) ，該算法重新設(shè)計(jì)了COPRA算法中的標(biāo)簽更新策略，一定程度上增加了算法的穩(wěn)定性，但是也使得算法的適應(yīng)性有所下降；2013年，王庚等人[24]在COPRA算法的基礎(chǔ)上提出了一種平衡重疊社區(qū)挖掘算法BOCLP(Balanced overlapping community detecting algorithm by label propagation),進(jìn)一步提高了算法的穩(wěn)定性，其在人工網(wǎng)絡(luò)上的實(shí)驗(yàn)表明該算法在社區(qū)結(jié)構(gòu)變模糊時效果優(yōu)于COPRA。2015年，Sun等人[25]提出了一種優(yōu)勢標(biāo)簽傳播算法(Dominant label propagation algorithm, DLPA)，該算法引入優(yōu)勢標(biāo)簽的概念，認(rèn)為節(jié)點(diǎn)傾向于處于優(yōu)勢標(biāo)簽所代表的社區(qū)中，并可根據(jù)輸入?yún)?shù)控制社區(qū)重疊率，當(dāng)然這也導(dǎo)致其結(jié)果不夠穩(wěn)定。隨后Liu等人[26]經(jīng)過進(jìn)一步研究提出了DLPAE(DLPA expansion)算法，提高了算法的穩(wěn)定性和劃分的準(zhǔn)確度。大量的實(shí)驗(yàn)表明[22,24]，雖然在處理社區(qū)結(jié)構(gòu)清晰的小型網(wǎng)絡(luò)時CPM有很好的效果，但是在大規(guī)模復(fù)雜網(wǎng)絡(luò)中，基于標(biāo)簽傳播的算法更有優(yōu)勢。

盡管基于標(biāo)簽傳播的算法具備簡單快速的優(yōu)點(diǎn)，適合目前的大規(guī)模社會網(wǎng)絡(luò)，但是普遍存在穩(wěn)定性差的問題，每次劃分結(jié)果可能不一致，且需要人為設(shè)置參數(shù)來限制節(jié)點(diǎn)所屬社區(qū)個數(shù)，這在很大程度上影響了算法在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集上社區(qū)劃分的準(zhǔn)確率?；贑OPRA的改進(jìn)算法也還存在需要設(shè)置參數(shù)，適應(yīng)性降低等缺陷。此外，傳統(tǒng)的多標(biāo)簽傳播算法在標(biāo)簽初始化及標(biāo)簽傳播過程中忽略了節(jié)點(diǎn)之間的差異，導(dǎo)致算法有較強(qiáng)的隨機(jī)性。可見，基于多標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法仍有改進(jìn)的空間。

1　MOLPA算法

針對COPRA算法及其改進(jìn)算法存在的缺陷，本文提出一種基于多標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)優(yōu)化算法(Multi-label propagation optimization algorithm, MOLPA),并從標(biāo)簽的初始化、標(biāo)簽傳播順序、標(biāo)簽選擇3個方面來對COPRA算法進(jìn)行改進(jìn)。

1.1　標(biāo)簽初始化

COPRA算法初始化時給每一個節(jié)點(diǎn)分配唯一的標(biāo)簽，然后通過標(biāo)簽迭代更新來完成社區(qū)發(fā)現(xiàn)。這種方式隨機(jī)性較強(qiáng)，每個節(jié)點(diǎn)之間都是平等的，容易導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定，降低準(zhǔn)確率。實(shí)際網(wǎng)絡(luò)中，不同節(jié)點(diǎn)的重要性和影響力往往是不一樣的，而且與節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置有很大關(guān)系。

Kitsak等人[27]提出K-核分解算法來確定節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性，K核是指所有節(jié)點(diǎn)度值均不小于K的最大子網(wǎng)絡(luò)，其中度值等于K小于K+1的那部分成為K-shell，簡稱Ks。其基本過程是：刪除網(wǎng)絡(luò)中所有度值為1的節(jié)點(diǎn)，然后更新網(wǎng)絡(luò)中節(jié)點(diǎn)的度值，繼續(xù)刪除度值為1的節(jié)點(diǎn)，重復(fù)此步驟直到剩余節(jié)點(diǎn)度值均大于1，此時被刪的部分Ks=1；同樣的方式，繼續(xù)刪除度值最小的節(jié)點(diǎn)，直到所有節(jié)點(diǎn)都被刪除，完成K核分解。該方法是一種全局的評估方法，在判斷節(jié)點(diǎn)重要度方面有較高的準(zhǔn)確度，而且時間復(fù)雜度為O(n)，比較適用于大規(guī)模網(wǎng)絡(luò)。

圖1　標(biāo)簽初始化示意圖Fig.1　Initialized labels of nodes

MOLPA算法在標(biāo)簽初始化時，先通過K-核分解方法來尋找網(wǎng)絡(luò)影響力比較大的節(jié)點(diǎn)，作為社區(qū)初始核心，并逐漸向外傳播標(biāo)簽，當(dāng)多個核心節(jié)點(diǎn)往外擴(kuò)張到一定程度時，以它們?yōu)橹行乃纬傻纳鐓^(qū)很可能會產(chǎn)生交集，就是要尋找的重疊社區(qū)。如圖1所示，核心節(jié)點(diǎn)1和2在往外傳播標(biāo)簽的過程中產(chǎn)生的重疊部分的節(jié)點(diǎn)就是兩個社區(qū)間的重疊節(jié)點(diǎn)。

1.2　標(biāo)簽傳播順序

COPRA算法在進(jìn)行標(biāo)簽傳播的時候，首先將所有節(jié)點(diǎn)隨機(jī)排列，然后按照隨機(jī)序列的順序來更新每一個節(jié)點(diǎn)的標(biāo)簽。這樣的更新方式忽略了節(jié)點(diǎn)之間的差異，而且不同的排列順序下所產(chǎn)生的標(biāo)簽傳播結(jié)果也不同，導(dǎo)致社區(qū)劃分的穩(wěn)定性差、準(zhǔn)確率不高。

為了提高社區(qū)劃分結(jié)果的質(zhì)量，減少隨機(jī)性，MOLPA對COPRA算法的標(biāo)簽更新順序進(jìn)行了改進(jìn)。將標(biāo)簽初始化時找到的網(wǎng)絡(luò)核心節(jié)點(diǎn)按照Ks值進(jìn)行降序排列得到序列T，首先更新序列T中的第一個核心節(jié)點(diǎn)的第一層鄰居節(jié)點(diǎn)，然后更新第二個核心節(jié)點(diǎn)的第一層鄰居節(jié)點(diǎn)，直到把所有核心節(jié)點(diǎn)的第一層鄰居節(jié)點(diǎn)都更新完畢；下一次迭代再從第一個核心節(jié)點(diǎn)開始更新其第二層鄰居節(jié)點(diǎn)，依次進(jìn)行，每次迭代都按順序以所有核心節(jié)點(diǎn)為中心向外傳播一層，直到所有節(jié)點(diǎn)的標(biāo)簽都達(dá)到穩(wěn)定狀態(tài)，兩個社區(qū)交界處的重疊部分就是要找的重疊社區(qū)。這樣的標(biāo)簽更新策略，以節(jié)點(diǎn)的重要度為指導(dǎo)，使得標(biāo)簽傳播過程更加有序，社區(qū)劃分結(jié)果更穩(wěn)定。并且由于只從核心節(jié)點(diǎn)向外層傳播標(biāo)簽，減少了許多無意義社區(qū)的產(chǎn)生，使得其在提高社區(qū)劃分準(zhǔn)確度的同時，算法效率不至于損失過大。

1.3　標(biāo)簽選擇

COPRA算法在標(biāo)簽更新的過程中，通過設(shè)置參數(shù)v來決定節(jié)點(diǎn)的標(biāo)簽個數(shù)，篩選出隸屬度大于1/v的標(biāo)簽。顯然v值的設(shè)置很關(guān)鍵。然而在一個陌生的網(wǎng)絡(luò)中，事先很難得知一個節(jié)點(diǎn)最多屬于幾個社區(qū)，而且每個節(jié)點(diǎn)的情況都不一樣，如果用一個統(tǒng)一的參數(shù)去衡量它們，必定會影響到最終結(jié)果的準(zhǔn)確性。

圖2　多標(biāo)簽傳播過程示例Fig.2　Process of multi-label propagation

針對此問題，MOLPA算法采用一種新的標(biāo)簽選擇策略，由節(jié)點(diǎn)鄰接點(diǎn)的標(biāo)簽種類來決定節(jié)點(diǎn)的標(biāo)簽個數(shù)。如圖2所示，通過更新節(jié)點(diǎn)1的標(biāo)簽比較兩種更新策略。

使用COPRA算法來更新節(jié)點(diǎn)1的標(biāo)簽，首先計(jì)算它的鄰居節(jié)點(diǎn)標(biāo)簽的和a:1/2+1/2=1；b:1；c:1/2+1/2=1；d:1。屬于標(biāo)簽隸屬度相同的情況，就隨機(jī)選擇兩個(假設(shè)算法初始化的時候設(shè)置參數(shù)v=2)，比如選擇a,b，然后歸一化處理，使得節(jié)點(diǎn)更新后的標(biāo)簽隸屬度和為1。因此，節(jié)點(diǎn)1更新后的標(biāo)簽為(a,1/2)和(b,1/2)。本來節(jié)點(diǎn)1是a，b，c，d這4個社區(qū)的重疊節(jié)點(diǎn)，但由于人為地設(shè)置參數(shù)v和隨機(jī)選擇，最終節(jié)點(diǎn)1只屬于a和b這兩個社區(qū)，這跟實(shí)際情況顯然有出入。顯然參數(shù)v的設(shè)置對COPRA劃分結(jié)果的影響很大，而MOLPA采用新的標(biāo)簽選擇策略能夠避免標(biāo)簽選擇時的隨機(jī)性，有助于提高算法的穩(wěn)定性和劃分的準(zhǔn)確度。

使用MOLPA算法的標(biāo)簽選擇策略，就不需要設(shè)置v的值，而是根據(jù)節(jié)點(diǎn)1的鄰接點(diǎn)標(biāo)簽種類個數(shù)來確定。因此，此時v等于4，這4個標(biāo)簽值都大于1/4，所以都保留下來，經(jīng)過歸一化，最終節(jié)點(diǎn)1的標(biāo)簽為(a,1/4)，(b,1/4)，(c,1/4)，(d,1/4)，節(jié)點(diǎn)1同時屬于這4個社區(qū)。很顯然，與COPRA算法的結(jié)果相比，這種標(biāo)簽選擇更加符合實(shí)際需求。

1.4　算法描述和流程

MOLPA算法具體過程如下。

輸入：G=(V,E)。

輸出：社區(qū)劃分結(jié)果。

Step1利用K-核分解計(jì)算所有節(jié)點(diǎn)的Ks值，找到所有初始核心節(jié)點(diǎn)并按照降序排列為序列T={corei}，i=1,…,k，為每一個核心節(jié)點(diǎn)corei賦予唯一的標(biāo)簽，標(biāo)簽的格式為(corei,1)。

Step2首先更新序列T中第一個社區(qū)核心節(jié)點(diǎn)的第一層鄰居節(jié)點(diǎn)，接著更新序列T中第二個社區(qū)核心節(jié)點(diǎn)的第一層鄰居節(jié)點(diǎn)，直到所有社區(qū)核心節(jié)點(diǎn)的第一層鄰居都更新完畢；然后再從序列T中的第一個社區(qū)核心節(jié)點(diǎn)開始更新它的第二層鄰居節(jié)點(diǎn)，依次進(jìn)行。

Step3當(dāng)所有節(jié)點(diǎn)標(biāo)簽不再變化，結(jié)束標(biāo)簽更新。

Step4將標(biāo)簽相同的節(jié)點(diǎn)合并為同一個社區(qū)。

MOLPA算法的時間復(fù)雜度包括兩部分：第一部分為使用K-核分解法找出核心節(jié)點(diǎn)，時間復(fù)雜度為O(n+nlogn)；第二部分為標(biāo)簽傳播，時間復(fù)雜度為O(vavgmlog(vavgm/n))，vavg為節(jié)點(diǎn)平均所屬社區(qū)個數(shù)。因此算法總的時間復(fù)雜度為O(n+nlogn+vavgmlog(vavgm/n))，在稀疏網(wǎng)絡(luò)上，vavg值很小，此時算法的時間復(fù)雜度接近O(n+nlogn)。MOLPA算法按照核心節(jié)點(diǎn)的重要度大小來規(guī)定標(biāo)簽更新順序，避免了許多不必要的迭代，實(shí)際應(yīng)用中算法的效率很高。算法流程見圖3。

圖3　基于多標(biāo)簽傳播的重疊社區(qū)優(yōu)化算法流程圖Fig.3　Process of MOLPA

2　實(shí)驗(yàn)結(jié)果和分析

為進(jìn)一步驗(yàn)證算法的有效性，將MOLPA算法和兩種標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)算法COPRA與BOCLP算法以及傳統(tǒng)的基于團(tuán)過濾的重疊社區(qū)算法CPM算法進(jìn)行實(shí)驗(yàn)對比，由于標(biāo)簽傳播算法具有不穩(wěn)定性，每一次的結(jié)果會有差異，因此以下實(shí)驗(yàn)都是進(jìn)行10次并取平均值。

2.1　實(shí)驗(yàn)數(shù)據(jù)

(1)LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集

LFR 基準(zhǔn)網(wǎng)絡(luò)[28]是人工數(shù)據(jù)集，被許多研究者用來檢測社區(qū)發(fā)現(xiàn)算法的功能，它能夠生成用戶指定分布的網(wǎng)絡(luò)，包括網(wǎng)絡(luò)節(jié)點(diǎn)度的分布和各個社區(qū)中節(jié)點(diǎn)數(shù)的分布。

LFR基準(zhǔn)網(wǎng)絡(luò)主要包含以下參數(shù)：N表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目；mink和maxk分別表示節(jié)點(diǎn)最小度數(shù)和最大度數(shù)；minc和maxc表示社區(qū)內(nèi)節(jié)點(diǎn)個數(shù)的最小值和最大值；μ為混合參數(shù)，表示社區(qū)結(jié)構(gòu)清晰程度，它的取值范圍為0到1，μ的值越大說明網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越模糊；on指的是重疊節(jié)點(diǎn)個數(shù)；om代表重疊節(jié)點(diǎn)所屬社區(qū)的數(shù)目?？梢詫@些參數(shù)設(shè)置不同的值來控制節(jié)點(diǎn)數(shù)目、邊密度、社區(qū)重疊情況等。實(shí)驗(yàn)所用的LFR數(shù)據(jù)集參數(shù)如表1所示。

表1　LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)

(2)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

為驗(yàn)證算法在真實(shí)網(wǎng)絡(luò)中的有效性，選取了7組真實(shí)網(wǎng)絡(luò)數(shù)據(jù)，Zachary′s Karate Club、Dolphin Social Network、American College Football以及PGP、DBLP等[29]。這些真實(shí)網(wǎng)絡(luò)的數(shù)據(jù)來自http://www-personal.umich.edu/～mejn/netdata/和 http://snap.stanford.edu/data/index.html，具體參數(shù)如表2所示。

表2　真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

2.2　評價標(biāo)準(zhǔn)

實(shí)驗(yàn)用到兩個評價指標(biāo)：標(biāo)準(zhǔn)化互信息(Normalized mutual information，NMI)[1]和模塊度函數(shù)Q(Modularity)[9]。

(1)標(biāo)準(zhǔn)化互信息NMI

2009年，Lancichinetti等人[30]提出了基于重疊社區(qū)結(jié)構(gòu)的NMI。假設(shè)C表示網(wǎng)絡(luò)實(shí)際的社區(qū)集合，|C|表示社區(qū)的個數(shù)。則可以使用二元向量xi來表示節(jié)點(diǎn)i屬于哪一個社區(qū)，xi的長度為|C|，(xi)k取值是0或1，表示節(jié)點(diǎn)是否屬于社區(qū)k。將xi的第k個元素當(dāng)成一個隨機(jī)變量Xk，它的概率分布為P(Xk=1)=nk/n，P(Xk=0)=1-nk/n，其中nk指的是社區(qū)k的節(jié)點(diǎn)數(shù)目，n指網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)。類似地，在社區(qū)劃分集合C'中，Yl代表節(jié)點(diǎn)屬于社區(qū)l的概率分布。Xk在Yl上的條件熵定義為H(Xk|Yl)=H(Xk,Yl)-H(Yl)，根據(jù)H(Xk|Y)，Xk在Y(所有Yl構(gòu)成的集合)上的條件熵H(Xk|Y)為

(1)

X(所有Xk構(gòu)成的集合)在Y上的規(guī)范化條件熵為

(2)

類似地，可以計(jì)算Y在X上的規(guī)范化條件熵 。最終根據(jù)式(1)計(jì)算2個社區(qū)集合的規(guī)范化互信息

NMI(X|Y)=1-[H(X|Y)+H(Y|X)]/2

(3)

(2)模塊度函數(shù)EQ

模塊度Q指標(biāo)針對的是非重疊社區(qū)結(jié)構(gòu)，Shen等[31]將模塊度進(jìn)一步擴(kuò)展，給出可以衡量重疊社區(qū)結(jié)構(gòu)的EQ函數(shù)。表達(dá)式如下

(4)

式中：Ov表示節(jié)點(diǎn)v從屬的社區(qū)個數(shù)，A表示網(wǎng)絡(luò)所對應(yīng)的鄰接矩陣，Avw表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的邊數(shù)，m表示網(wǎng)絡(luò)中的邊數(shù)，kv和kw分別表示節(jié)點(diǎn)v和w的度。用EQ函數(shù)評價非重疊社區(qū)，EQ的值越大則表示重疊社區(qū)的模塊化程度越高。

2.3　測試實(shí)驗(yàn)參數(shù)

圖4　算法參數(shù)測試結(jié)果Fig.4　NMI results of COPRA and BOCLP of b1 and b2

考慮到算法存在的不穩(wěn)定性，為了更加客觀地對比MOLPA與COPRA、BOCLP以及CPM 4種算法的性能，選取這些算法的最優(yōu)結(jié)果與MOLPA算法結(jié)果進(jìn)行對比。由于COPRA算法和BOCLP算法在標(biāo)簽傳播過程中，需要設(shè)置參數(shù)v(節(jié)點(diǎn)最多屬于v個社區(qū))來確定節(jié)點(diǎn)的標(biāo)簽個數(shù)，為了得到一個最優(yōu)的v值，在b1和b2兩個不同規(guī)模的人工網(wǎng)絡(luò)上對COPRA算法和BOCLP算法進(jìn)行實(shí)驗(yàn)，其中混合參數(shù)μ=0.4，實(shí)驗(yàn)結(jié)果如圖4所示。由圖4可知，當(dāng)v取7或者8的時候，COPRA算法和BOCLP算法的效果最好，在后面的人工數(shù)據(jù)實(shí)驗(yàn)當(dāng)中這兩種算法的v值統(tǒng)一取8。

同理，由于CPM算法通過尋找完全子圖的方式來挖掘社區(qū)結(jié)構(gòu)，需要確定初始團(tuán)的規(guī)模K。Bron和Kerbosch[32]在測試團(tuán)生成算法的時候，發(fā)現(xiàn)K值取4～6都能取得較為理想的社區(qū)發(fā)現(xiàn)結(jié)果。因此實(shí)驗(yàn)中選取K=4。BOCLP算法也需要尋找完全子圖來確定網(wǎng)絡(luò)初始社區(qū)核心，同樣設(shè)置K=4。

2.4　結(jié)果分析

2.4.1LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集

實(shí)驗(yàn)選取了兩種不同的人工網(wǎng)絡(luò)，實(shí)驗(yàn)結(jié)果如下。

(1)NMI normalized mutual information結(jié)果

從圖5可以看出，在社區(qū)劃分的準(zhǔn)確度方面MOLPA算法要優(yōu)于其他幾種算法。在μ值較小時，所有的算法都能取得不錯的結(jié)果。但是隨著μ值的增大，社區(qū)結(jié)構(gòu)越來越模糊，雖然社區(qū)發(fā)現(xiàn)的難度增大了，但MOLPA算法一直保持不錯的效果。由于CPM算法和BOCLP算法都要通過尋找網(wǎng)絡(luò)中相互連通的團(tuán)(完全子圖)， 這對于網(wǎng)絡(luò)結(jié)構(gòu)的要求比較嚴(yán)格， 不適用于完全子圖較少的網(wǎng)絡(luò)；而且CORPA算法和BOCLP算法還需要設(shè)置參數(shù)v來控制節(jié)點(diǎn)的標(biāo)簽個數(shù)，所以社區(qū)發(fā)現(xiàn)效果不夠理想。這一實(shí)驗(yàn)表明了MOLPA初始化方法和標(biāo)簽傳播順序以及標(biāo)簽選擇策略的有效性。

圖5　LFR基準(zhǔn)數(shù)據(jù)集上的NMI結(jié)果對比Fig.5　NMI results of LFP Networks

(2)模塊度

LFR基準(zhǔn)數(shù)據(jù)集上模塊度實(shí)驗(yàn)結(jié)果如圖6所示。從圖6明顯看出，當(dāng)μ值比較小的時候，這4種算法的模塊度值較大，社區(qū)發(fā)現(xiàn)的結(jié)果質(zhì)量較高；當(dāng)μ逐漸增大的時候，即社區(qū)結(jié)構(gòu)越來越模糊，這時幾種算法的模塊度都有不同程度的降低，但是本文提出的MOLPA算法的效果相比其他算法表現(xiàn)較好，說明通過K-核分解方法以及新的標(biāo)簽傳播策略來改進(jìn)COPRA算法能夠很大程度提高社區(qū)模塊化程度，提升社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量。

圖6　LFR基準(zhǔn)數(shù)據(jù)集上模塊度實(shí)驗(yàn)結(jié)果Fig.6　Modulanity test results of LFR networks

(3)算法效率

接下來在人工網(wǎng)絡(luò)數(shù)據(jù)上測試這幾種算法的效率。表3列出了實(shí)驗(yàn)所用參數(shù)。節(jié)點(diǎn)個數(shù)N為1 000～5 000，網(wǎng)絡(luò)規(guī)模不斷增大，mink，maxk，minc，maxc，on，om等也會增大。

表3　人工網(wǎng)絡(luò)實(shí)驗(yàn)數(shù)據(jù)

圖7　算法運(yùn)行效率對比Fig.7　Comparison of efficiency of the four methods

不同算法的運(yùn)行效率對比如圖7所示。從圖7中可以看出，MOLPA算法的效率稍微遜色于COPRA，但是比其他兩種算法的性能都要好。CPM和BOCLP算法都要尋找完全子圖，這個過程耗費(fèi)的時間比較多；而MOLPA算法通過使用K-核分解方法尋找核心節(jié)點(diǎn)，K-核分解方法自身的效率就很高，而且固定的標(biāo)簽傳播順序也能減少迭代次數(shù)，社區(qū)結(jié)構(gòu)很快就穩(wěn)定，所以算法總體的時間復(fù)雜度相對于COPRA算法并沒有提高太多。

2.4.2真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

(1)與COPRA的對比試驗(yàn)

在真實(shí)網(wǎng)絡(luò)上，為了更加充分地了解K-核分解方法確定社區(qū)初始核心和標(biāo)簽傳播順序以及新提出的標(biāo)簽選擇策略的優(yōu)勢，分別比較3個多標(biāo)簽傳播算法：COPRA算法，K-COPRA算法和MOLPA算法。其中K-COPRA算法代表利用K-核分解方法確定社區(qū)初始核心和標(biāo)簽傳播順序的COPRA算法，節(jié)點(diǎn)的標(biāo)簽個數(shù)仍由參數(shù)確定。比較COPRA算法和K-COPRA算法，可以驗(yàn)證K-核分解方法的有效性，進(jìn)一步比較K-COPRA算法和MOLPA算法可以評估新的標(biāo)簽選擇策略的效果。實(shí)驗(yàn)結(jié)果如表4所示，其中v值均取算法最優(yōu)值。

表43種多標(biāo)簽傳播算法在真實(shí)網(wǎng)絡(luò)中的模塊度對比

Tab.4Comparisonofmodularityofthreemethodsbasedonmuti-labelpropagationinrealnetworks

網(wǎng)絡(luò)COPRAK?COPRAMOLPAvEQvEQEQKarate20．55920．6190．652Dolphins30．59720．6360．678Football20．48040．6290．664C．elegansmetabolicnetwork40．53350．5710．619PGPnetwork70．54780．5650．634Collaborationnetwork80．45980．5190．572DBLPcollaborationnetwork100．432110．4750．514

從表4中可以看出，在Karate網(wǎng)絡(luò)上，COPRA和K-COPRA算法取得最優(yōu)值時參數(shù)都為2，但是K-COPRA的社區(qū)模塊度更高，說明K-COPRA算法提高了社區(qū)發(fā)現(xiàn)的質(zhì)量，同時也驗(yàn)證了K-核分解方法確定社區(qū)初始核心和標(biāo)簽傳播順序的有效性；通過對比K-COPRA算法和MOLPA算法，發(fā)現(xiàn)MOLPA算法的社區(qū)模塊性能更好，這表明MOLPA算法的標(biāo)簽選擇策略有效。其他兩個網(wǎng)絡(luò)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果也證實(shí)了MOLPA算法在真實(shí)網(wǎng)絡(luò)上也能取得不錯的效果。

(2)不同的重疊社區(qū)發(fā)現(xiàn)算法對比

在真實(shí)網(wǎng)絡(luò)上測試CPM、BOCLP和MOLPA這3種重疊社區(qū)發(fā)現(xiàn)算法的表現(xiàn)。如表5所示，無論在規(guī)模比較小的空手道數(shù)據(jù)集上還是規(guī)模較大的足球比賽數(shù)據(jù)集上，MOLPA算法得到的社區(qū)發(fā)現(xiàn)的模塊度都高于其他3個算法，表明其社區(qū)劃分的質(zhì)量較好。

表5　3種重疊社區(qū)發(fā)現(xiàn)算法在真實(shí)網(wǎng)絡(luò)上的模塊度對比

3　結(jié)束語

本文介紹了一種基于多標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)算法MOLPA，并與傳統(tǒng)的團(tuán)過濾算法CPM、標(biāo)簽傳播算法COPRA及其改進(jìn)算法BOCLP進(jìn)行了對比。CPM算法是一種經(jīng)典的重疊社區(qū)發(fā)現(xiàn)算法，但和標(biāo)簽傳播算法相比效率不夠高。COPRA是標(biāo)簽傳播算法的核心算法之一，但存在隨機(jī)性強(qiáng)，社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定等缺陷；BOCLP對COPRA進(jìn)行了改進(jìn)一定程度上提高了穩(wěn)定性，但劃分結(jié)果仍受到參數(shù)設(shè)置的影響。本文提出的MOLPA算法首先利用K-核分解法找出網(wǎng)絡(luò)社區(qū)核心節(jié)點(diǎn)，給這些節(jié)點(diǎn)賦予唯一的標(biāo)簽，并且設(shè)置合理的標(biāo)簽迭代順序，避免了傳播過程中的隨機(jī)性，提高了算法的穩(wěn)定性；在標(biāo)簽選擇的時候由標(biāo)簽種類來決定節(jié)點(diǎn)的標(biāo)簽個數(shù)而不是人為設(shè)置參數(shù)，避免了結(jié)果受到參數(shù)的影響。實(shí)驗(yàn)表明MOLPA算法能在很大程度上減少無意義社區(qū)的生成，改善傳統(tǒng)標(biāo)簽傳播算法的不穩(wěn)定性問題，提高重疊社區(qū)發(fā)現(xiàn)的質(zhì)量。

參考文獻(xiàn):

[1]Xie J, Kelley S, Szymanski B K. Overlapping community detection in networks: The state-of-the-art and comparative study [J]. ACM Computing Surveys, 2011,45(4):115-123.

[2]Coscia M, Giannotti F, Pedreschi D. A classification for community discovery methods in complex networks [J]. Statistical Analysis & Data Mining, 2011,4(5):512-546.

[3]Yang J, Mcauley J, Leskovec J. Community detection in networks with node attributes[C]// 2013 IEEE 13th International Conference on Data Mining. [S.l.]: IEEE Computer Society, 2014:1151-1156.

[4]李亞芳,賈彩燕,于劍, 等. 一種新的社區(qū)/動態(tài)社區(qū)優(yōu)化方法 [J]. 數(shù)據(jù)采集與處理, 2015,30(6):1215-1224.

Li Yafang, Jia CaiYan, Yu Jian, et al. Novel community/dynamic community optimization algorithm[J]. Journal of Data Acquisition and Processing, 2015,30(6):1215-1224.

[5]Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell Labs Technical Journal, 1970,49(2):291-307.

[6]Barnes E R. An algorithm for partitioning the nodes of a graph [J]. SIAM Journal on Algebraic & Discrete Methods, 1981,3(4):303-304.

[7]Jiang Y, Jia C, Yu J. An efficient community detection algorithm using greedy surprise maximization [J]. Journal of Physics A Mathematical & Theoretical, 2014,47(16):1644-1649.

[8]Jia H, Ding S, Xu X, et al. The latest research progress on spectral clustering [J]. Neural Computing & Applications, 2014,24(7/8):1477-1486.

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

[10] 張海燕, 梁循, 周小平. 針對有向圖的局部擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法 [J]. 數(shù)據(jù)采集與處理, 2015，30(6):683-693.

Zhang Haiyan, Liang Xun, Zhou Xiaoping. Overlapping commuity detection from local extension in directed graphs[J]. Journal of Data Acquisition and Processing, 2015,30(6):683-693.

[11] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics Theory & Experiment, 2008,2008(10):155-168.

[12] Clauset A, Newman M E, Moore C. Finding community structure in very large networks [J]. Physical Review E, 2005,70(6 Pt 2):264-277.

[13] Lancichinetti A, Radicchi F, Ramasco J J, et al. Finding statistically significant communities in networks[J]. Plos One, 2011, 6(4):336-338.

[14] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007,76(3 Pt 2):036106.

[15] 駱志剛, 丁凡, 蔣曉舟, 等.復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J]. 國防科技大學(xué)學(xué)報,2011,33(1):47-52.

Luo Zhigang, Ding Fan, Jiang Xiaozhou, et al. New progress on community detectionin complex networks [J]. Journal of National University of Defense Technology, 2011, 33(1):47-52.

[16] Chakraborty T. Leveraging disjoint communities for detecting overlapping community structure[J]. Journal of Statistical Mechanics Theory & Experiment, 2015(5):P05017.

[17] Palla G, Derényi 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] Leskovec J, Lang K J, Dasgupta A, et al. Statistical properties of community structure in large social and information networks[C]// The International Conference of World Wide Web. 2008:695-704.

[19] Kim P, Kim S. Detecting overlapping and hierarchical communities in complex network using interaction-based edge clustering [J]. Physica A Statistical Mechanics & Its Applications, 2015,417(C):46-56.

[20] Abrahao B, Soundarajan S, Hopcroft J, et al. A separability framework for analyzing community structure [J]. ACM Transactions on Knowledge Discovery from Data, 2014,8(1):101-129.

[21] 王庚, 宋傳超, 盛玉曉, 等. 基于標(biāo)簽傳播的社區(qū)挖掘算法研究綜述 [J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2013(12):69-73.

Wang Geng, Song Chuanchao, Sheng Yuxiao, et al. Research summary on communities mining algorithm based on label propagation [J]. Computer Technology and Development, 2013(12):69-73.

[22] Gregory S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics, 2009,12(10):2011-2024.

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

[24] 王庚. 社會網(wǎng)絡(luò)中基于標(biāo)簽傳播的重疊社區(qū)挖掘研究[D]. 濟(jì)南：山東建筑大學(xué), 2013.

Wang Geng. Research to stable detecting overlapping communities by label propagation on social networks[D]. Jinan: Shandong Jianzhu University, 2013.

[25] Sun H L, Huang J B, Tian Y Q, et al. Detecting overlapping communities in networks via dominant label propagation [J]. Chinese Physics B, 2015, 24(1):551-559.

[26] Liu K, Huang J, Sun H, et al. Label propagation based evolutionary clustering for detecting overlapping and non-overlapping communities in dynamic networks [J]. Knowledge-Based Systems, 2015, 89(C):487-496.

[27] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks [J].Nat Phys, 2010, 6(11):888-893.

[28] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms [J]. Physical Review E, 2008, 78(4):561-570.

[29] Wang Z, Zhao Y, Xi J, et al. Fast ranking influential nodes in complex networks using a k-shell iteration factor [J]. Physica A Statistical Mechanics & Its Applications, 2016(461):171-181.

[30] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New Journal of Physics, 2008, 11(3):19-44.

[31] Shen Huawei. Detect overlapping and hierarchical community structure in networks[J]. Physica A: Statistical Mechanics and Its Applications, 2009, 388(8):1706-1712.

[32] Bron C, Kerbosch J. Finding all cliques of an undirected graph (algorithm 457)[J]. Communications of the ACM, 1973, 16(9):575-576.