基于資源分配指標的最大約束社區發現算法

寧念文 許合利 劉喜峰

1(河南理工大學計算機科學與技術學院 河南 焦作 454000)2(鄭州工程技術學院機電與車輛工程學院 河南 鄭州 450044)

?

基于資源分配指標的最大約束社區發現算法

寧念文1許合利1劉喜峰2

1(河南理工大學計算機科學與技術學院 河南 焦作 454000)2(鄭州工程技術學院機電與車輛工程學院 河南 鄭州 450044)

在復雜網絡中的社區發現一直受到廣泛的關注，基于模塊度最大化的方法是目前流行的社區發現技術。提出一種基于資源分配(RA)指標和多步貪婪凝聚策略的模塊度最大化社區發現算法RALPA(Resource Allocation-based of Label propagation Algorithm)。該算法利用準確衡量節點間相似性的RA指標，通過最大約束標記傳播模型使社區內部節點擁有較高的相似性，與社區外部的節點擁有較低的相似性。然后，通過多步貪婪凝聚策略將劃分模塊度增加最大的多對小社區進行合并。實驗結果表明，該算法不僅避免了對節點更新順序的敏感和易得到平凡解的問題，而且提高了算法的穩定性和社區劃分的精度。

社區發現 模塊度最大化 資源分配指標 最大約束標記傳播模型

0 引 言

社區結構具有內部個體之間聯系密切，但與外部其他個體聯系稀疏的特點。因此，根據“在具有社區結構的網絡中，任何一個節點都應當與其大多數相鄰節點在同一個社區內”的思想，2007年Raghavan[1]等提出了接近線性復雜度的大規模復雜網絡社區發現算法—標簽傳播算法(LPA)。該算法具有簡單高效、不需要提供社區規模和社區個數等先驗知識的特點。但是，由于LPA在標簽傳播過程中存在著大量的隨機性，這些隨機性嚴重破壞了算法的魯棒性，進而破壞了所識別社區結構的穩定性[2]。針對上述缺點，Barber[3]等為了避免算法將所有節點劃分到同一社區，提出了一種帶有約束的模塊化標簽傳播算法(LPAm)，將社區聚類問題轉化為求基于模塊度的目標函數最大值問題。但是，LPAm易陷入局部最優并且基于不同的社區具有相似的總節點度數。Liu[4]等提出了LPAm+算法，該算法在LPAm的基礎上通過多步貪婪凝聚算法(MSG)使LPAm跳出局部最大值，提高了社區劃分的精度。但是，該算法循環迭代效率較低，并且應用到大數據集上時性能受到限制。Leung等[5]發現算法經過5次迭代后，大部分節點已經正確聚集，后面的迭代主要是對社區內的節點進行不必要的更新。因此，通過改進LPA的節點更新策略和迭代規則可以提高算法的執行效率，減少迭代次數，使算法盡快收斂。

為了提高算法的迭代效率和劃分社區的準確度，一方面通過節點影響力的優化，另一方面通過節點之間相似度的優化。張素智等[6]提出了基于節點聚集系數的分布式標簽傳播算法。該算法通過聚集系數衡量節點的影響力，使算法能夠快速收斂到正確的社區中，同時通過并行化處理提高算法的執行效率。黃健斌等[7]提出基于相似性模塊度最大約束標記傳播算法。該算法將最大約束標記傳播模型為目標函數，使劃分的社區結構更加緊密。很多研究者通過網絡拓撲結構中節點間的相似性衡量節點之間聯系的強弱。周濤等[8]基于不同類型的網絡對9種已知的基于局部信息的相似性指標在鏈路預測中的效果進行比較分析，并提出了資源分配指標RA(Resource Allocation index) 和LP(Local Path index)。通過在網絡中的預測效果表明這種指標都具有明顯好于9種已知指標的預測能力。

