馮成強, 左萬利, 王 英

(吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 長春 130012)

隨著科技的發(fā)展, 出現(xiàn)了很多大型系統(tǒng), 如果將這些系統(tǒng)的對象視為節(jié)點, 對象之間的關(guān)系視為邊, 則這些系統(tǒng)將構(gòu)成社會網(wǎng)絡(luò). 如電話通信網(wǎng)絡(luò)、 WWW網(wǎng)絡(luò)[1]、 社交網(wǎng)絡(luò)用戶關(guān)系網(wǎng)、 科學(xué)家合作關(guān)系網(wǎng)絡(luò)[2]、 全球的Internet網(wǎng)等, 研究這些網(wǎng)絡(luò)的特性將有助于發(fā)掘網(wǎng)絡(luò)中隱藏的有用信息. 常見的社會網(wǎng)絡(luò)特性有小世界性、 無標度性和社區(qū)結(jié)構(gòu)性[3]. 社區(qū)劃分是目前社會網(wǎng)絡(luò)分析的研究熱點. 社區(qū)劃分就是找出社會網(wǎng)絡(luò)中的某種內(nèi)在結(jié)構(gòu), 使社會網(wǎng)絡(luò)分裂成一個個的社區(qū), 社區(qū)結(jié)構(gòu)的定義如下： 社區(qū)結(jié)構(gòu)是一些社區(qū)內(nèi)成員關(guān)系密切聯(lián)系, 社區(qū)間的成員關(guān)系稀疏的節(jié)點集合[4]. 近年來對社會網(wǎng)絡(luò)劃分的研究已取得了很多成果, 主要分為4類： 基于譜分割思想的方法[5]、 基于優(yōu)化思想的方法[6-7]、 基于模塊度的方法[8]以及基于相似度的劃分算法. 基于模塊度的方法一般屬于層次聚類算法, 又分為凝聚式與分裂式兩類, 均使用模塊度作為社區(qū)劃分準確率的評判標準. 文獻[4]提出了第一個基于模塊度的社區(qū)劃分算法, 稱為GN算法, 該算法通過不斷刪除邊介數(shù)最大的邊增大模塊度, 直到模塊度不再增加為止, 從而實現(xiàn)對網(wǎng)絡(luò)的社區(qū)劃分, 是一種分裂式的層次聚類算法； Newman[9]提出了一種凝聚型的層次聚類算法----FN算法, 該算法通過不斷合并使模塊度增加最大的兩個社區(qū)對網(wǎng)絡(luò)節(jié)點進行聚類, 最后達到劃分的目的. 但以上兩種算法對于大規(guī)模的社會網(wǎng)絡(luò)在時間效率上存在明顯缺陷, 為實現(xiàn)對大規(guī)模社會網(wǎng)絡(luò)進行快速劃分的目的, Blondel等[10]提出了Louvain算法, 該算法相對于GN算法和FN算法具有運行速度較快、 劃分效果較好等優(yōu)點. Louvain算法通過不斷地將節(jié)點在其鄰接社區(qū)中移除與并入來劃分社區(qū), 每次移動均需要計算模塊度增量, 對于大規(guī)模的稠密網(wǎng)絡(luò)迭代次數(shù)一般較多, 收斂速度較慢. 基于相似度的劃分算法有： 近鄰傳播AP算法[11]、 基于聚簇相似度的社區(qū)劃分方法[12]以及通過相似性度量條件進行社區(qū)劃分的方法[13]. 節(jié)點相似度的構(gòu)造[14]一般分為基于節(jié)點局部信息的與基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的兩類. 基于節(jié)點局部信息的相似度計算方式主要有3種[15], 分別是Jaccard公式、 余弦相似度公式及分母最小化公式, 而基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的方法主要原理是依據(jù)隨機游走的思想[16]. 由文獻[14]結(jié)果可見, 基于節(jié)點局部信息計算相似度, 速度較快, 且準確度也較高.

鑒于局部相似度的計算簡單、 速度快等優(yōu)點與Louvain算法底層劃分存在重復(fù)開銷, 本文針對大規(guī)模的稠密網(wǎng)絡(luò)提出一種基于節(jié)點相似度投票的改進算法來改善Louvain算法的第一層劃分, 然后再結(jié)合基于模塊度的Louvain算法實現(xiàn)對社會網(wǎng)絡(luò)的快速劃分.

