基于傳播影響力的重疊社區(qū)劃分算法

譚文安,陳雅雯,潘義博

(1.上海第二工業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,上海201209;2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京211106)

0 引言

隨著信息技術(shù)的迅速發(fā)展,復(fù)雜網(wǎng)絡(luò)研究逐漸成為學(xué)術(shù)界的熱點(diǎn)。社區(qū)結(jié)構(gòu)與小世界性、無標(biāo)度性并列,是復(fù)雜網(wǎng)絡(luò)最重要的特性之一,同一社區(qū)內(nèi)部節(jié)點(diǎn)之間聯(lián)系密切,不同社區(qū)之間的節(jié)點(diǎn)聯(lián)系稀疏[1]。

目前已有的社區(qū)發(fā)現(xiàn)算法根據(jù)劃分所得的社區(qū)是否存在重疊節(jié)點(diǎn),可分為重疊社區(qū)和非重疊社區(qū)。早期的研究多為非重疊社區(qū)發(fā)現(xiàn),即將完整的網(wǎng)絡(luò)拆分成若干個(gè)互不相交的子網(wǎng),較經(jīng)典的有FN算法(Fast-Newman Algorithm)[2]、GN算法(Girvan-Newman Algorithm)[3]和LPA(Label Propagation Algorithm)算法[4]等。之后涌現(xiàn)了許多經(jīng)典算法的改進(jìn)算法,Jin等[4]采用結(jié)構(gòu)相似度取代了GN算法中邊介數(shù)的概念,從而有效降低了算法的時(shí)間復(fù)雜度;Zhang等[6]與Peng等[7]分別針對(duì)LPA算法的缺陷進(jìn)行了改進(jìn)。

隨著對(duì)復(fù)雜網(wǎng)絡(luò)的深入研究,人們發(fā)現(xiàn)大多數(shù)真實(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)與社區(qū)之間可能并不是簡(jiǎn)單的“非此即彼”關(guān)系,對(duì)重疊社區(qū)的研究更具有現(xiàn)實(shí)意義。為此,Palla等[8]提出了CPM(Clique Percolation Method)算法,該算法通過搜索鄰接團(tuán)來挖掘重疊社區(qū)。Gregory等[9]提出COPRA算法(Community Overlap PRopagation Algorithm),對(duì)傳統(tǒng)LPA算法進(jìn)行修改,使之適用于重疊社區(qū)發(fā)現(xiàn)。Lancichinetti等[10]提出LFM算法(Local Fitness Method),該算法通過局部擴(kuò)展的方法進(jìn)行重疊社區(qū)發(fā)現(xiàn)。Shen等[11]提出了基于極大團(tuán)的凝聚式層次聚類方法,將極大團(tuán)視為社區(qū)的基本單元,用于發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)。Meghanathan等[12]提出了基于鄰域重疊的貪婪社區(qū)挖掘算法,以鄰域重疊度的遞增順序依次迭代刪除網(wǎng)絡(luò)的邊,并以模塊度值為算法優(yōu)化目標(biāo)。

加權(quán)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)研究成果相對(duì)較少。Blonel等[13]基于加權(quán)復(fù)雜網(wǎng)絡(luò)的模塊度提出了十分經(jīng)典的Louvain算法,實(shí)現(xiàn)在較大規(guī)模的復(fù)雜網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)。Bai等[14]提出利用成員向量來分配節(jié)點(diǎn)所屬社區(qū),實(shí)現(xiàn)基于密度峰值的社區(qū)發(fā)現(xiàn)算法。楊貴等[15]根據(jù)節(jié)點(diǎn)權(quán)重選取種子節(jié)點(diǎn),并根據(jù)節(jié)點(diǎn)對(duì)子圖的適應(yīng)度函數(shù)將種子節(jié)點(diǎn)擴(kuò)展成局部稠密子圖,最后合并局部稠密子圖實(shí)現(xiàn)社區(qū)劃分。

上述算法大多只能應(yīng)用于無權(quán)網(wǎng)絡(luò),現(xiàn)實(shí)生活中,網(wǎng)絡(luò)中的邊并非完全是存在與否的布爾關(guān)系。因此,加權(quán)網(wǎng)絡(luò)相比無權(quán)網(wǎng)絡(luò)更具有現(xiàn)實(shí)意義。針對(duì)加權(quán)網(wǎng)絡(luò)中的重疊社區(qū)劃分問題,本文提出了一種基于傳播影響力的重疊社區(qū)劃分算法COPRA-PI,該算法能夠高效地挖掘加權(quán)網(wǎng)絡(luò)中的重疊社區(qū)。

1 理論基礎(chǔ)與技術(shù)

1.1 相關(guān)算法介紹

1.1.1 LPA算法

2007年,Raghavan等[4]提出LPA算法。該算法基于相似的節(jié)點(diǎn)應(yīng)屬于同一個(gè)社區(qū)的思想,其主要過程如下:①初始化過程,為每個(gè)節(jié)點(diǎn)賦予一個(gè)與節(jié)點(diǎn)編號(hào)相同的標(biāo)簽;②迭代過程,將標(biāo)簽更新為與大多數(shù)鄰節(jié)點(diǎn)相同,若出現(xiàn)頻率最高的標(biāo)簽不止一個(gè),則隨機(jī)選取其中一個(gè)來更新自己的標(biāo)簽;③重復(fù)第②步,直到整個(gè)網(wǎng)絡(luò)中的標(biāo)簽達(dá)到穩(wěn)定的狀態(tài);④將標(biāo)簽相同的節(jié)點(diǎn)歸為一個(gè)社區(qū)。

