張霄宏,吳鳳祥,賈會(huì)梅,羅軍偉

1(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000) 2(河南理工大學(xué) 軟件學(xué)院,河南 焦作 454000) 3(河南中光學(xué)集團(tuán)有限公司,河南 南陽 473003)

0 引 言

現(xiàn)實(shí)世界中的很多系統(tǒng)都能抽象成復(fù)雜網(wǎng)絡(luò)[1].復(fù)雜網(wǎng)絡(luò)往往具有社區(qū)結(jié)構(gòu).同一社區(qū)內(nèi)的節(jié)點(diǎn)連接緊密,不同社區(qū)內(nèi)的節(jié)點(diǎn)連接相對稀疏.研究復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)有助于理解網(wǎng)絡(luò)的功能和特性,具有十分重要的理論和應(yīng)用價(jià)值[2-5].局部社區(qū)發(fā)現(xiàn)算法因不需要了解網(wǎng)絡(luò)的全局信息、時(shí)間復(fù)雜度較低而備受關(guān)注.局部社區(qū)發(fā)現(xiàn)方法可分為局部擴(kuò)展優(yōu)化[6,7]、派系過濾[8,9]、標(biāo)簽傳播[10,11]以及局部邊聚類優(yōu)化[12-14]4類.其中,基于局部擴(kuò)展優(yōu)化的社區(qū)發(fā)現(xiàn)方法不僅能有效揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu),而且劃分結(jié)果穩(wěn)定[15].

基于局部擴(kuò)展優(yōu)化的社區(qū)發(fā)現(xiàn)方法分為種子節(jié)點(diǎn)選取和局部社區(qū)擴(kuò)展兩個(gè)階段.在種子節(jié)點(diǎn)選取階段,可根據(jù)隨機(jī)策略[16]、節(jié)點(diǎn)排名[17,18]以及極大團(tuán)[8,9]等選擇出種子節(jié)點(diǎn).然而如果種子節(jié)點(diǎn)選擇不當(dāng),則會(huì)造成社區(qū)劃分不合理的后果.為了應(yīng)對這一問題,文獻(xiàn)[19-24]提出構(gòu)建種子社區(qū)并從種子社區(qū)開始社區(qū)擴(kuò)展的方法.在社區(qū)擴(kuò)展過程中,現(xiàn)有的方法往往根據(jù)某個(gè)優(yōu)化函數(shù)融合鄰居節(jié)點(diǎn).常見的優(yōu)化函數(shù)有模糊關(guān)系函數(shù)[13]、相關(guān)度函數(shù)[25]、中心度函數(shù)[26]、模塊度函數(shù)[27]、適應(yīng)度函數(shù)[18]等.然而,比起不同社區(qū)中的節(jié)點(diǎn),同一社區(qū)內(nèi)的節(jié)點(diǎn)之間的相似程度更高.上述方法在構(gòu)建種子社區(qū)和進(jìn)行社區(qū)擴(kuò)展的過程中并沒同時(shí)考慮節(jié)點(diǎn)間連接的緊密程度和相似程度,不可避免的會(huì)存在社區(qū)劃分合理性問題.此外,在社區(qū)擴(kuò)展過程中,現(xiàn)有方法往往采用貪婪的策略,逐步融合最優(yōu)的鄰居節(jié)點(diǎn),制約了算法的收斂速度.

針對基于局部擴(kuò)展優(yōu)化的社區(qū)發(fā)現(xiàn)方法在社區(qū)劃分結(jié)果合理性和收斂速度方面存在的問題,本文提出了一種均衡的局部社區(qū)發(fā)現(xiàn)算法,均衡考慮節(jié)點(diǎn)間的相似程度和連接的緊密程度進(jìn)行社區(qū)擴(kuò)展.該算法在選定種子節(jié)點(diǎn)的基礎(chǔ)上,結(jié)合相似程度和連接的緊密程度構(gòu)建種子社區(qū),以種子社區(qū)作為初始社區(qū)以迭代的方式對它進(jìn)行擴(kuò)展,直至收斂.本文的主要貢獻(xiàn)有以下幾點(diǎn):

1)本文提出了一種種子社區(qū)構(gòu)建算法,該算法根據(jù)種子節(jié)點(diǎn)及其連通節(jié)點(diǎn)之間的相似程度和連接緊密程度構(gòu)建種子社區(qū),保證了種子社區(qū)的質(zhì)量,提升了社區(qū)劃分的合理性.

2)本文提出了一種兩級節(jié)點(diǎn)篩選機(jī)制,該機(jī)制均衡考慮相似程度和連接緊密程度篩選最適宜與社區(qū)合并的節(jié)點(diǎn),緩解了因合并不恰當(dāng)節(jié)點(diǎn)造成的社區(qū)劃分不合理問題.

3)本文提出了一種寬容的節(jié)點(diǎn)合并策略,可以在一次迭代中將多個(gè)節(jié)點(diǎn)合并到社區(qū),提高了社區(qū)擴(kuò)展過程的收斂速度.

1 問題分析

在本文中,復(fù)雜網(wǎng)絡(luò)用無向無權(quán)圖G=(V,E)來表示.V為節(jié)點(diǎn)集合,且V={vi|i=1,2,…,n},n為節(jié)點(diǎn)總數(shù);E為邊集合,且E={(vi,vj)|vi∈V,vj∈Vandi≠j}.

