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

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

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

?

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

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

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

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

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

1970年，Kernighan和Lin基于貪婪算法提出了Kernighan-Lin方法[6]，用于將網(wǎng)絡(luò)劃分為兩個規(guī)模確定的社區(qū). 該方法需要預(yù)先設(shè)定社區(qū)規(guī)模等較多先驗知識，在實際網(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算法時間復(fù)雜度較高，為O(m2n)，其中，m表示網(wǎng)絡(luò)中邊的數(shù)量，n表示網(wǎng)絡(luò)中的節(jié)點數(shù). Newman等提出模塊度[8]作為衡量社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量優(yōu)劣的標(biāo)準(zhǔn). Palla等[4,9-10]首次針對重疊社區(qū)提出了極大團過濾社區(qū)發(fā)現(xiàn)方法. 該方法需要事先確定參數(shù)，不同的參數(shù)值使得社區(qū)發(fā)現(xiàn)結(jié)果差異較大.

針對上述傳統(tǒng)方法參數(shù)難以確定、算法復(fù)雜度高的不足，Zhu等[11]提出了標(biāo)簽傳播算法LPA(label propagation algorithm). 由于LPA方法時間復(fù)雜度低且效果好，研究人員對其進行了大量深入研究. Raghavan等[12]首次將LPA方法用于復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)，提出了RAK方法. 該方法首先將網(wǎng)絡(luò)中每個節(jié)點賦予一個唯一的標(biāo)簽，然后根據(jù)當(dāng)前節(jié)點的鄰接點標(biāo)簽分布情況更新當(dāng)前節(jié)點的標(biāo)簽，重復(fù)上述過程直到每個節(jié)點的標(biāo)簽都與其鄰接點最多的標(biāo)簽相同，標(biāo)簽相同的節(jié)點劃分為同一個社區(qū). RAK方法節(jié)點初始化標(biāo)簽時間復(fù)雜度為O(n)，每次標(biāo)簽傳播的時間復(fù)雜度為O(m). 此外，RAK方法無需社區(qū)數(shù)量、社區(qū)規(guī)模等先驗知識，僅根據(jù)網(wǎng)絡(luò)自身結(jié)構(gòu)發(fā)現(xiàn)社區(qū)，因此RAK方法對網(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，避免整個網(wǎng)絡(luò)僅為一個社區(qū)的情況；Cordasco等[14]提出了一種基于半同步標(biāo)簽傳播過程的方法，標(biāo)簽傳播過程是并行的，從而提高了RAK方法社區(qū)發(fā)現(xiàn)的計算速度；Leung等[15]提出了一種擴展的RAK方法用于實時社區(qū)監(jiān)測，通過設(shè)定參數(shù)，使得算法具有擴展性，提高了RAK方法的計算速度. 為降低RAK方法的隨機性，Zhao等[16]提出了基于標(biāo)簽的熵的標(biāo)簽傳播方法LPA-E(label propagation in entropic order)，將節(jié)點按照標(biāo)簽的熵從小到大排序進行標(biāo)簽傳播；康旭彬等[17]提出了基于節(jié)點相似度的標(biāo)簽傳播算法；Sun等[18]提出了利用鄰接點影響力確定標(biāo)簽傳播順序的方法. 盡管上述方法一定程度上提高了標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法的性能和穩(wěn)定性，但都是僅從一個方面進行改進，且改進的方面完全消除了隨機性，不能體現(xiàn)RAK方法的僅依據(jù)網(wǎng)絡(luò)自身結(jié)構(gòu)發(fā)現(xiàn)社區(qū)的特點.

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

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

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

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

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

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

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

輸入：鄰接矩陣AdjacentMatrix，節(jié)點個數(shù)VerticeNum，節(jié)點鄰居集合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é)點v1，v2和v3組成一個三角形，初始化標(biāo)簽均為l1，其他不能組成三角形的節(jié)點分別賦予不同的標(biāo)簽.

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

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

1.2 基于節(jié)點標(biāo)簽的熵的隨機隊列

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

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

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

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

算法2 基于節(jié)點標(biāo)簽的熵的隨機隊列方法偽代碼

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

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

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

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

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

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

輸入：鄰接矩陣AdjacentMatrix，節(jié)點個數(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;

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

2 實驗及分析

2.1 實驗數(shù)據(jù)

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

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

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

2.2 實驗評測方法

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

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

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

為評測社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量，采用了Newman等提出的模塊度[8]作為評價標(biāo)準(zhǔn). Newman等認為，復(fù)雜網(wǎng)絡(luò)社區(qū)最優(yōu)發(fā)現(xiàn)結(jié)果并不代表社區(qū)間的邊數(shù)在絕對數(shù)量最少，而是比期望邊數(shù)少. 模塊度定義為社區(qū)內(nèi)的邊數(shù)減去隨機生成圖中的期望邊數(shù)，形式化定義如下：網(wǎng)絡(luò)劃分為k個社區(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中的點相連邊數(shù)占所有邊數(shù)的比例；如果不考慮社區(qū)，假定節(jié)點間隨機連接，那么eij=aiaj. 模塊度可以定義為

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

2.3 實驗結(jié)果與分析

在Karate、Dolphins和Football網(wǎng)絡(luò)上對本文方法、RAK方法和LPA-E方法進行測試，選擇5個社區(qū)發(fā)現(xiàn)結(jié)果進行兩兩比較. 實驗結(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實驗結(jié)果看，LPA-E方法和本文方法的fsame函數(shù)值和Jjaccard’s index函數(shù)值均高于RAK方法，表明兩種方法都提升了社區(qū)發(fā)現(xiàn)穩(wěn)定性. 在規(guī)模較小的Karate網(wǎng)絡(luò)中，隨著算法隨機性的下降，經(jīng)常會出現(xiàn)社區(qū)發(fā)現(xiàn)結(jié)果完全一致的情況，如表2中LPA-E方法和本文方法左下角數(shù)值為1.000.

為從整體上比較三種方法的穩(wěn)定性，對Karate、Dolphins和Football網(wǎng)絡(luò)分別用RAK方法、LPA-E方法和本文方法進行100次社區(qū)發(fā)現(xiàn)，計算兩兩結(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)計了初始化時不重疊三角形個數(shù)F1和標(biāo)簽傳播時遇到鄰接點最多數(shù)量標(biāo)簽不唯一的次數(shù)F2，用來分析本文1.1節(jié)中改進方法和1.3節(jié)中改進方法在不同網(wǎng)絡(luò)中的影響力，如表6所示.

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

對Karate、Dolphins和Football網(wǎng)絡(luò)分別用RAK方法、LPA-E方法和本文方法進行100次社區(qū)發(fā)現(xiàn)，并計算社區(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ù)與隨機生成圖中期望邊數(shù)的差，反映了社區(qū)內(nèi)部緊密程度，Q函數(shù)值越大，表明發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)越緊密，越符合社區(qū)的定義，社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量越好. 實驗結(jié)果表明，本文方法的Q函數(shù)平均值高于RAK方法和LPA-E方法，提升了社區(qū)發(fā)現(xiàn)質(zhì)量.

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

3 結(jié) 論

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

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

3)本文改進的算法較好地提高了標(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]康旭彬, 賈彩燕. 一種改進的標(biāo)簽傳播快速社區(qū)發(fā)現(xiàn)方法[J]. 合肥工業(yè)大學(xué)學(xué)報(自然科學(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

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

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

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

TP301.6

A

0367-6234(2016)11-0047-06