LPA算法的優(yōu)點(diǎn)是時(shí)間復(fù)雜度低,其缺點(diǎn)也很明顯:迭代過程中隨機(jī)選取新標(biāo)簽會(huì)導(dǎo)致算法結(jié)果不穩(wěn)定。傳統(tǒng)標(biāo)簽傳播算法采用異步更新策略,即一部分節(jié)點(diǎn)在第t次迭代時(shí)及時(shí)更新自身所攜帶的標(biāo)簽,剩余節(jié)點(diǎn)在第t次迭代后不立即更新自身的標(biāo)簽。每次迭代時(shí)隨機(jī)選擇本次需要及時(shí)更新的節(jié)點(diǎn)。劉世超等[16]通過實(shí)驗(yàn)證明同步更新策略比異步更新策略劃分結(jié)果更穩(wěn)定、準(zhǔn)確。

1.1.2 COPRA算法

2010年,Gregory等[9]基于LPA的重疊社區(qū)發(fā)現(xiàn)算法提出了COPRA算法。當(dāng)社區(qū)允許出現(xiàn)重疊時(shí),一個(gè)節(jié)點(diǎn)就可能出現(xiàn)在兩個(gè)不同的社區(qū)中,為此Gregory設(shè)計(jì)了一種標(biāo)簽對(duì)集合的形式來表示節(jié)點(diǎn)所屬社區(qū)。標(biāo)簽對(duì)(c,b)中的c是標(biāo)簽號(hào),b是節(jié)點(diǎn)與社區(qū)c的隸屬度或符合度。該算法還設(shè)置了一個(gè)最大標(biāo)簽數(shù)m,即節(jié)點(diǎn)最多只能屬于m個(gè)社區(qū)。迭代次數(shù)為t時(shí),節(jié)點(diǎn)x與社區(qū)c的隸屬度可用下式計(jì)算:

其中,N(v)表示節(jié)點(diǎn)v鄰居節(jié)點(diǎn)的集合。

算法主要過程如下:

(1)社區(qū)初始化。將每個(gè)節(jié)點(diǎn)v的標(biāo)簽cv賦值,值與節(jié)點(diǎn)編號(hào)相同,將節(jié)點(diǎn)v與標(biāo)簽cv的隸屬度設(shè)置為1,即(cv,1)。

(2)迭代過程。每個(gè)節(jié)點(diǎn)v通過式(1)計(jì)算自身與鄰居節(jié)點(diǎn)攜帶的社區(qū)標(biāo)簽的隸屬度。保留隸屬度大于1/m的標(biāo)簽,加入標(biāo)簽對(duì)集合。如果所有的標(biāo)簽對(duì)中的隸屬度都小于1/m,則選擇其中隸屬度最大的標(biāo)簽加入標(biāo)簽對(duì)集合。當(dāng)隸屬度最大的標(biāo)簽對(duì)不止一個(gè)時(shí),從其中隨機(jī)選擇一個(gè)加入標(biāo)簽對(duì)集合。確定節(jié)點(diǎn)的標(biāo)簽對(duì)集合后,對(duì)隸屬度進(jìn)行規(guī)范化表示,使其滿足

式中,c(v)表示節(jié)點(diǎn)v可能屬于的社區(qū)標(biāo)簽的集合。

(3)重復(fù)步驟②,直到算法終止條件(跟蹤每輪計(jì)算結(jié)束后網(wǎng)絡(luò)中剩余標(biāo)簽集合的大小,當(dāng)連續(xù)兩輪不變,則認(rèn)為滿足終止條件)。

(4)每個(gè)節(jié)點(diǎn)所帶的標(biāo)簽對(duì)中的標(biāo)簽即代表節(jié)點(diǎn)所屬的社區(qū),節(jié)點(diǎn)的標(biāo)簽對(duì)集合中有幾個(gè)標(biāo)簽對(duì)即代表節(jié)點(diǎn)屬于幾個(gè)社區(qū)。

COPRA算法的優(yōu)、缺點(diǎn)和LPA算法相似。算法在執(zhí)行過程中穩(wěn)定性較差,主要表現(xiàn)在以下方面:m值需要手動(dòng)設(shè)置,具體選取方式不確定;算法執(zhí)行過程中對(duì)標(biāo)簽的隨機(jī)選取操作會(huì)造成結(jié)果不穩(wěn)定。

1.1.3 LFM算法

Lancichinetti等[10]提出LFM算法。該算法利用網(wǎng)絡(luò)的局部特性,從單獨(dú)的節(jié)點(diǎn)開始直至擴(kuò)展成一個(gè)社區(qū)。算法主要過程如下:

(1)隨機(jī)選取一個(gè)節(jié)點(diǎn)作為社區(qū)G的初始成員;

(2)選擇社區(qū)G所有鄰居節(jié)點(diǎn)中貢獻(xiàn)最大的節(jié)點(diǎn)加入社區(qū)G;

