穩定標簽傳播的社區發現方法

張 鑫， 劉秉權， 王曉龍

(哈爾濱工業大學 計算機科學與技術學院, 哈爾濱 150001)

?

穩定標簽傳播的社區發現方法

張 鑫， 劉秉權， 王曉龍

(哈爾濱工業大學 計算機科學與技術學院, 哈爾濱 150001)

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

社區發現；標簽傳播；隨機性；標簽的熵；穩定性

網絡聚簇結構是復雜網絡的重要特征之一，網絡聚簇結構特征表明社區結構存在于復雜網絡中. 社區，即其內部節點之間關系相對緊密、內部節點與外部節點關系相對稀疏的節點集合. 通過分析復雜網絡的結構特征，挖掘復雜網絡中的社區結構，這個過程就是社區發現. 起初，研究人員利用圖論和概率統計相關理論挖掘網絡的本質和特點. 隨著互聯網的信息爆炸和人們溝通方式的轉變，復雜網絡的數據規模越來越大，快速、有效的社區發現方法成為多領域研究的熱點問題之一[1]. 研究復雜網絡社區發現方法對分析復雜網絡的拓撲結構和層次結構、理解社區的形成過程、預測復雜網絡的動態變化、發現復雜網絡中蘊含的規律特征具有重要意義,在眾多領域有廣泛的應用前景[2-5].

1970年，Kernighan和Lin基于貪婪算法提出了Kernighan-Lin方法[6]，用于將網絡劃分為兩個規模確定的社區. 該方法需要預先設定社區規模等較多先驗知識，在實際網絡中應用有限. GN算法[7]是社區發現經典方法之一，由Girvan和Newman于2001年提出. 該方法核心思想為社區內的邊介數應小于社區間的邊介數. GN算法時間復雜度較高，為O(m2n)，其中，m表示網絡中邊的數量，n表示網絡中的節點數. Newman等提出模塊度[8]作為衡量社區發現結果質量優劣的標準. Palla等[4,9-10]首次針對重疊社區提出了極大團過濾社區發現方法. 該方法需要事先確定參數，不同的參數值使得社區發現結果差異較大.

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

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

本文提出一種穩定的標簽傳播社區發現方法，既保留了RAK方法無需先驗知識等優點，又提高了標簽傳播社區發現結果的質量和穩定性. 首先通過網絡中不重疊三角形進行標簽初始化，然后根據節點標簽計算得到的熵確定隨機隊列，最后考慮鄰接點的鄰接點標簽分布情況確定傳播標簽.

1 穩定標簽傳播的社區發現方法

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

1.1 不重疊三角形標簽初始化

RAK方法中，每個節點的初始化標簽是各不相同的，本文提出了一種無重疊三角形標簽初始化方法，用來減少初始標簽數量. 網絡中，有很多聯系緊密具有團體性的節點簇，如極大團，節點簇往往屬于同一社區，且易成為社區的核心部分. CPM算法中[4]，極大團往往作為社區的核心部分，進行社區發現. 社區核心部分的確定，社區發現的結果也將更加穩定.

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

算法1 不重疊三角形標簽初始化方法偽代碼

輸入：鄰接矩陣AdjacentMatrix，節點個數VerticeNum，節點鄰居集合Neighbor.

輸出：標簽數組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所示，節點v1，v2和v3組成一個三角形，初始化標簽均為l1，其他不能組成三角形的節點分別賦予不同的標簽.

圖1 不重疊三角形標簽初始化

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

1.2 基于節點標簽的熵的隨機隊列

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

圖2 6個節點的網絡

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

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

算法2 基于節點標簽的熵的隨機隊列方法偽代碼

輸入：鄰接矩陣AdjacentMatrix，節點個數VerticeNum，標簽數組Community.

輸出：基于節點標簽的熵的隨機隊列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;

這種排序方法消除了傳播節點隊列的隨機性，使結果變得確定，標簽傳播方法的適應性大幅度降低. 為了保證標簽傳播算法的適應性，本文提出將這種方法排序好的隊列平均分成三個部分，每個部分內節點進行隨機排列. 這樣既降低了算法的隨機性，又未徹底消除算法隨機性，保持了標簽傳播算法僅依靠網絡本身連接結構進行社區發現的初衷.

1.3 基于鄰接點的鄰接點標簽分布的標簽選擇

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

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

算法3 基于鄰接點的鄰接點標簽分布的標簽傳播方法偽代碼

輸入：鄰接矩陣AdjacentMatrix，節點個數VerticeNum.

輸出：傳播后的標簽數組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;

考慮鄰接點的鄰接點標簽分布情況，相當于給鄰接點標簽加上了一個權重. 如果權重值高，則說明該鄰接點的標簽背后有更多的支撐，鄰接點的標簽具有更強的影響力，應該選擇該權重值高的鄰接點標簽. 這使得原來的標簽隨機性選擇變成確定性選擇，從而提高了社區發現結果的穩定性. 同時，在權重值相同的情況下，保留了標簽選擇的隨機性，保持了RAK方法的適應性.

2 實驗及分析

2.1 實驗數據

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

表1 實驗網絡的基本數據

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

2.2 實驗評測方法

采用文獻[12]提出的fsame函數和Jjaccard’s index函數作為衡量不同社區相似度標準，將本文方法與RAK方法和LPA-E方法進行比較. fsame函數用于比較兩個社區發現結果的相似度，計算公式為

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