本文所做的工作：第一，利用RA相似性指標，使其準確地衡量直接相連節點間的相似性；第二，通過最大約束標記傳播模型對網絡進行粗粒度的社區發現，提高社區劃分的準確度，避免算法對節點更新順序敏感的缺點；第三，使用MSG算法依據模塊度最大化策略合并已得到的社區結構，使算法得到更高質量的社區結構。

圖1 Karate網絡中社區結構特點

1 相關工作

現有的針對標簽傳播算法的改進都存在迭代次數增加導致算法性能降低或者是仍然存在較高隨機性和不穩定性。本節通過資源分配指標準確衡量節點之間的相似性，減少標簽傳播過程中的隨機操作和迭代次數。在基于節點之間的資源分配相似性和目標函數優化理論的基礎上，通過最大約束標記傳播模型判定標簽的傳播方向, 使社團的劃分結果更加符合社團內部結構相對緊密, 社團之間結構較為稀疏的性質，提高算法對社區劃分的精度。

1.1 標簽傳播算法基本步驟

網絡G=(V,E),V表示節點集,E表示邊集。對于任意的x∈V,Cx(t)=Lx。Cx(t)表示t時刻節點x所屬的社區，Lx表示x節點t時刻的標簽。LPA算法的具體步驟如下：

(1) 每個節點初始化唯一的標簽Lx=x。

(2) 將V中節點隨機重新排序，并賦予節點集x。

(3) 對于重新排序后的任意x∈X，節點x將自身的標簽更新為其鄰節點中擁有相同標簽節點個數最多的標簽。

(4) 當所有節點的標簽都與其大多數相鄰節點的標簽相同時，算法結束。否則，繼續返回第2步再次進行標簽的更新。

標簽的更新策略分為：同步更新策略和異步更新策略。同步更新策略是當對節點進行第t+1次標簽更新時，依據鄰居的第t次標簽來更新自身的標簽。異步更新策略是對節點進行第t+1次更新時，依據鄰居最新的標簽來更新自身的標簽。由于同步更新策略容易產生震蕩現象，所以本文算法采用異步更新策略。

1.2 資源分配指標(RA)

為了更加準確地衡量節點間的相似度，我們利用RA指標相似性反映節點之間聯系的緊密程度。在圖1中節點12.0和節點1.0直接相連。那么，根據文獻[8]中RA的定義不能夠直接計算，文獻[9]計算得到兩點之間的相似性為0，將節點12.0和不在節點1.0鄰域中的其他節點同等對待，這樣導致衡量的結果不夠準確，不能正確反映節點之間的關系。因此，本文對RA相似性進行了擴展：

(1)

x和y直接相連， 表示節點x和節點y之間的相似性， 表示x的鄰接點集(包括x節點本身以及與x直接相連的節點)，k(z)表示x和y共享的鄰節點集中節點z的度數。擴展之后的RA相似性能夠更加準確地反映節點之間的相似性，將相鄰節點之間的相似性與非相鄰節點進行了區分。

1.3 最大約束標記傳播模型

(2)

本文基于RA指標和最大約束標記傳播模型對網絡進行粗粒度的社區發現。因為RA指標能夠通過節點局部信息準確地反映節點之間聯系的緊密程度，所以使最大約束標記傳播模型能夠提高社區劃分的準確度，并且使劃分結果更加符合社區結構的特點。

2 RALPA算法

2.1 RALPA算法思想

本文提出的RALPA算法主要分為兩個部分：1) 通過RA相似性的最大約束標記傳播模型進行社區發現，得到粗粒度的社區劃分；2) 在上一步劃分的基礎上，進行基于MSG算法的模塊度最大化社區的修正。

MSG算法的對于社區對的修正準則為：假設t1和t2是要合并的社區對，合并后模塊度增加量為ΔQ(t1,t2)并且不存在其他任意的社區t，與t1、t2組成社區對(t,t1)或(t,t2)，使ΔQ(t,t1)、ΔQ(t,t2)>ΔQ(t1,t2)。通過兩種方式的結合，隨著迭代次數的增加，能夠更快、更準確地將節點劃分到正確的社區中。同時，減少模塊度最大化合并的社區數目和在局部最優空間中的小范圍循環次數，避免低效率的迭代。

