穩(wěn)定標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)方法

張 鑫， 劉秉權(quán)， 王曉龍

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 哈爾濱 150001)

?

穩(wěn)定標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)方法

張 鑫， 劉秉權(quán)， 王曉龍

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 哈爾濱 150001)

為提高標(biāo)簽傳播算法的穩(wěn)定性，解決標(biāo)簽傳播算法隨機(jī)性導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果相差較大的問(wèn)題，對(duì)標(biāo)簽初始化、隨機(jī)隊(duì)列設(shè)置和標(biāo)簽傳播中隨機(jī)選擇過(guò)程進(jìn)行了改進(jìn)，提出一種穩(wěn)定的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法. 該方法首先通過(guò)尋找不重疊三角形進(jìn)行標(biāo)簽初始化，然后以節(jié)點(diǎn)標(biāo)簽的熵確定節(jié)點(diǎn)隊(duì)列并分段隨機(jī)排序，最后考慮鄰接點(diǎn)的鄰接點(diǎn)標(biāo)簽分布情況進(jìn)行標(biāo)簽選擇. 實(shí)驗(yàn)結(jié)果表明，在Zachary’s Karate Club、Dolphin Social Network和American College Football 3個(gè)社會(huì)網(wǎng)絡(luò)上，本文方法的穩(wěn)定指標(biāo)和質(zhì)量指標(biāo)結(jié)果均高于其他方法. 穩(wěn)定標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)方法保持了標(biāo)簽傳播算法優(yōu)點(diǎn)的同時(shí)，提高了社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量和穩(wěn)定性.

社區(qū)發(fā)現(xiàn)；標(biāo)簽傳播；隨機(jī)性；標(biāo)簽的熵；穩(wěn)定性

網(wǎng)絡(luò)聚簇結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要特征之一，網(wǎng)絡(luò)聚簇結(jié)構(gòu)特征表明社區(qū)結(jié)構(gòu)存在于復(fù)雜網(wǎng)絡(luò)中. 社區(qū)，即其內(nèi)部節(jié)點(diǎn)之間關(guān)系相對(duì)緊密、內(nèi)部節(jié)點(diǎn)與外部節(jié)點(diǎn)關(guān)系相對(duì)稀疏的節(jié)點(diǎn)集合. 通過(guò)分析復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特征，挖掘復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，這個(gè)過(guò)程就是社區(qū)發(fā)現(xiàn). 起初，研究人員利用圖論和概率統(tǒng)計(jì)相關(guān)理論挖掘網(wǎng)絡(luò)的本質(zhì)和特點(diǎn). 隨著互聯(lián)網(wǎng)的信息爆炸和人們溝通方式的轉(zhuǎn)變，復(fù)雜網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模越來(lái)越大，快速、有效的社區(qū)發(fā)現(xiàn)方法成為多領(lǐng)域研究的熱點(diǎn)問(wèn)題之一[1]. 研究復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法對(duì)分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和層次結(jié)構(gòu)、理解社區(qū)的形成過(guò)程、預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的動(dòng)態(tài)變化、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中蘊(yùn)含的規(guī)律特征具有重要意義,在眾多領(lǐng)域有廣泛的應(yīng)用前景[2-5].

1970年，Kernighan和Lin基于貪婪算法提出了Kernighan-Lin方法[6]，用于將網(wǎng)絡(luò)劃分為兩個(gè)規(guī)模確定的社區(qū). 該方法需要預(yù)先設(shè)定社區(qū)規(guī)模等較多先驗(yàn)知識(shí)，在實(shí)際網(wǎng)絡(luò)中應(yīng)用有限. GN算法[7]是社區(qū)發(fā)現(xiàn)經(jīng)典方法之一，由Girvan和Newman于2001年提出. 該方法核心思想為社區(qū)內(nèi)的邊介數(shù)應(yīng)小于社區(qū)間的邊介數(shù). GN算法時(shí)間復(fù)雜度較高，為O(m2n)，其中，m表示網(wǎng)絡(luò)中邊的數(shù)量，n表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù). Newman等提出模塊度[8]作為衡量社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量?jī)?yōu)劣的標(biāo)準(zhǔn). Palla等[4,9-10]首次針對(duì)重疊社區(qū)提出了極大團(tuán)過(guò)濾社區(qū)發(fā)現(xiàn)方法. 該方法需要事先確定參數(shù)，不同的參數(shù)值使得社區(qū)發(fā)現(xiàn)結(jié)果差異較大.

