一種基于最大度節(jié)點擴展的社區(qū)發(fā)現(xiàn)算法

趙衛(wèi)績,劉井蓮,佟 良

(綏化學(xué)院 信息工程學(xué)院，黑龍江 綏化 152061)

?

一種基于最大度節(jié)點擴展的社區(qū)發(fā)現(xiàn)算法

趙衛(wèi)績,劉井蓮,佟 良

(綏化學(xué)院 信息工程學(xué)院，黑龍江 綏化 152061)

針對星狀社會網(wǎng)絡(luò)，提出一種基于最大度節(jié)點擴展的社區(qū)發(fā)現(xiàn)算法.首先，計算網(wǎng)絡(luò)中所有節(jié)點的度，選取節(jié)點的度大于等于閾值p的k個節(jié)點，以這k個節(jié)點為中心，與其各自的鄰居節(jié)點形成k個分散的初始社區(qū)，刪除重疊度高于給定閾值q的小社區(qū).然后，對出現(xiàn)在這些初始社區(qū)中的重疊節(jié)點，提出一種近鄰方法，通過計算這些節(jié)點到所在社區(qū)的距離，將其劃分到距離最近的社區(qū).對于k個初始社區(qū)外的節(jié)點，采用同樣方法，將其劃入到相應(yīng)距離最近的社區(qū).在真實網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實驗，實驗結(jié)果表明，該方法能有效地處理初始社區(qū)內(nèi)外邊緣部分的不確定節(jié)點的劃分問題，揭示出網(wǎng)絡(luò)中存在的社區(qū)結(jié)構(gòu).相比經(jīng)典的GN算法，該算法能得到更準(zhǔn)確的劃分結(jié)果，也具有更高的性能.

星狀網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)；最大度節(jié)點

社會媒體網(wǎng)站的出現(xiàn)，不僅給人們提供了豐富的網(wǎng)絡(luò)信息，也提供了新的社交手段.在社交網(wǎng)站上人們可以互相交流、分享信息、評價信息，這些操作的背后形成了豐富的關(guān)系數(shù)據(jù).在這些數(shù)據(jù)背后，存在著大量的密集社區(qū)，社區(qū)發(fā)現(xiàn)能夠揭示網(wǎng)絡(luò)中的社區(qū)，已經(jīng)成為社會網(wǎng)絡(luò)分析中的一項重要研究.2002年，Girvan和Newman首次提出著名的GN算法[1]，通過計算網(wǎng)絡(luò)中所有邊的介數(shù)，并去除介數(shù)最大的邊，重復(fù)該操作以獲取網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，引發(fā)了國內(nèi)外學(xué)者的廣泛關(guān)注.文獻(xiàn)[2，3]采用派系過濾思想，通過建立派系圖，發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū).文獻(xiàn)[4]基于領(lǐng)域粗糙化，給出了一種啟發(fā)式的社區(qū)發(fā)現(xiàn)方法.文獻(xiàn)[5]基于圖中的極大完全圖擴展來挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).文獻(xiàn)[6]將隨機游走的蟻群算法應(yīng)用于社區(qū)發(fā)現(xiàn)中.文獻(xiàn)[7]基于傳統(tǒng)密度聚類算法來發(fā)現(xiàn)層次社區(qū)結(jié)構(gòu).此外，還有采用圖劃分、拓?fù)涫降确椒ǖ纳鐓^(qū)發(fā)現(xiàn)方法[8-10].Radicchi[11]對經(jīng)典的GN算法進(jìn)行了改進(jìn)，采用邊聚類系數(shù)代替邊介數(shù)，算法運行效率相比GN算法有很大的提升.但該算法適合處理回路較多的復(fù)雜網(wǎng)絡(luò)，不適合處理樹狀拓?fù)渚W(wǎng)絡(luò)和星型拓?fù)渚W(wǎng)絡(luò).針對星狀拓?fù)渚W(wǎng)絡(luò)，本文提出一種基于最大度節(jié)點的社區(qū)發(fā)現(xiàn)算法.首先計算網(wǎng)絡(luò)中所有節(jié)點的度，然后找出大于等于閾值p的top-k個節(jié)點，以這k個節(jié)點為中心，與其各自鄰居節(jié)點形成k個分散的初始社區(qū).對于初始社區(qū)交叉區(qū)域中的節(jié)點，提出一種近鄰方法，通過計算交叉區(qū)域節(jié)點到其所在社區(qū)的距離，將其劃分到距離最小的社區(qū).對于k個初始社區(qū)外的節(jié)點，采用同樣方法，將其劃入到相應(yīng)社區(qū).在真實網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了測試，實驗結(jié)果表明，該方法能夠快速找到星狀網(wǎng)絡(luò)中的社區(qū).