基于局部擴(kuò)展優(yōu)化的社區(qū)發(fā)現(xiàn)方法首先按照一定的策略選擇種子節(jié)點(diǎn),然后從種子節(jié)點(diǎn)出發(fā),根據(jù)預(yù)先定義的優(yōu)化函數(shù)以迭代的方式融合鄰居節(jié)點(diǎn),直至收斂,形成社區(qū).然而,如果種子節(jié)點(diǎn)選擇不當(dāng),將會(huì)降低社區(qū)劃分結(jié)果的合理性.針對這一問題,有學(xué)者提出在種子節(jié)點(diǎn)的基礎(chǔ)上構(gòu)建種子社區(qū),從種子社區(qū)出發(fā)進(jìn)行社區(qū)擴(kuò)展.而社區(qū)具有社區(qū)內(nèi)部的節(jié)點(diǎn)連接緊密,而社區(qū)之間的節(jié)點(diǎn)連接相對稀疏的特點(diǎn).比起不同社區(qū)中的節(jié)點(diǎn),同一社區(qū)內(nèi)的節(jié)點(diǎn)更加相似.現(xiàn)有的方法在構(gòu)建種子社區(qū)以及社區(qū)擴(kuò)展過程中并沒有從社區(qū)的角度出發(fā),同時(shí)考慮社區(qū)內(nèi)部節(jié)點(diǎn)連接的緊密性和節(jié)點(diǎn)間的相似性,因而不可避免的會(huì)出現(xiàn)社區(qū)劃分結(jié)果不合理的問題.

此處,以社區(qū)擴(kuò)展過程為例說明在只考慮社區(qū)內(nèi)部節(jié)點(diǎn)連接的緊密程度或者節(jié)點(diǎn)間的相似程度單個(gè)因素的情況下社區(qū)劃分結(jié)果的不合理問題.在只考慮社區(qū)內(nèi)部節(jié)點(diǎn)間相似程度的情況下,社區(qū)的劃分結(jié)果如圖1(a)所示.在這個(gè)劃分結(jié)果中,盡管v0和vs與v1,v2,v3,v4連接緊密,但是卻被劃分到不同的社區(qū).在只考慮社區(qū)內(nèi)部節(jié)點(diǎn)間連接緊密程度的情況下,社區(qū)的劃分結(jié)果如圖1(b)所示.盡管v6與v7,v8,v9,v10,v11連接緊密,但是卻被劃分到不同的社區(qū).上述這兩種劃分結(jié)果顯然是不合理的.

圖1 社區(qū)劃分分析Fig.1 Analysis of the community division

貪婪擴(kuò)展是最常用的一種社區(qū)擴(kuò)展方法,它以迭代的方式將優(yōu)化函數(shù)最優(yōu)值對應(yīng)的節(jié)點(diǎn)并入當(dāng)前社區(qū).假設(shè)優(yōu)化函數(shù)最優(yōu)值對應(yīng)的節(jié)點(diǎn)只有一個(gè),以圖2(a)所示的網(wǎng)絡(luò)為例,則要經(jīng)過5輪迭代社區(qū)擴(kuò)展過程才能收斂.以圖2(b)所示,如果在每輪迭代中可以合并多個(gè)節(jié)點(diǎn),則經(jīng)過2輪即可收斂.顯然,每次只合并優(yōu)化函數(shù)最優(yōu)值對應(yīng)的節(jié)點(diǎn)會(huì)制約社區(qū)擴(kuò)展過程的收斂速度.

圖2 迭代次數(shù)分析(Ci表示第i輪迭代生成的社區(qū))Fig.2 Analysis of iterations( Ci represents the community generated by i round iteration)

2 均衡相似程度和緊密程度的局部社區(qū)發(fā)現(xiàn)算法

針對基于局部擴(kuò)展優(yōu)化的社區(qū)發(fā)現(xiàn)方法在社區(qū)劃分結(jié)果合理性和收斂速度方面存在的問題,本文提出了一種新的局部社區(qū)發(fā)現(xiàn)算法,通過均衡考慮節(jié)點(diǎn)間的相似程度和連接的緊密程度進(jìn)行社區(qū)擴(kuò)展.該算法在選定種子節(jié)點(diǎn)后,首先結(jié)合相似程度和連接的緊密程度構(gòu)建種子社區(qū),然后以種子社區(qū)作為初始社區(qū)以迭代的方式進(jìn)行擴(kuò)展,直至收斂.在擴(kuò)展過程中,提出了節(jié)點(diǎn)的兩級篩選機(jī)制,利用該機(jī)制將在相似程度和連接緊密程度兩方面優(yōu)勢均衡的節(jié)點(diǎn)作為最佳的節(jié)點(diǎn),合并到當(dāng)前社區(qū),以提高社區(qū)劃分結(jié)果的合理性.兩級篩選機(jī)制允許在一次迭代過程中合并多個(gè)節(jié)點(diǎn),以提高社區(qū)擴(kuò)展的收斂速度.

2.1 種子社區(qū)生成