1 模塊度與Louvain算法

1.1 模塊度

模塊度是通過比較社區(qū)內(nèi)節(jié)點的緊密程度及社區(qū)間節(jié)點的稀疏程度與相同規(guī)模隨機網(wǎng)絡(luò)中的期望值得出的, 定義如下：

(1)

其中：Avu表示節(jié)點v到u的邊的權(quán)重;Kv表示節(jié)點v的度;m表示邊的權(quán)重之和;γ(v,u)表示當u=v時表達式取1, 否則取0;Cv表示節(jié)點v所在的社區(qū). 所以整個Q值的定義是所有節(jié)點到其他節(jié)點的邊分布與隨機分配節(jié)點邊的差的加權(quán)求和. 對式(1)進行化簡可得

(2)

其中： ∑in表示社區(qū)C內(nèi)邊的權(quán)重之和; ∑tot表示連接到社區(qū)C內(nèi)節(jié)點的邊的權(quán)重之和. 式(2)表明模塊度是各個社區(qū)的模塊度之和, 可分別進行計算. 模塊度的取值范圍為[-1,1][17], 值越大, 社區(qū)劃分就越合理. 模塊度作為一種廣泛使用的度量標準, 其劃分結(jié)果相對可靠.

1.2 Louvain算法

1.2.1 模塊度增量 Louvain算法中的模塊度增量是指把一個孤立節(jié)點v合并到其鄰接社區(qū)C時帶來的模塊度的增加量ΔQ, 計算公式為

(3)

其中： ∑in表示合并前社區(qū)C內(nèi)邊的權(quán)重之和； ∑tot表示合并前連接到社區(qū)C內(nèi)點邊的權(quán)重之和；Kv,in表示節(jié)點v到社區(qū)C中節(jié)點邊的權(quán)重之和;λv表示連接到v的邊的權(quán)重之和. 對式(3)進行化簡, 得

(4)

1.2.2 Louvain算法思想 Louvain算法是基于模塊度的貪婪式算法.

1) 通過不斷地將節(jié)點從當前所在社區(qū)中移除成為一個單獨節(jié)點, 再把這個節(jié)點重新分配到其某個鄰接社區(qū)中, 使得與該社區(qū)合并所帶來的模塊度增量最大；

2) 依次對每個節(jié)點進行上述操作, 直到所有的節(jié)點都穩(wěn)定在各自社區(qū)中或達到最大迭代次數(shù)；

3) 將每個社區(qū)合成一個超點, 社區(qū)間的連邊合并為超點間的連邊, 為超點增加一條自環(huán)邊, 權(quán)重為超點所代表的社區(qū)內(nèi)邊的權(quán)重之和, 合并后即重構(gòu)為一個更簡單的社會網(wǎng)絡(luò), 第一層劃分完畢；

4) 以此類推進行其他層次劃分, 直到某一層劃分前后總的模塊度不再增加為止.

使用偽代碼描述如下：

算法1Louvain算法.

輸入： 社會網(wǎng)絡(luò)G(V,E); 輸出：G(V,E)的社區(qū)劃分結(jié)果Partition.

1) 計算網(wǎng)絡(luò)的模塊度Q1；

2) 初始化網(wǎng)絡(luò)G, 每個節(jié)點作為一個社區(qū)；

3) FORvIN RANGE(n): /*n為節(jié)點總數(shù)*/

4) 將v從原來的社區(qū)取出, 合并到使得ΔQ最大且ΔQ>0的鄰接社區(qū)中；

5) END FOR

6) 重復(fù)步驟3), 直到在一次遍歷中沒有節(jié)點改變劃分或達到最大迭代次數(shù)；

7) 計算新的模塊度Q2；

8) 將社區(qū)劃分結(jié)果存入Partition中, 重構(gòu)網(wǎng)絡(luò)G；

9) 重復(fù)步驟1), 直到Q1=Q2；

10) 返回Partition, 結(jié)束.

1.3 Louvain算法的缺陷

