趙衛(wèi)績 田 雨 王鐵濱 劉井蓮

（綏化學院信息工程學院 綏化 152061）

度中心性節(jié)點局部擴展的社區(qū)發(fā)現(xiàn)算法?

趙衛(wèi)績 田 雨 王鐵濱 劉井蓮

（綏化學院信息工程學院 綏化 152061）

針對傳統(tǒng)社區(qū)發(fā)現(xiàn)方法在存在度中心節(jié)點的社會網(wǎng)絡中表現(xiàn)不佳的問題，提出一種面向度中心性網(wǎng)絡的局部社區(qū)發(fā)現(xiàn)算法。首先，基于最大度k個節(jié)點和重疊度閾值形成網(wǎng)絡中多個分散的初始社區(qū)，然后采用局部社區(qū)發(fā)現(xiàn)方法，計算每個初始社區(qū)的鄰居節(jié)點的局部模塊度增量，每次選取增量最大的節(jié)點歸入相應社區(qū)，以此方法逐步擴展初始社區(qū)，直至所有節(jié)點劃入到社區(qū)中。然后，在兩個真實網(wǎng)絡數(shù)據(jù)集上與GN和FN算法進行了比較，實驗結(jié)果表明，該文給出的算法能夠揭示出網(wǎng)絡中存在的以某個節(jié)點為中心的社區(qū)結(jié)構(gòu)，相比傳統(tǒng)算法，具有更高的準確度。

社區(qū)發(fā)現(xiàn)；社會網(wǎng)絡；度中心性；局部社區(qū)發(fā)現(xiàn)；重疊度

1 引言

隨著在線社交網(wǎng)絡如Facebook、Twitter、新浪微博、微信的興起，用戶在這些網(wǎng)站上的溝通、評價、分享，產(chǎn)生了豐富的內(nèi)容。在這些網(wǎng)絡上，人與人之間、人與內(nèi)容之間、內(nèi)容與內(nèi)容之間形成了海量的關系數(shù)據(jù)。這些關系數(shù)據(jù)可以用網(wǎng)絡來表示，網(wǎng)絡中的節(jié)點表示人或內(nèi)容，邊表示節(jié)點之間的關系。在這些網(wǎng)絡中隱含著很多密集區(qū)，區(qū)內(nèi)節(jié)點間聯(lián)系緊密，與區(qū)外節(jié)點聯(lián)系稀疏，這樣的密集區(qū)即為社區(qū)［1］。社區(qū)發(fā)現(xiàn)可用來揭示這類網(wǎng)絡中有共同特征的人或內(nèi)容，為開展個性化服務提供依據(jù)，因此社區(qū)發(fā)現(xiàn)的研究具有理論價值和實際應用意義。

Girvan和Newman首先提出網(wǎng)絡中存在著社區(qū)結(jié)構(gòu)，并給出了著名的社區(qū)發(fā)現(xiàn)GN算法［1～2］。該算法首先將整個網(wǎng)絡看成一個社區(qū)，然后計算網(wǎng)絡中每條邊的介數(shù)并去除介數(shù)最大的邊，重復以上操作，直至網(wǎng)絡中的所有邊都被刪除。該算法生成的結(jié)果是一棵層次聚類樹，得到了網(wǎng)絡的很多劃分。為了找到網(wǎng)絡的最佳劃分，Newman和Girvan給出了模塊度的概念［2］，模塊度越大意味著相應社區(qū)劃分越好，為從多個社區(qū)劃分結(jié)果中選擇最佳的劃分提供了依據(jù)。之后Newman基于模塊度的概念提出了一種被稱為FN的快速社區(qū)發(fā)現(xiàn)算法［3］。該算法首先將各個節(jié)點看成一個社區(qū)，然后不斷合并能夠使模塊度增量最大的兩個社區(qū)成為一個新社區(qū)，直至所有的節(jié)點成為一個社區(qū)。文獻［4］將網(wǎng)絡看作一個動力學系統(tǒng)，每個節(jié)點與周圍節(jié)點進行交互，通過模擬網(wǎng)絡中節(jié)點間的距離變化動態(tài)地發(fā)現(xiàn)社團結(jié)構(gòu)。除了以上方法，還有一類基于度中心節(jié)點的聚類方法，文獻［5］提出Top Leaders算法，該算法將社區(qū)定義為領袖節(jié)點與其跟隨者節(jié)點組成的集合。文獻［6］提出從度中心節(jié)點出發(fā)進行社區(qū)發(fā)現(xiàn)可以保證社區(qū)發(fā)現(xiàn)的準確度，基于該思想，文獻［7］提出了一種基于度中心節(jié)點的社區(qū)發(fā)現(xiàn)算法，該算法將相異度大的中心節(jié)點的集合組成核心節(jié)點集，然后采用相似性度量方法將網(wǎng)絡中其他的節(jié)點劃分到最相似的核心節(jié)點所在的社區(qū)。同Top Leaders算法一樣，該算法在處理網(wǎng)絡中的其他節(jié)點的劃分時，也是采用基于全局的相似度計算方法，需要計算節(jié)點到每一個初始社區(qū)的相似度，時間復雜度高。文獻［8］提出一種面向度中心性及重疊網(wǎng)絡社區(qū)的發(fā)現(xiàn)算法，考慮到度中心性節(jié)點的影響力以及重疊節(jié)點與不同社區(qū)的連接緊密程度，實現(xiàn)了同時具有度中心性節(jié)點和重疊節(jié)點網(wǎng)絡的準確劃分。

