李 雷,閆光輝,楊紹文,張海韜

蘭州交通大學(xué) 電子與信息工程學(xué)院,蘭州 730070)(*通信作者電子郵箱yan_guanghui@163.com)

基于孤立節(jié)點(diǎn)分離策略的改進(jìn)魯汶算法

李 雷,閆光輝*,楊紹文,張海韜

蘭州交通大學(xué) 電子與信息工程學(xué)院,蘭州 730070)(*通信作者電子郵箱yan_guanghui@163.com)

魯汶算法(LM)是基于模塊度優(yōu)化的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，有關(guān)模塊度的現(xiàn)有研究中沒有計算節(jié)點(diǎn)離開原屬社區(qū)后模塊度增益的方法。針對這一不足,基于模塊度的定義和節(jié)點(diǎn)合并后模塊度增益的計算方法,推導(dǎo)出了節(jié)點(diǎn)離開原屬社區(qū)后模塊度增益的計算方法,完善了該領(lǐng)域的理論研究。針對魯汶算法對存儲空間需求高的缺點(diǎn),提出了基于孤立節(jié)點(diǎn)分離策略的改進(jìn)魯汶算法,該算法在每次迭代中將輸入網(wǎng)絡(luò)的孤立節(jié)點(diǎn)提前分離出去,只令其中的連通節(jié)點(diǎn)實(shí)際參與迭代過程,并在存儲社區(qū)發(fā)現(xiàn)結(jié)果時將孤立節(jié)點(diǎn)和非孤立節(jié)點(diǎn)分開存儲?；谡鎸?shí)網(wǎng)絡(luò)的相關(guān)實(shí)驗(yàn)結(jié)果表明,采用孤立節(jié)點(diǎn)分離策略的改進(jìn)方法,使算法對存儲空間的需求減少了40%以上,并進(jìn)一步縮短了算法的運(yùn)行時間。因此,改進(jìn)后的算法在處理真實(shí)網(wǎng)絡(luò)時更具優(yōu)勢。

復(fù)雜網(wǎng)絡(luò);社區(qū)發(fā)現(xiàn);模塊度;模塊度優(yōu)化;魯汶算法

0 引言

復(fù)雜網(wǎng)絡(luò)普遍存在著 “同一社區(qū)內(nèi)節(jié)點(diǎn)連接緊密、不同社區(qū)間節(jié)點(diǎn)連接稀疏”的社區(qū)結(jié)構(gòu)特性[1]。社區(qū)是從中觀視角研究復(fù)雜網(wǎng)絡(luò)的一種高效手段,可以充分利用社區(qū)這一特點(diǎn)研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、物理意義和功能行為。2004年,Newman等[2]提出了一個用于刻畫網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)優(yōu)劣的量化標(biāo)準(zhǔn),被稱之為模塊度Q。模塊度Q給出了社區(qū)結(jié)構(gòu)的清晰定義,最初是為評價社區(qū)發(fā)現(xiàn)結(jié)果的優(yōu)劣,并在實(shí)際應(yīng)用中獲得了很大的成功,同時以模塊度Q為目標(biāo)函數(shù)的模塊度優(yōu)化方法也成為復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)領(lǐng)域的主流方法之一。最簡單的模塊度優(yōu)化方法是找出一個網(wǎng)絡(luò)所有可能的劃分,從中選擇擁有最大Q值的劃分作為最后的社區(qū)發(fā)現(xiàn)結(jié)果,但這是一個NP難問題[3],因?yàn)橐粋€網(wǎng)絡(luò)可以擁有的劃分?jǐn)?shù)目是節(jié)點(diǎn)數(shù)目的指數(shù)量級。因此一些基于啟發(fā)式策略的模塊度優(yōu)化算法被提出,主要有基于貪心策略算法[4-5]、基于層次聚類的算法[6-7],以及融合多種策略(貪心策略、局部優(yōu)化、層次聚類等)的算法[8-10]。在這些算法中,融合了貪心策略和層次聚類策略的魯汶算法(Louvain Method, LM)[8]以其時間復(fù)雜度低且具有高質(zhì)量的社區(qū)發(fā)現(xiàn)結(jié)果,得到了許多學(xué)者的認(rèn)可,被著名社區(qū)挖掘?qū)＜褾ortunato[11]評為當(dāng)前性能最佳的模塊度優(yōu)化算法,另外復(fù)雜網(wǎng)絡(luò)分析軟件Gephi中的社區(qū)發(fā)現(xiàn)子模塊也采用了該算法。