本文方法擬通過同時(shí)考慮節(jié)點(diǎn)間的相似程度和連接的緊密程度構(gòu)建種子社區(qū),來消除由種子節(jié)點(diǎn)選擇不當(dāng)引起的社區(qū)劃分結(jié)果不合理問題.在構(gòu)建種子社區(qū)時(shí),首先要計(jì)算種子節(jié)點(diǎn)與其連通節(jié)點(diǎn)的相似程度和連接的緊密程度.根據(jù)“物以類聚,人以群分”的道理,本文從鄰居節(jié)點(diǎn)的角度衡量某個(gè)節(jié)點(diǎn)與種子節(jié)點(diǎn)間的相似程度.具體來講,本文認(rèn)為兩個(gè)節(jié)點(diǎn)擁有的共同鄰居越多,這兩個(gè)節(jié)點(diǎn)越相似,反之亦然.基于此,本文引入了式(1)計(jì)算節(jié)點(diǎn)的相似程度.在該式中,v表示種子節(jié)點(diǎn),v1表示v的某個(gè)連通節(jié)點(diǎn),ds(vi,v)表示vi和v的相似程度,N(vi)和N(v)分別表示vi和v的鄰居節(jié)點(diǎn)集合.

(1)

種子社區(qū)的構(gòu)建過程就是種子節(jié)點(diǎn)不斷地與其連通節(jié)點(diǎn)合并的過程.在種子節(jié)點(diǎn)和某個(gè)節(jié)點(diǎn)合并后,種子節(jié)點(diǎn)和已合并節(jié)點(diǎn)就構(gòu)成了一個(gè)整體.在后續(xù)節(jié)點(diǎn)的合并過程中,只考慮和種子節(jié)點(diǎn)的相似程度是不合理的,應(yīng)當(dāng)考慮和這個(gè)整體的相似程度.為便于計(jì)算和這個(gè)整體的相似程度,引入了超級節(jié)點(diǎn)來描述這個(gè)整體.

定義1.超級節(jié)點(diǎn):種子節(jié)點(diǎn)和某個(gè)或者某些節(jié)點(diǎn)合并后,由這些節(jié)點(diǎn)和這些節(jié)點(diǎn)間的連邊構(gòu)成的子圖稱為種子社區(qū)構(gòu)建過程中的超級節(jié)點(diǎn).

引入超級節(jié)點(diǎn)后,從超級節(jié)點(diǎn)外部連接到超級節(jié)點(diǎn)內(nèi)部某個(gè)節(jié)點(diǎn)的邊,最后要變換為連接到超級節(jié)點(diǎn)的邊.某個(gè)節(jié)點(diǎn)和超級節(jié)點(diǎn)間的相似程度仍然可以用式(1)計(jì)算,只需要用超級節(jié)點(diǎn)替換公式中的種子節(jié)點(diǎn),用超級節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合替代公式中種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合.對于超級節(jié)點(diǎn)包含的各個(gè)節(jié)點(diǎn),其鄰居節(jié)點(diǎn)有可能在超級節(jié)點(diǎn)內(nèi)部,也有可能在超級節(jié)點(diǎn)外部.超級節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合由在超級節(jié)點(diǎn)外部的這些鄰居節(jié)點(diǎn)構(gòu)成.

在構(gòu)建種子社區(qū)的過程中,除了考慮相似程度,還應(yīng)當(dāng)考慮緊密程度.本文認(rèn)為,節(jié)點(diǎn)間的連邊越多,它們之間的連接越緊密.故而,從節(jié)點(diǎn)間的連邊入手衡量節(jié)點(diǎn)間的連接緊密程度.給定節(jié)點(diǎn)v′,?vi∈V,且v′≠vi,記dc(vi,v′)表示v1和v′之間連接的緊密程度,由式(2)計(jì)算.在該式中,V′表示超級節(jié)點(diǎn)中各節(jié)點(diǎn)構(gòu)成的集合.

(2)

為了能同時(shí)根據(jù)節(jié)點(diǎn)間的相似程度和連接的緊密程度構(gòu)建種子社區(qū),引入了J因子,從相似程度和連接的緊密程度兩個(gè)角度度量某個(gè)節(jié)點(diǎn)適宜加入種子社區(qū)的程度,也就是適宜與種子節(jié)點(diǎn)或者超級節(jié)點(diǎn)合并的程度.?vi∈V,vi與種子節(jié)點(diǎn)或超級節(jié)點(diǎn)v′的J因子根據(jù)式(3)計(jì)算.J因子越大,越適宜與種子節(jié)點(diǎn)或者超級節(jié)點(diǎn)合并.

J(vi,v′)=dc(vi,v′)·ds(vi,v′)

(3)