針對(duì)上述傳統(tǒng)方法參數(shù)難以確定、算法復(fù)雜度高的不足，Zhu等[11]提出了標(biāo)簽傳播算法LPA(label propagation algorithm). 由于LPA方法時(shí)間復(fù)雜度低且效果好，研究人員對(duì)其進(jìn)行了大量深入研究. Raghavan等[12]首次將LPA方法用于復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)，提出了RAK方法. 該方法首先將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)賦予一個(gè)唯一的標(biāo)簽，然后根據(jù)當(dāng)前節(jié)點(diǎn)的鄰接點(diǎn)標(biāo)簽分布情況更新當(dāng)前節(jié)點(diǎn)的標(biāo)簽，重復(fù)上述過(guò)程直到每個(gè)節(jié)點(diǎn)的標(biāo)簽都與其鄰接點(diǎn)最多的標(biāo)簽相同，標(biāo)簽相同的節(jié)點(diǎn)劃分為同一個(gè)社區(qū). RAK方法節(jié)點(diǎn)初始化標(biāo)簽時(shí)間復(fù)雜度為O(n)，每次標(biāo)簽傳播的時(shí)間復(fù)雜度為O(m). 此外，RAK方法無(wú)需社區(qū)數(shù)量、社區(qū)規(guī)模等先驗(yàn)知識(shí)，僅根據(jù)網(wǎng)絡(luò)自身結(jié)構(gòu)發(fā)現(xiàn)社區(qū)，因此RAK方法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)有很好的適應(yīng)性.

為了提高RAK方法社區(qū)發(fā)現(xiàn)的性能，許多研究人員做出很多嘗試[13-23]. Barber等[13]提出了一種模塊化標(biāo)簽傳播算法，定義目標(biāo)函數(shù)H，將社區(qū)發(fā)現(xiàn)映射到最優(yōu)化目標(biāo)函數(shù)H，避免整個(gè)網(wǎng)絡(luò)僅為一個(gè)社區(qū)的情況；Cordasco等[14]提出了一種基于半同步標(biāo)簽傳播過(guò)程的方法，標(biāo)簽傳播過(guò)程是并行的，從而提高了RAK方法社區(qū)發(fā)現(xiàn)的計(jì)算速度；Leung等[15]提出了一種擴(kuò)展的RAK方法用于實(shí)時(shí)社區(qū)監(jiān)測(cè)，通過(guò)設(shè)定參數(shù)，使得算法具有擴(kuò)展性，提高了RAK方法的計(jì)算速度. 為降低RAK方法的隨機(jī)性，Zhao等[16]提出了基于標(biāo)簽的熵的標(biāo)簽傳播方法LPA-E(label propagation in entropic order)，將節(jié)點(diǎn)按照標(biāo)簽的熵從小到大排序進(jìn)行標(biāo)簽傳播；康旭彬等[17]提出了基于節(jié)點(diǎn)相似度的標(biāo)簽傳播算法；Sun等[18]提出了利用鄰接點(diǎn)影響力確定標(biāo)簽傳播順序的方法. 盡管上述方法一定程度上提高了標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法的性能和穩(wěn)定性，但都是僅從一個(gè)方面進(jìn)行改進(jìn)，且改進(jìn)的方面完全消除了隨機(jī)性，不能體現(xiàn)RAK方法的僅依據(jù)網(wǎng)絡(luò)自身結(jié)構(gòu)發(fā)現(xiàn)社區(qū)的特點(diǎn).

本文提出一種穩(wěn)定的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法，既保留了RAK方法無(wú)需先驗(yàn)知識(shí)等優(yōu)點(diǎn)，又提高了標(biāo)簽傳播社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量和穩(wěn)定性. 首先通過(guò)網(wǎng)絡(luò)中不重疊三角形進(jìn)行標(biāo)簽初始化，然后根據(jù)節(jié)點(diǎn)標(biāo)簽計(jì)算得到的熵確定隨機(jī)隊(duì)列，最后考慮鄰接點(diǎn)的鄰接點(diǎn)標(biāo)簽分布情況確定傳播標(biāo)簽.

1 穩(wěn)定標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)方法

為提高標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法的穩(wěn)定性，本文在RAK方法的標(biāo)簽初始化、隨機(jī)隊(duì)列設(shè)置和標(biāo)簽傳播過(guò)程分別進(jìn)行了改進(jìn). 在標(biāo)簽初始化中，發(fā)現(xiàn)網(wǎng)絡(luò)中所有不重疊三角形，給予三角形三個(gè)節(jié)點(diǎn)相同的標(biāo)簽，每個(gè)三角形標(biāo)簽各不相同，剩余節(jié)點(diǎn)賦予其他不同標(biāo)簽；在隨機(jī)隊(duì)列設(shè)置上，先將節(jié)點(diǎn)標(biāo)簽計(jì)算得到的熵從小到大對(duì)節(jié)點(diǎn)排序，再在排序基礎(chǔ)上分三段隨機(jī)排序；針對(duì)標(biāo)簽傳播的隨機(jī)選擇，考慮被傳播節(jié)點(diǎn)鄰接點(diǎn)的鄰接點(diǎn)標(biāo)簽與鄰接點(diǎn)標(biāo)簽相同的概率，選擇概率大的標(biāo)簽確定傳播標(biāo)簽選擇.