LM是迭代算法。在每次迭代中,算法首先在每個節(jié)點(diǎn)的鄰居區(qū)域內(nèi)局部優(yōu)化模塊度Q并獲得一個社區(qū)劃分結(jié)果,然后將得到的每個社區(qū)作為一個超級節(jié)點(diǎn)、社區(qū)間的連接作為加權(quán)邊,構(gòu)建一個新的網(wǎng)絡(luò)并作為下次迭代的輸入;不斷迭代上述兩步,直至Q值不再增加為止。盡管LM是很優(yōu)秀的算法,但其依然有改進(jìn)的空間。文獻(xiàn)[12]通過降低每次迭代的結(jié)束條件,在略微犧牲社區(qū)發(fā)現(xiàn)結(jié)果精度的基礎(chǔ)上可以較大幅度地縮短算法的運(yùn)行時間;文獻(xiàn)[13]在原算法社區(qū)發(fā)現(xiàn)結(jié)果的基礎(chǔ)上,加入細(xì)化提純過程以進(jìn)一步提升社區(qū)發(fā)現(xiàn)結(jié)果的精度;文獻(xiàn)[14]在原算法中加入了并行策略以縮短算法的運(yùn)行時間;文獻(xiàn)[12,15]綜合考慮了網(wǎng)絡(luò)的其他屬性重新定義了邊的權(quán)值,然后應(yīng)用LM進(jìn)行社區(qū)甄別,從而使社區(qū)發(fā)現(xiàn)的結(jié)果更符合實(shí)際情形。本文對LM的改進(jìn)如下:

1)LM需要頻繁地計算節(jié)點(diǎn)合并以及節(jié)點(diǎn)離開原屬社區(qū)后Q的增益,但是有關(guān)模塊度Q的現(xiàn)有研究中只有第一類增益的計算方法,對于第二類增益只能通過第一類增益的計算方法間接地計算。本文給出了一種節(jié)點(diǎn)離開原屬社區(qū)后Q增益的計算方法,完善了該領(lǐng)域的理論研究。

2)LM具有高質(zhì)量的社區(qū)發(fā)現(xiàn)結(jié)果,部分原因是因?yàn)槠渫ㄟ^算法運(yùn)行的中間結(jié)果提供了層次化的社區(qū)結(jié)構(gòu)。存儲算法運(yùn)行的中間結(jié)果,使得LM對存儲空間的需求較高,約為其他相近算法的20倍[8]。本文在LM中引入了分離孤立節(jié)點(diǎn)的改進(jìn)策略。實(shí)驗(yàn)結(jié)果表明,與原算法相比，改進(jìn)后的算法不僅對存儲空間的需求大幅減小,而且其運(yùn)行時間也得到了進(jìn)一步的縮減。

1 模塊度Q及其增益的計算方法

1.1 模塊度Q

模塊度Q有兩種等價的定義[5],分別是基于網(wǎng)絡(luò)鄰接矩陣的定義和基于網(wǎng)絡(luò)社區(qū)連接矩陣的定義,這里只給出第二種定義。

定義1 網(wǎng)絡(luò)G=(V,E,w)。其中：V為節(jié)點(diǎn)集合,E為邊集合,w為邊權(quán)值的映射函數(shù),即w為V×V→R的映射函數(shù),?{u,v}∈E,w(〈u,v〉)≠0;?{u,v}?E,w(〈u,v〉)=0。在無向網(wǎng)絡(luò)中,每條邊被存儲兩次,即若節(jié)點(diǎn)u和節(jié)點(diǎn)v之間存在一條邊,則有w(〈u,v〉)=w(〈v,u〉)=該邊的權(quán)值。將邊〈u,v〉的權(quán)值簡記為wu,v(或wv,u)。令2m=∑wu,v,表示網(wǎng)絡(luò)中所有邊的權(quán)值之和的兩倍。

(1)

Q值越大意味著在網(wǎng)絡(luò)的社區(qū)連接矩陣中,其對角線上的元素之和占矩陣中所有元素之和的比例越大,對于整個網(wǎng)絡(luò)而言,表現(xiàn)為社區(qū)內(nèi)部中邊的權(quán)值之和占網(wǎng)絡(luò)中所有邊的權(quán)值之和的比例越大,即“同一社區(qū)內(nèi)節(jié)點(diǎn)連接緊密、不同社區(qū)間節(jié)點(diǎn)連接稀疏”,也就是社區(qū)結(jié)構(gòu)越明顯。模塊度Q給出了社區(qū)結(jié)構(gòu)的清晰定義,并且其取值區(qū)間為[-0.5,1]。

1.2Q增益的計算方法

ΔQmerge=QB-QA=

(2)