在構(gòu)建種子社區(qū)時(shí),只根據(jù)J因子決定是否將一個(gè)節(jié)點(diǎn)與種子合并.根據(jù)影響力傳播的三度分割原理,在所有的連通節(jié)點(diǎn)中,一個(gè)節(jié)點(diǎn)和它三跳范圍內(nèi)連通的節(jié)點(diǎn)關(guān)系更為密切.基于此,本文方法只考慮與種子節(jié)點(diǎn)的距離不超過三跳的連通節(jié)點(diǎn).在構(gòu)建種子社區(qū)的具體過程中,按照與種子節(jié)點(diǎn)的距離依次遍歷這些連通節(jié)點(diǎn).在第1輪遍歷中,只訪問與種子節(jié)點(diǎn)距離為一跳的各連通節(jié)點(diǎn),分別計(jì)算各連通節(jié)點(diǎn)與種子節(jié)點(diǎn)的J因子,將最大J因子對應(yīng)的節(jié)點(diǎn)與種子節(jié)點(diǎn)合并,形成超級節(jié)點(diǎn).在第2輪和第3輪遍歷中,分別訪問與種子節(jié)點(diǎn)距離為二跳和三跳的各連通節(jié)點(diǎn),分別計(jì)算這些連通節(jié)點(diǎn)與對應(yīng)超級節(jié)點(diǎn)的J因子,將J因子最大的節(jié)點(diǎn)與超級節(jié)點(diǎn)合并.

超級節(jié)點(diǎn)最終演變?yōu)榉N子社區(qū).超級節(jié)點(diǎn)形成后,可能會(huì)出現(xiàn)某個(gè)連通節(jié)點(diǎn)與超級節(jié)點(diǎn)的因子大于該節(jié)點(diǎn)與種子節(jié)點(diǎn)的J因子.鑒于這一情況,在第2輪和第3輪遍歷中應(yīng)考慮超級節(jié)點(diǎn)的鄰居節(jié)點(diǎn),即與超級節(jié)點(diǎn)有直接連邊的節(jié)點(diǎn).綜上,本文方法構(gòu)建種子社區(qū)的過程如算法1所述.

算法1.種子社區(qū)構(gòu)建

輸入：網(wǎng)絡(luò)G=(V,E),種子節(jié)點(diǎn)seed

輸出：種子社區(qū)Cseeds

1.Vseeds={seed}

2.h←1,Δ←3

3.whileh≤Δ

4.rnodes←與種子節(jié)點(diǎn)距離為h的連通節(jié)點(diǎn);

5.If(h==1)

6.計(jì)算rnodes中各節(jié)點(diǎn)與seed的J因子

7.最大J因子對應(yīng)的節(jié)點(diǎn)與種子節(jié)點(diǎn)合并生成超級節(jié)點(diǎn)

8.else

9.neinodes←獲取當(dāng)前超級節(jié)點(diǎn)的鄰居節(jié)點(diǎn)

10.將僅在neinodes中出現(xiàn)的節(jié)點(diǎn)加入rnodes

11.計(jì)算rnodes中各節(jié)點(diǎn)與當(dāng)前超級節(jié)點(diǎn)的J因子

12.將最大J因子對應(yīng)的節(jié)點(diǎn)加入超級節(jié)點(diǎn)

13.end if

14.End while

15.ReturnCseeds

2.2 第1級節(jié)點(diǎn)篩選

為了在社區(qū)擴(kuò)展過程中同時(shí)考慮節(jié)點(diǎn)與社區(qū)間的相似程度和連接的緊密程度,本文根據(jù)前文定義的因子逐步合并鄰居節(jié)點(diǎn)直至收斂.如果一個(gè)節(jié)點(diǎn)是社區(qū)內(nèi)部的節(jié)點(diǎn),它的所有鄰居節(jié)點(diǎn)都在社區(qū)內(nèi)部.如果是社區(qū)的邊界節(jié)點(diǎn),它的一部分鄰居節(jié)點(diǎn)在社區(qū)內(nèi)部,另一部分鄰居節(jié)點(diǎn)則在其它社區(qū).在進(jìn)行社區(qū)擴(kuò)展時(shí),應(yīng)盡量避免合并可能是邊界的節(jié)點(diǎn).因此,在進(jìn)行社區(qū)擴(kuò)展時(shí)沒有必要去嘗試合并每個(gè)鄰居節(jié)點(diǎn).基于此,本文引入了對節(jié)點(diǎn)的第1級篩選.

第1級篩選的目標(biāo)是將大概率不屬于給定社區(qū)的節(jié)點(diǎn)排除在給定社區(qū)可能合并的節(jié)點(diǎn)范圍之外.為了達(dá)到這一目的,引入了歸屬度,利用歸屬度來判斷某個(gè)鄰居節(jié)點(diǎn)屬于給定社區(qū)的概率.?vi∈V,vi相對于給定社區(qū)的歸屬度記為db(vi,C),根據(jù)式(4)計(jì)算.在該式中,Vc表示社區(qū)C的節(jié)點(diǎn)集合.當(dāng)db(vi,C)的值大于等于給定閾值θb時(shí),認(rèn)為vi可能屬于社區(qū)C;否則,認(rèn)為vi不可能屬于社區(qū)C.

(4)

Vmerge(C)={vi|vi∈N(C) anddb(vi,C)≥θb}

(5)

在節(jié)點(diǎn)歸屬度的基礎(chǔ)上,引入了可合并節(jié)點(diǎn)集合.在迭代擴(kuò)展過程中,社區(qū)只能融合可合并節(jié)點(diǎn)集合中的節(jié)點(diǎn).記給定社區(qū)C的可合并節(jié)點(diǎn)集合為Vmerge(C),由式(5)表示.在該式中,N(C)為社區(qū)C的鄰居節(jié)點(diǎn)集合.由式(5)中的條件db(vi,C)≥θb可知,不可能屬于社區(qū)C的節(jié)點(diǎn)被排除在可合并節(jié)點(diǎn)集合之外,從而實(shí)現(xiàn)了第1級篩選的目標(biāo).算法2展示了可合并節(jié)點(diǎn)集合的構(gòu)建過程.

