基于相似度的雙向合并社區(qū)發(fā)現(xiàn)算法研究

陳 晶，萬 云

1(燕山大學 信息科學與工程學院計算機系，河北 秦皇島 066004)2(河北省計算機虛擬技術實驗室，河北 秦皇島 066004)3(河北省軟件工程重點實驗室，河北 秦皇島 066004)

1 引 言

社區(qū)發(fā)現(xiàn)作為社會網(wǎng)絡分析的核心問題之一，其目標是在社會網(wǎng)絡中發(fā)現(xiàn)一個社區(qū)或識別一個節(jié)點的集合，并使得集合內(nèi)節(jié)點間的相互作用比集合間節(jié)點的相互作用強[1].社區(qū)發(fā)現(xiàn)的研究具有很多現(xiàn)實意義和商用價值[2].例如，利用社會關系網(wǎng)絡中的用戶興趣、地域、職業(yè)以及背景等分析所形成的真實社會中的團體，并對團體中的人物進行好友推薦或精準的廣告投放業(yè)務；在生物化學網(wǎng)絡社區(qū)中，應用網(wǎng)絡中某些特定的功能單元可以進行人類基因庫和食物鏈分析、并對蛋白質網(wǎng)絡和新陳代謝網(wǎng)絡進行研究；在引文網(wǎng)絡社區(qū)中，可以依據(jù)主題、作者、單位和內(nèi)容等信息對文章進行搜索與挖掘，并對處理結果進行文章引用次數(shù)及質量分析，以達到對用戶進行文章或內(nèi)容推薦的目的.因此，社區(qū)發(fā)現(xiàn)作為社會網(wǎng)絡分析的基本任務，不僅其研究意義重大，而且也影響著我們的生產(chǎn)及生活方式.

雖然許多學者針對社區(qū)發(fā)現(xiàn)問題從不同的角度給出了實現(xiàn)方案，但在諸多實現(xiàn)方案中，對社區(qū)穩(wěn)定性和社區(qū)結構方面的關注較少.因此，在相關研究成果的基礎上，本文提出了一種基于相似度的雙向合并社區(qū)發(fā)現(xiàn)算法PMCD.算法根據(jù)網(wǎng)絡的相似度定義邊的權重值，將網(wǎng)絡劃分成子社區(qū)；以子社區(qū)作為社區(qū)合并的起點，雙向判斷模塊度值是否均增加至最大來決定是否將子社區(qū)進行合并；對形成的社區(qū)進行社區(qū)結構檢查，避免具有弱結構社區(qū)出現(xiàn).本文的主要貢獻是通過合理地劃分子社區(qū)，減少子社區(qū)的數(shù)目，避免弱結構社區(qū)的出現(xiàn)，從而提高了社區(qū)劃分質量，使其更接近真實網(wǎng)絡的劃分結果.

2 相關工作

社區(qū)發(fā)現(xiàn)問題的研究受到了普遍關注，因此，研究人員從不同的角度提出了相應的算法.Raghavan U N等人提出了基于標簽傳播的社區(qū)發(fā)現(xiàn)算法[3]，該算法的主要思想是為每個節(jié)點分配唯一的標簽，并根據(jù)自己鄰居節(jié)點的標簽不斷更新節(jié)點本身的標簽，直至節(jié)點標簽不再變化.Palla G等人提出了一種發(fā)現(xiàn)重疊社區(qū)的層次聚類算法[4]，該算法的主要思想是發(fā)現(xiàn)網(wǎng)絡中所有的k-團.Newman M等人提出了經(jīng)典的GN算法和模塊度的概念，GN算法通過反復移除具有最大邊介數(shù)的邊，將網(wǎng)絡分裂成社區(qū)，而模塊度的概念被大多數(shù)研究者作為社區(qū)質量的評判標準[5].Clauset A等人提出了一種基于模塊度最優(yōu)化的貪婪算法[6]，這種方法開始將單個節(jié)點作為一個社區(qū)，通過不斷地將邊添加到已有的社區(qū)，使社區(qū)的模塊度增加至最大.