1.1 不重疊三角形標(biāo)簽初始化

RAK方法中，每個(gè)節(jié)點(diǎn)的初始化標(biāo)簽是各不相同的，本文提出了一種無(wú)重疊三角形標(biāo)簽初始化方法，用來(lái)減少初始標(biāo)簽數(shù)量. 網(wǎng)絡(luò)中，有很多聯(lián)系緊密具有團(tuán)體性的節(jié)點(diǎn)簇，如極大團(tuán)，節(jié)點(diǎn)簇往往屬于同一社區(qū)，且易成為社區(qū)的核心部分. CPM算法中[4]，極大團(tuán)往往作為社區(qū)的核心部分，進(jìn)行社區(qū)發(fā)現(xiàn). 社區(qū)核心部分的確定，社區(qū)發(fā)現(xiàn)的結(jié)果也將更加穩(wěn)定.

基于網(wǎng)絡(luò)和社區(qū)的這個(gè)特點(diǎn)，在標(biāo)簽初始化前，首先找出網(wǎng)絡(luò)中所有極大團(tuán)，賦予每個(gè)極大團(tuán)內(nèi)節(jié)點(diǎn)相同的標(biāo)簽. 然而，發(fā)現(xiàn)網(wǎng)路中所有極大團(tuán)是NP完全問(wèn)題，算法的時(shí)間復(fù)雜度較高，發(fā)現(xiàn)所有極大團(tuán)所耗時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)標(biāo)簽傳播整個(gè)算法的時(shí)間. 因此，本文提出了采用發(fā)現(xiàn)網(wǎng)絡(luò)中沒(méi)有節(jié)點(diǎn)重疊的不重疊三角形的方法，賦予發(fā)現(xiàn)到的三角形節(jié)點(diǎn)相同的標(biāo)簽，進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)簽初始化，如算法1所示.

算法1 不重疊三角形標(biāo)簽初始化方法偽代碼

輸入：鄰接矩陣AdjacentMatrix，節(jié)點(diǎn)個(gè)數(shù)VerticeNum，節(jié)點(diǎn)鄰居集合Neighbor.

輸出：標(biāo)簽數(shù)組Community.

for i←to VerticeNum Do

isVisited[i]←False;

c=0;

for i←0 to VerticeNum Do

for j←0 to Neighbor[i].size Do

for k←0 to Neighbor[j].size Do

if AdjacentMatrix[k][i]=1 and isVisited[ijk]=False then

Community[ijk]←c;

isVisited[ijk]←True;

c++;

for i←to VerticeNum Do

if isVisited[i]←False;

Community[i]←c;

isVisited[i]←True;

return Community;

如圖1所示，節(jié)點(diǎn)v1，v2和v3組成一個(gè)三角形，初始化標(biāo)簽均為l1，其他不能組成三角形的節(jié)點(diǎn)分別賦予不同的標(biāo)簽.

圖1 不重疊三角形標(biāo)簽初始化

不重疊三角形標(biāo)簽方法的時(shí)間復(fù)雜度為O(n2)，比RAK方法的近似線性時(shí)間復(fù)雜度有所提升，但減少了初始標(biāo)簽的數(shù)量. 其原因是RAK方法初始標(biāo)簽數(shù)量等于節(jié)點(diǎn)數(shù)量，而不重疊三角形的3個(gè)節(jié)點(diǎn)被賦予相同的標(biāo)簽，因此，初始標(biāo)簽數(shù)量要少于節(jié)點(diǎn)數(shù)量，即少于RAK方法的初始標(biāo)簽數(shù)量.

1.2 基于節(jié)點(diǎn)標(biāo)簽的熵的隨機(jī)隊(duì)列

分析隨機(jī)隊(duì)列對(duì)社區(qū)發(fā)現(xiàn)結(jié)果穩(wěn)定性的影響，考慮圖2所示網(wǎng)絡(luò)，6個(gè)節(jié)點(diǎn)v1，v2，v3，v4，v5，v6，初始化標(biāo)簽分別為l1，l2，l3，l4，l5，l6. 從直觀角度看，節(jié)點(diǎn)v1，v2和v3構(gòu)成一個(gè)社區(qū)，節(jié)點(diǎn)v4，v5和v6構(gòu)成另一個(gè)社區(qū). 若v1最先進(jìn)行標(biāo)簽更新，選擇的標(biāo)簽可能為l2或l3. 接下來(lái)無(wú)論v2還是v3先更新標(biāo)簽，v1，v2，v3都能被劃分到同一個(gè)社區(qū). 若v5或v6先進(jìn)行標(biāo)簽更新，或v4標(biāo)簽更新的時(shí)候不選擇l3，則v4，v5，v6將被劃分到另外一個(gè)社區(qū). 如果v3最先更新標(biāo)簽，則可能為l1，l2或 l4. 若為l1或l2，則結(jié)果與上述分析一樣；若為l4，則6個(gè)節(jié)點(diǎn)可能劃分為一個(gè)社區(qū). 因此，降低隨機(jī)隊(duì)列的隨機(jī)性將提高社區(qū)發(fā)現(xiàn)結(jié)果的穩(wěn)定性.