設(shè)某時刻網(wǎng)絡(luò)有n個社區(qū),A為其社區(qū)連接矩陣。合并第n-1個社區(qū)和第n社區(qū),即在A中將第n行(列)元素加到第n-1行(列),記合并后網(wǎng)絡(luò)的社區(qū)連接矩陣為B,則合并后Q增益的計算方法如式(2)所示。因?yàn)樯鐓^(qū)編號相互獨(dú)立且是人為設(shè)定的,所以在計算任意兩個社區(qū)合并后Q的增益時,可以將這兩個社區(qū)的編號分別記為n-1和n,即式(2)可以計算任意兩個社區(qū)合并后Q的增益。式(2)也可以計算任意兩組節(jié)點(diǎn)(包括兩個節(jié)點(diǎn))合并后Q的增益,只需將這兩組節(jié)點(diǎn)視為兩個社區(qū)。

記節(jié)點(diǎn)v所屬社區(qū)為cv,cv′表示在cv中去除v以及與v相連的邊后形成的社區(qū),此時將v視為只含有一個節(jié)點(diǎn)的社區(qū),按照式(2)逆向推導(dǎo),則v離開cv后Q增益的計算方法如式(3)所示：

(3)

其中:av為節(jié)點(diǎn)v的度；acv為社區(qū)cv中所有節(jié)點(diǎn)的度求和；ev,cv′為連接v節(jié)點(diǎn)與社區(qū)cv′中節(jié)點(diǎn)的邊的權(quán)值之和。同樣式(3)也可以計算一組節(jié)點(diǎn)離開原屬社區(qū)后Q的增益,只需將這組節(jié)點(diǎn)視為一個社區(qū),此時av為這組節(jié)點(diǎn)的度求和。

2 基于孤立節(jié)點(diǎn)分離策略的改進(jìn)LM算法

2.1 符號說明

1)Gl=(Vl,El,wl):算法第l次迭代的生成網(wǎng)絡(luò),同時也是第l+1次迭代的輸入網(wǎng)絡(luò),簡稱為第l層網(wǎng)絡(luò),在具體實(shí)現(xiàn)時采用鄰接鏈表存儲;wl(i,j)/wl(j,i)表示Gl中連接節(jié)點(diǎn)i和節(jié)點(diǎn)j的邊的權(quán)值。G0=(V0,E0,w0)為初始網(wǎng)絡(luò)。因?yàn)長M是迭代算法,其第l次迭代生成的社區(qū)是第l+1次迭代的輸入節(jié)點(diǎn),所以下文中的節(jié)點(diǎn)和社區(qū)具有相同的含義,不再特殊說明。

2)Il:Gl中孤立節(jié)點(diǎn)的集合。

3)為了方便計算Q的增益以及每一層網(wǎng)絡(luò)的Q值,依據(jù)式(1)～(3),為每個社區(qū)設(shè)置三個參數(shù),分別是：1)in，社區(qū)內(nèi)部所有邊的權(quán)值之和的兩倍;2)all，社區(qū)內(nèi)部所有節(jié)點(diǎn)的度之和;3)cid，社區(qū)標(biāo)識號,算法結(jié)束后,各層網(wǎng)絡(luò)中的社區(qū)由參數(shù)cid連接形成樹形層次網(wǎng)絡(luò)(即層次化的社區(qū)發(fā)現(xiàn)結(jié)果)?！?”表示引用關(guān)系,例如Vl[i].all表示第l層網(wǎng)絡(luò)中編號為i的社區(qū)(節(jié)點(diǎn))中所有節(jié)點(diǎn)的度之和。需要注意的是,在計算Q的增益時,不需要參數(shù)in。

4)Nl(i)={j|j∈Vl,(i,j)∈El}:第l層網(wǎng)絡(luò)中節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合。

5)AdjionCommunity:節(jié)點(diǎn)的鄰接社區(qū)哈希表,由鍵值對[Cid,Weight]組成,其中Cid是社區(qū)的標(biāo)識號,Weight為該節(jié)點(diǎn)與Cid社區(qū)間所有連邊的權(quán)值之和。圖1為擁有3個社區(qū)的一個網(wǎng)絡(luò),若其中每條邊的權(quán)值為1,記3個社區(qū)的標(biāo)識號從左到右依次為1、2、3,則節(jié)點(diǎn)3的鄰接社區(qū)哈希表為:{(1,1);(2,3);(3,2)}。

圖1 擁有3個社區(qū)的網(wǎng)絡(luò)

2.2 改進(jìn)后的算法

基于孤立節(jié)點(diǎn)分離策略的改進(jìn)魯汶算法(LouvainMethod+,LM+)的主要流程如算法1所示。

算法1LouvainMethod+。

