度中心性節點局部擴展的社區發現算法?

趙衛績 田 雨 王鐵濱 劉井蓮

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

度中心性節點局部擴展的社區發現算法?

趙衛績 田 雨 王鐵濱 劉井蓮

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

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

社區發現；社會網絡；度中心性；局部社區發現；重疊度

1 引言

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

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

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

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

2 度中心性節點局部擴展的社區發現

2.1 問題定義及相關概念

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

1）問題定義

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

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

2）重疊度

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

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

3）局部模塊度 R［8］

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

2.2 算法描述

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

輸入：網絡G=（V，E），初始社區 C={C1，C2，…，Ck′}；

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

方法：

/*計算初始社區Ci的鄰居節點集Neighborsi*/

f

o

r everyCi∈C

for everyvj∈Ci

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

end for

Neighborsi=Neighborsi-Ci；

end for

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

for every Neighborsi∈Neighbors

for every vj∈Neighborsi

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

DeltaRi=DeltaRi∪｛dr｝；

end for

end for

while|C|＜|G|

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

Cx=Cx∪｛Neighborsx［y］｝；

更新Cx的鄰居節點集Neighborsx及相應的DeltaRx；

for every Ci∈ C&i！=x

if Neighborsx［y］∈Neighborsi

從Neighborsi中刪除Neighborsx［y］節點；

end if

end for

end while

3 實驗分析

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

1）在Karate數據集上的實驗

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

圖1 Karate俱樂部網絡及其社區結構

以k=6，q=0.25，本文算法得到2個社區，分別為［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］，該結果與真實結果完全一樣。而GN錯劃了節點3，FN算法錯劃了節點10。比較結果如圖2，本文算法的NMI和ARI值均為1，而 GN 算 法 的 NMI、ARI值 分 別 為 0.8365、0.8823，FN 算法的 NMI和 ARI分別為 0.8372、0.8823。本文算法在該數據集上的準確度高于GN和FN算法。

圖2 在Karate數據集上的比較結果

2）在Dolphins數據集上的實驗

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

圖3 海豚網絡及其社區結構

以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］兩個社區，相比真實社區只錯劃了節點39。GN算法同樣錯劃了節點39，而FN算法錯劃了28和30兩個節點。比較結果如圖4，本文算法與GN算法的NMI和ARI值相同，分別為0.8888、0.9348，FN算法的NMI和ARI值分別為0.8141、0.8721。本文算法與GN算法在該數據集上的準確度都高于FN算法。

圖4 在海豚數據集上的比較結果

4 結語

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

［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］牛冬冬，陳鴻昶，金鑫，等.基于核心節點的復雜網絡社區 劃 分 算 法［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］劉井蓮，王大玲，馮時，等.一種面向度中心性及重疊網絡社區的發現算法［J］.計算機科學，2016，43（3）：33-37.LIU Jinglian，WANG Daling，FENG 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，Feng 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年黑龍江省大學生創新創業訓練計劃項目（編號：201610236014）；國家青年科學基金項目（編號：61401185）資助。

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