圖2 6個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)

為降低隨機(jī)隊(duì)列的隨機(jī)性，本文首先采用了文獻(xiàn)[16]的方法，利用節(jié)點(diǎn)標(biāo)簽計(jì)算得到的熵的大小對(duì)節(jié)點(diǎn)進(jìn)行先后排序. 節(jié)點(diǎn)標(biāo)簽計(jì)算得到的熵公式為

式中：L(v, N(v))為節(jié)點(diǎn)v和其鄰居節(jié)點(diǎn)的標(biāo)簽集合；p(l)為標(biāo)簽l在L(v, N(v))中的概率，即在節(jié)點(diǎn)v和N(v)中，標(biāo)簽為l的節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)v及其鄰接點(diǎn)N(v)節(jié)點(diǎn)數(shù)的比. 具體算法如算法2所示.

算法2 基于節(jié)點(diǎn)標(biāo)簽的熵的隨機(jī)隊(duì)列方法偽代碼

輸入：鄰接矩陣AdjacentMatrix，節(jié)點(diǎn)個(gè)數(shù)VerticeNum，標(biāo)簽數(shù)組Community.

輸出：基于節(jié)點(diǎn)標(biāo)簽的熵的隨機(jī)隊(duì)列Ssort.

for i←0 to VerticeNum Do

FindNeighbor(i,AdjacentMatrix,NeighBor)

for j←0 to Neighbor.size Do

labelNum[Community[Neighbor[j]]]++;

for k←0 to Neighbor.size Do

pl←labelNum[k]/(Neighbor.size()+1.0);

Ssort[i].S +=-pl*log(pl);

qsort(Ssort)

RandomSort(Ssort,VerticeNum/3);

RandomSort(Ssort+VerticeNum/3,VerticeNum/3*2);

RandomSort(Ssort+(VerticeNum/3)*2,VerticeNum);

return Ssort;

這種排序方法消除了傳播節(jié)點(diǎn)隊(duì)列的隨機(jī)性，使結(jié)果變得確定，標(biāo)簽傳播方法的適應(yīng)性大幅度降低. 為了保證標(biāo)簽傳播算法的適應(yīng)性，本文提出將這種方法排序好的隊(duì)列平均分成三個(gè)部分，每個(gè)部分內(nèi)節(jié)點(diǎn)進(jìn)行隨機(jī)排列. 這樣既降低了算法的隨機(jī)性，又未徹底消除算法隨機(jī)性，保持了標(biāo)簽傳播算法僅依靠網(wǎng)絡(luò)本身連接結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)的初衷.

1.3 基于鄰接點(diǎn)的鄰接點(diǎn)標(biāo)簽分布的標(biāo)簽選擇

標(biāo)簽傳播過(guò)程中，當(dāng)遇到最多數(shù)量的相同標(biāo)簽不唯一時(shí)，RAK方法采用隨機(jī)的方式進(jìn)行選擇，這使得最終社區(qū)發(fā)現(xiàn)結(jié)果隨機(jī)性較大. 為降低標(biāo)簽傳播過(guò)程中的隨機(jī)性，本文提出根據(jù)被傳播節(jié)點(diǎn)鄰接點(diǎn)的鄰接點(diǎn)集標(biāo)簽分布情況，進(jìn)行標(biāo)簽選擇的方法，如算法3所示.

v為當(dāng)前被傳播節(jié)點(diǎn)，K為N(v)中相同標(biāo)簽數(shù)量最多的節(jié)點(diǎn)集合，kl?K,kl為標(biāo)簽是l的節(jié)點(diǎn)集合. 考慮N(kl)中標(biāo)簽與標(biāo)簽l相同的節(jié)點(diǎn)所占比例，選擇比例最大的那個(gè)標(biāo)簽，作為節(jié)點(diǎn)v新的標(biāo)簽. 如果比例相同，則隨機(jī)選擇一個(gè).

算法3 基于鄰接點(diǎn)的鄰接點(diǎn)標(biāo)簽分布的標(biāo)簽傳播方法偽代碼