算法2.可合并節(jié)點(diǎn)集合

輸入：網(wǎng)絡(luò)G=(V,E),當(dāng)前正在擴(kuò)展社區(qū)C,閾值θb

輸出：可合并節(jié)點(diǎn)集合Vmerge

1.Vmerge=?

2.neinodes←C的鄰居節(jié)點(diǎn)

3.for eachnodeinneinodes

4.計(jì)算db(node,C)

5.ifdb(vi,C)≥θb

6.Vmetge=Vmerge∪{node}

7.end if

8.end for

9.ReturnVmetge

2.3 第2級節(jié)點(diǎn)篩選

為了能根據(jù)節(jié)點(diǎn)間的相似程度和連接的緊密程度劃分社區(qū),本文方法在社區(qū)擴(kuò)展過程中仍根據(jù)J因子來選擇可以合并的節(jié)點(diǎn).在社區(qū)擴(kuò)展過程中,J因子由節(jié)點(diǎn)和社區(qū)的相似程度以及節(jié)點(diǎn)與社區(qū)連接的緊密程度共同決定.?vi∈V,vcur表示正在擴(kuò)展的社區(qū)Ccur對應(yīng)的超級節(jié)點(diǎn).在ds(vi,vcur)較小,也就是vj與當(dāng)前擴(kuò)展社區(qū)相似度較低的情況下,如果dc(vj,ccur)足夠大,也就是vj與當(dāng)前社區(qū)連接的緊密程度足夠大,那么J(vj,ccur)也較大,從而使得vj與當(dāng)前擴(kuò)展社區(qū)合并.在dc(vj,vcur)較小的情況下,如果ds(vj,vcur)足夠大,也會(huì)使得vj與當(dāng)前社區(qū)擴(kuò)展社區(qū)合并.前一種情況相當(dāng)于在社區(qū)合并過程中過于強(qiáng)調(diào)緊密度,后一種情況則相當(dāng)于過于強(qiáng)調(diào)相似度.

這兩種情況都與本文均衡考慮相似程度和連接緊密程度的初衷相悖.基于此,本文提出了第2級節(jié)點(diǎn)篩選.第2級節(jié)點(diǎn)篩選的目標(biāo)是從可合并節(jié)點(diǎn)集合中篩選出上述兩種情況涉及到的節(jié)點(diǎn),將它們從可合并節(jié)點(diǎn)集合中刪除,并從可合并節(jié)點(diǎn)集合中選擇相似程度和連接緊密程度都能兼顧的節(jié)點(diǎn),也就是相似程度和連接緊密程度均衡的節(jié)點(diǎn),合并到當(dāng)前社區(qū).基于此,本文引入了以下均衡性判定策略:

按照均衡性判定策略1-2對Vmerge(C)的節(jié)點(diǎn)進(jìn)行篩選后,Vmerge(C)中保留的節(jié)點(diǎn)就是相似程度和連接緊密程度均衡的節(jié)點(diǎn).為了提高社區(qū)擴(kuò)展過程的收斂速度,本文引入了如下的合并策略.該策略通過允許在一輪迭代中合并滿足條件的多個(gè)節(jié)點(diǎn),來提升合并過程的收斂速度.

通過執(zhí)行均衡性判定策略1-2可以保證將相似程度和連接緊密程度都比較高的節(jié)點(diǎn)合并到當(dāng)前擴(kuò)展社區(qū),可以實(shí)現(xiàn)第2級篩選的目標(biāo).貪婪策略在每輪迭代擴(kuò)展過程中只合并優(yōu)化函數(shù)最大值對應(yīng)的節(jié)點(diǎn),限制了算法的收斂速度.與貪婪策略不同,本文提出的合并策略在每輪迭代過程中將滿足合并條件的多個(gè)節(jié)點(diǎn)都合并到當(dāng)前社區(qū)中,以此來加快社區(qū)擴(kuò)展過程的收斂速度.根據(jù)上述策略,本文方法擴(kuò)展社區(qū)的過程如算法3所示.

算法3.社區(qū)擴(kuò)展

輸入：網(wǎng)絡(luò)G=(V,E),種子節(jié)點(diǎn)Seed

輸出：局部社區(qū)Ccur

1.Ccur←Cseeds

2.Vcda←為Ccur創(chuàng)建可合并節(jié)點(diǎn)集合

3.Jsum=0

4.WhileVcda≠?

5.dcresults←計(jì)算Vcda中每個(gè)節(jié)點(diǎn)與Ccur的緊密度

6.dsresults←計(jì)算Vcda中每個(gè)節(jié)點(diǎn)與Ccur的相似度

7.dsave←計(jì)算平均相似程度

8.dsave←計(jì)算平均緊密程度

9.for eachnodainVcda

10.Ifds(node,vcur)

11.從Vcda中刪除node

12.else

13.計(jì)算node與ccur的J因子

14.Jsum←node與Ccur的J因子+Jsum

15.End if

16. End for

17. IfVcda!=?

