郭理，王嘉岐，張恒旭，曾窕俊

(石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院,新疆 石河子 832003)

社會(huì)網(wǎng)絡(luò)根據(jù)其使用類(lèi)型可分為社交網(wǎng)絡(luò)和社交媒體網(wǎng)絡(luò)[1]。群組結(jié)構(gòu)是社交網(wǎng)絡(luò)中觀察和理解網(wǎng)絡(luò)拓?fù)涞囊粋€(gè)重要結(jié)構(gòu)，將它抽象到圖中，即存在子圖內(nèi)個(gè)體關(guān)系緊密、子圖間個(gè)體關(guān)系稀疏。Newman[2]把符合這一特點(diǎn)的子圖結(jié)構(gòu)稱(chēng)為社區(qū)結(jié)構(gòu)。因此，這些在線(xiàn)網(wǎng)絡(luò)社交關(guān)系就形成了復(fù)雜的社區(qū)結(jié)構(gòu)。社會(huì)網(wǎng)絡(luò)內(nèi)的社區(qū)結(jié)構(gòu)在現(xiàn)實(shí)世界中相互重疊[3]，即網(wǎng)絡(luò)的一個(gè)點(diǎn)可以同時(shí)存在于多個(gè)社區(qū)，該結(jié)構(gòu)稱(chēng)為重疊社區(qū)，該節(jié)點(diǎn)稱(chēng)為重疊節(jié)點(diǎn)。

重疊社區(qū)發(fā)現(xiàn)技術(shù)對(duì)于分析與研究網(wǎng)絡(luò)社區(qū)間關(guān)系具有重要意義。常用重疊社區(qū)發(fā)現(xiàn)算法有基于局部擴(kuò)張的LFM算法[4-5]、基于標(biāo)簽傳播的COPRA算法[6]和基于派系過(guò)濾的CPM算法[7]。LFM算法結(jié)果與其適應(yīng)度增益函數(shù)中參數(shù)α的選擇有關(guān)，由于本文研究的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)重疊社區(qū)處在不斷的變化中，因此，參數(shù)α值無(wú)法確定；COPRA算法是一種基于LPA算法重疊社區(qū)發(fā)現(xiàn)算法，因此其具有LPA算法隨機(jī)性強(qiáng)、魯棒性差的缺點(diǎn)；CPM算法發(fā)現(xiàn)的重疊社區(qū)與人工劃分的重疊社區(qū)比較相似，但是CPM算法要在運(yùn)行之前確定社區(qū)數(shù)量k值，但本文研究社會(huì)網(wǎng)絡(luò)是動(dòng)態(tài)的，其k值不是一成不變的。

目前，常用的非重疊社區(qū)發(fā)現(xiàn)算法有基于圖分割的Kernighan-Lin 算法[8]、基于分裂法的GN 算法[9-10]與Newman算法[2,11]、基于標(biāo)簽傳播的LPA算法[12]和Louvain算法[13]等。Kernighan-Lin算法需要指定子圖的個(gè)數(shù)，但本文研究中無(wú)法實(shí)現(xiàn)預(yù)知子圖的個(gè)數(shù)或者子圖的大小，所以Kernighan-Lin 算法在本文研究中是不可行的；GN算法時(shí)間復(fù)雜度高，但本文研究的數(shù)據(jù)量龐大，所以很難在一個(gè)可以接受的時(shí)間內(nèi)獲取結(jié)果；Newman算法通過(guò)計(jì)算模塊度，將其增長(zhǎng)最大的二個(gè)社區(qū)合并，然而該算法存在的最大缺點(diǎn)是二個(gè)節(jié)點(diǎn)一旦合并，就沒(méi)法再分開(kāi)，這導(dǎo)致可能無(wú)法得到理想的結(jié)果；LPA算法每次迭代結(jié)果不穩(wěn)定，準(zhǔn)確率不高；Louvain算法使用兩層迭代的方式，即由自下而上的凝聚法作為外層迭代和由添加交換策略的凝聚法作為內(nèi)層迭代，可避免單純凝聚方法合并節(jié)點(diǎn)后無(wú)法再分開(kāi)的缺點(diǎn)，具有算法簡(jiǎn)單直觀、容易實(shí)現(xiàn)、速度快和效果好的特點(diǎn)。

