基于節點重要性和局部擴展的重疊社區發現算法*

郭 峰 尤凱麗 李昕澤

（北方工業大學信息學院 北京 100000）

1 引言

社區發現是復雜網絡［1～3］及數據挖掘領域中關鍵的研究內容。社區結構［4～6］作為復雜網絡的共同特征，是網絡圖中最普遍、最重要的屬性之一，表現在社區內部節點之間的連接要比社區外其他部分節點的連接要更加緊密［5］。通過社區發現可以幫助我們了解和分析病毒傳播行為，有助于推斷病毒的傳播機制，從而快速地采取有效防范、制定應對措施。社區發現問題具有重要的研究價值和科學意義，近年來，如何對社區結構進行快速、準確地劃分成為眾多學者研究的熱點。

社區結構具有一些明顯的屬性和特征［7］，使得在重疊社區劃分方法上出現不同的優秀思想。2002年，Girvan和Newman基于分裂思想提出經典的GN算法［8］，為復雜網絡研究開辟了新的道路；2005年，Palla等對原有非重疊社區發現方法進行擴展，首次提出基于派系過濾思想的重疊社區發現算法CPM［9］。隨后，各種重疊社區發現思想層出不窮，典型算法有圍繞CPM算法中尋找相鄰k階完全子圖的核心思想，Farkas等提出對加權網絡的社區劃分算法CPMm［10］、Kumpula等提出快速的派系過濾算法SCP［11］等。2007年Raghavan首次運用標簽傳播思想對圖進行劃分，提出著名的非重疊社區發現算法LPA［12］。其后，在LPA算法基礎上，Steve等引入多標簽和隸屬度概念提出重疊社區發現算法COPRA［13］；Xie等引入Listener和Speaker概念提出SLPA算法［14］；Xie等結合派系相似度，以派系為載體進行標簽傳播，提出CSLPA算法［15］等。

局部擴展方法是重疊社區發現任務中比較常用且成功的策略之一。Lancichinetti等提出的LFM算法［16］是局部擴展思想中的一個典型算法，但該算法受參數影響及初始節點的隨機選擇，導致檢測精度不穩定，算法不具有魯棒性。Shen等引入樹狀圖概念提出EAGLE算法［17］，還提出了一種評估重疊社區的模塊化度量EQ；與EAGLE算法思想相同的還有Huang等提出的DenShrik算法［18］和Lee等提出的GCE算法［19］等，但DenShrik與EAGLE類似，需要在檢測小規模社區時手動調節閾值，GCE算法對初始節點進行貪婪擴展，并設計函數計算社區之間的距離來刪除相似社區，但在人工網絡上的表現效果比在大規模密集型網絡上表現效果更好。

如何在復雜網絡圖中準確、快速找出重疊節點和社區、有效地劃分社區結構是本文研究的重點。

2 算法

2.1 DocNet

DOCNet算法［20］是2014年Delel Rhouma等提出的基于局部擴展的一種重疊社區發現方法。該算法的主要策略是：找到最重要的節點與其鄰節點形成一個初始社區，篩選達到規定質量函數標準的節點加入初始社區，遍歷各個節點對初始社區其進行擴展。DOCNet算法發現重疊社區的過程可以總結為兩個階段，即構建初始社區和社區擴展。

1）構建初始社區

DOCNet算法選取最重要的節點及其鄰節點組成初始社區，節點重要性隨著其鄰節點的增加以及這些鄰節點之間邊數的增加而增加，也就是說，當一個節點成為網絡中“有影響力的中心節點”時，其重要性就會增加。節點重要性是度量一個節點是否能夠形成初始社區C的重要因素。

文中將節點重要性N I(u)定義為式（1）：

其中cf c(u)代表聚類系數， ||B(u)代表節點u的鄰節點數。

2）社區擴展

初始社區形成后，DOCNet算法遍歷社區相鄰節點，定義節點u對社區C的隸屬度來判斷選取哪個節點加入到社區C。隸屬度di st moy定義如式（2）所示：

其中dist(u，v)代表節點u，v之間的最短距離，即從節點u到節點v的最短路徑的邊數。

選取出加入社區C的候選節點u后，DOCNet算法通過定義質量函數來判定節點u是否能加入社區C。質量函數通過社區內外部聯系來限定一個社區，當加入節點u后的IC(C)比原來的IC(C)大時，則說明u可以加入社區C。計算方式如式（3）所示：