18.Jave←計(jì)算Vcda節(jié)點(diǎn)與Ccur的J因子平均值

19.else

20. break

21. for eachnodeinVcda

22.ifJ(node,vcur)≥Jave

23.將node合并到Ccur

24.End if

25. End for

26.Vcda←為Ccur創(chuàng)建可合并節(jié)點(diǎn)集合

27.End while

28.ReturnCcur

2.4 算法復(fù)雜度分析

假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度為d,算法迭代t次檢測完整社區(qū).本文算法主要分為種子社區(qū)生成和種子社區(qū)擴(kuò)展兩個(gè)階段.在種子社區(qū)生成階段,假設(shè)超級節(jié)點(diǎn)的鄰接節(jié)點(diǎn)在種子節(jié)點(diǎn)三跳之內(nèi)的節(jié)點(diǎn)個(gè)數(shù)為q,當(dāng)h為1時(shí)計(jì)算給定種子節(jié)點(diǎn)與鄰接節(jié)點(diǎn)的J因子值的時(shí)間復(fù)雜度為O(d);當(dāng)h不為1時(shí)計(jì)算超級節(jié)點(diǎn)和其符合條件鄰居節(jié)點(diǎn)的J因子值的時(shí)間復(fù)雜度為O(q).因此,種子社區(qū)生成的時(shí)間復(fù)雜度為O(d+q).在種子社區(qū)擴(kuò)展階段,引入節(jié)點(diǎn)兩級節(jié)點(diǎn)篩選機(jī)制.在第1級種子節(jié)點(diǎn)篩選,根據(jù)歸屬度篩選社區(qū)的鄰居節(jié)點(diǎn),假設(shè)社區(qū)的平均鄰接節(jié)點(diǎn)個(gè)數(shù)為m,則第1級節(jié)點(diǎn)篩選的時(shí)間復(fù)雜度為O(m);假設(shè)經(jīng)過第1級節(jié)點(diǎn)篩選,可合并節(jié)點(diǎn)集合中的節(jié)點(diǎn)個(gè)數(shù)為k,則在第2級節(jié)點(diǎn)篩選階段中,計(jì)算可合并節(jié)點(diǎn)集合中各個(gè)節(jié)點(diǎn)與當(dāng)前計(jì)算社區(qū)相似程度和連接緊密程度的時(shí)間復(fù)雜度都為O(k),按照均衡判定策略篩選遍歷各個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(k).假設(shè)按照均衡判定策略篩選后可合并節(jié)點(diǎn)集合的節(jié)點(diǎn)個(gè)數(shù)為n,按合并策略遍歷該集合中節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n),篩選滿足融合社區(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n).由于滿足合并策略的節(jié)點(diǎn)屬于可合并候選集k≥n,即,則第2級種子節(jié)點(diǎn)篩選的時(shí)間復(fù)雜度為O(k).因此,種子社區(qū)擴(kuò)展階段的時(shí)間復(fù)雜度為O(m+k).綜上所述,本文算法的時(shí)間復(fù)雜度約為O(t(d+q+k+m)).

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

為了驗(yàn)證本文算法的正確性和有效性,在多個(gè)真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上與LCDMD算法[16]、LCDFSR算法[28]、MULTICOM算法[29]、MLC算法[30]進(jìn)行了對比實(shí)驗(yàn).實(shí)驗(yàn)中用到的操作系統(tǒng)為行Win10,處理器為Intel(R)Pentium(R)CPU G4600 @ 3.60GHz,內(nèi)存容量為16GB.所有算法由python語言實(shí)現(xiàn).

3.1 實(shí)驗(yàn)數(shù)據(jù)

在實(shí)驗(yàn)過程中選取了6個(gè)真實(shí)數(shù)據(jù)集和9個(gè)人工數(shù)據(jù)集,這些數(shù)據(jù)集的社區(qū)結(jié)構(gòu)都是已知的.

1)真實(shí)數(shù)據(jù)集

Karate網(wǎng)絡(luò)[31]是根據(jù)一個(gè)空手道俱樂部成員間的關(guān)系創(chuàng)建的社交網(wǎng)絡(luò),包含34個(gè)節(jié)點(diǎn)和78條邊,共分成2個(gè)社區(qū).Dolphins網(wǎng)絡(luò)[32]由海豚之間交互行為構(gòu)成的社交網(wǎng)絡(luò),包含62個(gè)節(jié)點(diǎn)和159條邊,共分成2個(gè)社區(qū);Polbooks網(wǎng)絡(luò)[33]是根據(jù)美國政治書籍網(wǎng)絡(luò),包含105個(gè)節(jié)點(diǎn)和441條邊,共分成3個(gè)社區(qū);Football網(wǎng)絡(luò)[34]是根據(jù)足球比賽構(gòu)建的網(wǎng)絡(luò),包含115個(gè)節(jié)點(diǎn)和616條邊,共分成12個(gè)社區(qū);DBLP網(wǎng)絡(luò)[35]是一個(gè)科學(xué)家合作網(wǎng)絡(luò),該網(wǎng)絡(luò)包含317080個(gè)節(jié)點(diǎn)和1049866條邊,共分成13477個(gè)社區(qū);亞馬遜網(wǎng)絡(luò)[35]是一個(gè)關(guān)于在亞馬遜網(wǎng)站上銷售產(chǎn)品的網(wǎng)絡(luò),該網(wǎng)絡(luò)有334863個(gè)節(jié)點(diǎn)和925872條邊,共分成75149個(gè)社區(qū).