從效率和效果維度來(lái)看，Louvain算法是目前發(fā)現(xiàn)非重疊社區(qū)方法中最好的，并作為一種簡(jiǎn)單、靈活、有效的社區(qū)發(fā)現(xiàn)算法被廣泛用于社會(huì)網(wǎng)絡(luò)領(lǐng)域，但是不能發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中的重疊社區(qū)。在實(shí)際的社會(huì)網(wǎng)絡(luò)中，重疊社區(qū)更加符合人們的行為方式，無(wú)法發(fā)現(xiàn)重疊社區(qū)的Louvain算法可能會(huì)丟失最優(yōu)解，因此，本文在分析研究重疊社區(qū)發(fā)現(xiàn)算法和非重疊社區(qū)發(fā)現(xiàn)算法的基礎(chǔ)上，提出一種基于Louvain重疊社區(qū)發(fā)現(xiàn)算法，該算法既能保留原Louvain算法的優(yōu)點(diǎn)，又能有效發(fā)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的重疊社區(qū)，這對(duì)于分析與研究網(wǎng)絡(luò)社區(qū)間關(guān)系具有重要意義。

1 基于Louvain重疊社區(qū)發(fā)現(xiàn)算法

1.1 Louvain算法

Louvain算法是Newman等提出的基于模塊度最優(yōu)化的啟發(fā)式算法，這個(gè)算法的思想最早由BLONDEL V D、GUILLAUME JL、LAMBIOTTE R、LEFEBVRE E等在2008年提出，又被稱(chēng)為BGLL算法。

1.1.1 社會(huì)網(wǎng)絡(luò)的表示方法

社會(huì)網(wǎng)絡(luò)通常抽象成圖來(lái)表示，每個(gè)人為圖中的一個(gè)節(jié)點(diǎn)，人與人之間的聯(lián)系為圖中的邊。圖通常表示為G=(V,E)，其中V表示點(diǎn)集合，E表示邊集合，通常用n表示圖的節(jié)點(diǎn)數(shù)，m表示邊數(shù)。在圖中，與一個(gè)點(diǎn)相關(guān)聯(lián)的邊的數(shù)量稱(chēng)為該點(diǎn)的度。對(duì)于無(wú)向圖，圖中所有點(diǎn)的度之和是邊數(shù)的2倍。在使用計(jì)算機(jī)對(duì)圖進(jìn)行處理時(shí)，通常使用鄰接矩陣A來(lái)表示圖，鄰接矩陣A的(v,w)位置元素使用Avw表示，Avw值為1則表示節(jié)點(diǎn)v與節(jié)點(diǎn)w之間有邊，為0則表示無(wú)邊。

1.1.2 模塊度的定義

模塊度Q由Newman等[2]提出，目前常被用于評(píng)價(jià)無(wú)向網(wǎng)絡(luò)中社區(qū)劃分結(jié)果的好壞程度，一般模塊度越大表示社區(qū)劃分結(jié)果越好，其對(duì)應(yīng)的計(jì)算公式如下：

(1)

其中,cv和cw分別表示節(jié)點(diǎn)v和節(jié)點(diǎn)w所在的2個(gè)社區(qū)，Avw為鄰接矩陣A中(v,w)位置的值;其中函數(shù)δ(cv,cw)的取值定義為：如果v和w在一個(gè)社區(qū)，即cv=cw，則為 1，否則為 0;m為網(wǎng)絡(luò)中邊的總數(shù)kv表示點(diǎn)v的度,即

(2)

1.2 基于Louvain重疊社區(qū)發(fā)現(xiàn)算法

1.2.1 算法設(shè)計(jì)

為了解決Louvain算法無(wú)法發(fā)現(xiàn)重疊社區(qū)的問(wèn)題，本文對(duì)Louvain算法進(jìn)行改進(jìn)，提出了基于Louvain重疊社區(qū)發(fā)現(xiàn)算法，其中，定義模塊度Q，并根據(jù)增益度函數(shù)dq判斷一個(gè)節(jié)點(diǎn)是否具有重疊性，即節(jié)點(diǎn)是否為重疊節(jié)點(diǎn)。

1.2.2 模塊度Q的增益度函數(shù)dq

對(duì)式(1)進(jìn)行拆分，得到以下公式：

(3)

假設(shè)存在若干個(gè)社區(qū)，則式(3)中∑v,wAvwδ(cv,cw)為每個(gè)社區(qū)內(nèi)邊的數(shù)量的累加，∑vkvδ(cv,cw)為每個(gè)社區(qū)內(nèi)點(diǎn)的度數(shù)之和的累加，將對(duì)無(wú)向圖中節(jié)點(diǎn)的遍歷轉(zhuǎn)換為對(duì)社區(qū)的遍歷，則可以得到化簡(jiǎn)后的模塊度函數(shù)