輸入:初始網(wǎng)絡(luò)G0=(V0,E0,w0)。 輸出: 連通網(wǎng)絡(luò)集合G=(G1,G2,…,Gl); 孤立節(jié)點(diǎn)集合I=(I0,I1,…,Il)。 局部變量：l、t分別標(biāo)識迭代的次數(shù)和每次迭代中對連通網(wǎng)絡(luò)的掃描次數(shù),初始值為0；increase標(biāo)識一次遍歷中是否有節(jié)點(diǎn)發(fā)生移動,初始值為true。

1)

While(true)

2)

l←l+1;

3)

Init(Gl-1)

4)

Whileincreasedo

5)

increase←false;

6)

t←t+1;

7)

ForeachiofVl-1do

8)

〈ΔQdepart|ΔQmaxEnter|MaxCid〉←getΔQ(Nl-1(i))

9)

if(ΔQdepart+ΔQmaxEnter>0)

10)

increase←true;

11)

Vl[i.cid].all←Vl[i.cid].all-i.all

12)

Vl[MaxCid].all←Vl[MaxCid].all+i.all

13)

if(Vl[i.cid].all==0)

14)

Vl.Delete(i.cid);

15)

i.cid←MaxCid;

16)

if(t==1)

17)

Return;

18)

ForeachiofVl-1do

19)

Vl[i.cid].in←Vl[i.cid].in+i.in;

20)

ForeachjofNl-1(i)do

21)

if(i.cid==j.cid)

22)

Vl[i.cid].in←Vl[i.cid].in+wl-1(i,j);

23)else

24)

wl(i.cid,j.cid)←wl(i.cid,j.cid)+wl-1(i,j)

25)

G.Add(Gl)

LM+是迭代算法,第l次迭代中,算法的輸入為第l-1層網(wǎng)絡(luò)Gl-1,輸出為Gl-1中的孤立節(jié)點(diǎn)集合Il-1和第l層網(wǎng)絡(luò)Gl。在每次迭代中,首先通過初始化函數(shù)Init篩選出Il-1,并用每一個非孤立節(jié)點(diǎn)(連通節(jié)點(diǎn))建立的一個社區(qū)。第4)～15)步循環(huán)遍歷Gl-1中的連通節(jié)點(diǎn),直至不再有節(jié)點(diǎn)的社區(qū)發(fā)生變化;在每次遍歷中,對每一個節(jié)點(diǎn)首先通過Q增益計算函數(shù)getΔQ計算出該節(jié)點(diǎn)離開原屬社區(qū)后Q的增益ΔQdepart以及進(jìn)入鄰居社區(qū)能產(chǎn)生的最大“進(jìn)入增益”ΔQmaxEnter,記ΔQmaxEnter對應(yīng)的鄰接社區(qū)編號為MaxCid;當(dāng)ΔQdepart+ΔQmaxEnter>0,即節(jié)點(diǎn)離開原社區(qū)并進(jìn)入MaxCid社區(qū)后,將給全網(wǎng)絡(luò)的Q帶來正的最大增益,則移動節(jié)點(diǎn);第11)～12)步表示節(jié)點(diǎn)離開原社區(qū)以及進(jìn)入MaxCid社區(qū)后,原社區(qū)與MaxCid社區(qū)all參數(shù)的更新方法;當(dāng)某個社區(qū)中的所有節(jié)點(diǎn)都移動到了其他社區(qū),則刪除該社區(qū)(第13)～14)步)。第18)～24)步通過遍歷1次Gl-1中的連通節(jié)點(diǎn),完成Gl邊集合的更新以及Gl中每個節(jié)點(diǎn)參數(shù)in的更新。需要注意的是,每次迭代中對連通節(jié)點(diǎn)的最后一次遍歷不會發(fā)生節(jié)點(diǎn)的移動操作,所以若某次迭代中對輸入網(wǎng)絡(luò)的連通節(jié)點(diǎn)只遍歷了1次,則表明網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都不會再移動,此時算法終止(第16)～17)步)。

LM+中使用了兩個功能函數(shù)。初始化函數(shù)Init通過掃描一次Gl-1中的節(jié)點(diǎn),篩選出其中的孤立節(jié)點(diǎn),并將這些孤立節(jié)點(diǎn)添加至Il-1,然后用每一個非孤立節(jié)點(diǎn)建立一個社區(qū)(即Gl中的初始節(jié)點(diǎn))。Q增益計算函數(shù)getΔQ遍歷1次節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合Nl-1(i),得到i的鄰接社區(qū)哈希表,然后利用式(2)計算出i離開原屬社區(qū)后Q的增益,利用式(3)分別計算出孤立節(jié)點(diǎn)i進(jìn)入每個鄰居社區(qū)后Q的增益,并從中選出最大“進(jìn)入增益”ΔQmaxEnter,最后用MaxCid標(biāo)識ΔQmaxEnter對應(yīng)的鄰居社區(qū)編號。