輸入：鄰接矩陣AdjacentMatrix，節(jié)點(diǎn)個(gè)數(shù)VerticeNum.

輸出：傳播后的標(biāo)簽數(shù)組Community.

for i←0 to VerticeNum Do

VectorFrequency(Neighbor[i], label);

if label.size() = 1 then

Community[i]←label[0];

else then

for j←0 to label.size Do

LabelFrequency(label[j], freqmax);

if freqmax.size=1 then

Community[i]←freqmax[0].label;

else then

Community[i]←freqmax[random].label;

return Community;

考慮鄰接點(diǎn)的鄰接點(diǎn)標(biāo)簽分布情況，相當(dāng)于給鄰接點(diǎn)標(biāo)簽加上了一個(gè)權(quán)重. 如果權(quán)重值高，則說(shuō)明該鄰接點(diǎn)的標(biāo)簽背后有更多的支撐，鄰接點(diǎn)的標(biāo)簽具有更強(qiáng)的影響力，應(yīng)該選擇該權(quán)重值高的鄰接點(diǎn)標(biāo)簽. 這使得原來(lái)的標(biāo)簽隨機(jī)性選擇變成確定性選擇，從而提高了社區(qū)發(fā)現(xiàn)結(jié)果的穩(wěn)定性. 同時(shí)，在權(quán)重值相同的情況下，保留了標(biāo)簽選擇的隨機(jī)性，保持了RAK方法的適應(yīng)性.

2 實(shí)驗(yàn)及分析

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

選擇了Zachary’s Karate Club[24]、Dolphin Social Network[25]和American College Football[7](簡(jiǎn)稱Karate、Dolphins和Football網(wǎng)絡(luò))這3個(gè)被廣泛使用的社會(huì)網(wǎng)絡(luò)進(jìn)行測(cè)試，網(wǎng)絡(luò)具體數(shù)據(jù)如表1所示.

表1 實(shí)驗(yàn)網(wǎng)絡(luò)的基本數(shù)據(jù)

實(shí)驗(yàn)環(huán)境為intel(R) Core(TM) i5 CPU M 430 @2.27GHz,2.27GHz,4GB,Windows 7操作系統(tǒng).

2.2 實(shí)驗(yàn)評(píng)測(cè)方法

采用文獻(xiàn)[12]提出的fsame函數(shù)和Jjaccard’s index函數(shù)作為衡量不同社區(qū)相似度標(biāo)準(zhǔn)，將本文方法與RAK方法和LPA-E方法進(jìn)行比較. fsame函數(shù)用于比較兩個(gè)社區(qū)發(fā)現(xiàn)結(jié)果的相似度，計(jì)算公式為

式中Mij表示在一個(gè)社區(qū)發(fā)現(xiàn)結(jié)果中社區(qū)i和在另一個(gè)社區(qū)發(fā)現(xiàn)結(jié)果中社區(qū)j相同節(jié)點(diǎn)的個(gè)數(shù). fsame函數(shù)對(duì)在一個(gè)社區(qū)發(fā)現(xiàn)結(jié)果中幾個(gè)小的社區(qū)在另一個(gè)社區(qū)發(fā)現(xiàn)結(jié)果中合并成一個(gè)大的社區(qū)這種情況不是很敏感. 因此，還用到了Jjaccard’s index函數(shù)，計(jì)算公式為

式中：a是在兩次發(fā)現(xiàn)結(jié)果中都在同一個(gè)社區(qū)的節(jié)點(diǎn)對(duì)數(shù)量，b是第一次在同一個(gè)社區(qū)而第二次在不同社區(qū)的節(jié)點(diǎn)對(duì)數(shù)量，c是第一次在不同社區(qū)而第二次在同一社區(qū)的節(jié)點(diǎn)對(duì)數(shù)量. Jjaccard’s index函數(shù)值越大，表明兩種社區(qū)發(fā)現(xiàn)結(jié)果越相近.

為評(píng)測(cè)社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量，采用了Newman等提出的模塊度[8]作為評(píng)價(jià)標(biāo)準(zhǔn). Newman等認(rèn)為，復(fù)雜網(wǎng)絡(luò)社區(qū)最優(yōu)發(fā)現(xiàn)結(jié)果并不代表社區(qū)間的邊數(shù)在絕對(duì)數(shù)量最少，而是比期望邊數(shù)少. 模塊度定義為社區(qū)內(nèi)的邊數(shù)減去隨機(jī)生成圖中的期望邊數(shù)，形式化定義如下：網(wǎng)絡(luò)劃分為k個(gè)社區(qū)，k*k的矩陣E=(eij)，eij表示網(wǎng)絡(luò)中社區(qū)i與社區(qū)j之間的邊數(shù)占所有邊數(shù)的比例； 矩陣的跡Tr(E)=∑ieij，表示網(wǎng)絡(luò)中社區(qū)內(nèi)部的邊數(shù)占所有邊數(shù)的比例；矩陣中第i行的和ai=∑jeij，表示與社區(qū)i中的點(diǎn)相連邊數(shù)占所有邊數(shù)的比例；如果不考慮社區(qū)，假定節(jié)點(diǎn)間隨機(jī)連接，那么eij=aiaj. 模塊度可以定義為

