+一種基于邊界節點識別的復雜網絡局部社區發現算法

劉 陽 季新生 劉彩霞

?

+一種基于邊界節點識別的復雜網絡局部社區發現算法

劉 陽 季新生 劉彩霞

(國家數字交換系統工程技術研究中心 鄭州 450002)

在網絡日益巨大化和復雜化的背景下，挖掘全局網絡的社區結構代價較高。因此，基于給定節點的局部社區發現對研究復雜網絡社區結構有重要的應用意義。現有算法往往存在著穩定性和準確性不高，預設定閾值難以獲取等問題。該文提出一種基于邊界節點識別的復雜網絡局部社區發現算法，全面比較待合并節點的連接相似性進行節點聚類；并通過邊界節點識別控制局部社區的規模和范圍，從而獲取給定節點所屬社區的完整信息。在計算機生成網絡和真實網絡上的實驗和分析證明，該算法能夠自主挖掘給定節點所屬的局部社區結構，有效地提升局部社區發現穩定性和準確率。

復雜網絡；社區發現；局部社區；邊界節點識別

1 引言

近年來復雜網絡的研究蓬勃發展，已成為人們深入了解和分析真實世界網絡的重要理論和方法之一。其中，社區結構作為復雜網絡中廣泛存在的重要屬性，是認識復雜網絡的功能與特征的基礎，對研究網絡的模塊化、異質性等特征，分析網絡內部相互作用、網絡演化都具有重要意義。而在許多實際應用中，由于條件限制往往只能獲取局部網絡信息，或者只需分析某特定節點、特定群體的社區結構，這就從網絡拓撲信息和復雜度等方面對社區發現提出了限制和要求，需要根據局部網絡信息進行局部社區發現。

基于此，本文提出了一種基于邊界節點識別的局部社區發現算法，主要貢獻如下：(1)在局部社區聚合的過程中，綜合考慮并比較待合并節點與局部社區及其外部節點的連接相似性，避免直接從給定節點進行外部擴張而引入異質節點；(2)通過邊界節點識別以控制社區聚類，從而確定局部社區的范圍和大小，無需設置人工參數進行干預。通過計算機生成網絡和真實網絡實驗發現，本文算法能夠基于給定節點自主有效地挖掘并識別其真實邊界，從而發現接近真實完整的局部社區結構，具有相對較高的穩定性和準確率。

本文第2節分析現有局部社區發現方法的問題與局限；第3節介紹基于邊界節點識別的局部社區發現算法；第4節介紹了局部社區發現的評價準則與方法，并基于計算機生成網絡和真實網絡給出實驗和分析結果；第5節對全文進行總結。

2 問題分析

如圖1所示，在局部社區“由內而外”的擴展過程中，沿用了全局網絡社區發現中最大化模塊度的思想，將滿足或者能夠改善社區內聚指標的節點加入到該社區中，使得局部社區傾向于優先引入大度數節點。而大度數節點的引入往往又會引起連鎖反應，改變了局部社區擴展的方向和范圍，使其鄰近節點容易被劃分到給定節點所屬的局部社區，引入原本不屬于該局部社區的異質節點，影響了局部社區發現的性能。

基于上述分析，本文提出了一種基于局部社區聚合和邊界節點識別的兩階段局部社區發現算法，一方面通過全面分析局部社區鄰接子圖范圍內連接相似性，從而獲取給定節點所在社區的局部結構特征并進行節點聚類；同時在社區聚類過程中，基于鄰接節點內外的連接狀況反復識別其邊界節點，從而控制社區聚類的規模和范圍以完成局部社區發現。該算法采用了有別于最大化局部社區結構指標的思路和方法，以節點相似性模塊度作為局部社區發現的衡量標準，通過邊界節點識別解決已有方法存在的“何時停止聚類迭代”和給定節點位置敏感等問題。

圖1 “由內而外”的局部社區發現模型

3 基于邊界節點識別的局部社區發現算法

3.1 基本定義

連接相似度借鑒了余弦相似性[8]作為衡量節點相似性的標準，表示兩節點的共有連接在兩節點的所有直接連接中權重越大，說明二者聯系越緊密，節點連接的相似性越強，越有可能屬于同一社區。

如圖2所示，由于網絡結構具有社區內部連接緊密而社區間連接稀疏，呈現出“內緊外松”的結構特征，使得距離社區核心較遠的邊緣節點構成了所屬社區的天然邊界。在局部社區發現過程中，隨著社區聚類的擴展，必然逐步到達社區的邊界。邊界節點大多處于多個網絡社區的交界處，并往往同時與多個社區建立了連接。因此，如何基于節點及其鄰接子圖的連接關系與拓撲結構判斷其所屬社區，是局部社區發現的一個重要難點。而通過邊界節點識別，能夠幫助確定局部社區的邊界，從而有效地精確控制局部社區發現的范圍和規模，確保社區發現的穩定性和有效性，使得從同一社區不同節點出發所獲得局部社區趨于一致。

