+一種基于邊界節(jié)點識別的復(fù)雜網(wǎng)絡(luò)局部社區(qū)發(fā)現(xiàn)算法

劉 陽 季新生 劉彩霞

?

+一種基于邊界節(jié)點識別的復(fù)雜網(wǎng)絡(luò)局部社區(qū)發(fā)現(xiàn)算法

劉 陽 季新生 劉彩霞

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

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

復(fù)雜網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)；局部社區(qū)；邊界節(jié)點識別

1 引言

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

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

本文第2節(jié)分析現(xiàn)有局部社區(qū)發(fā)現(xiàn)方法的問題與局限；第3節(jié)介紹基于邊界節(jié)點識別的局部社區(qū)發(fā)現(xiàn)算法；第4節(jié)介紹了局部社區(qū)發(fā)現(xiàn)的評價準則與方法，并基于計算機生成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)給出實驗和分析結(jié)果；第5節(jié)對全文進行總結(jié)。

2 問題分析

如圖1所示，在局部社區(qū)“由內(nèi)而外”的擴展過程中，沿用了全局網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中最大化模塊度的思想，將滿足或者能夠改善社區(qū)內(nèi)聚指標的節(jié)點加入到該社區(qū)中，使得局部社區(qū)傾向于優(yōu)先引入大度數(shù)節(jié)點。而大度數(shù)節(jié)點的引入往往又會引起連鎖反應(yīng)，改變了局部社區(qū)擴展的方向和范圍，使其鄰近節(jié)點容易被劃分到給定節(jié)點所屬的局部社區(qū)，引入原本不屬于該局部社區(qū)的異質(zhì)節(jié)點，影響了局部社區(qū)發(fā)現(xiàn)的性能。

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

圖1 “由內(nèi)而外”的局部社區(qū)發(fā)現(xiàn)模型

3 基于邊界節(jié)點識別的局部社區(qū)發(fā)現(xiàn)算法

3.1 基本定義

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

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

3.2 算法描述

本文提出了基于邊界識別的局部社區(qū)發(fā)現(xiàn)算法，主要包含兩個環(huán)節(jié)：社區(qū)節(jié)點聚類階段及社區(qū)邊界節(jié)點識別階段。該算法基于網(wǎng)絡(luò)節(jié)點的局部結(jié)構(gòu)信息來衡量節(jié)點間的連接相似度，從給定節(jié)點開始進行節(jié)點聚類；并基于節(jié)點相似性模塊度判別邊界節(jié)點，以優(yōu)化局部社區(qū)發(fā)現(xiàn)。通過兩階段的反復(fù)迭代，最終得到具有穩(wěn)定邊界的局部社區(qū)。

圖3 局部社區(qū)節(jié)點聚類示意圖

4 實驗

4.1 評價準則與方法

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

由于計算機生成網(wǎng)絡(luò)和部分真實網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)已知，其給定節(jié)點所屬社區(qū)的標準數(shù)據(jù)集易于獲?。粚τ谖粗鐓^(qū)結(jié)構(gòu)的真實網(wǎng)絡(luò)，本文采用當前公認準確度較高的Louvain[11]社區(qū)發(fā)現(xiàn)算法挖掘給定節(jié)點的所屬社區(qū)結(jié)構(gòu)作為標準數(shù)據(jù)集。為了分析基于邊界節(jié)點識別的局部社區(qū)發(fā)現(xiàn)算法的性能，實驗同時基于計算機生成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)進行局部社區(qū)發(fā)現(xiàn)，并選取文獻[1]，文獻[3]和文獻[12]3種常見的典型算法與之進行性能對比。

表1 局部社區(qū)發(fā)現(xiàn)算法

4.2 計算機生成網(wǎng)絡(luò)

表2 LFR網(wǎng)絡(luò)配置參數(shù)

4.3 真實網(wǎng)絡(luò)

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

表3實驗采用的真實網(wǎng)絡(luò)的基本屬性

網(wǎng)絡(luò)數(shù)據(jù)集節(jié)點數(shù)邊數(shù)連接類型網(wǎng)絡(luò)結(jié)構(gòu) Football[14] 115 616無向已知 Poldlogs[15] 149019025有向已知 US Airport[16] 157428236有向未知 US Power grid[17] 4941 6594無向未知 Interner[18]34761171403無向未知

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

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

表4調(diào)和指標均值：4種算法在真實網(wǎng)絡(luò)中基于隨機給定節(jié)點的局部社區(qū)發(fā)現(xiàn)性能

網(wǎng)絡(luò)數(shù)據(jù)集文獻[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種算法基于真實網(wǎng)絡(luò)的正確率、查全率、調(diào)和指標的性能對比

5 結(jié)束語

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

[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] 潘磊, 金杰, 王崇駿, 等. 社會網(wǎng)絡(luò)中基于局部信息的邊社區(qū)挖掘[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年生，博士生，研究方向為社會網(wǎng)絡(luò)分析、數(shù)據(jù)挖掘.

季新生： 男，1969年生，教授，博士生導(dǎo)師，主要研究領(lǐng)域為電信網(wǎng)安全、移動通信安全.

劉彩霞： 女，1974年生，副教授，碩士生導(dǎo)師，主要研究領(lǐng)域為移動通信安全、社會網(wǎng)絡(luò)分析.

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)資助課題