式中‖X‖為所有x元素之和.

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

在Karate、Dolphins和Football網(wǎng)絡(luò)上對(duì)本文方法、RAK方法和LPA-E方法進(jìn)行測(cè)試，選擇5個(gè)社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行兩兩比較. 實(shí)驗(yàn)結(jié)果如表2～4所示，表中右上半部分為fsame函數(shù)值，左下半部分為Jjaccard’s index函數(shù)值.

表2 RAK方法、LPA-E方法和本文方法在Karate網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)結(jié)果比較

表3 RAK方法、LPA-E方法和本文方法在Dolphins網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)結(jié)果比較

表4 RAK方法、LPA-E方法和本文方法在Football網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)結(jié)果比較

從表2～4實(shí)驗(yàn)結(jié)果看，LPA-E方法和本文方法的fsame函數(shù)值和Jjaccard’s index函數(shù)值均高于RAK方法，表明兩種方法都提升了社區(qū)發(fā)現(xiàn)穩(wěn)定性. 在規(guī)模較小的Karate網(wǎng)絡(luò)中，隨著算法隨機(jī)性的下降，經(jīng)常會(huì)出現(xiàn)社區(qū)發(fā)現(xiàn)結(jié)果完全一致的情況，如表2中LPA-E方法和本文方法左下角數(shù)值為1.000.

為從整體上比較三種方法的穩(wěn)定性，對(duì)Karate、Dolphins和Football網(wǎng)絡(luò)分別用RAK方法、LPA-E方法和本文方法進(jìn)行100次社區(qū)發(fā)現(xiàn)，計(jì)算兩兩結(jié)果Jjaccard’s index函數(shù)值的平均值，如表5所示.

表5 100次社區(qū)發(fā)現(xiàn)結(jié)果相互之間的jaccard’s index 函數(shù)平均值

Tab.5 Average value of jaccard’s index with 100 trails

在Dophins和Football網(wǎng)絡(luò)中，本文方法的Jjaccard’s index函數(shù)值平均值最高；在Karate網(wǎng)絡(luò)中，LPA-E方法的Jjaccard’s index函數(shù)值平均值最高. 為了分析造成這種結(jié)果的原因，統(tǒng)計(jì)了初始化時(shí)不重疊三角形個(gè)數(shù)F1和標(biāo)簽傳播時(shí)遇到鄰接點(diǎn)最多數(shù)量標(biāo)簽不唯一的次數(shù)F2，用來(lái)分析本文1.1節(jié)中改進(jìn)方法和1.3節(jié)中改進(jìn)方法在不同網(wǎng)絡(luò)中的影響力，如表6所示.

表6 100次社區(qū)發(fā)現(xiàn)中不重疊三角形個(gè)數(shù)和標(biāo)簽傳播時(shí)鄰接點(diǎn)最多數(shù)量標(biāo)簽不唯一次數(shù)的平均值

Tab.6 Average value of non-overlapping triangles and number of maximum label not unique with 100 trials

網(wǎng)絡(luò)F1F2Karate46Dophins1121Football3111

從表6數(shù)據(jù)可知，Karate網(wǎng)絡(luò)中的不重疊三角形個(gè)數(shù)和標(biāo)簽傳播時(shí)遇到鄰接點(diǎn)最多數(shù)量標(biāo)簽不唯一的次數(shù)都要少于Dophins和Football網(wǎng)絡(luò)中的個(gè)數(shù)和次數(shù)，這表明本文1.1節(jié)中改進(jìn)方法和1.3節(jié)中改進(jìn)方法在Karate網(wǎng)絡(luò)中的影響力低于在Dophins和Football網(wǎng)絡(luò)中的影響力. 表5 Karate結(jié)果中，本文方法結(jié)果低于LPA-E方法結(jié)果，是由于本文1.1節(jié)中改進(jìn)方法和1.3節(jié)中改進(jìn)方法所提高的穩(wěn)定性不足以抵消1.2節(jié)中改進(jìn)方法里保留的隨機(jī)性，這主要是由網(wǎng)絡(luò)規(guī)模決定的，網(wǎng)絡(luò)規(guī)模越大，網(wǎng)絡(luò)中的不重疊三角形數(shù)量越多，發(fā)生標(biāo)簽傳播時(shí)鄰接點(diǎn)最多數(shù)量標(biāo)簽不唯一的情況越多. 雖然本文方法的Jjaccard’s index函數(shù)平均值略低于LPA-E方法，但遠(yuǎn)高于RAK方法，說(shuō)明本文方法較好地提高了社區(qū)發(fā)現(xiàn)結(jié)果穩(wěn)定性，同時(shí)也驗(yàn)證了本文方法沒(méi)有完全消除RAK方法的隨機(jī)性，保留了RAK方法對(duì)網(wǎng)絡(luò)本身結(jié)構(gòu)適應(yīng)性的優(yōu)點(diǎn).