3.2 算法描述

本文提出了基于邊界識別的局部社區發現算法，主要包含兩個環節：社區節點聚類階段及社區邊界節點識別階段。該算法基于網絡節點的局部結構信息來衡量節點間的連接相似度，從給定節點開始進行節點聚類；并基于節點相似性模塊度判別邊界節點，以優化局部社區發現。通過兩階段的反復迭代，最終得到具有穩定邊界的局部社區。

圖3 局部社區節點聚類示意圖

4 實驗

4.1 評價準則與方法

局部社區發現的評價準則相比全局社區發現，除了評價社區發現精確度，還需要評價節點劃分的正確性。因而選擇的評價準則也必須能夠從這兩方面來考察該模型的性能。本文實驗部分采用了復雜網絡局部社區發現領域常用的典型指標：precision[10](正確率)，recall[10](查全率)及調和指標F-measure評價局部社區發現算法的性能。

由于計算機生成網絡和部分真實網絡社區結構已知，其給定節點所屬社區的標準數據集易于獲取；對于未知社區結構的真實網絡，本文采用當前公認準確度較高的Louvain[11]社區發現算法挖掘給定節點的所屬社區結構作為標準數據集。為了分析基于邊界節點識別的局部社區發現算法的性能，實驗同時基于計算機生成網絡和真實網絡進行局部社區發現，并選取文獻[1]，文獻[3]和文獻[12]3種常見的典型算法與之進行性能對比。

表1 局部社區發現算法

4.2 計算機生成網絡

表2 LFR網絡配置參數

4.3 真實網絡

真實網絡相比計算機生成網絡更不規則，因而其社區結構往往也更加復雜。這里采用5個具有不同規模的典型真實網絡數據集：2000賽季大學生美式足球聯賽網絡(Football)[14], 2004年美國政治博客網絡(Polblogs)[15]、美國航空網絡(US Airport)[16]、美國電力網絡(US power grid)[17]、2005年Internet拓撲網絡(Internet)[18]來進一步測試算法性能，表3描述了這些真實網絡的基本屬性。

表3實驗采用的真實網絡的基本屬性

網絡數據集節點數邊數連接類型網絡結構 Football[14] 115 616無向已知 Poldlogs[15] 149019025有向已知 US Airport[16] 157428236有向未知 US Power grid[17] 4941 6594無向未知 Interner[18]34761171403無向未知

在真實網絡中，4種局部社區發現算法的調和指標如表4所示。分析可知：由于真實網絡的社區結構彼此存在差異，給定節點的選取也具有一定的隨機性，因而4種算法的調和評價指標在不同真實網絡中也各不相同。對于 Football, US power grid，本文算法對局部社區發現性能改善有限；對于Polblog, US Airport, Internet網絡，本文算法的社區發現性能優勢更加明顯。相比真實網絡條件下的其它3種算法，基于邊界節點識別的局部社區發現算法都表現出了相對較高的社區發現精確度；在給定節點隨機選取的條件下，本文算法的綜合調和指標均值達到了86.07%，體現了較強的抗干擾能力，說明本文算法穩定性更優，并且與標準社區結構的匹配效果較好。

綜合計算機生成網絡和真實網絡的實驗可以得出結論：在不同網絡環境、不同給定節點條件下，基于邊界節點識別的局部社區發現算法在正確率、查全率方面相比其它算法都有不同程度的改善。盡管并不能在正確率、查全率兩項指標上同時達到最優，但在這兩項評價指標上較為均衡且處于較高水平，使其性能具有一定的整體優勢。該結論在表4所示的綜合調和指標上也得到了充分驗證。

表4調和指標均值：4種算法在真實網絡中基于隨機給定節點的局部社區發現性能

網絡數據集文獻[1]文獻[12]文獻[3]本文算法 Football[14]0.62670.76230.76330.7815 Poldlogs[15]0.54330.81110.80250.8603 US Airport[16]0.49500.78330.82570.9145 US Power grid[17]0.68820.74520.75840.8160 Interner[18]0.63190.85730.87260.9314

圖5 4種算法基于真實網絡的正確率、查全率、調和指標的性能對比

5 結束語

本文提出了一種基于邊界節點識別的復雜網絡局部社區發現算法，采用有別于最大化局部社區結構指標的思路和方法，通過擴展余弦相似性作為局部社區發現的衡量標準，以邊界節點識別控制社區聚類的規模和范圍以完成局部社區發現，從而解決已有方法穩定性不高，預設定閾值難以獲得等問題。通過實驗和分析證明：對于不同的給定節點，基于邊界節點識別的局部社區發現算法具有較高的準確率和穩定性，能夠較真實地反映給定節點所屬的局部社區結構。在保證準確度和穩定性的前提下，如何將局部社區發現進一步應用于大規模網絡局部結構分析，以及動態時序網絡中局部社區結構的演化分析等實際問題，是我們下一步研究工作的重點。