近年來，不少學者在上述研究的基礎上又提出了許多新的算法.Liu W等人基于網(wǎng)絡拓撲結構提出一種新穎的算法來發(fā)現(xiàn)社區(qū)，在該算法中，基于無標度、社區(qū)結構和小世界效應三個屬性定義社區(qū)，將社區(qū)結構分為強結構社區(qū)和弱結構社區(qū)，并以此為基礎研究了社區(qū)發(fā)現(xiàn)過程[7].馬慧芳等人針對傳統(tǒng)微博社區(qū)發(fā)現(xiàn)算法具有重疊度不可控、內(nèi)聚低等問題，對用戶標簽屬性信息進行擴充，提出了基于核心標簽的可重疊微博社區(qū)發(fā)現(xiàn)策略Tag Cut，并對提出的策略在真實的數(shù)據(jù)集中進行了驗證[8].劉冰玉等人針對博文長度受限、傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法無法有效解決微博網(wǎng)絡的稀疏性問題，提出了DC-DTM算法.該算法利用DTM微博主題模型計算節(jié)點之間的權重和語義相似度，進行微博網(wǎng)絡的社區(qū)發(fā)現(xiàn)[9].賀超波等人針對復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)時由于節(jié)點鏈接信息或屬性信息比較單一的特點，提出了一種可集成節(jié)點鏈接和屬性信息進行社區(qū)挖掘的方法LANMF，并通過實際應用驗證了LANMF方法進行社區(qū)挖掘的優(yōu)勢[10].喬少杰等人提出了基于Spark分布式大規(guī)模復雜網(wǎng)絡社區(qū)并行發(fā)現(xiàn)算法DBCS.算法利用模塊度的聚類思想，迭代查找出所有模塊度增量最大的節(jié)點對，并對所提出的算法在不同的數(shù)據(jù)集中進行了運行時間和識別準確性的驗證[11].Niu X Z等人以動態(tài)網(wǎng)絡研究為基礎，考慮社區(qū)的時變特性，提出了基于標簽的多目標優(yōu)化動態(tài)社區(qū)發(fā)現(xiàn)算法，該算法以聚類質量和時間成本作為遺傳算法的優(yōu)化目標，并驗證了所提出的算法在動態(tài)網(wǎng)絡中進行社區(qū)發(fā)現(xiàn)的優(yōu)勢[12].Zhou H F等人基于吸引度和推薦度的概念提出了復雜網(wǎng)絡的社區(qū)結構聚類方法AR，采用協(xié)同相似度計算節(jié)點相似度，并對所提出的AR聚類在真實數(shù)據(jù)集上進行測試[13].Chen Y等人針對重疊社區(qū)發(fā)現(xiàn)提出了一種貝葉斯混合網(wǎng)絡模型BMN，并對加權網(wǎng)絡提出了一種“軟分區(qū)”解決方案[14].

3 基于相似度的雙向合并社區(qū)發(fā)現(xiàn)算法

3.1 算法的相關定義和處理流程

對于給定的網(wǎng)絡，首先，利用社區(qū)的相似度對網(wǎng)絡進行劃分得到子社區(qū)；其次，對子社區(qū)進行雙向合并，直到形成最終社區(qū).本文算法主要分為兩個部分，一是對網(wǎng)絡進行劃分，得到子社區(qū)；二是結合社區(qū)強弱結構雙向合并子社區(qū)，直至形成最終社區(qū).

定義1. 相似度(Similarity measure)處于同一社區(qū)的節(jié)點具有相似性，若兩個節(jié)點擁有共同的鄰居節(jié)點，即使它們之間不相鄰，也認為是相似節(jié)點，并稱為結構相似度.本文采用余弦相似度衡量節(jié)點之間的結構相似性.形式表示如下：

其中Ni和Nj分別是節(jié)點i與節(jié)點j的鄰居節(jié)點集合，|Ni|和|Nj|分別表示鄰居節(jié)點的個數(shù).

定義2. 模塊度公式定義如下：

其中eii表示屬于社區(qū)i中連接節(jié)點之間邊的比例，ai表示連接社區(qū)i中節(jié)點的邊比例.求和表示給定網(wǎng)絡中所有的社區(qū).Q值越大，則對應的劃分結果就越準確.

定義3. 單向合并(Single neighbor merging)對于社區(qū)ci，計算其模塊度Qi，尋找社區(qū)ci的鄰居社區(qū)cj，計算其模塊度Qj，社區(qū)Qi和社區(qū)Qj合并后得到新的模塊度Qm，計算Qm-(Qi+Qj)得到模塊度增量ΔQ，且ΔQ為最大.若ΔQ為正，則合并兩個社區(qū)，該過程稱為單向合并.