文獻［9］提出了局部社區(qū)發(fā)現(xiàn)方法，從網(wǎng)絡中的一個節(jié)點出發(fā)可以找到其所在的社區(qū)。定義了局部模塊度R，用來衡量一個已有社區(qū)加入一個鄰居節(jié)點后該社區(qū)的模塊度增減情況。文獻［10］用一個節(jié)點的d層鄰居節(jié)點的集合來表示該節(jié)點，通過節(jié)點的相似性給出了稱為GMAC的局部社區(qū)發(fā)現(xiàn)算法。文獻［10］基于隨機游走方法給每個節(jié)點賦一個權重，通過定義了一個有偏向的密度指標來尋找局部社區(qū)。該類方法基于局部計算，時間復雜度低，而且當起始節(jié)點處于社區(qū)的中心位置，該算法的準確性很高［6］。

結(jié)合度中心性節(jié)點算法和局部社區(qū)發(fā)現(xiàn)算法的優(yōu)點，本文提出一種基于度中心節(jié)點局部擴展的社區(qū)發(fā)現(xiàn)算法，首先，基于最大度k個節(jié)點和重疊度閾值形成網(wǎng)絡中多個分散的初始社區(qū)，然后，采用局部社區(qū)發(fā)現(xiàn)方法，計算每個初始社區(qū)的鄰居節(jié)點的局部模塊度增量，每次選取增量最大的節(jié)點歸入相應社區(qū)，更新該初始社區(qū)的鄰居節(jié)點及其局部模塊度增量，以此方法逐步擴展初始社區(qū)，直至所有節(jié)點劃入到社區(qū)中。本文算法采用局部社區(qū)發(fā)現(xiàn)方法，從初始社區(qū)局部擴展，獲取全局上的社區(qū)模塊度增加最大的節(jié)點，以局部的計算量取得了全局計算的效果，保證社區(qū)劃分的準確性。

2 度中心性節(jié)點局部擴展的社區(qū)發(fā)現(xiàn)

2.1 問題定義及相關概念

在描述本文算法之前，先給出問題定義及相關概念。

1）問題定義

通常用圖G=（V，E）來表示一個無向網(wǎng)絡，其中V是圖中節(jié)點的集合，E是圖中邊的集合，n=|V|是圖中節(jié)點的數(shù)目，d(vi)表示節(jié)點vi的度。社區(qū)發(fā)現(xiàn)是將圖G分為m（m≥1）個連通內(nèi)部連接緊密的子圖，而子圖間連接稀疏，可表示為：C={V1，V2，…，Vm}

Vi(1≤i≤m)是圖G的一個連通子圖的節(jié)點集合，V1∪V2∪…∪Vm=V。若任意兩個社區(qū)的節(jié)點集合的交集為空，則稱C為圖G的一個非重疊社區(qū)劃分，否則C為圖G的一個重疊社區(qū)劃分。本文關注的是非重疊社區(qū)劃分。

2）重疊度

本文采用重疊度來度量一個候選初始社區(qū)包含于另一個候選初始社區(qū)的程度。如果兩個候選初始社區(qū)的重疊度較大，則節(jié)點個數(shù)較小的候選初始社區(qū)不能成為初始社區(qū)。