圖2為LM+的一個運(yùn)行實(shí)例,其中左側(cè)方框中注明了每次迭代開始(上次迭代結(jié)束)時,連通網(wǎng)絡(luò)集合G和孤立節(jié)點(diǎn)集合I的元素值。因?yàn)槠?對每一個連通網(wǎng)絡(luò),圖中只列出其節(jié)點(diǎn)集合,未列出邊集合。另外初始網(wǎng)絡(luò)中可能有孤立節(jié)點(diǎn),所以在最后的結(jié)果中,集合I比集合G多一個元素。

圖2 LM+運(yùn)行實(shí)例

LM+的兩個功能函數(shù)如下：

Init(Gl-1)ForeachiofVl-1doIf(Nl-1(i).count==0)Il-1.Add(i);Vl-1.Delete(i);

elseGl.Add(i);Gl[i].cid←i.cid;Gl[i].all←i.all;Gl[i].in←0;

I.Add(Il-1);

getΔQ(Nl-1(i))ForeachjofNl-1(i)doJ←j.cid;if(AdjionCommunity.Contain(J))AdjionCommunity[J]←AdjionCommunity[J]+wl-1(i,j);

elseAdjionCommunity.Add(J,wl-1(i,j));

Return〈ΔQdepart|ΔQmaxEnter|MaxCid〉;

2.3LM+復(fù)雜度分析

設(shè)初始網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目為n,節(jié)點(diǎn)度的最大值為k,記每次迭代中輸入網(wǎng)絡(luò)的規(guī)模與初始網(wǎng)絡(luò)的規(guī)模相同(其實(shí)隨著迭代的進(jìn)行,輸入網(wǎng)絡(luò)的規(guī)模越來越小),迭代總次數(shù)為c1,每次迭代中掃描連通節(jié)點(diǎn)的次數(shù)為c2。大量實(shí)驗(yàn)結(jié)果表明c1、c2是與網(wǎng)絡(luò)規(guī)模無關(guān)的常數(shù)[8,12-15],并且它們的取值較小。所以LM+的時間復(fù)雜度為:

c1·(n+c2·n·k+n·k)=O(n·k)

當(dāng)為稀疏網(wǎng)絡(luò)即節(jié)點(diǎn)的度較小時,LM+為線性時間復(fù)雜度O(n)，LM+算法的空間復(fù)雜度也為O(n·k),在稀疏網(wǎng)絡(luò)上為O(n)。

表1 LM+和LM銀行客戶交易網(wǎng)絡(luò)運(yùn)行過程結(jié)果對比

3 實(shí)驗(yàn)對比分析

這里需要明確,LM+和LM的最終運(yùn)行結(jié)果完全相同,它們的時空復(fù)雜度也相同,本文的改進(jìn)策略只是進(jìn)一步縮減了原算法對時間及空間資源的需求。表1是LM+和LM在銀行客戶交易網(wǎng)絡(luò)上運(yùn)行時過程結(jié)果的對比,表中分別給出了每次迭代時兩種算法輸入、輸出網(wǎng)絡(luò)的規(guī)模(節(jié)點(diǎn)個數(shù))。LM+每次迭代時將輸入網(wǎng)絡(luò)的孤立節(jié)點(diǎn)提前分離出去,只令其中連通節(jié)點(diǎn)實(shí)際參與迭代過程,使得后續(xù)迭代中輸入網(wǎng)絡(luò)的規(guī)模大幅減小,進(jìn)而可縮減算法對時間、空間資源的需求。比如第4次迭代時,LM+中實(shí)際參與迭代的節(jié)點(diǎn)為798個,而LM中為38 776個節(jié)點(diǎn),這38 776個節(jié)點(diǎn)中主要包含的是前幾次迭代產(chǎn)生的36 748+1 212+18=37 978個孤立節(jié)點(diǎn)。

盡管LM為線性空間復(fù)雜度,但相對于其他算法,其對存儲空間的需求較高,是其他相近算法的20倍,這是因?yàn)長M需要存儲中間迭代過程產(chǎn)生的結(jié)果,有時甚至需要存儲每次迭代中每一次掃描后的結(jié)果。通過中間迭代過程產(chǎn)生的結(jié)果,LM提供了層次化的社區(qū)發(fā)現(xiàn)結(jié)果。層次化的社區(qū)結(jié)構(gòu)很好地體現(xiàn)了復(fù)雜網(wǎng)絡(luò)的自相似性和層次特性,為后續(xù)研究網(wǎng)絡(luò)的相關(guān)特性提供了很重要的信息。另外，模塊度優(yōu)化算法普遍存在著“分辨率限制問題”[16]——算法為了使模塊度達(dá)到最大,會將一些較小旳社區(qū)合并為較大的社區(qū),導(dǎo)致無法發(fā)現(xiàn)那些較小的社區(qū)。通過層次化的社區(qū)結(jié)構(gòu),LM提供了多粒度的社區(qū)發(fā)現(xiàn)結(jié)果,是解決分辨率限制問題一種有效手段。