式中：a是在兩次發現結果中都在同一個社區的節點對數量，b是第一次在同一個社區而第二次在不同社區的節點對數量，c是第一次在不同社區而第二次在同一社區的節點對數量. Jjaccard’s index函數值越大，表明兩種社區發現結果越相近.

為評測社區發現結果的質量，采用了Newman等提出的模塊度[8]作為評價標準. Newman等認為，復雜網絡社區最優發現結果并不代表社區間的邊數在絕對數量最少，而是比期望邊數少. 模塊度定義為社區內的邊數減去隨機生成圖中的期望邊數，形式化定義如下：網絡劃分為k個社區，k*k的矩陣E=(eij)，eij表示網絡中社區i與社區j之間的邊數占所有邊數的比例； 矩陣的跡Tr(E)=∑ieij，表示網絡中社區內部的邊數占所有邊數的比例；矩陣中第i行的和ai=∑jeij，表示與社區i中的點相連邊數占所有邊數的比例；如果不考慮社區，假定節點間隨機連接，那么eij=aiaj. 模塊度可以定義為

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

2.3 實驗結果與分析

在Karate、Dolphins和Football網絡上對本文方法、RAK方法和LPA-E方法進行測試，選擇5個社區發現結果進行兩兩比較. 實驗結果如表2～4所示，表中右上半部分為fsame函數值，左下半部分為Jjaccard’s index函數值.

表2 RAK方法、LPA-E方法和本文方法在Karate網絡上社區發現結果比較

表3 RAK方法、LPA-E方法和本文方法在Dolphins網絡上社區發現結果比較

表4 RAK方法、LPA-E方法和本文方法在Football網絡上社區發現結果比較

從表2～4實驗結果看，LPA-E方法和本文方法的fsame函數值和Jjaccard’s index函數值均高于RAK方法，表明兩種方法都提升了社區發現穩定性. 在規模較小的Karate網絡中，隨著算法隨機性的下降，經常會出現社區發現結果完全一致的情況，如表2中LPA-E方法和本文方法左下角數值為1.000.

為從整體上比較三種方法的穩定性，對Karate、Dolphins和Football網絡分別用RAK方法、LPA-E方法和本文方法進行100次社區發現，計算兩兩結果Jjaccard’s index函數值的平均值，如表5所示.

表5 100次社區發現結果相互之間的jaccard’s index 函數平均值

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

在Dophins和Football網絡中，本文方法的Jjaccard’s index函數值平均值最高；在Karate網絡中，LPA-E方法的Jjaccard’s index函數值平均值最高. 為了分析造成這種結果的原因，統計了初始化時不重疊三角形個數F1和標簽傳播時遇到鄰接點最多數量標簽不唯一的次數F2，用來分析本文1.1節中改進方法和1.3節中改進方法在不同網絡中的影響力，如表6所示.

表6 100次社區發現中不重疊三角形個數和標簽傳播時鄰接點最多數量標簽不唯一次數的平均值

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

網絡F1F2Karate46Dophins1121Football3111

從表6數據可知，Karate網絡中的不重疊三角形個數和標簽傳播時遇到鄰接點最多數量標簽不唯一的次數都要少于Dophins和Football網絡中的個數和次數，這表明本文1.1節中改進方法和1.3節中改進方法在Karate網絡中的影響力低于在Dophins和Football網絡中的影響力. 表5 Karate結果中，本文方法結果低于LPA-E方法結果，是由于本文1.1節中改進方法和1.3節中改進方法所提高的穩定性不足以抵消1.2節中改進方法里保留的隨機性，這主要是由網絡規模決定的，網絡規模越大，網絡中的不重疊三角形數量越多，發生標簽傳播時鄰接點最多數量標簽不唯一的情況越多. 雖然本文方法的Jjaccard’s index函數平均值略低于LPA-E方法，但遠高于RAK方法，說明本文方法較好地提高了社區發現結果穩定性，同時也驗證了本文方法沒有完全消除RAK方法的隨機性，保留了RAK方法對網絡本身結構適應性的優點.

對Karate、Dolphins和Football網絡分別用RAK方法、LPA-E方法和本文方法進行100次社區發現，并計算社區發現結果的Q函數平均值，結果如表7所示.

表7 100次社區發現結果的Q函數平均值

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

網絡RAK方法LPA-E方法本文方法Karate0.3670.3750.384Dophins0.4250.4450.449Football0.4600.4780.482

Q函數表示的是社區內邊數與隨機生成圖中期望邊數的差，反映了社區內部緊密程度，Q函數值越大，表明發現的社區結構越緊密，越符合社區的定義，社區發現結果質量越好. 實驗結果表明，本文方法的Q函數平均值高于RAK方法和LPA-E方法，提升了社區發現質量.

實驗表明，本文算法較好地提升了標簽傳播算法的穩定性和社區發現結果質量.

3 結 論

1)改進了RAK方法標簽初始化過程，通過挖掘網絡中的不重疊三角形，賦予三角形節點相同的標簽，減少了初始化標簽數量；

2)降低且未完全消除方法的隨機性，采用節點標簽計算得到的熵和鄰接點的鄰接點標簽分布情況進行標簽傳播選擇，提高了社區發現結果的穩定性，同時保持了標簽傳播方法的無需先驗知識，僅依靠網絡結構本身的特點.

3)本文改進的算法較好地提高了標簽傳播社區發現結果的質量和穩定性.

[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]. 合肥工業大學學報(自然科學版), 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

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

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

劉秉權， xzhang@insun.hit.edu.cn

TP301.6

A

0367-6234(2016)11-0047-06