定義4. 雙向合并(Pairwise Merging)[15]對于社區(qū)ci，計算其模塊度Qj，尋找社區(qū)ci的鄰居社區(qū)cj，計算其模塊度Qj，社區(qū)Qi和社區(qū)Qj合并后得到新的模塊度Qm，計算Qm-(Qi+Qj)得到模塊度增量ΔQ，且ΔQ為最大.若ΔQ為正，則在ci→cj之間畫一個箭頭，同理，尋找社區(qū)cj的鄰居社區(qū)，使得兩個社區(qū)合并后模塊度增量ΔQ最大.若使得社區(qū)cj的模塊度增量最大的社區(qū)是ci，則在cj→ci之間畫一個箭頭.若存在ci?cj，則合并兩個社區(qū)，該過程稱為雙向合并.

依據(jù)上述定義，本文給出了PMCD算法的處理流程，如圖1所示.

3.2 PMCD算法的描述

根據(jù)算法思想可知，本文算法主要分為3個部分，下面給出了3個算法的主要偽代碼描述.算法1描述了小社區(qū)形成過程的偽代碼；算法2描述了子社區(qū)形成過程的偽代碼；算法3描述了社區(qū)發(fā)現(xiàn)的偽代碼.

算法1. 利用余弦相似度進行網(wǎng)絡劃分

輸入：G=(V，E)

輸出：小社區(qū)集合Pair

(1)For eachv∈Vdo

(2) For each neighboruofvdo

(3)Find friends(u，v)；

(4)Computing Cosine Weight for edge(u，v)；

(5) End for

(6)End for

(7)For each edge e (u，v)Array do

(8) If(e.Cosine!=0)

(9) If(m.extended == false && n.extended == false)

(10) Assign new community label touandv；

(11)Pairu,v={u，v}；

(12) End if

(13) End if

(14) End for

(15) Return Pair；

圖1 PMCD算法處理流程Fig.1 Processing flow of PMCD algorithm

算法2. 對小社區(qū)進行擴展形成子社區(qū)

輸入：節(jié)點集合V

輸出：子社區(qū)subCom

(1)For eachz∈Vdo

(2) If(z.extended == false)

(3) For eachu∈Pair(u,v)do

(4) Computing Cosine weight for(z，u)；

(5) End for

(6) If(cosine weight for(z，u)is max)

(7) subCom=Pair(u,v)∪{z}；

(8) Else if(cosine weight for (z，u) is zero)

(9) single List=single List ∪{z}；

(10) subCom = subCom∪single List；

(11) End if

(12) End if

(13)End for

(14) Return subCom；

算法3. 社區(qū)雙向合并算法

輸入：subCom

輸出：Communities

(1) For eachsubi,∈subCom do

(2) For eachsubj∈subCom do

(3) If(IsPairwiseMerging(subi，subj)==true)

(4) Community=PairwiseMerging(subi，subj)；

(5) Communities=communities ∪ Community；

(6) End if

(7) End for

(8) End for

(9) find neighbor of eachv∈ single List

(10) 判斷eachv∈ single List屬于哪個communities并加入

(11) /*檢查社區(qū)結構，并進行相應的處理*/

(12) For each sub ∈ communities do

(13) 根據(jù)文獻[7]的社區(qū)結構的定義，判斷sub的社區(qū)結構

(14) If the strucutre of sub is weak structure community

(15) 將subCom與其連接緊密的強結構鄰居社區(qū)合并

(16) End if

(17) End for

(18) Return Communities；

算法1中包含節(jié)點相似度計算和小社區(qū)集合Pair形成兩部分.算法2中single List存放的是擴展后尚未被分配社區(qū)的節(jié)點，一般而言，這類節(jié)點的數(shù)目相對較少.將算法2中的single List加入subCom集合進行雙向判斷時，single List中的元素也將一起進行雙向判斷.由于雙向合并的條件嚴格且判斷耗時，本文為了減少計算時間和提高社區(qū)合并質量，利用算法3中的步驟9和10對single List中的元素進行最后處理.其結果是：生成的社區(qū)數(shù)目不會增多，且降低了時間復雜度.算法3中通過對合并后的社區(qū)進行社區(qū)結構的檢查，將出現(xiàn)的弱結構社區(qū)與其鄰居強社區(qū)合并，能夠保證最終獲得強社區(qū)結構，以提高社區(qū)劃分的質量.

3.3 PMCD算法時間復雜度分析

假設網(wǎng)絡G中包含n個節(jié)點和m條邊，PMCD算法分為3個部分，在算法1中，主要是檢查邊所連接的兩個節(jié)點的鄰居集合，利用公式1計算相似度作為邊的權重，w(ei)=k(u)+k(v)，其中k(u)和k(v)分別表示節(jié)點u和v的度，時間復雜度應為O(∑d(vi)).依次取邊，對邊的兩個節(jié)點進行分配社區(qū)，由于不是對所有邊的頂點進行操作，若生成z個小社區(qū)，z∑d(vi)>n，所以算法的時間復雜度為O(zlogn).