由Louvain算法的劃分過程可見, 將一個節(jié)點v從其原來的社區(qū)中移除, 再并入到模塊度增量最大的鄰接社區(qū)中, 如果假設(shè)當v移除后, 其鄰接社區(qū)數(shù)為m, 則再將其重新并入新的社區(qū)中要計算m次ΔQ, 然后選擇ΔQ增加最大的社區(qū)進行合并. 在移除過程中, 如果一個節(jié)點的社區(qū)歸屬改變了, 則其他頂點都將從其原來的社區(qū)中移除, 然后再重新歸入某個鄰接社區(qū)中, 即使其社區(qū)劃分沒有改變也需進行計算, 由此帶來的重復(fù)計算將導(dǎo)致大量開銷. 特別是在每層劃分的最后階段, 可能只有一個節(jié)點的劃分與上一次劃分不同, 但其他節(jié)點也得重新進行一次劃分, 這樣其他節(jié)點都在進行無效計算, 該缺點在大規(guī)模的稠密網(wǎng)絡(luò)上表現(xiàn)特別突出.

一個節(jié)點v的社區(qū)劃分變動, 可能引起另一個節(jié)點u的社區(qū)劃分變動, 而u的社區(qū)劃分變動可能再次引起v的社區(qū)劃分變動, 如此進入一個死循環(huán), 對于大規(guī)模的稠密網(wǎng)絡(luò)這種情況很容易出現(xiàn). Louvain算法中通過設(shè)置最大迭代次數(shù)跳出死循環(huán), 但最大迭代次數(shù)卻不易確定, 過大引起無效計算, 過小影響劃分效果, 這是Louvain算法的另一個缺陷.

2 改進算法

在Louvain算法的第一層劃分中由于網(wǎng)絡(luò)節(jié)點較多導(dǎo)致社區(qū)劃分收斂慢, 每次迭代過程中均有很多無效計算. 因此, 本文提出一種基于相似度投票的改進算法, 以改善Louvain算法的底層劃分, 并將劃分后的網(wǎng)絡(luò)與Louvain算法相結(jié)合, 進一步提升社區(qū)劃分的模塊度, 從而完成社區(qū)劃分.

2.1 改進算法主要思想

基于相似度投票的社區(qū)劃分算法是一種凝聚式的劃分算法, 通過為網(wǎng)絡(luò)中的每個節(jié)點選擇最佳的合并社區(qū)不斷擴大社區(qū)規(guī)模, 從而完成社區(qū)劃分.

1) 采取合適的相似度計算方式計算網(wǎng)絡(luò)中每對鄰居節(jié)點的相似度；

2) 初始化網(wǎng)絡(luò)中的每個節(jié)點為一個單獨社區(qū), 對網(wǎng)絡(luò)中的每個節(jié)點v進行如下操作：

① 通過v與其鄰居節(jié)點的相似度及鄰居節(jié)點的劃分情況, 為v選擇最佳合并社區(qū)C;

② 將v所在社區(qū)中的所有節(jié)點(包括v)合并到社區(qū)C中；

3) 根據(jù)步驟2)劃分結(jié)果重構(gòu)網(wǎng)絡(luò)；

4) 使用Louvain算法對重構(gòu)網(wǎng)絡(luò)進行更高層次的劃分, 從而完成社區(qū)劃分.

2.2 節(jié)點相似度計算

網(wǎng)絡(luò)中的節(jié)點彼此之間通過邊相連, 與一個節(jié)點相連的點稱為其鄰居節(jié)點. 一個節(jié)點在網(wǎng)絡(luò)中的位置與其鄰居節(jié)點緊密相關(guān). 利用兩個節(jié)點的鄰居分布, 可計算兩個節(jié)點的相關(guān)程度, 即節(jié)點相似度. 一個節(jié)點與鄰居節(jié)點的共同鄰居越多, 則與該鄰居節(jié)點越相似. 本文對相似度的計算方式定義如下： 首先根據(jù)網(wǎng)絡(luò)邊集合的每條邊(v,u), 分別計算節(jié)點v與u的鄰居集合Sv與Su； 然后利用Jaccard的變形公式計算節(jié)點v與u的相似度：

Simvu=Ψ(Sv,Su)/|Sv∪Su|,

(5)

其中： | |表示集合取模運算; ∪表示集合的并運算；Ψ(Sv,Su)表示當Sv與Su交集不為空時取交集的模, 否則取1. 計算完每條邊兩個節(jié)點的相似度后, 即得到了節(jié)點與每個鄰居的相似度, 然后將節(jié)點與鄰居的相似度作為劃分該節(jié)點的依據(jù). 改進算法的實驗結(jié)果證明了該節(jié)點相似度計算方法較準確.

