基于相似度投票的社區劃分改進算法

馮成強, 左萬利, 王 英

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

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

鑒于局部相似度的計算簡單、 速度快等優點與Louvain算法底層劃分存在重復開銷, 本文針對大規模的稠密網絡提出一種基于節點相似度投票的改進算法來改善Louvain算法的第一層劃分, 然后再結合基于模塊度的Louvain算法實現對社會網絡的快速劃分.

1 模塊度與Louvain算法

1.1 模塊度

模塊度是通過比較社區內節點的緊密程度及社區間節點的稀疏程度與相同規模隨機網絡中的期望值得出的, 定義如下：

(1)

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

(2)

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

1.2 Louvain算法

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

(3)

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

(4)

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

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

2) 依次對每個節點進行上述操作, 直到所有的節點都穩定在各自社區中或達到最大迭代次數；

3) 將每個社區合成一個超點, 社區間的連邊合并為超點間的連邊, 為超點增加一條自環邊, 權重為超點所代表的社區內邊的權重之和, 合并后即重構為一個更簡單的社會網絡, 第一層劃分完畢；

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

使用偽代碼描述如下：

算法1Louvain算法.

輸入： 社會網絡G(V,E); 輸出：G(V,E)的社區劃分結果Partition.

1) 計算網絡的模塊度Q1；

2) 初始化網絡G, 每個節點作為一個社區；

3) FORvIN RANGE(n): /*n為節點總數*/

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

5) END FOR

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

7) 計算新的模塊度Q2；

8) 將社區劃分結果存入Partition中, 重構網絡G；

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

10) 返回Partition, 結束.

1.3 Louvain算法的缺陷

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

一個節點v的社區劃分變動, 可能引起另一個節點u的社區劃分變動, 而u的社區劃分變動可能再次引起v的社區劃分變動, 如此進入一個死循環, 對于大規模的稠密網絡這種情況很容易出現. Louvain算法中通過設置最大迭代次數跳出死循環, 但最大迭代次數卻不易確定, 過大引起無效計算, 過小影響劃分效果, 這是Louvain算法的另一個缺陷.

2 改進算法

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

2.1 改進算法主要思想

基于相似度投票的社區劃分算法是一種凝聚式的劃分算法, 通過為網絡中的每個節點選擇最佳的合并社區不斷擴大社區規模, 從而完成社區劃分.

1) 采取合適的相似度計算方式計算網絡中每對鄰居節點的相似度；

2) 初始化網絡中的每個節點為一個單獨社區, 對網絡中的每個節點v進行如下操作：

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

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

3) 根據步驟2)劃分結果重構網絡；

4) 使用Louvain算法對重構網絡進行更高層次的劃分, 從而完成社區劃分.

2.2 節點相似度計算

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

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

(5)

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

2.3 最佳合并社區的選擇與社區合并

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

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

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

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

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

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

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

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

2.4 改進算法的實現

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

算法2改進算法.

輸入： 社會網絡G(V,E); 輸出：G(V,E)的社區劃分結果Partition.

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

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

3) FORvIN RANGE(n): /*v為網絡中的一個節點,n為節點總數目*/

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

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

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

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

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

9) END FOR

10) END IF

11) END FOR

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

13) 將社區合并為超點, 重構網絡G；

14) 調用算法1對網絡G進行進一步劃分, 結果保存在Partion2中；

15) 合并Partion1與Parttion2為Partition；

16) 返回Partition, 結束.

函數choseBestComunity為根據相似度投票為v代表的社區選擇合并的鄰接社區C, 實現步驟如下.

函數1choseBestCommunity.

輸入: 節點v, 網絡G, 相似度Sim, 當前社區劃分Community; 輸出： 節點v應合并的鄰接社區C.

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

2) 根據網絡G計算節點v的鄰居列表neighborList；

3) FORuIN neighborList： /*根據v的鄰居劃分情況計算v的所有鄰接社區, 初始票值為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的鄰接社區累積投票, 票值為sim*/

9) END FOR

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

11) 返回鄰接社區C, 結束.

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

2.5 算法時間復雜度對比分析

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

3 實驗結果與分析

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

表1 社會網絡參數

3.1 改進算法在真實社會網絡上的社區劃分

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

圖2 Zachary關系網絡Fig.2 Relational network of Zachary

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

圖3 Louvain算法對Zachary的社區劃分結果Fig.3 Community partition results of Zachary by Louvain algorithm

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

3.2 改進算法的模塊度與社區數分析

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

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

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

表2 兩種算法劃分的社區數目比較

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

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

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

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

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

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

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