(4)

其中∑in表示社區(qū)C內(nèi)包含邊的數(shù)量，∑tot表示社區(qū)C內(nèi)點(diǎn)的度數(shù)之和。

根據(jù)Louvain算法的流程，節(jié)點(diǎn)v分配到其相鄰節(jié)點(diǎn)w所在社區(qū)C時(shí)，只與節(jié)點(diǎn)v、社區(qū)C有關(guān)，而與其他社區(qū)無(wú)關(guān)，因此，Q的變化量ΔQ可以被表示為：

(5)

其中nv.C是節(jié)點(diǎn)v和社區(qū)C之間所有連邊的數(shù)量。

對(duì)式(5)進(jìn)行化簡(jiǎn)得

(6)

為了簡(jiǎn)化計(jì)算，對(duì)式(6)進(jìn)行適當(dāng)放縮，將模塊度Q的增益度函數(shù)dq定義如下：

(7)

其中，nv,C是節(jié)點(diǎn)v和社區(qū)C之間的所有連邊的數(shù)量，w是與v相連的在社區(qū)C內(nèi)的點(diǎn)，kv表示點(diǎn)v的度，m為網(wǎng)絡(luò)中邊的總數(shù)目。

如果節(jié)點(diǎn)加入某個(gè)社區(qū)的增益度dq與一次迭代后產(chǎn)生的最大增益度maxdq差值小于一定閾值時(shí)，則可認(rèn)為該節(jié)點(diǎn)具有重疊性，為重疊節(jié)點(diǎn)。在本文的實(shí)驗(yàn)中，為了更好地適應(yīng)社區(qū)邊數(shù)變化的情況，經(jīng)過(guò)多次測(cè)試后發(fā)現(xiàn)將該閾值設(shè)置為1/(2 m)有較好的適應(yīng)性，但該值也可以根據(jù)實(shí)際情況進(jìn)行微調(diào)。

1.2.3 算法實(shí)現(xiàn)

(1) 根據(jù)社會(huì)網(wǎng)絡(luò)關(guān)系生成鄰接矩陣A(v,w)。本文將社會(huì)網(wǎng)絡(luò)關(guān)系抽象成社會(huì)網(wǎng)絡(luò)圖G，每個(gè)人是社會(huì)網(wǎng)絡(luò)圖G中的一個(gè)節(jié)點(diǎn)，人與人之間的聯(lián)系為社會(huì)網(wǎng)絡(luò)圖G中的邊。對(duì)社會(huì)網(wǎng)絡(luò)圖G進(jìn)行遍歷，生成鄰接矩陣A(v,w)，流程如下：

算法：生成鄰接矩陣A(v,w)；

輸入：社會(huì)網(wǎng)絡(luò)圖G；

輸出：鄰接矩陣A(v,w)。

具體步驟如下:

1.遍歷社會(huì)網(wǎng)絡(luò)圖G中的每個(gè)節(jié)點(diǎn)v:

2.遍歷與節(jié)點(diǎn)v存在邊的節(jié)點(diǎn)w:

3.將Avw的值設(shè)為1

4.返回A(v,w)

(2)進(jìn)行重疊社區(qū)發(fā)現(xiàn)。初始時(shí)將每個(gè)節(jié)點(diǎn)即每個(gè)用戶(hù)看作一個(gè)社區(qū)。依次遍歷每個(gè)節(jié)點(diǎn)，將maxΔQ和maxdq的初始值分別設(shè)為-∞和0。對(duì)每個(gè)節(jié)點(diǎn)嘗試將其移至其每個(gè)相鄰節(jié)點(diǎn)所在的社區(qū)，并計(jì)算移動(dòng)前和移動(dòng)后的模塊度Q的變化ΔQ。ΔQ的變化分為以下三種情況：

情況一：若ΔQ>0，則加入該社區(qū)后模塊度增大，計(jì)算v加入該社區(qū)的增益度dq，如果ΔQ>maxΔQ，使maxΔQ=ΔQ，maxdq=dq。

情況二：若ΔQ=0，則加入該社區(qū)后模塊度不變，不考慮這種情況。

情況三：若ΔQ<0，則加入該社區(qū)后模塊度減小，不考慮這種情況。

