馮成強(qiáng), 左萬利, 王 英

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

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

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

1 模塊度與Louvain算法

1.1 模塊度

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

(1)

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

(2)

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

1.2 Louvain算法

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

(3)

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

(4)

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

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

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

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

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

使用偽代碼描述如下：

算法1Louvain算法.

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

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

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

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

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

5) END FOR

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

7) 計(jì)算新的模塊度Q2；

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

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

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

1.3 Louvain算法的缺陷

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

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

2 改進(jìn)算法

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

2.1 改進(jìn)算法主要思想

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

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

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

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

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

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

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

2.2 節(jié)點(diǎn)相似度計(jì)算

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

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

(5)

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

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

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

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

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

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

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

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

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

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

2.4 改進(jìn)算法的實(shí)現(xiàn)

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

算法2改進(jìn)算法.

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

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

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

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

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

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

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ū)合并為超點(diǎn), 重構(gòu)網(wǎng)絡(luò)G；

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

15) 合并Partion1與Parttion2為Partition；

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

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

函數(shù)1choseBestCommunity.

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

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

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

3) FORuIN neighborList： /*根據(jù)v的鄰居劃分情況計(jì)算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)是本文提出的改進(jìn)算法部分, 其余部分則是直接運(yùn)用Louvain算法, 所以二者的差距只在第一層的劃分上. 改進(jìn)算法在進(jìn)行社團(tuán)合并的過程中利用了節(jié)點(diǎn)的鄰居劃分情況, 以保證節(jié)點(diǎn)選擇社區(qū)進(jìn)行合并的合理性, 從而省去了模塊度增量計(jì)算. 整個過程只需遍歷所有節(jié)點(diǎn)一次即可完成初步社區(qū)劃分, 相比Louvain算法的多次迭代要快很多.

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

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

3 實(shí)驗(yàn)結(jié)果與分析

下面通過對改進(jìn)算法與Louvain算法在真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果進(jìn)行比較與分析, 說明算法的有效性. 實(shí)驗(yàn)中采用的社會網(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é)點(diǎn)數(shù)遞增的關(guān)系, 表1列出了上述各網(wǎng)絡(luò)的基本參數(shù).

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

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

為對比改進(jìn)算法在實(shí)際社會網(wǎng)絡(luò)上的社區(qū)劃分效果, 選用較經(jīng)典的Zachary空手道俱樂部網(wǎng)絡(luò)的劃分結(jié)果對兩種算法的社會網(wǎng)絡(luò)劃分差異做比較. Zachary是用于社區(qū)劃分分析的經(jīng)典社會網(wǎng)絡(luò), 包含34個點(diǎn), 代表俱樂部的成員, 78條邊代表成員之間的社會關(guān)系. 俱樂部因?yàn)槭欠裉岣呤召M(fèi)產(chǎn)生爭執(zhí), 分為2個真實(shí)關(guān)系社區(qū). 如圖2所示, 分別以節(jié)點(diǎn)v1為代表的白色社區(qū)1和以節(jié)點(diǎn)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. 改進(jìn)算法對未劃分的Karate網(wǎng)絡(luò)的劃分結(jié)果如圖4所示, 同樣劃分4個社區(qū), 相比Louvain算法劃分的社區(qū)結(jié)構(gòu)只有節(jié)點(diǎn)v24不同, 它從社區(qū)4移入到了社區(qū)2, 分析節(jié)點(diǎn)v24可知它與社區(qū)2中的度數(shù)較大的節(jié)點(diǎn)v33, 節(jié)點(diǎn)v34均直接相連, 所以將它劃分到社區(qū)2更合理. 對比圖3和圖4可見, 改進(jìn)算法在社區(qū)劃分結(jié)構(gòu)方面與Louvain算法相差較小.

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

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

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

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

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

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

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

表3 FN算法與改進(jìn)算法比較

3.3 改進(jìn)算法的時間效率分析

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

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

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

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

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