(3)計(jì)算并過濾社區(qū)G中貢獻(xiàn)值為負(fù)數(shù)的節(jié)點(diǎn);

(4)重復(fù)第②步和第③步,直至社區(qū)G所有鄰居節(jié)點(diǎn)對(duì)其的貢獻(xiàn)值都為負(fù)數(shù);

(5)若網(wǎng)絡(luò)中還存在未劃分的節(jié)點(diǎn),則在其中隨機(jī)選取一個(gè)節(jié)點(diǎn)作為新社區(qū)G′的初始成員,返回第(2)步,否則結(jié)束。

算法中提出了社區(qū)的適應(yīng)度函數(shù):

式中:是社區(qū)G內(nèi)部邊的數(shù)量;是社區(qū)G與社區(qū)外節(jié)點(diǎn)連邊的數(shù)量;參數(shù)α控制社區(qū)數(shù)量,取值為0～2之間的整數(shù)。

節(jié)點(diǎn)對(duì)社區(qū)的貢獻(xiàn)函數(shù)為

式中:fG+v是節(jié)點(diǎn)v加入社區(qū)G后社區(qū)的適應(yīng)度;fG?v是節(jié)點(diǎn)v未加入時(shí)社區(qū)的適應(yīng)度。

LFM算法的優(yōu)點(diǎn)是算法過程易理解,但算法隨機(jī)選取的種子節(jié)點(diǎn)的優(yōu)劣程度直接影響著后續(xù)的劃分結(jié)果,導(dǎo)致其魯棒性較差。

1.2 社區(qū)劃分的評(píng)價(jià)指標(biāo)

Newman等[17]提出了一種衡量社區(qū)劃分質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn),稱為模塊度函數(shù)。模塊度函數(shù)定義為

式中:Auv為網(wǎng)絡(luò)鄰接矩陣中的元素,定義為,如果節(jié)點(diǎn)u和v相鄰,Auv為1,否則為0;kv表示點(diǎn)v的度;m為網(wǎng)絡(luò)中邊的總數(shù)。如果v和u在一個(gè)社區(qū),函數(shù)σ(cv,cu)的取值為1,否則為0。

分析上述模塊度函數(shù)公式可知,Q的數(shù)值越大說明劃分的社區(qū)質(zhì)量越好。但是,當(dāng)社區(qū)之間存在重疊節(jié)點(diǎn)的情況下,該模塊度公式將不再適用。學(xué)者們?cè)谥丿B社區(qū)發(fā)現(xiàn)的研究過程中對(duì)衡量指標(biāo)進(jìn)行了改進(jìn),如喬少杰等[18]提出引入節(jié)點(diǎn)的模糊隸屬函數(shù)來表示節(jié)點(diǎn)屬于不同社區(qū)的“程度”;Shen等[11]對(duì)模塊度函數(shù)Q進(jìn)行改進(jìn),把模塊度函數(shù)擴(kuò)展到具有重疊社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)中,并且證明了重新定義的模塊度數(shù)值越高表示重疊社區(qū)劃分的效果越好,模塊度函數(shù)被重新定義為

式中,Ov表示點(diǎn)v所屬的社區(qū)個(gè)數(shù)。分析式(5)與式(6)可以看出,如果社區(qū)之間不存在重疊,那么表達(dá)式Q與表達(dá)式EQ是完全等價(jià)的。

2 基于傳播影響力的重疊社區(qū)劃分算法COPRA-PI

2.1 概念定義

加權(quán)網(wǎng)絡(luò)是由一組節(jié)點(diǎn)和其帶權(quán)值的邊所組成的全連通網(wǎng)絡(luò),其中網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為m,邊的數(shù)量為n。下面是關(guān)于基于傳播影響力的重疊社區(qū)劃分算法(COPRA-PI)的概念定義。

定義1(邊權(quán)值) 節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的邊權(quán)值用Aij表示,若Aij=0則表示i與j之間不存在連邊。

定義2(節(jié)點(diǎn)的度) 或稱節(jié)點(diǎn)強(qiáng)度,是連接該節(jié)點(diǎn)全部邊的權(quán)重之和,節(jié)點(diǎn)i的度用Di表示,可由下式計(jì)算:

定義3(節(jié)點(diǎn)影響力) 指的是標(biāo)簽在傳播的過程中,傳播者對(duì)接受者的影響。用V Ii→j表示標(biāo)簽從節(jié)點(diǎn)i傳播到節(jié)點(diǎn)j時(shí)的節(jié)點(diǎn)影響力,計(jì)算式為

定義4(邊影響力) 指標(biāo)簽在傳播過程中所經(jīng)過的邊對(duì)傳播過程的影響。用EIi→j表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間連邊的邊影響力值,其公式為

定義5(歷史標(biāo)簽影響力) 指節(jié)點(diǎn)的歷史標(biāo)簽對(duì)新標(biāo)簽的影響。歷史標(biāo)簽影響力HIi衡量節(jié)點(diǎn)i的歷史標(biāo)簽對(duì)當(dāng)前更新策略的影響,采用下式計(jì)算HIi:

式中:Ei為與節(jié)點(diǎn)i相連的邊的數(shù)量;Di/Ei表示節(jié)點(diǎn)i的平均度,因此可以把歷史標(biāo)簽影響力看作是一個(gè)跟節(jié)點(diǎn)i相同度數(shù)的節(jié)點(diǎn)通過一條權(quán)值為Di/Ei的邊對(duì)節(jié)點(diǎn)i進(jìn)行標(biāo)簽傳播的影響。

定義6(標(biāo)簽概率矩陣) 指每個(gè)節(jié)點(diǎn)擁有每個(gè)標(biāo)簽(屬于某個(gè)社區(qū))的概率大小,用一個(gè)m×m的矩陣P來表示,其中Pij表示節(jié)點(diǎn)i擁有標(biāo)簽j(節(jié)點(diǎn)i屬于社區(qū)j)的概率大小。最終每個(gè)節(jié)點(diǎn)所擁有的標(biāo)簽的概率和應(yīng)為1,即

定義7(節(jié)點(diǎn)最大標(biāo)簽數(shù)) 指節(jié)點(diǎn)能擁有的最大標(biāo)簽個(gè)數(shù)?？捎孟率?12)計(jì)算節(jié)點(diǎn)i的最大標(biāo)簽數(shù),

式中:CLi為節(jié)點(diǎn)i當(dāng)前的候選標(biāo)簽數(shù)量;Ei為節(jié)點(diǎn)i的邊的數(shù)量。

定義8(標(biāo)簽過濾)由于有最大標(biāo)簽數(shù)量L max的限制,因此需要對(duì)標(biāo)簽概率矩陣中的標(biāo)簽進(jìn)行過濾操作,當(dāng)標(biāo)簽概率小于1/(L max)時(shí),表明該標(biāo)簽與節(jié)點(diǎn)之間匹配程度不高,不足以保留。實(shí)際操作中,標(biāo)簽過濾操作指的是將標(biāo)簽概率小于1/(L max)的標(biāo)簽的概率值置為0。

定義9(標(biāo)準(zhǔn)化) 每輪標(biāo)簽傳播迭代結(jié)束后,都需要對(duì)標(biāo)簽概率矩陣進(jìn)行標(biāo)準(zhǔn)化操作,使其符合的要求。采用式(13)對(duì)標(biāo)簽概率矩陣進(jìn)行標(biāo)準(zhǔn)化處理。

2.2 算法描述

2.2.1 算法流程

基于傳統(tǒng)標(biāo)簽傳播算法中節(jié)點(diǎn)應(yīng)與其大多數(shù)鄰居屬于同一社區(qū)這一思想,本文提出COPRA-PI算法,來解決復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)發(fā)現(xiàn)問題。該算法在經(jīng)典重疊社區(qū)發(fā)現(xiàn)算法COPRA的基礎(chǔ)上進(jìn)行了以下改進(jìn)。

(1)將邊的權(quán)值與節(jié)點(diǎn)的度結(jié)合,采用節(jié)點(diǎn)強(qiáng)度的概念代替節(jié)點(diǎn)的度。在標(biāo)簽傳播過程中,即使是直接相鄰的節(jié)點(diǎn)也有“親疏”之分,這種“親疏”之分來源于節(jié)點(diǎn)之間連邊的權(quán)值不等,因此計(jì)算新標(biāo)簽時(shí)應(yīng)該將邊影響力因素也考慮進(jìn)去。

(2)影響節(jié)點(diǎn)迭代后所屬社區(qū)的不應(yīng)該只有節(jié)點(diǎn)鄰居的影響力與加權(quán)邊的影響力,節(jié)點(diǎn)自身的歷史標(biāo)簽信息也應(yīng)作為節(jié)點(diǎn)下一輪所屬社區(qū)的影響因素。針對(duì)上述分析的3個(gè)影響因素,COPRA-PI算法綜合考慮歷史標(biāo)簽遺留的影響力、邊影響力和節(jié)點(diǎn)影響力對(duì)節(jié)點(diǎn)新標(biāo)簽的影響。

(3)現(xiàn)有研究中,節(jié)點(diǎn)每次迭代可容納的標(biāo)簽數(shù)是固定的,并且需要人為設(shè)置,然而實(shí)際各個(gè)節(jié)點(diǎn)可容納的標(biāo)簽數(shù)量應(yīng)與節(jié)點(diǎn)本身以及當(dāng)前候選標(biāo)簽情況相關(guān),同時(shí)人為設(shè)置節(jié)點(diǎn)的最大標(biāo)簽數(shù)需要較多的先驗(yàn)知識(shí)。針對(duì)這一問題,COPRA-PI算法采用動(dòng)態(tài)確定節(jié)點(diǎn)最大標(biāo)簽數(shù)的方法,更具有合理性。

算法流程如圖1所示。

圖1 COPRA-PI算法流程圖Fig.1 COPRA-PI algorithm f l ow chart

2.2.2 算法主要步驟

(1)社區(qū)初始化。每個(gè)節(jié)點(diǎn)初始化時(shí)只攜帶一個(gè)與自身編號(hào)相同的標(biāo)簽,將標(biāo)簽概率矩陣置為一個(gè)單位矩陣。

(2)標(biāo)簽傳播。傳播過程中新的標(biāo)簽概率由節(jié)點(diǎn)影響力、邊影響力和歷史標(biāo)簽影響力這3個(gè)因素共同決定。傳播后新的標(biāo)簽概率采用下式計(jì)算:

式中:表示第t輪迭代時(shí)節(jié)點(diǎn)i屬于社區(qū)j的概率;HIi表示歷史標(biāo)簽影響力;表示第t?1輪迭代時(shí)節(jié)點(diǎn)i屬于社區(qū)j的概率;s表示節(jié)點(diǎn)i鄰居節(jié)點(diǎn)的個(gè)數(shù);vk表示節(jié)點(diǎn)i的第k個(gè)鄰居節(jié)點(diǎn);V Ivk→i表示標(biāo)簽從vk傳播到節(jié)點(diǎn)i的節(jié)點(diǎn)影響力;E表示連接節(jié)點(diǎn)vk與節(jié)點(diǎn)i的邊影響力;表示第t?1輪迭代時(shí)節(jié)點(diǎn)vk屬于社區(qū)j的概率。

(3)標(biāo)準(zhǔn)化概率矩陣與標(biāo)簽過濾。在每輪標(biāo)簽傳播結(jié)束以后,由于可能無法保證標(biāo)簽概率矩陣中各個(gè)節(jié)點(diǎn)所攜帶的標(biāo)簽的概率之和為1和最大標(biāo)簽數(shù)量L_max的限制,因此需要對(duì)節(jié)點(diǎn)進(jìn)行標(biāo)簽過濾以及標(biāo)簽概率矩陣標(biāo)準(zhǔn)化的過程。過濾與標(biāo)準(zhǔn)化時(shí)采用以下原則:如果節(jié)點(diǎn)的最大標(biāo)簽數(shù)量為1,則直接選擇概率最大的標(biāo)簽,將其概率置為1,同時(shí)將其余標(biāo)簽的概率置為0;否則,采用式(13)對(duì)標(biāo)簽概率矩陣進(jìn)行標(biāo)準(zhǔn)化,然后對(duì)節(jié)點(diǎn)的標(biāo)簽進(jìn)行過濾操作,最后再用式(13)重新進(jìn)行標(biāo)準(zhǔn)化。

(4)整個(gè)網(wǎng)絡(luò)中的標(biāo)簽達(dá)到穩(wěn)定的狀態(tài),不再隨著標(biāo)簽傳播而變化或者已經(jīng)達(dá)到了給定的最大迭代次數(shù)則算法終止,否則重復(fù)步驟(2)～(4)直到滿足算法終止條件。

2.2.3 算法偽代碼

算法1COPRA-PI算法

輸入 網(wǎng)絡(luò)的鄰接矩陣A,節(jié)點(diǎn)個(gè)數(shù)m,邊的個(gè)數(shù)

n,最大迭代次數(shù)max-C

輸出 標(biāo)簽概率矩陣P

1.for i from 1 to m do

2.for j from 1 to m do

3. Di=Di+Aij

4.end for

5.end for

6.for i from 1 to m do

7.Pii=1

8.end for

9.count=0

10.do

11.for i from 1 to m do

12. 根據(jù)式(14)計(jì)算新的標(biāo)簽概率new_Pi

13.end for

14.根據(jù)式(13)對(duì)標(biāo)簽概率矩陣new_P標(biāo)準(zhǔn)化

15.調(diào)用new-P=LF(new-P,A,m)進(jìn)行標(biāo)簽過濾然后對(duì)new-P標(biāo)準(zhǔn)化

16.count=count+1;

17.P=new-P

18.until每個(gè)節(jié)點(diǎn)的標(biāo)簽都穩(wěn)定或者count≥max-C

說明:第1～4步計(jì)算網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的強(qiáng)度,將邊的權(quán)值信息融入節(jié)點(diǎn)中。隨后在第6～8步將標(biāo)簽概率矩陣初始化為單位矩陣,即將每個(gè)節(jié)點(diǎn)只擁有與自身編號(hào)相同的一個(gè)標(biāo)簽。第11～13步計(jì)算得到新的標(biāo)簽概率矩陣,第12～16步進(jìn)行標(biāo)簽的標(biāo)準(zhǔn)化與過濾操作,其中第15步LF調(diào)用算法2實(shí)現(xiàn)。重復(fù)執(zhí)行第10～18步的操作直到每個(gè)節(jié)點(diǎn)的標(biāo)簽都穩(wěn)定或者算法已經(jīng)達(dá)到了給定的最大迭代次數(shù)。最后輸出最終的標(biāo)簽概率矩陣。其中標(biāo)簽過濾的偽代碼實(shí)現(xiàn)如算法2所示。

算法2 標(biāo)簽過濾過程

輸入 標(biāo)簽概率矩陣P,網(wǎng)絡(luò)的鄰接矩陣A,節(jié)點(diǎn)個(gè)數(shù)m

輸出 標(biāo)簽概率矩陣P

1.for i from 1 to m do

2.根據(jù)式(12)計(jì)算最大標(biāo)簽數(shù)L-maxi

3.if L-maxi=1 then

4. 找出節(jié)點(diǎn)i的標(biāo)簽中概率最大的標(biāo)簽label

5. for j from 1 to m do

6. Pi,j=0

7. end for

8. Pi,label=1

9.else

10. for j from 1 to m do

11. if Pi,j?L-maxi＜1 then

12. Pi,j=0

13. end if