LM+在存儲中間迭代過程產(chǎn)生的結(jié)果時,將孤立節(jié)點(diǎn)和連通節(jié)點(diǎn)分開存儲,使得每次迭代產(chǎn)生的孤立節(jié)點(diǎn)只存儲1次,避免了對這類節(jié)點(diǎn)的重復(fù)存儲,進(jìn)而大幅縮減了其對存儲空間的需求。這里采用空間壓縮比量化LM+相對于LM對存儲空間需求的縮減程度。

定義3 空間壓縮比=(LM存儲節(jié)點(diǎn)數(shù)-LM+存儲節(jié)點(diǎn)數(shù))/LM存儲節(jié)點(diǎn)數(shù)。

因?yàn)閺?fù)雜網(wǎng)絡(luò)是稀疏網(wǎng)絡(luò),且隨著算法的運(yùn)行,逐次迭代的輸出網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)越明顯即邊越少,因此在計算存儲空間時,只計入網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù),不計入邊數(shù)目。在統(tǒng)計每次迭代中需要存儲的節(jié)點(diǎn)數(shù)目時,只計入本次迭代最終結(jié)果的節(jié)點(diǎn)數(shù)目,不計入中間掃描過程產(chǎn)生結(jié)果的節(jié)點(diǎn)數(shù)目。

表2展示了不同網(wǎng)絡(luò)上兩種算法在運(yùn)行時間和空間上的對比(兩種算法的社區(qū)發(fā)現(xiàn)結(jié)果相同,不再羅列),可以看出LM+在處理真實(shí)網(wǎng)絡(luò)時更具優(yōu)勢。首先如圖3所示,LM+和LM一樣,不同的節(jié)點(diǎn)輸入順序?qū)?yīng)有不同的社區(qū)發(fā)現(xiàn)結(jié)果和相異的運(yùn)行時間,為此在表2中,每個網(wǎng)絡(luò)的運(yùn)行結(jié)果是100次不同節(jié)點(diǎn)輸入順序下的平均結(jié)果。另外在LM+中,每次迭代時分離孤立節(jié)點(diǎn)的操作集成在初始化函數(shù)中,不會帶來對輸入網(wǎng)絡(luò)的額外掃描,所以在全連通網(wǎng)絡(luò)上,兩種算法的運(yùn)行時間幾乎相同。誠然,在一個系統(tǒng)的全數(shù)據(jù)集上或者時間跨度很大的情況下,建模出的網(wǎng)絡(luò)連通性較高,孤立社區(qū)較少,此時LM+的改進(jìn)效果不明顯。但全數(shù)據(jù)的處理必將導(dǎo)致很高的時間、空間需求,并且因?yàn)槠浜雎粤藭r間屬性,無法對系統(tǒng)進(jìn)行更全面的研究。社區(qū)進(jìn)化的研究是復(fù)雜網(wǎng)絡(luò)社區(qū)研究領(lǐng)域的一個重要分支[19],考慮時間屬性研究社區(qū)的進(jìn)化需頻繁地在時間跨度較小的網(wǎng)絡(luò)上進(jìn)行社區(qū)甄別,此時LM+對原算法的改進(jìn)策略將有很高的價值。

LM+同LM一樣,對節(jié)點(diǎn)屬于順序敏感,不同的節(jié)點(diǎn)輸入順序?qū)?yīng)有不同的社區(qū)發(fā)現(xiàn)結(jié)果和相異的算法運(yùn)行時間,但是不同的社區(qū)發(fā)現(xiàn)結(jié)果之間的差異較小,各個結(jié)果的Q值落會在一個以網(wǎng)絡(luò)實(shí)際擁有的最大Q值為中心、半徑比較小的一個區(qū)間上。在節(jié)點(diǎn)輸入順序隨機(jī)的情況下,文本在圖3所示的網(wǎng)絡(luò)上運(yùn)行了1 000次LM+,產(chǎn)生了圖中所示的3種不同結(jié)果,這3種結(jié)果從左到右分別發(fā)生了9次、65次和926次,可以看出,這3種結(jié)果之間的差異較小(Q值都在0.35左右)。