RALPA算法的主要思想：首先，利用RA指標計算每個點與相鄰節點之間的相似性；然后，根據最大約束標記傳播模型來更新節點的標簽，得到初步的社區劃分結果；最后，基于MSG算法合并能夠使社區模塊度最大程度提高的社區，得到最終的社區劃分。因為文獻[5]中經過大量實驗證明經過5次迭代后，95%的節點已正確的聚集。所以，本文設置算法的迭代次數為5次。因為通過MSG算法對結果進行修正，所以能夠同時合并多對符合要求的社區，提高算法的效率。

算法1 RALPA算法

輸入：網絡G=(V,E),V表示節點集,E表示邊集,迭代次數Iterate=5

輸出：各節點以及所屬的社區

變量和函數說明：

ΔQt1t2表示社區t1和t2合并之后模塊度的變化量；Initialize(x)表示節點x的標簽初始化；Merge(t1，t2)表示將社區t1和t2進行合并。

算法流程：

1) 初始化每個節點的標簽Vi=i。

2) 計算每個節點x的鄰域Γ(x)，根據式(1)計算每個節點x與其他節點y的資源分配相似性矩陣Sxy。

3) 迭代次數iter=1。

5) 如果每個節點的標簽都不再變化或者達到最大迭代次數Iterate，則算法結束，具有相同標簽的節點為同一個社區；否則iter=iter+1，返回步驟(4)。

6) 在步驟5)所得到結果的基礎上，根據MSG算法合并準則，同時合并使模塊度增大的多對社區。

7) 如果任意社區對合并后模塊度不再增加，那么算法結束；具有相同標簽的節點為同一個社區。

算法偽代碼：

For everyx∈V

xlabel= Initialize(x);

//將節點的標簽初始化

Fory∈xneighbor

//依次計算x和鄰域元素的相似度

// Sxy表示節點之間的相似矩陣

End for

End for

For iter=1:Iterate

//設置最大迭代次數

For everyx∈V

//根據下面公式更新節點自身的標簽

End for

End For

While ?(t1,t2):Δt1t2>0

//模塊度增加量為正整數

For every (t1,t2):Δt1t2>0∧!?t:Δt1t>Δt1t2∨Δt1t<Δt1t2

Merge(t1，t2);

//合并社區對

End For

End While

2.2 時間復雜度分析

對于圖G=(V,E)，N表示節點個數，M表示邊的個數，最大迭代次數Iterate。本文算法主要的時間復雜度為節點標簽更新的時間復雜度和計算社區劃分模塊度的時間復雜度。

節點標簽更新的時間復雜度為：對每個節點進行相似性計算和更新標簽的時間復雜度為O(N)；Iterate次迭代的總時間復雜度為O(Iterate×N)。

計算模塊度的時間復雜度：每次計算模塊度增量計算的時間復雜度為O(M)；以模塊度優化為目的進行社區之間的合并所需要的最大時間復雜度為O(N)，社區合并在最壞情況下需要的迭代次數為O(logN)。因此，RALPA算法的時間復雜度為O(M×logN)。由于采用基于相似性的社區發現和MSG凝聚策略所以比LPAm+算法擁有更優的時間復雜度。

3 實驗結果與分析

在真實網絡數據集和人工網絡數據集上，通過模塊度和NMI值，這兩種公認的評價標準來驗證算法的性能。本文所采用的數據集：1)真實網絡數據集，數據來源于現實世界中，通過對真實世界中關系的建模得到；2)人工網絡數據集，即利用程序自動生成的數據集。本文采用LFR基準程序生成人工網絡數據集。本文算法的實驗環境為Matlab2014a軟件，硬件的配置為：Pentium(R) Dual-Core CPU, E5800 @ 3.20GHz, RAM 4.00G；軟件配置：64位WIN8操作系統。

3.1 模塊度Q