對(duì)Karate、Dolphins和Football網(wǎng)絡(luò)分別用RAK方法、LPA-E方法和本文方法進(jìn)行100次社區(qū)發(fā)現(xiàn)，并計(jì)算社區(qū)發(fā)現(xiàn)結(jié)果的Q函數(shù)平均值，結(jié)果如表7所示.

表7 100次社區(qū)發(fā)現(xiàn)結(jié)果的Q函數(shù)平均值

Tab.7 Average value of Q function of community discovery with 100 trails

網(wǎng)絡(luò)RAK方法LPA-E方法本文方法Karate0.3670.3750.384Dophins0.4250.4450.449Football0.4600.4780.482

Q函數(shù)表示的是社區(qū)內(nèi)邊數(shù)與隨機(jī)生成圖中期望邊數(shù)的差，反映了社區(qū)內(nèi)部緊密程度，Q函數(shù)值越大，表明發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)越緊密，越符合社區(qū)的定義，社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量越好. 實(shí)驗(yàn)結(jié)果表明，本文方法的Q函數(shù)平均值高于RAK方法和LPA-E方法，提升了社區(qū)發(fā)現(xiàn)質(zhì)量.

實(shí)驗(yàn)表明，本文算法較好地提升了標(biāo)簽傳播算法的穩(wěn)定性和社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量.

3 結(jié) 論

1)改進(jìn)了RAK方法標(biāo)簽初始化過(guò)程，通過(guò)挖掘網(wǎng)絡(luò)中的不重疊三角形，賦予三角形節(jié)點(diǎn)相同的標(biāo)簽，減少了初始化標(biāo)簽數(shù)量；

2)降低且未完全消除方法的隨機(jī)性，采用節(jié)點(diǎn)標(biāo)簽計(jì)算得到的熵和鄰接點(diǎn)的鄰接點(diǎn)標(biāo)簽分布情況進(jìn)行標(biāo)簽傳播選擇，提高了社區(qū)發(fā)現(xiàn)結(jié)果的穩(wěn)定性，同時(shí)保持了標(biāo)簽傳播方法的無(wú)需先驗(yàn)知識(shí)，僅依靠網(wǎng)絡(luò)結(jié)構(gòu)本身的特點(diǎn).

3)本文改進(jìn)的算法較好地提高了標(biāo)簽傳播社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量和穩(wěn)定性.

[1] ADAMIC L A, HUBERMAN B A, BARABSI A L, et al. Power-law distribution of the world wide web[J]. Science, 2000, 287(287):2115a-2115a. doi: 10.1126/science.287.5461.2115a.

[2] SIDIROPOULOS A, PALLIS G, KATSAROS D, et al. Prefetching in content distribution networks via web communities identification and outsourcing[J]. World Wide Web-internet & Web Information Systems, 2008, 11(1):39-70. doi:10.1007/s11280-007-0027-8.

[3] WANG Zhi, ZHANG Jianzhi. In search of the biological significance of modular structures in protein networks[J]. Plos Computational Biology, 2007, 3(6):1011-1021. doi: 10.1371/journal.pcbi. 0030107.

[4] PALLA G, DERENYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043):814-818. doi:10.1038/nature03607.

[5] LI Xin, LIU Bing, YU P S. Discovering overlapping communities of named entities[J]. Lecture Notes in Computer Science, 2006, 4213:593-600. doi: 10.1007/11871637_60.

[6] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2):291-307. doi: 10.1002/j.1538-7305.1970.tb01770.x.

[7] 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. doi: 10.1073/pnas.122653799.

[8] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2 Pt 2):026113-026113. doi: 10.1103/PhysRevE.69.026113.

[9] DERENYI I, PALLA G, VICSEK T. Clique percolation in random networks[J]．Physical Review Letters, 2005,94(16): 160202-160202. doi: 10.1103/PhysRevLett.94.160202.

[10]PALLA G, FARKAS I J, POLLNER P, et al. Directed network modules[J]. New Journal of Physics, 2007, 9(26):186-206. doi: 10.1088/1367-2630/9/6/186.