4 結(jié)語

本文首先推導(dǎo)出了網(wǎng)絡(luò)中的節(jié)點(diǎn)離開原屬社區(qū)后模塊度Q增益的計算方法,完善了關(guān)于復(fù)雜網(wǎng)絡(luò)模塊度Q的理論研究;然后通過在LM中引入分離孤立節(jié)點(diǎn)的策略,克服了原算法對存儲空間需求高的缺點(diǎn),并進(jìn)一步縮減了算法的運(yùn)行時間。后續(xù)工作中,將重點(diǎn)研究節(jié)點(diǎn)輸入順序?qū)M+的影響,以改進(jìn)其對節(jié)點(diǎn)輸入順序敏感的缺點(diǎn)。

圖3 同一網(wǎng)絡(luò)的不同社區(qū)發(fā)現(xiàn)結(jié)果

網(wǎng)絡(luò)描 述節(jié)點(diǎn)數(shù)目邊數(shù)目總邊權(quán)和空間壓縮比運(yùn)行時間/msLMLM+Enron郵件網(wǎng)絡(luò)來源于安然公司郵件數(shù)據(jù)集[17],節(jié)點(diǎn)為郵件地址,邊的權(quán)值為1,若兩個郵件地址間至少有一次郵件來往,則這兩個地址之間存在一條邊366921838311838310.416815723DBLP科學(xué)家合作網(wǎng)絡(luò)來源于DBLP[18]中時間跨度為2005～2014年間的數(shù)據(jù),節(jié)點(diǎn)為科學(xué)家,邊的權(quán)值為期間兩個科學(xué)家合作發(fā)表論文的次數(shù)12126045318193147913950.4628131574230銀行客戶交易網(wǎng)絡(luò)來源于某商業(yè)銀行時間跨度為2015年1月～3月的客戶交易數(shù)據(jù),節(jié)點(diǎn)為客戶,邊的權(quán)值為兩個客戶3個月內(nèi)交易的次數(shù)2785652936326027170.70224571980全連通網(wǎng)絡(luò)銀行客戶交易網(wǎng)絡(luò)的最大連通子圖1797592325364968800.00014811596

)

[1]GIRVANM,NEWMANMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica, 2002, 99(12):7821-7826.

[2]NEWMANME,GIRVANM.Findingandevaluatingcommunitystructureinnetworks[J].PhysicalReviewE:Statistical,NonlinearandSoftMatterPhysics, 2004, 69(2Pt2):026113.

[3]BRANDESU,DELLINGD,GAERTLERM,etal.Onfindinggraphclusteringswithmaximummodularity[C]//Proceedingsofthe33rdInternationalConferenceonGraph-TheoreticConceptsinComputerScience.Piscataway,NJ:IEEE, 2007:121-132.

[4]NEWMANMEJ.Fastalgorithmfordetectingcommunitystructureinnetworks[J].PhysicalReviewE:Statistical,NonlinearandSoftMatterPhysics, 2004, 69(6Pt2):066133.

[5]CLAUSETA,NEWMANMEJ,MOOREC.Findingcommunitystructureinverylargenetworks[J].PhysicalReviewE:Statistical,NonlinearandSoftMatterPhysics, 2004, 70(6Pt2):066111.

[6]DUCHJ,ARENASA.Communitydetectionincomplexnetworksusingextremaloptimization[J].PhysicalReviewE:Statistical,NonlinearandSoftMatterPhysics, 2005, 72(2Pt2):027104.

[7]LüZ,HUANGW.Iteratedtabusearchforidentifyingcommunitystructureincomplexnetworks[J].PhysicalReviewE:Statistical,NonlinearandSoftMatterPhysics, 2009, 80(2Pt2):026130.

[8]BLONDELVD,GUILLAUMEJL,LAMBIOTTER,etal.Fastunfoldingofcommunitiesinlargenetworks[J].JournalofStatisticalMechanicsTheory&Experiment, 2008, 2008(10):155-168.

[9]LIUX,MURATAT.Advancedmodularity-specializedlabelpropagationalgorithmfordetectingcommunitiesinnetworks[J].PhysicaA:StatisticalMechanics&ItsApplications, 2009, 389(7):1493-1500.

[10]GACHO,HAOJK.Amemeticalgorithmforcommunitydetectionincomplexnetworks[C]//PPSN2012:Proceedingsofthe12thInternationalConferenceonParallelProblemSolvingfromNature.Berlin:Springer, 2012:327-336.

[11]LANCICHINETTIA,FORTUNATOS.Communitydetectionalgorithms:acomparativeanalysis[J].PhysicalReviewE:Statistical,NonlinearandSoftMatterPhysics, 2009, 80:056117.