Newman和Girvan在文獻[10]中提出模塊度的概念，后來作為衡量社區算法性能的公認評價標準。模塊度用來衡量社區結構性的強弱，其值越接近1，表示劃分出的社區結構性越強，劃分的結果越好。模塊度的定義如下：

(3)

其中，N表示社區數目，lc表示社區c中的總邊數，m表示網絡中的總邊數，dc表示社區c中節點度數的總和。

3.2 標準化互信息NMI

NMI[11]即標準化互信息，通過NMI值比較社區劃分的結果與標準社區結構的相似度，從而衡量社區劃分的質量。由于本文采用的真實網絡數據集的社區結構已知，以此衡量劃分結果與真實社區的相似度。NMI的定義為：

(4)

其中，Ni,j表示兩個社區公共節點數，Ni和Nj分別表示混合矩陣中第i行與第j列的和。

3.3 真實數據集

為了驗證本文提出的RALPA算法的性能，選擇的真實數據集為空手道俱樂部Karate數據集、海豚Dolphins數據集、橄欖球俱樂部Football數據集、政治書Polbooks數據集四種公認的真實網絡數據集，其參數如表1所示。

表1 真實網絡數據集信息

將算法應用到真實網絡數據集測試所劃分社區的平均模塊度Q和NMI指標。將本文算法與傳統LPA、LPAm、LPAm+、MLPA進行比較。不同算法分別在四種數據集上進行100次運算，計算結果的平均模塊度和NMI值見表2和表3。

表2 各種算法平均模塊度的比較

表3 各種算法NMI值的比較

通過對表2和表3的分析可知，RALPA算法在四種不同的真實數據集中表現出較好的性能。但在Karate數據集中本文算法的平均模塊度值不是最好。由于LPAm+算法從初始節點開始進行模塊度的優化，所以獲得了很好的模塊度，同時導致算法具有較高的時間復雜度。總體而言，本文算法表現出較好的性能，特別是在Polbooks社區結構不明顯的情況下也獲得了較好的結果。本文算法對karate數據集的劃分結果如圖2所示。

圖2 本文算法對Karate數據集劃分結果

通過圖1與圖2的對比，本文算法將以33.0為中心的社區劃分為兩部分。其中{25.0,26.0,29.0,32.0}表示一個小社區，這樣使獲得的社區結構具有較高的模塊度。這四個節點在最大約束標記傳播模型和模塊度最大化兩者作用下，最終獲得了具有更高模塊度的社區劃分。綜上所述，RALPA算法在4個真實網絡數據集中得到了較好的社區結構。

3.4 LFR人工網絡數據集

通過LFR基準程序分別生成了500個節點基準數據集和1 000節點的基準數據集。節點數N,平均度數AD, 最大度數MD, 最大社區規模MXC, 最小社區規模MIC，節點度分布指數DD, 社團規模分布指數DC, 社區混合參數μ。其中，μ表示混合參數，反映生成社區結構性的關鍵指標。具體信息如表4所示。

表4 兩種LFR網絡參數信息

LFR人工數據集已有確定的社區結構，在這兩種數據集上通過分析NMI值比較算法的性能，考慮到實驗中算法的不穩定性，不考慮結果為0的樣本。實驗結果如圖3(a)、(b)所示。

(a) 算法在LFR500數據集上NMI值

(b) 算法在LFR1000數據集上NMI值圖3 4種算法分別在兩種數據集上的NMI值

在節點為500和1 000的人工網絡數據集中，RALPA算法表現出較好的性能，劃分出更準確的社區結果。其中，在μ≤0.6時，社區結構不明顯的情況下能表現出比LPA、LPAm、LPAm+算法更好的性能。無論是在500個節點的數據集中還是1 000個節點的數據集中，本文算法劃分結果的NMI值都在0.60以上。表5為本文算法和MLPA算法在μ=0.6和μ=0.65時的NMI結果比較，可以看出本文算法在社區結構不明顯的情況下優于MLPA算法。由于RALPA算法具有較低的時間復雜度和較好的劃分結果，所以本文算法比以上算法具有更好的性能。