2.3 最佳合并社區(qū)的選擇與社區(qū)合并

在改進算法中通過為每個節(jié)點選擇社區(qū)進行合并來不斷增大社區(qū)規(guī)模, 從而達到社區(qū)劃分的目的, 如何為節(jié)點v選擇最佳的合并社區(qū)是改進算法的關(guān)鍵. 為節(jié)點v選擇最佳合并社區(qū)時利用了節(jié)點v與鄰居節(jié)點的相似度以及鄰居節(jié)點的劃分情況, 最佳社區(qū)選擇與社區(qū)合并過程如下：

1) 利用網(wǎng)絡(luò)拓撲結(jié)構(gòu)計算節(jié)點v0的所有鄰接社區(qū). 此時鄰接社區(qū)可能會因為社區(qū)劃分的程度不同(已劃分節(jié)點的數(shù)量)而出現(xiàn)不同情況, 如圖1所示, 其中： (A)表示在劃分v0時其鄰居節(jié)點尚未劃分, 每個鄰居是節(jié)點v0的一個鄰接社區(qū); (B)表示有些鄰居節(jié)點已經(jīng)完成劃分, 劃分到一起的鄰居節(jié)點形成一個鄰接社區(qū); (C)表示已經(jīng)有鄰居節(jié)點被劃分到節(jié)點v0的初始單獨社區(qū)中, 形成了一個新的社區(qū)C3, 此時將社區(qū)C3除v0外的點構(gòu)成的社區(qū)視為一個鄰接社區(qū).

圖1 不同情況下的節(jié)點劃分示意圖Fig.1 Schematic diagram of nodes partition under different circumstances

2) 利用相似度為每個鄰接社區(qū)投票. 遍歷v0的所有鄰居節(jié)點, 先將每個鄰居vi與v0的相似度作為票值投給vi所在的鄰接社區(qū), 再將同一鄰接社區(qū)獲得的票值累加, 形成投票積累, 如圖1(B)中的鄰接社區(qū)C2的得票即為v1與v0的相似度加上v2與v0的相似度, 其他類似.

3) 計算每個鄰接社區(qū)的票值, 獲得最大投票的鄰接社區(qū)即為節(jié)點v0的最佳合并社區(qū)C.

4) 將節(jié)點v0或v0所屬社區(qū)的所有節(jié)點合并到C中. 如圖1所示, 其中: (A)表示將v0合并到與獲得最高票值的鄰居v3中, 形成社區(qū)C1； (B)表示將v0合并到獲得最高投票的鄰接社區(qū)C2中; (C)表示將v0所在社區(qū)中的所有節(jié)點v0與v3合并到C2中.

經(jīng)過上述過程后,圖1中的一個節(jié)點即完成了初步劃分, 所有節(jié)點都經(jīng)過處理后即完成改進算法描述中的步驟2).

開始階段節(jié)點的每個鄰居都是一個鄰接社區(qū), 相當于將節(jié)點代表的社區(qū)與最相似的鄰居所代表的社區(qū)進行合并, 如圖1(A)所示. 經(jīng)過一部分節(jié)點劃分后, 對于未劃分的節(jié)點, 其節(jié)點的鄰居可能已經(jīng)完成了社區(qū)劃分, 如圖1(B)和(C)所示. 此時由于節(jié)點的一些鄰居劃分在同一個鄰接社區(qū), 對節(jié)點的鄰接社區(qū)進行相似度投票將出現(xiàn)投票積累, 選擇累積票值最高的社區(qū)進行合并, 而不是選擇單個相似度最高的節(jié)點進行合并原因如下： 1) 通過累積獲得最高相似度的鄰接社區(qū)將有更多鄰居節(jié)點與該節(jié)點相連, 將節(jié)點合并到這樣的鄰接社區(qū)中, 形成的社區(qū)更緊湊, 使得實驗結(jié)果中改進算法社區(qū)數(shù)更少; 2) 該合并方式傾向合并出大的社區(qū), 減少了小社區(qū)出現(xiàn)后又被合并的可能性, 從而減少了中間計算量.

2.4 改進算法的實現(xiàn)

為了更好地理解改進算法描述的社區(qū)劃分過程, 下面將改進算法用算法2實現(xiàn)如下.

算法2改進算法.

輸入： 社會網(wǎng)絡(luò)G(V,E); 輸出：G(V,E)的社區(qū)劃分結(jié)果Partition.