2)人工數(shù)據(jù)集

人工數(shù)據(jù)集根據(jù)Lancichinetti等人[36]提出的LFR基準(zhǔn)網(wǎng)絡(luò)生成.在生成過程中,參數(shù)配置如下:N=10000,k=17,maxk=3,minc=20,maxc=70,μ從0.1開始取值,每次遞增0.05,直到μ=0.5,共生成9個(gè)人工網(wǎng)絡(luò).μ值越大,給對應(yīng)網(wǎng)絡(luò)劃分社區(qū)的難度越大.故而,在實(shí)驗(yàn)中μ的最大值只取到0.5.

由于Karate、Dolphins、Polbooks、Football和人工網(wǎng)絡(luò)數(shù)據(jù)集中包含的節(jié)點(diǎn)數(shù)較少,在實(shí)驗(yàn)過程中將這些數(shù)據(jù)集中的每一個(gè)節(jié)點(diǎn)都視作種子節(jié)點(diǎn),分別從各個(gè)種子節(jié)點(diǎn)出發(fā)進(jìn)行社區(qū)劃分.而DBLP和Amazon數(shù)據(jù)集中包含的節(jié)點(diǎn)數(shù)較多,在實(shí)驗(yàn)過程中隨機(jī)從每個(gè)數(shù)據(jù)集中選取10000個(gè)不同的節(jié)點(diǎn)作為種子節(jié)點(diǎn),分別從每個(gè)種子出發(fā)進(jìn)行社區(qū)劃分.

3.2 評價(jià)指標(biāo)

本文采用調(diào)和均值F-Score[15]作為評價(jià)指標(biāo),來評估本文方法的正確性和有效性,這個(gè)指標(biāo)根據(jù)式(6)計(jì)算.在式(6)中,Precision是查準(zhǔn)率,表示被正確劃分的節(jié)點(diǎn)占所有實(shí)際劃分節(jié)點(diǎn)的比例;Recall是查全率,表示被正確劃分的節(jié)點(diǎn)占真實(shí)劃分節(jié)點(diǎn)的比例.Precision和Recall分別根據(jù)式(7)和式(8)來計(jì)算.在式(7)和式(8)中,CT表示由種子節(jié)點(diǎn)所屬真實(shí)社區(qū)中節(jié)點(diǎn)構(gòu)成的集合,CF表示由算法檢測出的種子節(jié)點(diǎn)所屬社區(qū)節(jié)點(diǎn)構(gòu)成的集合.

(6)

(7)

(8)

3.3 實(shí)驗(yàn)參數(shù)

本文方法在第1級節(jié)點(diǎn)篩選過程中需要計(jì)算各鄰居節(jié)點(diǎn)相對于給定社區(qū)的歸屬度,根據(jù)計(jì)算結(jié)果和預(yù)設(shè)的閾值θb把大概率不屬于給定社區(qū)的鄰接節(jié)點(diǎn)排除在外.本文通過實(shí)驗(yàn)的方法設(shè)置θb的取值.令θb從0.1開始取值,每次遞增0.1,共取9個(gè)不同的值.分別在θb取不同值時(shí),對各個(gè)數(shù)據(jù)集進(jìn)行社區(qū)劃分,并根據(jù)劃分結(jié)果計(jì)算θb取不同值時(shí)算法在不同數(shù)據(jù)集上的F-Score平均值,結(jié)果如圖3和圖4所示.綜合考慮各個(gè)數(shù)據(jù)集上的結(jié)果,在本次實(shí)驗(yàn)中θb的值設(shè)置為0.4.

圖3 θb取不同值時(shí)本文方法在真實(shí)數(shù)據(jù)集上的結(jié)果Fig.3 Experimental results with different values of θb on the real datasets

圖4 θb取不同值時(shí)本文方法在人工數(shù)據(jù)集上的結(jié)果Fig.4 Experimental results with different values of θb on the artificial datasets

3.4 真實(shí)數(shù)據(jù)集上的對比實(shí)驗(yàn)與分析

圖5展示了各算法在真實(shí)數(shù)據(jù)集上的對比結(jié)果.圖5(a)展示的是各算法Precision指標(biāo)平均值的對比結(jié)果.由此圖可知,本文算法在Karate、Polbooks、Football和Amazon數(shù)據(jù)集上的Precision指標(biāo)平均值在所有算法中是最高的,在Dolphins和DBLP數(shù)據(jù)集上的Precision指標(biāo)平均值僅分別高于LCDFSR算法和MLC算法.

圖5 在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.5 Experimental results on the real datasets

圖5(b)展示的是各算法Recall指標(biāo)平均值的對比結(jié)果.由此圖可知,本文算法在Dolphins、DBLP和Amazon數(shù)據(jù)集上的Recall指標(biāo)平均值在所有算法中是最高的,在Polbooks數(shù)據(jù)集上的Recall指標(biāo)平均值僅次于LCDFSR算法,在Karate數(shù)據(jù)集上的Recall指標(biāo)平均值高于LCDMD算法和MULTICOM算法,在Football數(shù)據(jù)集上的Recall指標(biāo)平均值高于LCDMD算法和MLC算法.