4 實驗及結果分析

4.1 實驗數(shù)據(jù)集

實驗分別在跆拳道俱樂部(Karate club)與海豚網(wǎng)絡(Dolphins)、email網(wǎng)絡3個真實網(wǎng)絡數(shù)據(jù)集和LFR基準網(wǎng)絡模擬數(shù)據(jù)集上進行實驗.本文的社區(qū)發(fā)現(xiàn)算法PMCD體現(xiàn)了一種凝聚的思想，通過在算法初始階段產(chǎn)生子社區(qū)，合并子社區(qū)發(fā)現(xiàn)最終社區(qū)，因此，算法產(chǎn)生的子社區(qū)尤為重要.本文在Karate club與Dolphins兩個真實數(shù)據(jù)集上驗證算法的性能，將文獻[15]的社區(qū)發(fā)現(xiàn)算法進行還原，并對兩個算法產(chǎn)生結果進行對比，PMCD算法在Karate club和Dolphins數(shù)據(jù)集上的最終結果分別如圖2和圖3所示，其劃分結果與真實結果一樣.

在Karate club數(shù)據(jù)集上文獻[15]的結果為{[ 20，13，14，1，2，3，4，8，10，12，18，22 ]，[5，6，17，7，11]，[25，29，28，32，26 ]，[16，15，27，24，23，19，9，21，30，33，31，34 ]}4個部分，其中[25，29，28，32，26 ]是1個弱結構社區(qū)；在Dolphins數(shù)據(jù)集上，文獻[15]將網(wǎng)絡劃分成了5個部分，即{[22，36，12，19，24，52，5，30，46，25]，[40，9，21，4，29，37，60]，[15，59，17，47，13，35，38，41，39，53，44，45，50，51，34]，[49，32，6，23，33，8，20，18，26，27，28，57，42，55，2，7，58，10，14，61]，[62，11，56，16，1，48，31，3，54，43]}，其中[49，32，6，23，33，8，20，18，26，27，28，57，42，55，2，7，58，10，14，61]是1個強結構社區(qū)，其余4個社區(qū)均為弱結構社區(qū).

圖2 PMCD算法在Karate數(shù)據(jù)集上的劃分結果Fig.2 Partition results of PMCD algorithm on the Karate data set

從上述實驗結果可知，在文獻[15]中初始階段產(chǎn)生的子社區(qū)主要是由2個節(jié)點或1個節(jié)點構成，而PMCD算法產(chǎn)生的子社區(qū)大小不定，且很少產(chǎn)生由單個節(jié)點構成的子社區(qū).此外，本文以提高社區(qū)結構的穩(wěn)定性為目的，結合社區(qū)結構的概念對兩種算法生成的社區(qū)結果進行分析可知，PMCD算法在3個真實數(shù)據(jù)集上生成的社區(qū)全都是強結構社區(qū)，而文獻[15]中的算法在3個真實數(shù)據(jù)集上都有弱結構社區(qū)生成.

圖3 PMCD算法在Dolphins數(shù)據(jù)集上的劃分結果Fig.3 Partition results of PMCD algorithm on the Dolphins data set

本文在3個真實數(shù)據(jù)集中對生成的子社區(qū)數(shù)目、社區(qū)模塊度進行比較，實驗結果如表1所示.

表1 兩種算法的社區(qū)生產(chǎn)數(shù)量及模塊度比較Table 1 Comparison of the number and modularity of community generated by two algorithms

從表1中可以看出，PMCD算法產(chǎn)生的子社區(qū)數(shù)目相比于文獻[15]中的算法產(chǎn)生的子社區(qū)數(shù)目少.其原因是由于文獻[15]中的算法是將相似度最大的兩個節(jié)點放入同一社區(qū)，其余節(jié)點各自劃分為一個社區(qū)，因此，產(chǎn)生的社區(qū)數(shù)目較多.而PMCD算法是在文獻[15]算法產(chǎn)生的子社區(qū)基礎上繼續(xù)進行相似度計算過程，對子社區(qū)進行擴展，將部分單個節(jié)點加入已分配的社區(qū)中.其目的是為了減少子社區(qū)數(shù)目，增加子社區(qū)中的節(jié)點數(shù).