其中comp(C)是社區C內的邊數，sep(C)是社區C內節點與社區外節點相連的邊數。

DOCNet算法過程簡單，在復雜網絡以及社區之間的重疊率高的網絡上有著很高的穩定性，但仍存在一定的局限性，本文提出DOCLLE（Discover Overlapping Communities by LeaderRank and Local Expansion）算法，在節點重要性和隸屬度兩個方面對其進行改進。

2.2 DOCLLE

初始節點的選取是局部擴展方法中關鍵的第一步，對最終的社區劃分結果影響很大［21～22］。針對節點重要性的計算，本文采用更優的排序算法LeaderRank對圖中各節點進行排序。在擴展過程中，DOCNet算法采用平均距離來計算節點歸屬度，使得算法運行時間變長，本文結合節點間相似度概念，在局部范圍計算節點對社區的隸屬度，減小了計算范圍，并具有一定的準確性。

2.2.1 節點重要性

LeaderRank重要性排名算法是對PageRank算法的擴展，該算法加入延遲及自適應概率等思想有效地解決了PageRank算法中每個節點的隨機跳轉概率都相同且最優參數不具有普適性的問題，在標識圖中節點重要性上有很好的性能。

圖1 Zachary空手道數據集各節點重要性

在有向圖和無向圖上應用LeaderRank算法后發現，該算法在兩種類型的圖上均具有良好的性能，圖1所示為LeaderRank算法在無向網絡圖Zachary空手道俱樂部人員關系圖上對各個節點的重要性排序結果。

2.2.2 隸屬度

DOCNet算法采用節點到社區各點的平均距離值來衡量節點對該社區的歸屬度，算法運算過程需要計算兩個節點間的最短距離，處理節點數較多的網絡圖時所需時間較長。文中所提DOCLLE算法采用局部范圍內計算節點間的相似度的方式來衡量節點對社區的隸屬度，不需要遍歷全局節點，提高了運算效率。杰卡德（Jaccard）系數是衡量兩個集合之間相似度的指標，常用于比較有限樣本集之間的相似性與差異性。集合A、B的交集在兩個集合的并集中所占的比例即為杰卡德系數，如式（4）所示，Jaccard系數值越大，樣本相似度越高。

節點間相似度可以用杰卡德相似度系數來衡量，為適應圖中節點特征，對杰卡德系數進行更改，更改后的杰卡德節點相似度Si m(i)，j如式（5）所示：

節點對社區的隸屬度大小與該節點與社區內部各節點之間的關聯程度有關。DOCLLE算法在候選節點集中選擇加入社區中的節點時，定義了如式（6）中所示的節點隸屬度Bl(u，C)：

其中C為每次迭代過程中的初始社區集合，P是C的邊界鄰節點集合，ω、φ分別是C和P中的節點，e uω為節點u與社區C中節點的連邊數，e uφ為節點u與社區P中連邊數。

2.3 算法描述

基于局部擴展的核心思想，文中有效地改善了DocNet算法的局限之處。算法主要分為三個步驟：1）通過LeaderRank算法獲取圖中所有節點的重要性并用LR表示，將LR按重要性大小降序排列并選擇第一個節點作為初始節點，與其鄰節點共同構成初始社區C；2）對LR進行遍歷，通過式（6）依次計算C的邊界鄰節點對C的隸屬度大小，用Bldegree表示，在Bldegree中依次選擇隸屬度最大的節點加入初始社區C；3）通過式（3）定義的質量函數計算加入新節點后的社區質量，衡量該節點是否可以加入初始社區中；LR中節點全部遍歷后，算法終止。

3 實驗

3.1 人工生成網絡評估

LFR人工生成基準網絡能夠生成給定參數的網絡圖，其中混合參數μ代表了每個節點到其社區外部節點之間的連邊比例，μ值越大，合成網絡中的社區間邊數越多，社區內的邊數較少，從而使社區結構更難檢測。其他參數設置如表1所示。

表1 人工生成網絡參數設置

人工生成網絡benchmark根據設定的參數生成相應的網絡圖，社區個數是已知的，這里采用標準化互信息NMI（Normalized Mutual Information）［23］對算法進行檢驗。NMI的取值范圍為0～1，值越大，說明社區發現結果越準確。將DOCLLE與DOCNet算法在以上各組人工生成網絡圖上進行實驗，實驗結果如圖2所示。