設A、B是兩個候選初始社區(qū)，則這兩個候選初始社區(qū)的重疊度ove（rA，B）［12］定義為

3）局部模塊度 R［8］

社區(qū)D中的節(jié)點可以分為兩部分，那些與D外節(jié)點有連接的節(jié)點稱為邊界節(jié)點，與D外節(jié)點沒有連接的節(jié)點稱為內(nèi)部節(jié)點。邊界節(jié)點的集合，用B來表示。Bin為B中節(jié)點與D內(nèi)節(jié)點連接的邊數(shù)，Bout為B中節(jié)點與D外節(jié)點連接的邊數(shù)。局部模塊度R定義為

2.2 算法描述

針對存在度中心節(jié)點的社會網(wǎng)絡，本文充分利用從中心點出發(fā)更容易得到正確的社區(qū)以及局部方法時間復雜度低的優(yōu)點，提出一種基于度中心節(jié)點局部擴展的兩階段社區(qū)挖掘算法。首先，基于重疊度公式over（A，B），采用文獻［8］中算法1發(fā)現(xiàn) k′個初始社區(qū)，然后采用局部社區(qū)擴展方法，從這k′個初始社區(qū)出發(fā)，解決不在k′個初始社區(qū)中的節(jié)點歸屬問題。首先計算k′個初始社區(qū)的鄰居節(jié)點集Neighbors，其中初始社區(qū)Ci的鄰居節(jié)點集為Neighborsi。對于i從1～ k′，計算 Neighborsi中每一個節(jié)點如果加入Ci的模塊度增量，保存到DeltaRi中。選擇 DeltaR1，DeltaR2，…，DeltaRk′中取值最大的模塊度增量對應的節(jié)點并入相應的初始社區(qū)，如果該節(jié)點也出現(xiàn)在其他初始社區(qū)的鄰居節(jié)點中，則將之刪除，重復該操作，直至所有節(jié)點都劃分到社區(qū)中。具體算法為

輸入：網(wǎng)絡G=（V，E），初始社區(qū) C={C1，C2，…，Ck′}；

輸出：最終劃分結(jié)果 C={C1，C2，…，Ck′}

方法：

/*計算初始社區(qū)Ci的鄰居節(jié)點集Neighborsi*/

f

o

r everyCi∈C

for everyvj∈Ci

Neighborsi=Neighborsi∪nbrs（G，vj）；/*函數(shù)nbrs（G，vi）以集合的形式返回節(jié)點vi的所有鄰居節(jié)點*/

end for

Neighborsi=Neighborsi-Ci；

end for

/*計算初始社區(qū)Ci鄰居節(jié)點集Neighborsi中每個節(jié)點的局部模塊度增量*/

for every Neighborsi∈Neighbors

for every vj∈Neighborsi

計算vj相對于社區(qū)Ci的局部模塊度增量，用dr表示；//應用公式（2）

DeltaRi=DeltaRi∪｛dr｝；

end for

end for

while|C|＜|G|

計算DeltaR中取值最大的元素所在的DeltaRx，以及在DeltaRx中的序號 y；

Cx=Cx∪｛Neighborsx［y］｝；

更新Cx的鄰居節(jié)點集Neighborsx及相應的DeltaRx；

for every Ci∈ C&i！=x

if Neighborsx［y］∈Neighborsi

從Neighborsi中刪除Neighborsx［y］節(jié)點；

end if

end for

end while

3 實驗分析

為了測試本文算法的準確性，在Karate［13］和Dolphins［14］兩個真實網(wǎng)絡數(shù)據(jù)集上與GN和FN算法進行了對比。為了衡量各個算法的效果，我們采用社區(qū)劃分的兩個常用指標歸一化互信息NMI［15］和 ARI（Adjusted Rand Index）［16］來衡量各算法得到的社區(qū)劃分與真實社區(qū)劃分的相似性，NMI和ARI取值越大，表示與真實社區(qū)劃分越吻合。

1）在Karate數(shù)據(jù)集上的實驗

Karate數(shù)據(jù)集是美國大學空手道俱樂部成員間的社會關系，該網(wǎng)絡圖中包含34個節(jié)點，78條邊，其中每個節(jié)點表示一個俱樂部成員，節(jié)點間連接表示兩個成員之間經(jīng)常在一起參加俱樂部活動，在該俱樂部，因為主管節(jié)點34和教練節(jié)點1之間發(fā)生分歧而分裂成以兩個節(jié)點為核心的俱樂部。該俱樂部成員的社會關系網(wǎng)具體如圖1（a）所示，社區(qū)劃分如圖圖1（b）所示。