1 相關(guān)概念與公式

1.1 社會網(wǎng)絡(luò)

“網(wǎng)絡(luò)”是指由節(jié)點及節(jié)點之間的關(guān)系構(gòu)成的集合.在社會學(xué)中，“社會網(wǎng)絡(luò)”定義為行動者及其關(guān)系構(gòu)成的集合[12].在社會網(wǎng)絡(luò)分析中，常常用節(jié)點表示社會網(wǎng)絡(luò)中的實體，邊用于表示實體之間的關(guān)系.社會網(wǎng)絡(luò)可以用圖來描述，社會網(wǎng)絡(luò)中的行動者是圖中的節(jié)點，行動者之間的關(guān)系是圖中的邊.表示社會網(wǎng)絡(luò)中的圖，可以記作G=(V,E),V是節(jié)點集合，E是邊集合，n=|V|表示圖中節(jié)點的個數(shù).

1.2 節(jié)點的度

節(jié)點vi的度用k(vi)表示，指與節(jié)點vi關(guān)聯(lián)的邊的數(shù)量.對于含有n個節(jié)點的圖，節(jié)點度的最小值為0，是圖中的孤立節(jié)點，不與任何節(jié)點相關(guān)聯(lián)；節(jié)點度的最大值為n-1，與圖中除了自身以外所有的節(jié)點都相關(guān)聯(lián).

1.3 重疊度

在社交網(wǎng)絡(luò)中，存在大量的以度大的節(jié)點為中心形成的密集社區(qū).為了衡量一個小社區(qū)在大社區(qū)中的包含程度，本文使用重疊度來衡量這一指標(biāo).設(shè)兩個社區(qū)分別為Ci和Cj，則其重疊度Oij計算方法如下：

(1)

1.4 距離

對于社區(qū)間的邊界節(jié)點及不在初始社區(qū)中的節(jié)點，為了衡量這些節(jié)點與哪個社區(qū)聯(lián)系最緊密，本文使用一種改進(jìn)的連接度方法來度量節(jié)點與社區(qū)之間的距離.設(shè)節(jié)點vi與初始社區(qū)Cj中的m個節(jié)點相連接，k(vi)是節(jié)點vi度，則節(jié)點vi到社區(qū)Cj的距離定義為：

dij=1-m/k(vi)

(2)

dij的值反映了一個節(jié)點vi與它的相鄰社區(qū)之間的距離，如果vi與初始社區(qū)Cj中任何節(jié)點沒有連接，則dij為1；節(jié)點vi與初始社區(qū)連接的節(jié)點越多，dij值越小.用m除以k(vi)，將距離規(guī)范化，使dij值分布[0,1].當(dāng)dij值為0時，表示節(jié)點vi的鄰居節(jié)點全在社區(qū)Cj中.

2 基于最大度節(jié)點擴展的社區(qū)發(fā)現(xiàn)算法

2.1 基本思想

在線社交網(wǎng)絡(luò)中存在海量網(wǎng)絡(luò)節(jié)點的同時，其形成的關(guān)系又往往是極度稀疏的.在這些社會網(wǎng)絡(luò)中，常常存在著以某些節(jié)點與其鄰居節(jié)點形成的密集社區(qū)結(jié)構(gòu).例如在明星粉絲團網(wǎng)絡(luò)中，越受關(guān)注的明星具有越大的度，明星的度能夠反映明星的活躍程度和被關(guān)注程度.針對此類網(wǎng)絡(luò)，文獻(xiàn)[13]提出了一種基于核心節(jié)點的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，該算法將相異度大的中心節(jié)點的集合組成核心節(jié)點集，然后采用相似性度量方法將網(wǎng)絡(luò)中其他的節(jié)點劃分到最相似的核心節(jié)點所在的社區(qū).本文借鑒了該算法的思想，針對社會網(wǎng)絡(luò)中存在以某些最大度節(jié)點為中心的密集區(qū)，提出一種新的社區(qū)發(fā)現(xiàn)算法.首先計算社會網(wǎng)絡(luò)中各個節(jié)點的度，選取前top-k個節(jié)點為核心節(jié)點，將這k個核心節(jié)點與其各自的鄰居節(jié)點生成k個分散的初始社區(qū).然后對于初始社區(qū)交集的節(jié)點，基于連接度指標(biāo)，將其劃分到與其連接緊密的相應(yīng)社區(qū)，對于初始社區(qū)外節(jié)點，采用同樣方法將其劃分到與其連接緊密的相應(yīng)社區(qū).該方法有效處理了初始社區(qū)不同程度的重疊問題和在初始社區(qū)外的節(jié)點的歸屬問題.