[12]DEMEOP,FERRARAE,FIUMARAG,etal.GeneralizedLouvainmethodforcommunitydetectioninlargenetworks[EB/OL]. [2016- 03- 10].https://arxiv.org/pdf/1108.1502v2.pdf.

[13]GACHO,HAOJK.Improvingthelouvainalgorithmforcommunitydetectionwithmodularitymaximization[C]//Proceedingsofthe11thInternationalConferenceonArtificialEvolution,LNCS8752.Berlin:Springer, 2013:145-156.

[14]BHOWMICKS,SRINIVASANS.Atemplateforparallelizingthelouvainmethodformodularitymaximization[M]//MUKHERJEEA,CHOUDHURYM,PERUANIF,etal.DynamicsonandofComplexNetworks.Berlin:Springer, 2013, 2:111-124.

[15] 劉瑤, 康曉慧, 高紅, 等. 基于節(jié)點(diǎn)親密度和度的社會網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法[J]. 計算機(jī)研究與發(fā)展, 2015, 52(10):2363-2372.(LIUY,KANGXH,GAOH,etal.Acommunitydetectingmethodbasedonthenodeintimacyanddegreeinsocialnetwork[J].JournalofComputerResearchandDevelopment, 2015, 52(10):2363-2372.)[16] FORTUNATO S, BARTHéLEMY M. Resolution limit in community detection [J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1):36-41.

[17] KLIMT B, YANG Y. Introducing the Enron corpus[EB/OL]. [2016- 03- 10]. https://bklimt.com/papers/2004_klimt_ceas.pdf.

[18] YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth [J]. Knowledge & Information Systems, 2012, 42(1):745-754.

[19] 王莉, 程學(xué)旗. 在線社會網(wǎng)絡(luò)的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J]. 計算機(jī)學(xué)報, 2015, 38(2):219-237.(WANG L, CHENG X Q. Dynamic community in online social network [J]. Chinese Journal of Computers, 2015, 38(2):219-237.)

This work is partially supported by National Natural Science Foundation of China (61163010), the Science Project of Lanzhou (2014-1-171), the Pre-research Fund of JinChuan Group Company Limited (JCYY2013012).

LI Lei, born in 1990, M. S. candidate. His research interests include data mining, community detection.

YAN Guanghui, born in 1970, Ph. D., professor. His research interests include data mining, social network analysis.

YANG Shaowen, born in 1990, M. S. candidate. His research interests include community detection.

ZHANG Haitao, born in 1989, M. S. candidate. His research interests include community detection.

Improved Louvain method with strategy of separating isolated nodes

LI Lei, YAN Guanghui*, YANG Shaowen, ZHANG Haitao

(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China)

Louvain Method (LM) is an algorithm to detect community in complex network based on modularity optimization. Since there is no method to calculate the gain of modularity after nodes leave their community in the existing research, a method was presented to calculate the modularity-gain after nodes leave their community based on the definition of modularity and the method for calculating the modularity-gain after nodes merge. Secondly, aiming at the problem that LM requires large memory space, an improved algorithm was proposed with the strategy of separating isolated nodes. In each iteration of the algorithm, isolated nodes of the input network were separated in advance, only the connected nodes of the input network can actually participate in the iterative process. Isolated nodes and non-isolated nodes were stored respectively when storing communities detected. The experimental results based on real networks showed that the requirement of memory space was reduced by more than 40% in the improved algorithm, and the running time of the algorithm was further reduced. Experimental results indicate that the improved algorithm has more advantages in dealing with real networks.

complex network; community detection; modularity; modularity optimization; Louvain Method (LM)

2016- 11- 04;

2016- 12- 05。

國家自然科學(xué)基金資助項(xiàng)目(61163010);蘭州市科技計劃項(xiàng)目(2014-1-171);金川公司預(yù)研基金資助項(xiàng)目(JCYY2013012)。

李雷(1990—),男,甘肅天水人,碩士研究生,主要研究方向:數(shù)據(jù)挖掘、社區(qū)發(fā)現(xiàn); 閆光輝(1970—),男,河南商丘人,教授,博士,CCF會員,主要研究方向:數(shù)據(jù)挖掘、社交網(wǎng)絡(luò)分析; 楊紹文(1990—),男,陜西漢中人,碩士研究生,主要研究方向:社區(qū)發(fā)現(xiàn); 張海韜(1989—),男,甘肅白銀人,碩士研究生,主要研究方向:社區(qū)發(fā)現(xiàn)。

1001- 9081(2017)04- 0970- 05

10.11772/j.issn.1001- 9081.2017.04.0970

TP301

A