表1展示了各算法在真實(shí)數(shù)據(jù)集上F-Score指標(biāo)的平均值,最高的F-Score值用粗體顯示,次高的F-Score值加下劃線顯示.由此表可知,本文算法的F-Score指標(biāo)平均值均高于4種對比算法.在從Karate到Amazon的6個(gè)數(shù)據(jù)集上,本文算法的F-Score值相比于次高的F-Score值分別提高了2.13%、3.42%、6.86%、2.12%、3.35%以及7.94%.

表1 算法在真實(shí)數(shù)據(jù)集上的F-Score指標(biāo)對比結(jié)果Table 1 F-Score metrics comparison results of algorithm on real datasets

圖6展示各算法在真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間.由圖可知,本文算法的運(yùn)行時(shí)間明顯低于各對比算法.由于DBLP數(shù)據(jù)集和Amazon數(shù)據(jù)集規(guī)模較大,各算法在這兩個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間遠(yuǎn)大于在其它4個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間.考慮到篇幅和圖形的美觀,設(shè)置了斷層.

圖6 不同算法在真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間Fig.6 Running time of different algorithms on real datasets

3.5 人工數(shù)據(jù)集上的對比實(shí)驗(yàn)與分析

圖7展示了各算法在人工數(shù)據(jù)集上的對比結(jié)果.圖7(a)展示的是各算法Precision指標(biāo)平均值的對比結(jié)果.由此圖可知,本文算法和LCDFSR算法的Precision指標(biāo)平均值要高于其它3個(gè)對比算法.在μ值分別為0.25、0.4和0.5時(shí),本文算法的Precision指標(biāo)平均值略低于LCDFSR算法;在μ取其它6個(gè)值的情況下,本文算法的Precision指標(biāo)平均值與LCDFSR算法持平.

圖7 在人工數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.7 Experimental results on the artificial datasets

圖7(b)展示的是各算法Recall指標(biāo)平均值的對比結(jié)果.由此圖可知,本文算法的Recall指標(biāo)平均值僅在μ值分別為0.45和0.5兩種情況下略低于MULTICOM算法;在μ取其它7個(gè)值的情況下,本文算法的Recall指標(biāo)平均值均高于所有對比算法.

表2展示了各算法在人工數(shù)據(jù)集上F-Score指標(biāo)的平均值,最高的F-Score值用粗體顯示,次高F-Score值加下劃線顯示.由此表可知,本文算法的F-Score指標(biāo)平均值均高于4種對比算法.在4個(gè)對比算法中,LCDMD算法在值分別為0.4、0.45和0.5時(shí)相對于其他3個(gè)算法表現(xiàn)最好,在取其他6個(gè)值時(shí),LCDFSR算法相對于其他3個(gè)算法表現(xiàn)最好.本文算法在取前6個(gè)值時(shí)的F-Score指標(biāo)平均值相對于LCDFSR算法分別提高了0.77%、3.07%、6.67%、7.90%、8.71%和20.37%,在取后3個(gè)值時(shí)的F-Score指標(biāo)平均值相對于LCDMD算法分別提高了21.51%、19.47%和20.70%.圖8展示了各算法在人工數(shù)據(jù)集上的運(yùn)行時(shí)間.由圖可知,與LCDMD算法、MULTICOM算法和MLC算法相比,本文算法的運(yùn)行時(shí)間更短.與LCDFSR算法相比,本文算法的運(yùn)行時(shí)間則略長.但考慮到本文算法的F-Score值要明顯高于LCDFSR算法,而且在值增大的過程中,LCDFSR算法的F-Score值下降劇烈,而本文算法則表現(xiàn)較為平穩(wěn),故認(rèn)為本文算法更優(yōu).

表2 算法在人工數(shù)據(jù)集上的F-Score指標(biāo)對比結(jié)果Table 2 F-Score metrics comparison results of algorithm on artificial datasets

圖8 不同算法在人工數(shù)據(jù)集上的運(yùn)行時(shí)間Fig.8 Running time of different algorithms on artificial datasets

4 結(jié)束語

本文提出了一種局部社區(qū)劃分方法.該方法將局部社區(qū)劃分分為種子社區(qū)構(gòu)建和種子社區(qū)擴(kuò)展兩個(gè)階段.在種子社區(qū)構(gòu)建階段,根據(jù)節(jié)點(diǎn)間的相似程度和連接緊密程度生成種子社區(qū).在種子社區(qū)擴(kuò)展階段,引入節(jié)點(diǎn)的兩級篩選機(jī)制,利用該機(jī)制將在相似程度和連接緊密程度兩方面優(yōu)勢均衡的節(jié)點(diǎn)作為最佳的節(jié)點(diǎn),合并到當(dāng)前社區(qū),以提高社區(qū)劃分結(jié)果的合理性.兩級篩選機(jī)制允許在一次迭代過程中合并多個(gè)節(jié)點(diǎn),以提高社區(qū)擴(kuò)展過程的收斂速度.在多個(gè)真實(shí)數(shù)據(jù)集和多個(gè)人工數(shù)據(jù)集上的對比實(shí)驗(yàn)證明了本文方法的正確性和有效性.