將頂點(diǎn)v移至maxΔQ所在社區(qū)和與增益度dq與maxdq相差1/(2 m)以?xún)?nèi)的社區(qū)；重復(fù)該過(guò)程，直到任何頂點(diǎn)的移動(dòng)都不能使模塊度Q增大。

將遍歷后獲得的社區(qū)看作一個(gè)新的頂點(diǎn)，重新生成鄰接矩陣，重復(fù)本節(jié)(2)直到模塊度Q不再變化。

(3)基于Louvain重疊社區(qū)發(fā)現(xiàn)算法實(shí)現(xiàn)。

輸入為鄰接矩陣A(v,w)，輸出為社區(qū)集合c，具體步驟如下:

1.遍歷鄰接矩陣A中的每個(gè)節(jié)點(diǎn)v:

2.將v加入到節(jié)點(diǎn)集合vec中

3.將v看作只有一個(gè)節(jié)點(diǎn)的社區(qū)cv，加入到社區(qū)集合c中

4.計(jì)算社區(qū)模塊度Q0

5.令m為鄰接矩陣A中的邊數(shù)

6.遍歷節(jié)點(diǎn)集合vec中的每個(gè)節(jié)點(diǎn)v:

7.令maxΔQ=-∞,maxdq=0

8.計(jì)算社區(qū)模塊度Q1

9.遍歷節(jié)點(diǎn)v的相鄰節(jié)點(diǎn)w:

10.計(jì)算將節(jié)點(diǎn)v加入到節(jié)點(diǎn)w所在社區(qū)cw后的模塊度Q2

11.令ΔQ=Q2-Q1

12.如果ΔQ>0

13.計(jì)算增益度dq

14.如果ΔQ>maxΔQ：

15.maxΔQ=ΔQ

16.cwmax=cw

17.如果dq>maxdq:

18.maxdq=dq

19.cMap[cw]=dq

20.如果maxΔQ>0:

21.將節(jié)點(diǎn)v加入到社區(qū)cwmax中

22.遍歷cMap并將key賦值為cv，value賦值為dq:

23.如果maxdq-dq<1/(2m)且cv≠cwmax:

24.將節(jié)點(diǎn)v加入到cv中

25.更新社區(qū)集合c

26.否則節(jié)點(diǎn)v保持不動(dòng)

27.計(jì)算社區(qū)模塊度Q2

28.如果Q0≠Q(mào)2:

29.清空點(diǎn)集合vec和鄰接矩陣A

30.遍歷社區(qū)集合c中的每個(gè)社區(qū)cv:

31.將社區(qū)cv壓縮為一個(gè)節(jié)點(diǎn)v，將社區(qū)cv內(nèi)節(jié)點(diǎn)的邊轉(zhuǎn)化為新節(jié)點(diǎn)v的環(huán)

32.將節(jié)點(diǎn)v加入點(diǎn)集合vec

33.遍歷社區(qū)cv的不在點(diǎn)集合vec中的相鄰社區(qū)cw:

34.將社區(qū)cw壓縮為一個(gè)節(jié)點(diǎn)w，將社區(qū)cw內(nèi)節(jié)點(diǎn)的邊轉(zhuǎn)化為新節(jié)點(diǎn)w的環(huán)

35.將社區(qū)cv與社區(qū)cw之間的邊轉(zhuǎn)化為節(jié)點(diǎn)v與節(jié)點(diǎn)w之間的邊

36.將節(jié)點(diǎn)w加入點(diǎn)集合vec并更新鄰接矩陣A

37.跳轉(zhuǎn)1

38.返回社區(qū)集合c

2 實(shí)驗(yàn)測(cè)試

2.1 基于Louvain重疊社區(qū)發(fā)現(xiàn)算法與Louvain算法的對(duì)比

經(jīng)典數(shù)據(jù)集Zachary’s Karate Club Network[14]包含34個(gè)結(jié)點(diǎn)與78條邊，本文采用該數(shù)據(jù)集對(duì)本文提出的基于Louvain重疊社區(qū)發(fā)現(xiàn)算法與Louvain算法進(jìn)行實(shí)驗(yàn)測(cè)試對(duì)比，用于檢測(cè)本文算法是否可以發(fā)現(xiàn)重疊節(jié)點(diǎn)。