14. end for

15.end if

16.end for

2.2.4 算法時(shí)間復(fù)雜度分析

CORPA-PI算法中計(jì)算節(jié)點(diǎn)強(qiáng)度的時(shí)間復(fù)雜度為O(m2),初始化標(biāo)簽概率矩陣的時(shí)間復(fù)雜度O(m),一次完整傳播過程的時(shí)間復(fù)雜度為O(n·L max),其中Lmax是節(jié)點(diǎn)的最大標(biāo)簽數(shù),標(biāo)簽概率矩陣標(biāo)準(zhǔn)化與標(biāo)簽過濾過程的時(shí)間復(fù)雜度都為O(m2),由于Lmax一般都較小,因此算法時(shí)間復(fù)雜度為O((c+1)·m2),其中c是迭代次數(shù)。

3 實(shí)驗(yàn)與結(jié)果分析

采用真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),并與典型的重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行對(duì)比,從社區(qū)發(fā)現(xiàn)質(zhì)量、算法收斂速度等角度驗(yàn)證COPRA-PI算法的效果,并對(duì)加權(quán)網(wǎng)絡(luò)與無權(quán)網(wǎng)絡(luò)的劃分效果進(jìn)行對(duì)比。實(shí)驗(yàn)環(huán)境為:1.70 GHz的Intel(R)Core(TM)i5-3317U CPU,4GB內(nèi)存,Windows 7操作系統(tǒng),所有算法均采用Java語(yǔ)言實(shí)現(xiàn)。

3.1 數(shù)據(jù)集介紹

實(shí)驗(yàn)采用了1組加權(quán)數(shù)據(jù)集和3組無權(quán)數(shù)據(jù)集,其中空手道俱樂部數(shù)據(jù)集有加權(quán)和無權(quán)兩種形式,除此之外還采用了經(jīng)典的海豚數(shù)據(jù)集和美國(guó)政治書數(shù)據(jù)集。下面先介紹數(shù)據(jù)集的來源與構(gòu)成。

(1)海豚數(shù)據(jù)集(Dolphins)。海豚數(shù)據(jù)集是由動(dòng)物學(xué)家Lussean等人對(duì)新西蘭神奇峽灣中62只寬吻海豚歷時(shí)7年多的細(xì)致觀察后建立的。在觀察過程中,他們發(fā)現(xiàn)由于其中一只海豚成員的消失,導(dǎo)致這群海豚逐漸分為了2個(gè)小群體。海豚數(shù)據(jù)集共包含62個(gè)節(jié)點(diǎn),159條邊。

(2)空手道數(shù)據(jù)集(Karate&Karate?)。空手道俱樂部數(shù)據(jù)集是Zachary通過對(duì)美國(guó)一所大學(xué)中的空手道俱樂部成員歷時(shí)兩年的觀察而構(gòu)建的。通過統(tǒng)計(jì)一個(gè)月內(nèi)兩個(gè)成員之間的交流次數(shù)形成邊的權(quán)值。在Zachary觀察期間,俱樂部的兩位核心成員的意見產(chǎn)生了分歧,導(dǎo)致該俱樂部最終分裂成以這兩位成員為核心節(jié)點(diǎn)的兩個(gè)新俱樂部?？帐值罃?shù)據(jù)集共有34個(gè)節(jié)點(diǎn),78條邊,其中Karate*為加權(quán)數(shù)據(jù)集。

(3)美國(guó)政治書數(shù)據(jù)集(Polbooks)。美國(guó)政治書網(wǎng)絡(luò)數(shù)據(jù)集是由Krebs建立的,網(wǎng)絡(luò)中的節(jié)點(diǎn)代表亞馬遜網(wǎng)上書店賣出的有關(guān)美國(guó)政治的書籍,網(wǎng)絡(luò)中的邊將購(gòu)買者經(jīng)常一起購(gòu)買的書連接起來。以亞馬遜網(wǎng)上書店中的圖書主題內(nèi)容與讀者評(píng)價(jià)為依據(jù),上述書籍被分為:自由派、中間派和保守派。該網(wǎng)絡(luò)包含105個(gè)結(jié)點(diǎn)和441條邊。

3.2 算法效果對(duì)比

CMP、COPRA和LFM算法都是重疊社區(qū)發(fā)現(xiàn)的經(jīng)典算法。CPM算法的效果一定程度上依賴于社區(qū)規(guī)模,即k值的大小。k值合適時(shí),劃分結(jié)果比較理想,反之k值選擇不合適時(shí),效果較差。除此之外,該算法在邊密集的網(wǎng)絡(luò)中更適用?；谝陨蟽煞N局限性,因此本文不選擇其作為對(duì)比算法。本文選擇COPRA算法和LFM算法進(jìn)行對(duì)比實(shí)驗(yàn),但是LFM算法的社區(qū)劃分結(jié)果受初始種子節(jié)點(diǎn)質(zhì)量的影響,種子節(jié)點(diǎn)的優(yōu)劣會(huì)影響劃分結(jié)果,因此對(duì)LFM算法進(jìn)行100次實(shí)驗(yàn)取均值。