2.2 算法描述

(1)發(fā)現(xiàn)初始社區(qū).首先計算圖中每個節(jié)點的度，選取度大于等于閾值p的k個節(jié)點與其鄰居節(jié)點集形成候選初始社區(qū)Ci.判斷任意兩個候選初始社區(qū)的重疊度，如果高于閾值q，則刪除小社區(qū)，直到任意兩個社區(qū)之間的重疊度均低于閾值q，形成初始社區(qū)劃分.該方法保證了初始社區(qū)之間的重疊度低，提高了社區(qū)發(fā)現(xiàn)的穩(wěn)定性.

算法1:發(fā)現(xiàn)初始社區(qū)輸入:網(wǎng)絡(luò)G=(V,E),度閾值p,初始社區(qū)重疊度閾值q;輸出:初始社區(qū)劃分C;方法:1)k=1;2)fori=1to|V|3)if(k(vi)≥p)4)Ck={vi}∪Γ(vi);5)k++;6)C=C1∪C2...∪Ck7)foranyCi,Cj∈C8)if(Oij>q)9)if|Ci|>|Cj|10)deleteCjfromC;11)else12)deleteCifromC;13)k--;14)returnC;

(2)處理初始社區(qū)間重疊節(jié)點和初始社區(qū)外結(jié)點的歸屬.首先，計算出現(xiàn)在兩個及以上初始社區(qū)中出現(xiàn)的節(jié)點，構(gòu)成重疊節(jié)點集B，然后采用公式(2)，計算重疊節(jié)點到對應(yīng)重疊社區(qū)的距離，選擇最近距離，將節(jié)點劃到近鄰社區(qū)內(nèi).具體算法如下：

算法2:形成最終社區(qū)劃分輸入:網(wǎng)絡(luò)G=(V,E),初始社區(qū)C={C1,C2,…,Ck};輸出:最終劃分結(jié)果C={C1,C2,…,Ck};方法:1)B=Φ;2)fori=1to|V|3)ifviinmorethanonecommunities4)B=B∪{vi};5)forj=1to|B|6)calculatethedistancefromvjtoinitialcommunitieswhichvjbelongsto;7)addvjtothecommunitywhichhasminimumdistance;

對于初始社區(qū)外節(jié)點采用5)～7)同樣的方法處理，將其劃入到與其距離最小的社區(qū)內(nèi).

2.3 算法示例與分析

為了測試本文提出算法的有效性，在圖1(a)所示數(shù)據(jù)集上[13]，驗證了本文提出算法的有效性.網(wǎng)絡(luò)中的節(jié)點及邊，如圖1(a)所示.

圖1 一個小型社會網(wǎng)絡(luò)及其劃分結(jié)果

計算步驟：第1步，形成初始社區(qū)：設(shè)p=4,q=0.75,選取節(jié)點的度大于等于p的節(jié)點集合為{4,5,6,7}，形成4個初始社區(qū)，這四個節(jié)點與其各自的鄰居節(jié)點形成的初始社區(qū)分別為C1={4,1,3,5,6}，C2={5,4,6,7,8}，C3={6,4,5,7,8}，C4={7,5,6,8,9}.第2步，處理初始社區(qū)的重疊問題，逐一計算各個社區(qū)的重疊度，其中C4與C2和C3的重疊度0.8，大于等于q，則保留節(jié)點數(shù)目較多的C4，刪除C2和C3，形成最終的初始社區(qū)：C1={4,1,3,5,6}和C4={7,5,6,8,9}.第3步，處理社區(qū)交集間節(jié)點的歸屬問題，C1∩C4={5,6}，而節(jié)點5只與社區(qū)C1中的節(jié)點4連接，與C4中的節(jié)點6、7、8都連接，因此節(jié)點5距離C4最近，劃分到社區(qū)C4中，將節(jié)點5從社區(qū)C1中刪除.同理節(jié)點6距離C4社區(qū)最近，劃分到社區(qū)C4中，將它從社區(qū)C1刪除.處理完交叉節(jié)點后的社區(qū)為：C1={4,1,3}和C4={7,5,6,8,9}.第4步，處理初始社區(qū)外節(jié)點的歸屬.初始社區(qū)外的只有節(jié)點2，采用步驟3中的方法，由于節(jié)點2只與C1中節(jié)點有連接，與C4中節(jié)點沒有連接，所以節(jié)點2劃分到C1中.最終形成的兩個社區(qū)分別為{1,2,3,4}和{5,6,7,8,9}，與實際相符.社區(qū)劃分結(jié)果如圖1(b)所示.