[11]ZHU X, GHAHRAMANI Z. Learning from labeled and unlabeled data with label propagation: Technical Report CMUCALD-02-107 [R]. Pittsburgh PA: Carnegie Mellon University, 2002.

[12]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). doi: 10.1103/PhysRevE.76.036106.

[13]BARBER M J, CLARK J W. Detecting network communities by propagating labels under constraints.

[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 80(2 Pt 2):283-289. doi: 10.1103/PhysRevE.80.026129.

[14]CORDASCO G, GARGANO L. Community detection via semi-synchronous label propagation algori-thms[C]// 2010 IEEE International Workshop on Business Applications of Social Network Analysis(BASNA). Bangalore: IEEE, 2010:1-8.

[15]Leung I X Y, PAN Hui, LIO P, et al. Towards real-time community detection in large networks[J]. Physical Review E, 2009, 79(6):853-857. doi: 10.1103/PhysRevE.79.066107.

[16]ZHAO Yuxin, LI Shenghong, CHEN Xiuzhen. Community detection using label propagation in entropic order[C]// 2012 IEEE 12th International Conference on Computer and Information Technology (CIT). Si Chuan: IEEE, 2012: 18-24.

[17]康旭彬, 賈彩燕. 一種改進(jìn)的標(biāo)簽傳播快速社區(qū)發(fā)現(xiàn)方法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013,36(1):43-47. doi:10.3969/j.issn.1003-5060.2013.01.010.

KANG XUBIN, JIA CAIYAN. An improved fast community detection algorithm based on label propagation[J]. Journal of HeFei University of technology, 2013,36(1): 43-47. doi:10.3969/j.issn. 1003-5060.2013.01.010.

[18]SUN Heli, HUANG Jianbin, ZHONG Xiang, et al. Label propagation with α-degree neighborhood impact for network community detection[J]. Computational Intelligence & Neuroscience, 2014(2014): 130689-130689. doi:10.1155/2014/130689.

[19]XING Yan, MENG Fanrong, ZHOU Yong, et al. A node influence based label propagation algorithm for community detection in networks[J]. Scientific World Journal, 2014, 2014(3):627581-627581. doi: 10.1155/2014/627581.

[20]SUN Heli, LIU Jiao, HUANG Jianbin, et al. CenLP: a centrality-based label propagation algorithm for community detection in networks[J]. Physica A Statistical Mechanics & Its Applications, 2015, 436:767-780. doi:10.1016/j.physa.2015.05.080.

[21]HOSSEINI R, AZMI R. Memory-based label propagation algorithm for community detection in social networks[C]// 2015 International Symposium on Artificial Intelligence and Signal Processing (AISP). Mashhad : IEEE, 2015:256-260.

[22]DICKINSON B, HU Wei. The effects of centrality ordering in label propagation for community detection[J]. Social Networking, 2015, 4(4):103-111. doi: 10.4236/sn.2015.44012.

[23]ZHANG Xiankun, TIAN Xue, LI Yanan, et al. Label propagation algorithm based on edge clustering coefficient for community detection in complex networks[J]. International Journal of Modern Physics B, 2014, 28(30): 1450216-1450216. doi: 10.1142/S0217979214502166.

[24]ZACHARY W W. An Information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.

[25]LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology & Sociobiology, 2003, 54(4):396-405. doi: 10.1007/s00265-003-0651-y.

(編輯 王小唯 苗秀芝)

Community discovery method based on stable label propagation

ZHANG Xin，LIU Bingquan，WANG Xiaolong

(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)

In order to improve the stability of label propagation algorithm and reduce the randomness which causes difference in the results of community discovery, labels initialization, random nodes queues setting and labels random selection are improved respectively, and a stable label propagation method for community discovery is proposed. This method first initializes labels by searching for non-overlapping triangles in the networks, and then forms nodes queues based on labels entropy and random sorted nodes in the sub queues. At last, this method chooses labels for each node by the distribution of adjacent nodes labels. Experimental results shows that, stability indexes and quality indexes of our method are higher than other methods’ on three social networks—Zachary’s Karate club, dolphin social network and American College football. Community discovery based on stable label propagation method not only maintains the advantages of label propagation algorithm, but also improves the quality and stability of community discovery results.

community discovery; label propagation; randomness; entropy of labels; stability

10.11918/j.issn.0367-6234.2016.11.008

2015-10-26

國(guó)家自然科學(xué)基金青年科學(xué)基金(61300114);國(guó)家自然科學(xué)基金面上項(xiàng)目(61272383);國(guó)家自然科學(xué)基金(61572151)

張 鑫(1984—)，男，博士研究生； 王曉龍(1955—)，男，教授，博士生導(dǎo)師

劉秉權(quán)， xzhang@insun.hit.edu.cn

TP301.6

A

0367-6234(2016)11-0047-06