先使用Louvain算法對(duì) Zachary’s Karate Club Network數(shù)據(jù)集進(jìn)行社區(qū)發(fā)現(xiàn)，對(duì)數(shù)據(jù)結(jié)果進(jìn)行可視化處理，運(yùn)行結(jié)果如圖1a所示，其中一個(gè)圈表示一個(gè)社區(qū)，一個(gè)圈內(nèi)的節(jié)點(diǎn)即為同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)。從圖1a可以看出，原始的Louvain算法在Zachary’s Karate Club Network數(shù)據(jù)集中發(fā)現(xiàn)4個(gè)非重疊社區(qū)。

再使用本文提出的基于Louvain重疊社區(qū)發(fā)現(xiàn)算法對(duì)Zachary’s Karate Club Network數(shù)據(jù)集進(jìn)行重疊社區(qū)發(fā)現(xiàn)，結(jié)果如圖1b所示。從圖1b可知:基于Louvain重疊社區(qū)發(fā)現(xiàn)算法不僅發(fā)現(xiàn)了Louvain算法發(fā)現(xiàn)的4個(gè)非重疊社區(qū)，并且還發(fā)現(xiàn)了1個(gè)重疊社區(qū)(3,10,29,32,34)。

圖1 Louvain算法(a)、基于Louvain重疊社區(qū)發(fā)現(xiàn)算法(b)的結(jié)果

為了方便描述，Louvain算法發(fā)現(xiàn)的社區(qū)名稱(chēng)定義見(jiàn)表1。

表1 社區(qū)名稱(chēng)定義

根據(jù)表1中社區(qū)名稱(chēng)的定義，重疊社區(qū)與1號(hào)社區(qū)存在重疊節(jié)點(diǎn)(29,32)，與2號(hào)社區(qū)存在重疊節(jié)點(diǎn)(3,10)，與3號(hào)社區(qū)存在重疊節(jié)點(diǎn)(34)。在Zachary’s Karate Club Network數(shù)據(jù)集中認(rèn)為節(jié)點(diǎn)2、3、34、29、14是重疊節(jié)點(diǎn)[14]，由此可知本文提出的基于Louvain重疊社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)了大部分的重疊節(jié)點(diǎn)，從而驗(yàn)證了基于Louvain重疊社區(qū)發(fā)現(xiàn)算法可以有效發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中的重疊社區(qū)。

2.2 與其他重疊社區(qū)發(fā)現(xiàn)算法對(duì)比分析

式(1)是常用于評(píng)價(jià)非重疊社區(qū)劃分結(jié)果的指標(biāo)。SHEN H等[15]對(duì)模塊度Q函數(shù)進(jìn)行改進(jìn)，提出了重疊社區(qū)模塊度EQ函數(shù)，用于評(píng)價(jià)重疊社區(qū)的劃分結(jié)果，計(jì)算出的EQ值越大說(shuō)明重疊社區(qū)的劃分結(jié)果越好。EQ計(jì)算公式為

(8)

式(8)中，C代表社區(qū)集合，V表示頂點(diǎn)集合，Ov代表節(jié)點(diǎn)v所屬的社區(qū)的個(gè)數(shù)，kv表示點(diǎn)v的度，m為網(wǎng)絡(luò)中邊的總數(shù)目。

本文使用經(jīng)典數(shù)據(jù)集American College Football[9]對(duì)基于Louvain重疊社區(qū)發(fā)現(xiàn)算法與CPM算法、LFM算法和COPRA算法進(jìn)行實(shí)驗(yàn)測(cè)試對(duì)比，并使用重疊模塊度EQ和運(yùn)算時(shí)間對(duì)結(jié)果進(jìn)行綜合評(píng)價(jià)。

American College Football數(shù)據(jù)集是根據(jù)美國(guó)本科生足球聯(lián)賽創(chuàng)建的一個(gè)復(fù)雜的社會(huì)網(wǎng)絡(luò)，該網(wǎng)絡(luò)包括115個(gè)節(jié)點(diǎn)和616條邊。為了避免隨機(jī)性，本文對(duì)每個(gè)算法重復(fù)運(yùn)行100次后取平均值，結(jié)果如表2所示。

表2 American College Football數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

從表2可知：本文提出的基于Louvain重疊社區(qū)發(fā)現(xiàn)算法運(yùn)算時(shí)間比LFM算法降低了23.06%，且重疊模塊度EQ較LFM算法提高了12.81%，表明基于Louvain重疊社區(qū)發(fā)現(xiàn)算法明顯優(yōu)于LFM算法，而且比CPM、COPRA算法運(yùn)算時(shí)間分別提高12.62%和7.15%，重疊模塊度EQ分別提高17.05%和9.45%。