在表1中設置相同的運行次數(shù)，對生成的社區(qū)模塊度進行比較，多次實驗后會出現(xiàn)如下現(xiàn)象：文獻[15]中的算法與PMCD算法運行相同的次數(shù)，PMCD算法運行了如表1所示的次數(shù)后形成了最終社區(qū)，而文獻[15]中的算法則沒有形成最終的社區(qū)劃分結果.此外，文獻[15]中的算法形成的最終社區(qū)中存在弱結構社區(qū)，而PMCD算法為了確保發(fā)現(xiàn)的社區(qū)都是強結構社區(qū)，將弱結構社區(qū)與強結構社區(qū)合并，這樣合并之后保證了最終的發(fā)現(xiàn)結果都是穩(wěn)定結構的社區(qū).

LFR基準網(wǎng)絡是社區(qū)發(fā)現(xiàn)算法中常用的模擬數(shù)據(jù)集，通過設置不同的參數(shù)可以生成不同類型的網(wǎng)絡.本文利用LFR基準網(wǎng)絡生成5組網(wǎng)絡，前2組設置不同的混合參數(shù)mu，測試算法在不同網(wǎng)絡上生成社區(qū)的質量；后3組改變節(jié)點個數(shù)N，測試算法在網(wǎng)絡規(guī)模變化時的運行時間.LFR網(wǎng)絡中的參數(shù)設置如表2所示.

表2 LFR基準網(wǎng)絡數(shù)據(jù)信息Table 2 Network information of LFR

本文對生成社區(qū)的模塊度和運行時間進行比較，實驗結果如表3所示.

從表3可以看出，在模擬數(shù)據(jù)集上PMCD算法生成的社區(qū)模塊度值優(yōu)于文獻[15]中算法生成的模塊度.其原因是，PMCD采用雙向合并的思想，要求待合并的兩個社區(qū)應保證彼此的模塊度值都增加；而文獻[15]中的算法只需待合并的社區(qū)中任意一個社區(qū)模塊度值增加即可，因此，當兩個社區(qū)合并后存在模塊度變化值小于零的情況，從而降低了社區(qū)的整體模塊度值.從運行時間上分析，PMCD算法的運行時間優(yōu)于文獻[15]中算法的運行時間.在仿真實驗過程中出現(xiàn)如下情況：(1)當網(wǎng)絡節(jié)點數(shù)為5000時，兩種算法的運行時間均存在較大幅度的提升；(2)當網(wǎng)絡節(jié)點數(shù)超過5000時，PMCD算法的運行時間幅度變化相對穩(wěn)定，而文獻[15]中算法的運行時間會隨著節(jié)點數(shù)目的增加呈現(xiàn)出跳躍性增長的趨勢.其原因是由于PMCD算法的運行時間主要消耗在雙向合并過程，合并過程結束后，若存在弱結構社區(qū)，則需要進行有針對性的與強社區(qū)結構合并.因此，合并過程消耗的時間呈現(xiàn)出減少的趨勢，而文獻[15]中算法的運行時間會隨著運行次數(shù)、節(jié)點數(shù)目增多而增加.通過多次實驗可知，文獻[15]算法的運行次數(shù)通常多于PMCD算法的運行次數(shù)，因此算法的運行時間也會增加.

表3 模擬數(shù)據(jù)集上的模塊度與運行時間比較Table 3 Comparison of modularity and run time on LFR data sets

5 結 論

本文提出了基于相似度的雙向合并社區(qū)發(fā)現(xiàn)算法PMCD，該算法基于一種自底向上的思想，考慮社區(qū)的相似度，利用節(jié)點的共同鄰居為節(jié)點間的邊分配權值.從子社區(qū)開始，結合了雙向合并的思想和社區(qū)結構的概念，逐漸合并成大社區(qū)，直至形成最終社區(qū).在實驗初始階段，PMCD算法產(chǎn)生的子社區(qū)數(shù)目明顯減少，從而減少了子社區(qū)合并的次數(shù)，降低時間復雜度.在雙向合并過程中，充分利用了模塊度值的變化過程，因此，最終得到的社區(qū)更符合社區(qū)內(nèi)部連接緊密，社區(qū)之間連接相對稀疏的特點.算法中結合了社區(qū)強弱結構的概念，避免了一些弱結構社區(qū)的出現(xiàn).通過在真實數(shù)據(jù)集和模擬數(shù)據(jù)集上進行驗證，并與其它同類算法進行比較，其結果表明PMCD算法發(fā)現(xiàn)的社區(qū)更接近真實網(wǎng)絡的社區(qū)劃分結果，并且在運行時間以及獲得穩(wěn)定社區(qū)方面具有一定的優(yōu)勢.