1) 計算鄰居節(jié)點的相似度Sim； /*結(jié)果以字典形式保存在Sim中*/

2) 初始化Community[v]=v,cMember[v]=[v]； /*初始化每個節(jié)點為單獨社區(qū)并記錄成員*/

3) FORvIN RANGE(n): /*v為網(wǎng)絡(luò)中的一個節(jié)點,n為節(jié)點總數(shù)目*/

4)C=choseBestCommunity(v,G,Sim,Community) /*為v選擇最佳合并的鄰接社區(qū)C*/

5) IFv!=C: /*當選擇合并的社區(qū)不為自身所在社區(qū)時, 才進行合并*/

6) FORkINcMenber[v]: /*將v所在的社區(qū)與鄰接社區(qū)C合并*/

7)cMember[C].append(k); /*將v所在社區(qū)的成員加入社區(qū)C/

8) Community[k]=C; /*改變v所在社區(qū)成員的社區(qū)劃分*/

9) END FOR

10) END IF

11) END FOR

12) 將Community存入Partition1中, 作為第一層的劃分結(jié)果；

13) 將社區(qū)合并為超點, 重構(gòu)網(wǎng)絡(luò)G；

14) 調(diào)用算法1對網(wǎng)絡(luò)G進行進一步劃分, 結(jié)果保存在Partion2中；

15) 合并Partion1與Parttion2為Partition；

16) 返回Partition, 結(jié)束.

函數(shù)choseBestComunity為根據(jù)相似度投票為v代表的社區(qū)選擇合并的鄰接社區(qū)C, 實現(xiàn)步驟如下.

函數(shù)1choseBestCommunity.

輸入: 節(jié)點v, 網(wǎng)絡(luò)G, 相似度Sim, 當前社區(qū)劃分Community; 輸出： 節(jié)點v應(yīng)合并的鄰接社區(qū)C.

1) 聲明字典neighborCom={ }； /*用于記錄v每個鄰接社區(qū)獲得的票數(shù)*/

2) 根據(jù)網(wǎng)絡(luò)G計算節(jié)點v的鄰居列表neighborList；

3) FORuIN neighborList： /*根據(jù)v的鄰居劃分情況計算v的所有鄰接社區(qū), 初始票值為0*/

4) neighborCom[Community[u]]=0.0；

5) END FOR

6) FORuIN neighborList:

7) sim=Sim(v,u)； /*讀取v與u的相似度*/

8) neighborCom[Community[u]]+=sim； /*為包含u的鄰接社區(qū)累積投票, 票值為sim*/

9) END FOR

10)C=neighborCom中有最大投票數(shù)的鄰接社區(qū)； /*若最大投票有多個, 則任意選取一個社區(qū)*/

11) 返回鄰接社區(qū)C, 結(jié)束.

算法2的步驟1)～13)是本文提出的改進算法部分, 其余部分則是直接運用Louvain算法, 所以二者的差距只在第一層的劃分上. 改進算法在進行社團合并的過程中利用了節(jié)點的鄰居劃分情況, 以保證節(jié)點選擇社區(qū)進行合并的合理性, 從而省去了模塊度增量計算. 整個過程只需遍歷所有節(jié)點一次即可完成初步社區(qū)劃分, 相比Louvain算法的多次迭代要快很多.

2.5 算法時間復(fù)雜度對比分析

改進算法第一層劃分的時間開銷主要集中在節(jié)點的相似度計算及節(jié)點劃分中的社區(qū)選擇與合并兩部分. 第一部分的時間復(fù)雜度為O(c1|E|), 其中：E表示社會網(wǎng)絡(luò)的邊集合;c1表示每對節(jié)點相似度計算的開銷. 第二部分的時間復(fù)雜度為O(c2|V|), 其中:V表示頂點集合;c2表示為每個節(jié)點選擇社區(qū)與進行社區(qū)合并的開銷. 總的復(fù)雜度為O(|E|+|V|), 所以具有線性的時間復(fù)雜度. Louvain算法的第一層劃分過程中遍歷節(jié)點一次需要O(c3|V|)的時間復(fù)雜度, 其中c3表示移動一個節(jié)點的開銷, 需要多次遍歷直至節(jié)點劃分不再變化, 設(shè)次數(shù)為γ, 則其時間開銷為O(γ|V|), 所以當γ較大時, 其時間開銷可能大于改進算法. 由于其他層次的劃分采用相同的算法, 所以其時間復(fù)雜度相同, 且均為線性的. 將改進算法與Louvain算法第一層劃分所用的時間分別記為T11和T21, 第一層后的劃分所用時間分別記為T12和T22. 如果T11+T12