3 實驗

本文采用經(jīng)典數(shù)據(jù)集“美國大學(xué)空手道俱樂部成員間的社會關(guān)系”[14]來測試本文算法的準(zhǔn)確性.該俱樂部成員的社會關(guān)系網(wǎng)具體如圖2(a)所示，圖中包含34個節(jié)點，78條邊，其中每個節(jié)點表示該俱樂部的一個成員，節(jié)點間的邊表示兩個成員之間經(jīng)常在一起參加俱樂部活動.該俱樂部由于主管節(jié)點34和教練節(jié)點1之間發(fā)生分歧而分裂成以兩個節(jié)點為核心的俱樂部.

圖2 Karate網(wǎng)絡(luò)圖及其劃分結(jié)果

采用本文方法，首先度最大的節(jié)點1和34，與其鄰接節(jié)點構(gòu)成的初始社區(qū)為：A={1,2,3,4,5,6,7,8,9,11,12,13,14,18,20,22,32}和B={9,10,14,15,16,19,20,21,23,24,27,28,29,30,31,32,33,34}.其中A和B的交集為{9,14,20,32}，節(jié)點9分別與社區(qū)A中節(jié)點1、3相連接，與B中節(jié)點31,33,34相連，所以節(jié)點9到初始社區(qū)B距離最小.同理節(jié)點14、20劃分到社區(qū)A，節(jié)點32劃分到社區(qū)B.

對于初始社區(qū)A和B之外的節(jié)點{17，25，26}，采用同樣方法，由于節(jié)點17只與初始社區(qū)A中節(jié)點6，7連接，因此節(jié)點17劃分到社區(qū)A中；同理，節(jié)點25只與B中節(jié)點連接，劃分到社區(qū)B，節(jié)點26只與社區(qū)B相連，劃分到社區(qū)B.因此最終形成兩個社區(qū)：以節(jié)點1為中心16個節(jié)點組成的社區(qū){1,2,3,4,5,6,7,8,11,12,13,14,17,18,20,22}和以節(jié)點34為中心18個節(jié)點組成的社區(qū){9,10,15,16,19,20,21,23,24,25,26,27,29,30,31,32,33,34}.具體如圖2(b)所示.

從實驗結(jié)果來看，本文提出的基于最大度節(jié)點的社區(qū)發(fā)現(xiàn)算法，能夠得到與實際相符的社區(qū)結(jié)構(gòu).而經(jīng)典的GN算法[1]，將節(jié)點3錯誤劃分到以34為中心的社區(qū)B.對比GN算法，本文算法在星狀社會網(wǎng)絡(luò)中能夠得到更準(zhǔn)確的劃分結(jié)果.

4 總結(jié)

社區(qū)發(fā)現(xiàn)是社會網(wǎng)絡(luò)分析中一項重要的研究工作，目前已經(jīng)在生物領(lǐng)域、在全球傳染病病毒傳播上和恐怖主義活動分析、微博、電子商務(wù)中等多個領(lǐng)域發(fā)揮了重要作用.本文針對社會網(wǎng)絡(luò)分析中常常存在以度大節(jié)點為中心的密集區(qū)，提出一種基于最大度節(jié)點的社區(qū)發(fā)現(xiàn)算法.該算法通過選取度大節(jié)點與其鄰居節(jié)點形成多個分散的初始社區(qū)，對初始社區(qū)間重疊部分節(jié)點和初始社區(qū)外節(jié)點采用連接度指標(biāo)，實現(xiàn)復(fù)雜社會網(wǎng)絡(luò)社區(qū)的合理劃分.相比經(jīng)典的GN算法，能得到更加準(zhǔn)確的劃分結(jié)果.