雖然基于Louvain重疊社區(qū)發(fā)現(xiàn)算法運(yùn)算時(shí)間比CPM、COPRA這二種算法差，但是其重疊社區(qū)的劃分效果優(yōu)于CPM、COPRA這二種算法，因此，綜合運(yùn)算時(shí)間與重疊模塊度EQ，基于Louvain重疊社區(qū)發(fā)現(xiàn)算法要優(yōu)于其他算法。

2.3 基于轉(zhuǎn)發(fā)關(guān)系的微博重疊社區(qū)發(fā)現(xiàn)測(cè)試

轉(zhuǎn)發(fā)關(guān)系屬于交互關(guān)系的一種。由于新浪微博的推薦策略，在參與事件討論中，微博用戶(hù)之間的關(guān)注關(guān)系可能并不突出，因此，交互關(guān)系微博社區(qū)更能體現(xiàn)真實(shí)的微博網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)[16]。

本文設(shè)計(jì)基于轉(zhuǎn)發(fā)關(guān)系的微博重疊社區(qū)發(fā)現(xiàn)測(cè)試實(shí)驗(yàn)，用于驗(yàn)證該算法在實(shí)際應(yīng)用中的效果。本文采用北京理工大學(xué)張華平博士提供的微博語(yǔ)料數(shù)據(jù)[17]，該語(yǔ)料中包括約500萬(wàn)條微博內(nèi)容語(yǔ)料。根據(jù)2013年4月19日和20日的微博語(yǔ)料識(shí)別出其中的一個(gè)熱點(diǎn)話(huà)題為“雅安地震”，該話(huà)題包含微博數(shù)量5 685條，其中存在關(guān)注關(guān)系的用戶(hù)有83個(gè)，而存在轉(zhuǎn)發(fā)關(guān)系的用戶(hù)有247個(gè)，也證實(shí)了在同一個(gè)話(huà)題特別是非常規(guī)突發(fā)事件中，用戶(hù)之間的關(guān)注關(guān)系可能不會(huì)特別突出。因此，本文使用轉(zhuǎn)發(fā)關(guān)系構(gòu)建社會(huì)網(wǎng)絡(luò)，即一個(gè)用戶(hù)為一個(gè)節(jié)點(diǎn)，如果用戶(hù)A與用戶(hù)B之間存在轉(zhuǎn)發(fā)關(guān)系，則A與B之間有邊。

根據(jù)本文提出的基于Louvain重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行重疊社區(qū)發(fā)現(xiàn)，并將最終結(jié)果可視化,得到的結(jié)果如圖2所示，其中一個(gè)圈表示一個(gè)社區(qū)，一個(gè)圈內(nèi)的節(jié)點(diǎn)即為同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)。

圖2 運(yùn)算結(jié)果

由圖2可以看出，本文基于Louvain重疊社區(qū)發(fā)現(xiàn)算法在測(cè)試數(shù)據(jù)上總共發(fā)現(xiàn)64個(gè)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社區(qū)，其中存在有6個(gè)重疊的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社區(qū)。與“雅安地震”熱點(diǎn)話(huà)題手動(dòng)劃分的社區(qū)結(jié)果對(duì)比之后發(fā)現(xiàn)，本文提出的算法實(shí)驗(yàn)結(jié)果與手動(dòng)劃分的情況基本相符，說(shuō)明本文提出的基于Louvain重疊社區(qū)發(fā)現(xiàn)算法可以有效發(fā)現(xiàn)重疊的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社區(qū)。

3 結(jié)論

(1)本文提出了基于Louvain重疊社區(qū)發(fā)現(xiàn)算法，采用經(jīng)典數(shù)據(jù)集Zachary’s Karate Club Network對(duì)該算法的驗(yàn)證結(jié)果表明：增益度函數(shù)dq能判斷重疊節(jié)點(diǎn)，既能發(fā)現(xiàn)非重疊社區(qū)，也能發(fā)現(xiàn)重疊社區(qū)。

(2)綜合重疊模塊度EQ與運(yùn)算時(shí)間，基于Louvain重疊社區(qū)發(fā)現(xiàn)算法優(yōu)于CPM、LFM和COPRA這三種算法。

(3)面對(duì)當(dāng)前日益復(fù)雜的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)，基于Louvain重疊社區(qū)發(fā)現(xiàn)算法能更準(zhǔn)確地分析網(wǎng)絡(luò)社區(qū)間的關(guān)系，對(duì)分析網(wǎng)絡(luò)輿情信息具有重要意義。