3 實驗結(jié)果與分析

下面通過對改進算法與Louvain算法在真實數(shù)據(jù)上的實驗結(jié)果進行比較與分析, 說明算法的有效性. 實驗中采用的社會網(wǎng)絡(luò)分別是Zachary空手道俱樂部成員關(guān)系網(wǎng)絡(luò)[18]Karate、 海豚協(xié)作關(guān)系網(wǎng)Dolphins、 酵母遺傳網(wǎng)絡(luò)Yeast、 美國西部電力網(wǎng)絡(luò)Power及兩個規(guī)模更大的社會網(wǎng)絡(luò)： 物理學(xué)家合作網(wǎng)絡(luò)Astro-ph和Condensed matter collaborations網(wǎng)絡(luò)Cond-mat-2005. 上述6個社會網(wǎng)絡(luò)在規(guī)模上呈按節(jié)點數(shù)遞增的關(guān)系, 表1列出了上述各網(wǎng)絡(luò)的基本參數(shù).

表1 社會網(wǎng)絡(luò)參數(shù)

3.1 改進算法在真實社會網(wǎng)絡(luò)上的社區(qū)劃分

為對比改進算法在實際社會網(wǎng)絡(luò)上的社區(qū)劃分效果, 選用較經(jīng)典的Zachary空手道俱樂部網(wǎng)絡(luò)的劃分結(jié)果對兩種算法的社會網(wǎng)絡(luò)劃分差異做比較. Zachary是用于社區(qū)劃分分析的經(jīng)典社會網(wǎng)絡(luò), 包含34個點, 代表俱樂部的成員, 78條邊代表成員之間的社會關(guān)系. 俱樂部因為是否提高收費產(chǎn)生爭執(zhí), 分為2個真實關(guān)系社區(qū). 如圖2所示, 分別以節(jié)點v1為代表的白色社區(qū)1和以節(jié)點v33為代表的黑色社區(qū)2.

圖2 Zachary關(guān)系網(wǎng)絡(luò)Fig.2 Relational network of Zachary

Louvain算法對未劃分的Karate網(wǎng)絡(luò)的劃分結(jié)果如圖3所示, 相對原始網(wǎng)絡(luò)新增了3和4兩個較小的社區(qū), 整個網(wǎng)絡(luò)被劃分成4個社區(qū)： 白色的社區(qū)1, 黑色的社區(qū)2, 深灰色的社區(qū)3, 淺灰色的社區(qū)4. 改進算法對未劃分的Karate網(wǎng)絡(luò)的劃分結(jié)果如圖4所示, 同樣劃分4個社區(qū), 相比Louvain算法劃分的社區(qū)結(jié)構(gòu)只有節(jié)點v24不同, 它從社區(qū)4移入到了社區(qū)2, 分析節(jié)點v24可知它與社區(qū)2中的度數(shù)較大的節(jié)點v33, 節(jié)點v34均直接相連, 所以將它劃分到社區(qū)2更合理. 對比圖3和圖4可見, 改進算法在社區(qū)劃分結(jié)構(gòu)方面與Louvain算法相差較小.

圖3 Louvain算法對Zachary的社區(qū)劃分結(jié)果Fig.3 Community partition results of Zachary by Louvain algorithm

圖4 改進算法對Zachary的社區(qū)劃分結(jié)果Fig.4 Community partition results of Zachary by improved algorithm

3.2 改進算法的模塊度與社區(qū)數(shù)分析

圖5 兩種算法模塊度比較Fig.5 Modularity comparison of two algorithms