人工生成網絡參數的組合設置使得各組網絡圖規模、復雜度都有所區分，從圖2中可以看出，在網絡圖節點數達到5000時，DocNet算法的NMI值呈下降趨勢，在第7，8，9組實驗的網絡圖中的社區劃分結果并不好，而DOCLLE算法則呈上升趨勢，社區劃分能力比較穩定，能夠在節點較多的網絡中表現出很好的重疊社區發現效果。

圖2 DocNet與DOCLLE在人工網絡下NMI值對比

圖3 DocNet與DOCLLE在GN網絡中不同μ值下NMI值對比

為進一步檢驗DOCLLE算法，另外選擇在GN基準網絡在不同μ值下的網絡圖上進行實驗，從圖3中可看出，μ值大小對算法檢測到的社區劃分質量有很大的影響。隨著μ值增加，NMI減小，這意味在同等節點數的網絡規模下，隨著網絡變得更加復雜，算法計算出的劃分結果與真實社區劃分情況相差更遠。雖然如此，DOCLLE算法在復雜的網絡上表現出了比DocNet算法更好的重疊社區劃分性能，劃分結果更加準確。

3.2 真實網絡評估

為檢驗在真實的重疊網絡上DOCLLE算法的效果，文中在Zachary、Dolphins、Footbal、Netscience四個真實數據集進行實驗。其社區規模是增大的，Netscience中1589個節點，2742條邊。圖4展示了DOCLLE算法在Zachary數據集上的社區劃分情況，圖中的節點表示俱樂部成員，圖中的邊表示兩個成員之間有關聯。算法能夠識別出重疊節點，將該社團分為兩個社區，各包含21個節點，其中綠色節點為兩個社區間的重疊節點，以其為邊界將Zachary社區結構進行了明確的劃分。

圖4 DOCLLE在Zachary上的社區劃分結果

對真實網絡來說，社區個數是未知的，采用以下比較適合衡量社區結構［23］的評價系數：社區連接緊密度指標EQ［17］和模塊化指標Qov［24］對算法進行檢驗。評價系數的取值范圍均為（0～1），值越大說明算法效果越好。

將文中提出的DOCLLE算法與局部擴展經典算法LFM［16］、DEMON［25］、標簽傳播算法SLPA［14］以及DocNet［20］算法進行對比，并在上述四個真實數據集上做對比實驗。從圖5和圖6中可看出，DocNet算法在不同數據集上均有比較好表現，但在規模較大的Netscience數據集上，Qov分值較DOCLLE來說相對較低；DOCLLE算法在不同數據集上均有比較好的表現，尤其在Netscience數據集上，相較于LFM、SLPA、Demon算法來說，DOCLLE算法的EQ值、Qov值是最高的，這意味著隨著網絡中節點數量的增多，DOCLLE算法的社區劃分能力在逐步增強。

圖5 各數據集上各個算法的EQ值

圖6 各數據集上各個算法的Qov值

3.3 算法時間復雜度

假設圖中的節點數為n，邊數為m，平均社區規模為c，平均節點度數為d。算法在計算節點重要性的過程中，由于LeaderRank算法迭代次數多，運行時間過長，導致算法復雜度較高。實驗中，在保證結果正確的前提下，通過調整終止條件的參數來降低迭代次數，同時對代碼進行優化，這里設結果穩定時所需的迭代次數為s，優化后的LeaderRank算法時間復雜度為O（ms）；計算質量函數的時間復雜度為O（cd）；計算隸屬度的時間復雜度為O（n2），DOCLLE算法整體的時間復雜度為O（n2cd）。

4 結語

本文在局部擴展算法DocNet的基礎上，在初始節點選取和隸屬度兩個方面做了改進，通過引入經典的重要性排序算法LeaderRank對節點重要性進行排序，得到初始的核心節點；采用局部相似度的計算方式替代DocNet中的平均距離計算方式，以期在處理節點較多的網絡時減小計算范圍，提高算法效率。實驗結果表明，在節點多的網絡圖上，DOCLLE算法有更好的表現，能夠以較高的效率發現重疊社區。在未來工作中，需在真實場景中將算法進行應用和進一步的改進，使算法在處理這些網絡圖時更具有準確性和普適性。