使用上述4個(gè)數(shù)集對(duì)COPRA-PI算法的效果進(jìn)行驗(yàn)證。由于真實(shí)數(shù)據(jù)集的劃分形式無法確定,因此實(shí)驗(yàn)采用由Shen等[11]提出的重疊社區(qū)模塊度擴(kuò)展函數(shù)EQ來評(píng)價(jià)網(wǎng)絡(luò)中重疊型社區(qū)發(fā)現(xiàn)的質(zhì)量。表1給出了用不同算法在4個(gè)真實(shí)網(wǎng)絡(luò)中劃分所得社區(qū)的EQ值,其中COPRA算法的最大標(biāo)簽數(shù)k需手動(dòng)設(shè)置,當(dāng)k取值不同時(shí),所得的劃分結(jié)果也不相同,對(duì)比實(shí)驗(yàn)取EQ最優(yōu)時(shí)的k值。

表1 COPRA-PI算法與LFM、COPRA對(duì)比Tab.1 COPRA-PI Algorithm vs.LFM,COPRA

從表1中可以看出,所提出的COPRA-PI算法的EQ值都高于其他兩個(gè)算法,這表明所提出的COPRA-PI算法所劃分的社區(qū)質(zhì)量更高。分析表中Karate和Karate*的EQ值,可以看出3個(gè)算法在Karate*數(shù)據(jù)集上的模塊度值都高于Karate數(shù)據(jù)集,由此也印證了邊權(quán)重可以體現(xiàn)節(jié)點(diǎn)與節(jié)點(diǎn)之間的聯(lián)系強(qiáng)度,在社區(qū)發(fā)現(xiàn)的時(shí)候考慮權(quán)值信息可以取得更加合理和科學(xué)的結(jié)果。此外,LFM算法在無權(quán)網(wǎng)絡(luò)數(shù)據(jù)集上的劃分結(jié)果質(zhì)量一直不如COPRA算法,但是在加權(quán)網(wǎng)絡(luò)中卻取得了遠(yuǎn)比COPRA算法要好的效果,這表明LFM算法與COPRA算法相比可能更加適用于加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集中。

為了分析所提出的COPRA-PI算法的劃分速度,實(shí)驗(yàn)研究了COPRA-PI算法在4個(gè)數(shù)據(jù)集上的收斂情況,實(shí)驗(yàn)結(jié)果如圖2所示。從圖中可以看出,COPRA-PI算法的收斂速度較快,在4個(gè)真實(shí)數(shù)據(jù)集上均是在10次迭代內(nèi)就已經(jīng)達(dá)到收斂狀態(tài)了,結(jié)合表1的實(shí)驗(yàn)結(jié)果可以看出,COPRA-PI算法可以較快收斂并劃分出較高質(zhì)量的社區(qū)。

為了研究社會(huì)網(wǎng)絡(luò)圖中邊權(quán)值對(duì)社區(qū)劃分的影響,針對(duì)無權(quán)Karate和加權(quán)Karate?的社區(qū)劃分結(jié)果進(jìn)行重點(diǎn)分析。圖3和圖4分別為COPRAPI算法劃分無權(quán)Karate和加權(quán)Karate?社區(qū)結(jié)構(gòu)得到的。

圖2 算法COPRA-PI收斂性圖Fig.2 The convergence property of the algorithm COPRA-PI

圖3 COPRA-PI算法劃分Karate結(jié)果圖Fig.3 The result diagram of COPRA-PI algorithm by dividing the Karate community

圖4 COPRA-PI算法劃分Karate?結(jié)果圖Fig.4 The result diagram of COPRA-PI algorithm by dividing the Karate?community

分析圖3可知,COPRA-PI算法將無權(quán)Karate分成成了兩個(gè)社區(qū),分別用圓和正方形標(biāo)記以示區(qū)分。其中3號(hào)、9號(hào)和20號(hào)節(jié)點(diǎn)表示重疊節(jié)點(diǎn)。直觀可見,圓標(biāo)記的社區(qū)以34號(hào)節(jié)點(diǎn)為核心成員,正方形標(biāo)記的社區(qū)以1號(hào)節(jié)點(diǎn)為核心成員,社區(qū)個(gè)數(shù)及具有明顯核心成員這一信息數(shù)據(jù)集介紹中已知的信息相符合,3個(gè)重疊節(jié)點(diǎn)可視為這場(chǎng)分裂事件的“中立人員”。重疊節(jié)點(diǎn)中的9號(hào)和20號(hào)節(jié)點(diǎn)分別都與兩個(gè)小團(tuán)體的核心成員有聯(lián)系,因此被劃分為重疊節(jié)點(diǎn)是合理的。重疊節(jié)點(diǎn)中的3號(hào)節(jié)點(diǎn)與兩個(gè)社區(qū)中的成員聯(lián)系都很密切,且與“中立人員”9號(hào)也有聯(lián)系,所以3號(hào)節(jié)點(diǎn)被劃分為重疊節(jié)點(diǎn)也是合理的。

