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

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

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

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

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

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

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

1.1 Louvain算法

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

1.1.1 社會網(wǎng)絡的表示方法

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

1.1.2 模塊度的定義

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

(1)

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

(2)

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

1.2.1 算法設計

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

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

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

(3)

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

(4)

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

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

(5)

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

對式(5)進行化簡得

(6)

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

(7)

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

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

1.2.3 算法實現(xiàn)

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

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

輸入：社會網(wǎng)絡圖G；

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

具體步驟如下:

1.遍歷社會網(wǎng)絡圖G中的每個節(jié)點v:

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

3.將Avw的值設為1

4.返回A(v,w)

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

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

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

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

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

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

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

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

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

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

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

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

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

6.遍歷節(jié)點集合vec中的每個節(jié)點v:

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

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

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

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

11.令ΔQ=Q2-Q1

12.如果ΔQ>0

13.計算增益度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é)點v加入到社區(qū)cwmax中

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

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

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

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

26.否則節(jié)點v保持不動

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

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

29.清空點集合vec和鄰接矩陣A

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

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

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

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

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

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

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

37.跳轉(zhuǎn)1

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

2 實驗測試

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

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

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

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

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

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

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

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

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

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

(8)

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

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

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

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

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

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

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

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

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

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

圖2 運算結(jié)果

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

3 結(jié)論

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

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

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