[1]M.Girvan,M E J.Newman. Community structure in social and biological networks[C].Proceedings of the National Academy of Sciences，2002,99(12):7821-7826.

[2]G.Palla,I.Derenyi,T.Farkas et al..Uncovering the overlapping community structure of complex networks in nature and society[J].Nature，2005,435(7043):814-818.

[3]T S.Evans.Clique graphs and overlapping communities [J].Journal of Statistical Mechanics Theory and Experiment，2010,2010(3):257-265.

[4]張澤華,苗奪謙,錢進(jìn).鄰域粗糙化的啟發(fā)式重疊社區(qū)擴張方法[J].計算機學(xué)報，2013,36(10):2078-2086.

[5]劉井蓮,趙衛(wèi)績,佟良.一種基于極大完全圖擴展的社區(qū)挖掘算法[J].河南科學(xué)，2015,33(12):2140-2145.

[6]金弟,楊博,劉杰,劉大有,何東曉.復(fù)雜網(wǎng)絡(luò)族結(jié)構(gòu)探測-基于隨機游走的蟻群算法[J].軟件學(xué)報，2012,23(3):451-464.

[7]林旺群,盧風(fēng)順,丁兆云,吳泉源,周斌,賈焰.基于帶權(quán)圖的層次化社區(qū)并行計算方法[J].軟件學(xué)報，2012,23(6):1517-1530.

[8]黃健斌,孫鶴立,DustinBORTNER,劉亞光.從鏈接密度遍歷序列中挖掘網(wǎng)絡(luò)社區(qū)的層次結(jié)構(gòu)[J].軟件學(xué)報,2011,22(5):951-961.

[9]張忠元.基于字典學(xué)習(xí)的網(wǎng)絡(luò)社K結(jié)構(gòu)探測算法[J].中國科學(xué):信息科學(xué)，2011,41(11):1343-1355.

[10]淦文燕,赫南,李德毅,王建民.一種基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J].軟件學(xué)報，2009,20(8):2241-2254.

[11]F.Radicchi,C.Castellano,F.Cecconi,V.Loreto,D.Parisi.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America.2004,101(9):2658-2663.

[12]S.Wasserman,K.Faust.社會網(wǎng)絡(luò)分析：方法與應(yīng)用[M].陳禹，等譯.北京：中國人民大學(xué)出版社，2012:26,69.

[13]牛冬冬,陳鴻昶,金鑫,劉力雄.基于核心節(jié)點的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分算法[J].計算機工程與設(shè)計,2013(12):4089-4093.

[14]W.W.Zachary.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.

(責(zé)任編輯:王前)

A Novel Community Detection Algorithm Based on Maximal-degree Nodes Expansion

ZHAO Wei-ji, LIU Jing-lian, TONG Liang

(SchoolofInformationEngineering,SuihuaUniversity,Suihua,Heilongjiang152061,China)

For detecting community structure in star networks, a novel algorithm based on maximal-degree nodes expansion is proposed. Firstly, the degrees of all nodes in a network is computed. The top-k nodes as the center nodes whose degrees are bigger than or equal to threshold p, the top-k nodes and their neighbor nodes form k initial communities are found out. The small communities whose overlapping with other communities are larger than a predefined threshold q is deleted. Then, a close neighbor method, which adds the node to a community with which it has a minimum distance is proposed for dealing with the overlapping nodes among initial communities. Using the same method, add the nodes outside the k initial communities to the corresponding community with which they have minimum distances. Finally, our algorithm on a famous real-word network is evaluated. The result demonstrates that our algorithm can deal with overlapping nodes and nodes outside the initial communities effectively, and can uncover the community structure in networks. Compared with GN algorithm, our algorithm has a higher accuracy and better performance.

star network; community detection; maximal-degree node

10.13877/j.cnki.cn22-1284.2016.08.024

2016-06-06

綏化市2015年科技計劃項目“基于社區(qū)發(fā)現(xiàn)的社交網(wǎng)絡(luò)分析與研究”；綏化學(xué)院青年基金資助項目(KQ1301002)；黑龍江省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目(201610236014)

趙衛(wèi)績，男，山東青島人,講師.

TP311

A

1008-7974(2016)04-0072-04