劉 陽 季新生 劉彩霞

?

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

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

1 引言

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

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

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

2 問題分析

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

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

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

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

3.1 基本定義

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

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

3.2 算法描述

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

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

4 實(shí)驗(yàn)

4.1 評價準(zhǔn)則與方法

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

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

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

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

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

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

真實(shí)網(wǎng)絡(luò)相比計算機(jī)生成網(wǎng)絡(luò)更不規(guī)則，因而其社區(qū)結(jié)構(gòu)往往也更加復(fù)雜。這里采用5個具有不同規(guī)模的典型真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集：2000賽季大學(xué)生美式足球聯(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拓?fù)渚W(wǎng)絡(luò)(Internet)[18]來進(jìn)一步測試算法性能，表3描述了這些真實(shí)網(wǎng)絡(luò)的基本屬性。

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

網(wǎng)絡(luò)數(shù)據(jù)集節(jié)點(diǎn)數(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無向未知

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

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

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

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

5 結(jié)束語

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

[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].電子學(xué)報, 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年生，博士生，研究方向?yàn)樯鐣W(wǎng)絡(luò)分析、數(shù)據(jù)挖掘.

季新生： 男，1969年生，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)殡娦啪W(wǎng)安全、移動通信安全.

劉彩霞： 女，1974年生，副教授，碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)橐苿油ㄐ虐踩?、社會網(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計劃項(xiàng)目(2011AA010604)和國家重大科技專項(xiàng)(2012ZX03006002)資助課題