[1] Clauset A. Finding local community structure in networks[J].2005, 72(2): 026132..

[2] Radicchi F, Castellano C, Cecconi F,. Defining and identifying communities in networks[J]., 2004, 101(9): 2658-2663.

[3] Chen Q, Wu T T, and Fang M. Detecting local community structures in complex networks based on local degree central nodes[J]., 2013, 392(3): 529-537.

[4] Wu Y J, Huang H, Hao Z F,.. Local community detection using link similarity[J]., 2012, 27(6): 1261-1268.

[5] 潘磊, 金杰, 王崇駿, 等. 社會網絡中基于局部信息的邊社區挖掘[J].電子學報, 2012, 40(11): 2255-2263.

Pan Lei, Jin Jie, Wang Chong-jun,. Detecting link communities based on local information in social networks[J]., 2012, 40(11): 2255-2263.

[6] Qi X, Tang W, Wu Y,Optimal local community detection in social networks based on density drop of subgraphs[J]., 2014, 36(1): 46-53.

[7] Newman M E J. Modularity and community structure in networks[J]., 2006, 103(23): 8577-8582.

[8] Fouss F, Pirotte A, Renders J M,Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J].2007, 19(3): 355-369.

[9] Feng Z, Xu X, Yuruk N,A Novel Similarity-based Modularity Function for Graph Partitioning[M]. Berlin Heidelberg Springer, Data Warehousing and Knowledge Discovery2007: 385-396.

[10] Zhang Aidong. Protein Interaction Networks[M]. NewYork: Cambridge University Press, 2009: 44-47.

[11] Blondel V D, Guillaume J L, Lambiotte R,. Fast unfolding of communities in large networks[J].:, 2008, doi: 10.1088/1742-5468/2008/10/ P10008.

[12] Luo F, Wang J Z, and Promislow E. Exploring local community structures in large networks[J]., 2008, 6(4): 387-400.

[13] Lancichinetti A, Fortunato S, and Radicchi F. Benchmark graphs for testing community detection algorithms[J]., 2008, 78(4): 046l10.

[14] Girvan M and Newman M. Community structure in social and biological networks[J]., 2002, 9(12): 7821-7826.

[15] Adamic L A and Glance N. The political blogosphere and the 2004 US election: divided they blog[C]. Proceedings of the 3rd International Workshop on the Weblogging Ecosystem, New York, USA, ACM, 2005: 36-43.

[16] US power grid network dataset-KONECT[OL]. http://konect.uni-koblenz.de/networks/opsahl-powergrid, November 2013.

[17] US airports network dataset-KONECT[OL]. http:// konect.uni-koblenz.de/networks/opsahl-usairport, November 2013.

[18] Zhang Beichuan, Liu Raymond, Massey Daniel,Collecting the Internet AS-level topology[J]., 2005, 35(1): 53-61.

劉 陽： 男，1986年生，博士生，研究方向為社會網絡分析、數據挖掘.

季新生： 男，1969年生，教授，博士生導師，主要研究領域為電信網安全、移動通信安全.

劉彩霞： 女，1974年生，副教授，碩士生導師，主要研究領域為移動通信安全、社會網絡分析.

Detecting Local Community Structure Based on the Identification of Boundary Nodes in Complex Networks

Liu Yang Ji Xin-sheng Liu Cai-xia

(&&,450002,)

In the context that social network becomes more and more complicated and huge, it is extremely difficult and complex to mine the global community structures of large networks. Therefore, the local community detection has important application significance for studying and understanding the community structure of complex networks. The existing algorithms often have some defects, such as low accuracy and stability, the preset thresholds difficult to obtain,.. In this paper, a local community detecting algorithm is proposed based on boundary nodes identification, and a comprehensive consideration of the external and internal link similarity of neighborhood nodes for community clustering is given. Meanwhile, the method can effectively control the scale and scope of the local community based on the boundary node identification, so as the complete structure information of the local community is obtained. Through the experiments on both computer-generated and real-world networks, the results show that the proposed algorithm can automatically mine local community structure from the given node without predefined parameters, and improve the performance of local community detection in stability and accuracy.

Complex networks; Community detection; Local community; Identification of boundary nodes

TP311

A

1009-5896(2014)12-2809-07

10.3724/SP.J.1146.2013.01955

劉陽 liuyang198610@163.com

2013-12-17收到，2014-04-24改回

國家863計劃項目(2011AA010604)和國家重大科技專項(2012ZX03006002)資助課題