表5 社區結構不明顯的情況下算法NMI值的比較

4 結 語

RALPA算法利用資源分配指標更準確地衡量節點之間的相似性。通過引入最大約束標記傳播模型，使劃分出的社區結構內部節點之間具有更高的相似性，與社區之間具有較低的相似性，提高了社區劃分精度，減少了在局部最優取值空間中的迭代次數。通過多步貪婪凝聚算法進行模塊度最大化，提高了社區合并的效率，同時使算法能夠跳出局部最優解。通過在真實基準數據集和人工網絡數據集的實驗結果表明RALPA算法具有更好性能，能夠劃分出更高質量的社區結構。

本文算法運用模塊度最大化進行社區發現，但是由于模塊度的缺陷使以模塊度為目標函數的優化算法只能夠發現特定的社區結構，而真實網絡中的社區都是多規模的。因此，下一步的工作是對多分辨率社區發現算法的研究。

[1] Usha Nandini R, Réka A, Soundar K. Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007,76(3):36106.

[2] 石立新, 張俊星. 一種穩定的標簽傳播社區發現算法[J].計算機應用與軟件, 2015,32(3):261-265.

[3] 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):283-289.

[4] Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J].Physica A: Statistical Mechanics and its Applications, 2010,389(7):1493-1500.

[5] Leung X Y, Hui P, Lio P, et al. Towards real-time community detection in large networks[J].Physical review E, Statistical, nonlinear, and soft matter physics,2009,79(6):066107.

[6] 張素智, 孫嘉彬, 王威. 基于節點聚集系數的分布式標簽傳播算法[J].計算機應用與軟件,2016,33(4):125-128.

[7] 黃健斌, 鐘翔, 孫鶴立,等. 基于相似性模塊度最大約束標記傳播的網絡社團發現算法[J]. 北京大學學報(自然科學版),2013(3):389-396.

[8] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information[J].The European Physical Journal B, 2009,71(4):623-630.

[9] Pan Y, Li D H, Liu J G, et al. Detecting community structure in complex networks via node similarity[J].Physica A:Statistical Mechanics and its Applications,2010,389(14):2849-2857.

[10] Newman M E. Fast algorithm for detecting community structure in networks[J].Physical review. E, Statistical, nonlinear, and soft matter physics, 2004, 69(6):066133.

[11] Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identification[J].Journal of Statistical Mechanic:Theory and Experiment, 2005(9):P09008.

MAXIMUM CONSTRAINED COMMUNITY DETECTION ALGORITHM BASED ON RESOURCE ALLOCATION INDEX

Ning Nianwen1Xu Heli1Liu Xifeng2

1(CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)2(InstituteofElectricalandMechanicalVehicleEngineering,ZhengzhouInstituteofTechnology,Zhengzhou450044,Henan,China)

Community detection in complex networks have

wide attention, and the method based on modularity maximization is the popular community detection technology. In this paper, a modularity maximization community detection algorithm named RALPA (Resource Allocation-based of Label Propagation Algorithm) is proposed, which is based on resource allocation (RA) and multi-step greedy cohesion strategy. The algorithm uses the RA index to measure the similarity between nodes accurately. By using the maximum constraint label propagation model, the internal nodes of the community have high similarity, and have low similarity with the nodes outside the community. Then, through the multi-step greedy cohesion strategy, the multi-pair small communities with the largest increase of partitioning degree will be merged. The experimental results show that the proposed algorithm not only avoids the problem of the sensitivity of node update order and the trivial solution, but also improves the stability of the algorithm and the accuracy of community division.

Community detection Modularity optimization Resource allocation Maximum constraint label propagation model

2016-07-11。國家自然科學基金項目(61202286)；國家科技重大專項核心電子器件、高端通用芯片及基礎軟件產品專項(2014ZX01045-102)。寧念文，碩士生，主研領域：數據挖掘，并行計算。許合利，教授。劉喜峰，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.07.040