圖1 Karate俱樂部網(wǎng)絡及其社區(qū)結(jié)構(gòu)

以k=6，q=0.25，本文算法得到2個社區(qū)，分別為［1，2，3，4，5，6，7，8，11，12，13，14，17，18，20，22］和［9，10，15，16，19，21，23，24，25，26，27，28，29，30，31，32，33，34］，該結(jié)果與真實結(jié)果完全一樣。而GN錯劃了節(jié)點3，F(xiàn)N算法錯劃了節(jié)點10。比較結(jié)果如圖2，本文算法的NMI和ARI值均為1，而 GN 算 法 的 NMI、ARI值 分 別 為 0.8365、0.8823，F(xiàn)N 算法的 NMI和 ARI分別為 0.8372、0.8823。本文算法在該數(shù)據(jù)集上的準確度高于GN和FN算法。

圖2 在Karate數(shù)據(jù)集上的比較結(jié)果

2）在Dolphins數(shù)據(jù)集上的實驗

海豚關系網(wǎng)是社會網(wǎng)絡分析中的一個真實網(wǎng)絡，常用于測試社區(qū)挖掘算法的有效性。這是Lusseau等對棲息在新西蘭Doubtful Sound峽灣的62只海豚進行長達7年的觀察，并構(gòu)造海豚關系網(wǎng)如圖3（a）所示，圖中共有62個節(jié)點，159條邊。每個節(jié)點表示一個海豚，邊表示兩個海豚接觸頻繁。圖3（b）為該網(wǎng)絡的社區(qū)結(jié)構(gòu)。

圖3 海豚網(wǎng)絡及其社區(qū)結(jié)構(gòu)

以k=6，q=0.18，本文算法得到［0，2，3，4，8，10，11，12，14，15，16，18，20，21，23，24，28，29，30，33，34，35，36，37，38，40，42，43，44，45，46，47，49，50，51，52，53，55，58，59，61］和［1，5，6，7，9，13，17，19，22，25，26，27，31，32，39，41，48，54，56，57，60］兩個社區(qū)，相比真實社區(qū)只錯劃了節(jié)點39。GN算法同樣錯劃了節(jié)點39，而FN算法錯劃了28和30兩個節(jié)點。比較結(jié)果如圖4，本文算法與GN算法的NMI和ARI值相同，分別為0.8888、0.9348，F(xiàn)N算法的NMI和ARI值分別為0.8141、0.8721。本文算法與GN算法在該數(shù)據(jù)集上的準確度都高于FN算法。

圖4 在海豚數(shù)據(jù)集上的比較結(jié)果

4 結(jié)語

社區(qū)發(fā)現(xiàn)能夠揭示出網(wǎng)絡中隱含著的社區(qū)結(jié)構(gòu)，已經(jīng)成為一種分析社會網(wǎng)絡的重要手段。本文針對存在度中心節(jié)點的社會網(wǎng)絡，提出一種面向度中心性網(wǎng)絡的社區(qū)發(fā)現(xiàn)算法。首先基于最大度節(jié)點和重疊度閾值形成網(wǎng)絡中多個分散的初始社區(qū)。然后采用局部社區(qū)發(fā)現(xiàn)方法，從所有初始社區(qū)的鄰居節(jié)點中選擇局部模塊度增量最大的節(jié)點歸入相應社區(qū)，以此方法逐步擴展初始社區(qū)，直至所有節(jié)點劃入到社區(qū)中。最后，在真實網(wǎng)絡數(shù)據(jù)集上與GN和FN算法進行了比較，實驗結(jié)果表明，本文算法具有更高的準確度。

［1］Girvan M，Newman MEJ.Community structure in social and biological networks［C］//Proceedings of the National Academy of Sciences of the united States of America.2002，99（12）：7821-7826.

［2］Newman MEJ，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69（2）：026113.

［3］Newman MEJ.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69（6）：066133-1--066133-5.

［4］Shao J，Han Z，Yang Q，Zhou T.Community Detection based on Distance Dynamics［C］//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2015：1075-1084.