根據(jù)6個社會網(wǎng)絡(luò)的實驗結(jié)果對Louvain算法與改進算法關(guān)于模塊度與社區(qū)數(shù)目做出分析. 模塊度Q作為社區(qū)劃分算法效果的度量標準, 一般模塊度越高, 社區(qū)結(jié)構(gòu)劃分越合理. 由文獻[11]可見, Louvain算法相對于其他算法模塊度相對較高.圖5為Louvain算法與改進算法的模塊度柱狀圖比較. 由圖5可見, 改進算法與Louvain算法在模塊度上的差別較小, 只略低于原始算法. 其原因可能是由于算法開始階段, 對于處于劃分后社區(qū)邊界的節(jié)點由于其鄰居節(jié)點尚未劃分, 無法進行相似度投票而導(dǎo)致誤劃分. 純模塊度的度量標準傾向于小社區(qū), 具有極端退化的現(xiàn)象[19], 所以可能導(dǎo)致Louvain算法的社區(qū)結(jié)構(gòu)與實際社區(qū)結(jié)構(gòu)不同, 但模塊度卻很高； 而改進算法則傾向于更緊湊的社區(qū)結(jié)構(gòu), 可能會有一小部分的模塊度損失, 從而導(dǎo)致模塊度略低于Louvain算法.

社區(qū)數(shù)目G也是用于測評算法準確性的一個重要度量標準. 合理的社區(qū)數(shù)目將使劃分出來的社區(qū)結(jié)構(gòu)更緊湊, 社區(qū)成員間的關(guān)系更符合實際情況. 表2列出了兩種算法對6個社會網(wǎng)絡(luò)劃分的社區(qū)數(shù)目. 由表2可見, 改進算法與Louvain算法在前4個網(wǎng)絡(luò)上劃分的社區(qū)數(shù)目相差較小, 但均少于Louvain算法劃分的社區(qū)數(shù)目； 后2個網(wǎng)絡(luò)中, 改進算法相對于Louvain算法對大規(guī)模社會網(wǎng)絡(luò)劃分的社區(qū)數(shù)目更少.

表2 兩種算法劃分的社區(qū)數(shù)目比較

表3 FN算法與改進算法比較

3.3 改進算法的時間效率分析

準確性與時間效率是衡量算法優(yōu)劣的兩個重要指標.圖6與圖7分別是兩種算法的時間開銷(T)對比與時間提升百分數(shù)(1-改進算法時間/Louvain算法時間)對比結(jié)果. 由圖6可見, 在6個社會網(wǎng)絡(luò)中改進算法的時間開銷均較小.

圖7為改進算法對于Louvain算法的時間提升百分數(shù). 由圖7可見， 6個網(wǎng)絡(luò)的時間提升百分數(shù)分別為30.0%,22.4%,3.6%,42.1%,11.0%,16.9%. 因此在前4個規(guī)模較小的社會網(wǎng)絡(luò)上, 其中3個網(wǎng)絡(luò)中改進算法的提升效果在20%以上, 在Yeast網(wǎng)絡(luò)上只有3.6%. 分析Yeast網(wǎng)絡(luò)可知其節(jié)點數(shù)很少, 卻有近萬條邊, 在計算節(jié)點相似度上花銷較大, 且節(jié)點少會加快Louvain算法的收斂速度, 所以提升效果不明顯. 在Astro-ph和Cond-mat-2005大規(guī)模社會網(wǎng)絡(luò)上提升的效率都超過了10%, 所以大規(guī)模網(wǎng)絡(luò)的提升效果較明顯. 改進算法在大部分的社會網(wǎng)絡(luò)上的時間開銷比Louvain算法少, 將改進算法用于大規(guī)模社會網(wǎng)絡(luò)的社區(qū)劃分在時間效率上可行.

圖6 兩種算法的時間對比Fig.6 Time comparison of two algorithms

圖7 改進算法相對Louvain算法的時間提升百分數(shù)Fig.7 Time lifting percentage of improved algorithm relative to Louvain algorithm

綜上可見, 本文從模塊度、 社區(qū)數(shù)和時間效率三方面綜合分析總結(jié)了兩種算法在社區(qū)劃分上的差異, 說明了改進算法用于社區(qū)劃分的可行性. 對于一些基于社區(qū)劃分的應(yīng)用, 如果其對準確性要求不高, 則使用改進算法能更快地對用戶的請求做出回應(yīng), 從而提升用戶的體驗效果. 對于需要實時劃分的動態(tài)網(wǎng)絡(luò), 由于改進算法的節(jié)點相似度計算結(jié)果可重復(fù)利用, 只需重新計算由于節(jié)點變動帶來的相似度變化的節(jié)點, 省去了大部分節(jié)點的相似度計算, 所以能很快地完成動態(tài)網(wǎng)絡(luò)的社區(qū)劃分.