分析圖4可知,COPRA-PI算法將加權(quán)的空手道俱樂部也劃分成了兩個(gè)社區(qū),仍用圓和正方形標(biāo)記以示區(qū)分,節(jié)點(diǎn)之間邊的粗細(xì)代表權(quán)重大小,邊越粗代表這條邊的權(quán)重越大。其中9號(hào)節(jié)點(diǎn)表示重疊節(jié)點(diǎn)。相比較無權(quán)數(shù)據(jù)集,加權(quán)后的俱樂部中的3號(hào)和20號(hào)成員不再是“中立成員”,都向正方形社區(qū)倒戈。對(duì)于3號(hào)節(jié)點(diǎn)而言,盡管與兩個(gè)社團(tuán)交流都十分密切,但是從圖中可以直觀地看出,在節(jié)點(diǎn)影響力差不多的情況下,1號(hào)和2號(hào)節(jié)點(diǎn)與3號(hào)節(jié)點(diǎn)之間邊的權(quán)重明顯高于其他節(jié)點(diǎn),因此正方形社區(qū)的邊影響力更大,導(dǎo)致3號(hào)節(jié)點(diǎn)被劃分進(jìn)了正方形社區(qū)。對(duì)于9號(hào)節(jié)點(diǎn)所有的連邊中,與3號(hào)節(jié)點(diǎn)的連邊的權(quán)重是最大的,直觀并無法分辨9號(hào)節(jié)點(diǎn)應(yīng)該屬于哪個(gè)社區(qū),COPRA-PI算法將其歸為重疊節(jié)點(diǎn)也是合理的。

4 結(jié) 語(yǔ)

本文提出了一種基于傳播影響力的加權(quán)重疊社區(qū)發(fā)現(xiàn)算法。該算法將邊的權(quán)值與節(jié)點(diǎn)的度結(jié)合,采用節(jié)點(diǎn)強(qiáng)度表示加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的度,將加權(quán)網(wǎng)絡(luò)轉(zhuǎn)化為無權(quán)網(wǎng)絡(luò)進(jìn)行處理。算法通過定義節(jié)點(diǎn)標(biāo)簽概率矩陣,表示節(jié)點(diǎn)擁有每個(gè)標(biāo)簽(屬于某個(gè)社區(qū))的概率大小來實(shí)現(xiàn)社區(qū)重疊,即一個(gè)節(jié)點(diǎn)可以同時(shí)屬于不同社區(qū),并且記錄屬于每個(gè)社區(qū)的概率。標(biāo)簽概率矩陣由傳播影響力決定,即節(jié)點(diǎn)影響力、邊影響力和歷史標(biāo)簽影響力。在迭代傳播的同時(shí)進(jìn)行標(biāo)簽過濾,直至完成社區(qū)發(fā)現(xiàn)。實(shí)驗(yàn)結(jié)果表明所提出的算法充分考慮了可能影響節(jié)點(diǎn)所屬社區(qū)的因素,相比較其他兩種經(jīng)典的重疊社區(qū)發(fā)現(xiàn)算法表現(xiàn)出了更高的社區(qū)劃分質(zhì)量。

[1] FORTUNATO S.Community detection in graphs[J].Physics Reports,2010,486:75-174.

[2] ME N.Fast algorithm for detecting community structure in networks[J].Physical review.E,Statistical,nonlinear,and soft matter physics,2004,69:066133.

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

[4] RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in largescale networks[J].Physical Review.E,Statistical,nonlinear,and soft matter physics,2007,76(3):036106.

[5] JIN D,LIU J,JIA Z X,et al.K-nearest-neighbor network based data clustering algorithm[J].Pattern Recognition&Artif i cial Intelligence,2010,23(4):546-551.

[6] ZHANG X K,FEI S,SONG C,et al.Label propagation algorithm based on local cycles for community detection[J].International Journal of Modern Physics B,2015,29(5):1550029.

[7] PENG H,ZHAO D,LI L,et al.An improved label propagation algorithm using average node energy in complex networks[J].Physica A Statistical Mechanics&Its Applications,2016,460:98-104.

[8] PALLA G,DERE NYI I,FARKAS I S,et al.Uncovering the overlapping community structure of complex networks in nature and society[J],Nature,2005,435(7043):814-818.

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

[10]LANCICHINETTI A,FORTUNATO S,KERTESZ J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2008,11(3):19-44.

[11]SHEN H W,CHENG X,CAI K,et al.Detect overlapping and hierarchical community structure in networks[J].Physica A Statistical Mechanics&Its Applications,2008,388(8):1706-1712.

[12]MEGHANATHAN N.A greedy algorithm for neighborhood overlap-based community detection[J].Algorithms,2016,9(1):8.

[13]BLONDEL V D,GUILLAUME J,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics-Theory and Experiment,2008,2008(10):155-168.

[14]BAI X,YANG P,SHI X.An overlapping community detection algorithm based on density peaks[J].Neurocomputing,2016,226:7-15.

[15]楊貴,鄭文萍,王文劍,等.一種加權(quán)稠密子圖社區(qū)發(fā)現(xiàn)算法[J].軟件學(xué)報(bào),2017,28(11):3103-3114.

[16]劉世超,朱福喜,甘琳.基于標(biāo)簽傳播概率的重疊社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)學(xué)報(bào),2016,39(4):717-729.

[17]NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review.E,Statistical,Nonlinear,and Soft Matter Physics,2004,69(2):026113.

[18]喬少杰,韓楠,張凱峰,等.復(fù)雜網(wǎng)絡(luò)大數(shù)據(jù)中重疊社區(qū)檢測(cè)算法[J].軟件學(xué)報(bào),2017,28(3):631-647.