［5］Khorasgani RR，Chen J，Za?ane O R.Top Leaders Community Detection Approach in Information Networks［C］//4th SNA-KDD Workshop on Social Network Mining and Analysis.Washington，DC，USA，2010：2319-7323.

［6］Chen Q，Wu T：A method for local community detection by finding maximal-degree nodes［C］//ICMLC 2010：8-13.

［7］牛冬冬，陳鴻昶，金鑫，等.基于核心節(jié)點的復雜網(wǎng)絡社區(qū) 劃 分 算 法［J］.計 算 機 工 程 與 設 計 ，2013，12：4089-4093.NIU Dongdong，CHEN Hongchang，JIN Xin，et al.Com-plex network community detection algorithm based on core nodes［J］.Computer engineering and Design，2013，34（12）：4089-4093.

［8］劉井蓮，王大玲，馮時，等.一種面向度中心性及重疊網(wǎng)絡社區(qū)的發(fā)現(xiàn)算法［J］.計算機科學，2016，43（3）：33-37.LIU Jinglian，WANG Daling，F(xiàn)ENG Shi，et al.Algorithm for discovering network community with centrality and overlap［J］.Computer Science，2016，43（3）：33-37.

［9］Liu J L，Wang D L，F(xiàn)eng S，Zhang Y F，Zhao F J.Algorithm for discovering network community with centrality and overlap［J］，Computer Science，2016，43（3）：33-37.

［10］Clauset A：Finding local community structure in networks［J］.Physical Review E，2005，72（2）：026132.

［11］Ma L，Huang H，He Q，Chiew K，Wu J，Che Y：GMAC：A Seed-Insensitive Approach to Local Community Detection［C］//DaWaK 2013：297-308.

［12］Wu Y，Jin R，Li J，Zhang X.Robust local community detection：on free rider effect and its elimination［C］//VLDB，2015：798-809.

［13］PAN L，DAI C，WANG C J，et al.Overlapping community detection via leader-based local expansion in social Nnetworks［C］//Proceedings of IEEE 24th International Conference on Tools with Artificial Intelligence（ICTAI12）.Athens，Greece：Ioannis Vlahava，Sotirios G.Ziavras，2012：397-404.

［14］Zachary WW：An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33（4）：452-473.

［15］Lusseau D，Schneider K，Boisseau O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations—Can geographic isolation explain this unique trait？［J］.Behavioral Ecology and Sociobiology，2003，54（4）：396-405.

［16］DANON L，DíAZ-GUILERA A，DUCH J，et al.Comparing community structure identification［J］.Journal of Statistical Mechanics，2005，9（9）：P09008-1-P09008-10.

［17］Santos J M，Embrechts M.On the Use of the Adjusted Rand Index as a Metric for Evaluating Supervised Classification［C］//Artificial Neural Networks-ICANN.Springer Berlin Heidelberg，2009：175-184.

Community Detection Algorithm Based on Degree Central Nodes Local Expansion

ZHAO WeijiTIAN Yu WANG Tiebin LIU Jinglian
（Information Engineering College，Suihua University，Suihua 152061）

Because traditional community detection methods have poor performance on social networks with centrality，algorithm for discovering community structure in networks with centrality is proposed in this paper.First，based on the top-k maximum degree nodes and overlapping degree threshold，several separate initial community are formed.Then，adopting local community detection method，compute the local modularity incremental quantity of initial communities'neighbor nodes，the node with maximum value is added to the corresponding initial community，repeat these operations until all nodes are assigned to the respective community.We compare our proposed method with GN and FN algorithms on two well-known real-world networks whose community structures are already given.The results of the experiment demonstrate that our algorithm is highly effective at discovering community structure in networks with centrality，and it has high accuracy.

community detection，social network，degree centrality，local community detection，overlap degree

TP391

10.3969/j.issn.1672-9722.2017.11.026

Class Number TP391

2017年5月19日，

2017年6月14日

綏化學院青年基金重點項目（編號：KQ1301002），2016年黑龍江省大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目（編號：201610236014）；國家青年科學基金項目（編號：61401185）資助。

趙衛(wèi)績，男，碩士，講師，研究方向：數(shù)據(jù)挖掘、社會網(wǎng)絡分析。田雨，男，研究方向：算法設計與分析。王鐵濱，女，副教授，研究方向：數(shù)據(jù)倉庫、數(shù)據(jù)分析。劉井蓮，女，博士，講師，研究方向：社會網(wǎng)絡分析與社會媒體挖掘。