鳳麗洲，覃 悅，楊貴軍

天津財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)學(xué)院，天津 300222

1 引言

現(xiàn)實(shí)世界中的大部分系統(tǒng)都能以網(wǎng)絡(luò)的形式表示，如人際關(guān)系網(wǎng)、信息傳播網(wǎng)、神經(jīng)元網(wǎng)、蛋白質(zhì)交互網(wǎng)等。這些網(wǎng)絡(luò)往往具有很高的復(fù)雜性，被稱為復(fù)雜網(wǎng)絡(luò)。與隨機(jī)網(wǎng)絡(luò)不同，復(fù)雜網(wǎng)絡(luò)普遍具有“同一社區(qū)內(nèi)節(jié)點(diǎn)聯(lián)系緊密，不同社區(qū)間節(jié)點(diǎn)聯(lián)系稀疏”的特性，這一特性被稱為社區(qū)結(jié)構(gòu)[1]。復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)研究主要針對兩個(gè)重要問題展開：（1）如何識(shí)別復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，即社區(qū)發(fā)現(xiàn)；（2）如何識(shí)別連接不同社區(qū)的關(guān)鍵節(jié)點(diǎn)，即關(guān)鍵節(jié)點(diǎn)發(fā)掘。這兩個(gè)問題的研究對于解決謠言傳播、電網(wǎng)保護(hù)、抑制傳染病擴(kuò)散等現(xiàn)實(shí)問題具有重要的理論意義和廣泛的應(yīng)用前景。

2 相關(guān)工作

Girvan與Newman[1]最早于2002年提出了社區(qū)發(fā)現(xiàn)的概念。此后，圍繞著社區(qū)發(fā)現(xiàn)問題，各領(lǐng)域?qū)W者們提出了大量有效的社區(qū)發(fā)現(xiàn)算法。這些算法大致可分為4類：

（1）基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)算法，根據(jù)優(yōu)化算法的思想，將一種用于度量社區(qū)發(fā)現(xiàn)結(jié)果優(yōu)劣的指標(biāo)——模塊度[2-3]（modularity）作為目標(biāo)函數(shù)，旨在尋找一種使得模塊度最大的社區(qū)劃分方案，如快速Newman（fast Newman）算法[4]、魯汶（Louvain）算法[5]、模擬退火（simulated annealing）算法[6]等。文獻(xiàn)[7]在魯汶算法的基礎(chǔ)上加入了孤立節(jié)點(diǎn)分離策略，縮短了算法的運(yùn)行時(shí)間；文獻(xiàn)[8]針對網(wǎng)絡(luò)變化對靜態(tài)算法影響較大的問題，提出一種基于模塊度的增量學(xué)習(xí)算法，保持了社區(qū)發(fā)現(xiàn)的實(shí)時(shí)性；文獻(xiàn)[9]基于層次聚類的思想，利用拓?fù)鋭莸財(cái)U(kuò)展社區(qū)，最終從各層的社區(qū)劃分中選擇一個(gè)模塊度最大的作為劃分結(jié)果。

（2）基于啟發(fā)式規(guī)則的標(biāo)簽傳播（lable propagation algorithm）算法[10-12]將社區(qū)劃分視為節(jié)點(diǎn)標(biāo)簽預(yù)測問題，文獻(xiàn)[13]針對標(biāo)簽傳播算法存在的不必要更新問題，引入節(jié)點(diǎn)信息列表，提高了算法準(zhǔn)確率；文獻(xiàn)[14]基于度中心性設(shè)計(jì)了節(jié)點(diǎn)參與系數(shù)，解決了標(biāo)簽傳播算法在節(jié)點(diǎn)更新時(shí)順序的不確定性對社區(qū)發(fā)現(xiàn)結(jié)果的影響問題。

（3）基于動(dòng)力學(xué)與仿生模擬的社區(qū)發(fā)現(xiàn)算法，如基于Markov動(dòng)力學(xué)理論的Markov聚類算法[15]、基于自旋模型的社區(qū)發(fā)現(xiàn)算法[16]、蟻群算法[17]和遺傳算法[18]，文獻(xiàn)[19]設(shè)計(jì)了一種節(jié)點(diǎn)對社區(qū)的隸屬度計(jì)算方案，并將其與遺傳算法結(jié)合，提出一種能夠作用于大規(guī)模重疊網(wǎng)絡(luò)的改進(jìn)遺傳算法。

（4）以圖論作為理論支撐的聚類算法，如譜聚類（spectral clustering）算法[20]和基于節(jié)點(diǎn)中心性的社區(qū)發(fā)現(xiàn)算法[1，21]。其中基于節(jié)點(diǎn)中心性的社區(qū)發(fā)現(xiàn)算法是一種可同時(shí)進(jìn)行關(guān)鍵節(jié)點(diǎn)發(fā)掘與社區(qū)發(fā)現(xiàn)的算法，其準(zhǔn)確率與速度取決于中心性度量指標(biāo)的選擇。根據(jù)計(jì)算方式的不同，中心性度量指標(biāo)可分為兩類：①全局中心性，如介數(shù)中心性[1]（betweenness centrality）、緊密度中心性[22]（closeness centrality）、特征向量中心性[23]（eigenvector centrality）等。文獻(xiàn)[1]提出一種基于介數(shù)中心性的圖分割社區(qū)發(fā)現(xiàn)算法（Girvan and Newman algorithm，GN）；文獻(xiàn)[24]提出了一種基于社區(qū)動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)介數(shù)中心性的更新算法，提高了介數(shù)中心性的計(jì)算效率，并將其運(yùn)用到CNM（Clauset，Newman and Moore algorithm）等社區(qū)發(fā)現(xiàn)算法中。全局中心性的計(jì)算需要預(yù)先獲知圖的全局拓?fù)浣Y(jié)構(gòu)信息，這使得基于全局中心性的社區(qū)發(fā)現(xiàn)算法往往具有較高的準(zhǔn)確率。但由于其復(fù)雜度較高，對于大型網(wǎng)絡(luò)的計(jì)算是不可行的。②局部中心性，如度中心性[23]（degree centrality）、節(jié)點(diǎn)質(zhì)量[25]（node mass）等。文獻(xiàn)[26]將節(jié)點(diǎn)的度中心性作為該節(jié)點(diǎn)的關(guān)鍵性度量指標(biāo)，提出一種基于核心節(jié)點(diǎn)擴(kuò)展的社區(qū)挖掘算法（community mining algorithm based on core nodes expansion，CNE）；文獻(xiàn)[27]將網(wǎng)絡(luò)轉(zhuǎn)化為邊圖，基于節(jié)點(diǎn)的度中心性，迭代地將邊圖中的節(jié)點(diǎn)加入到已有社區(qū)中。度中心性雖然計(jì)算較為簡便，但只能反映出節(jié)點(diǎn)的局部特征，忽略了節(jié)點(diǎn)對于全局的影響，這會(huì)影響社區(qū)發(fā)現(xiàn)與關(guān)鍵節(jié)點(diǎn)發(fā)掘的結(jié)果。

為了解決上述節(jié)點(diǎn)中心性存在的缺陷，Chen 和Alfred[28]提出一種局部中心性度量指標(biāo)——局部Fiedler向量中心性（local Fiedler vector centrality，LFVC），并提出了一種基于LFVC的貪心社區(qū)發(fā)現(xiàn)算法（greedy community detection algorithm by node-LFVC，GCDN）。然而，GCDN算法在關(guān)鍵節(jié)點(diǎn)與關(guān)鍵邊的識(shí)別過程中經(jīng)常出現(xiàn)錯(cuò)誤識(shí)別問題，即將一些非關(guān)鍵節(jié)點(diǎn)誤識(shí)別為關(guān)鍵節(jié)點(diǎn)，導(dǎo)致錯(cuò)誤信息傳遞，給后續(xù)社區(qū)劃分帶來負(fù)面影響，降低社區(qū)劃分的準(zhǔn)確率。在圖分割的過程中易劃分出大量的孤立節(jié)點(diǎn)，破壞網(wǎng)絡(luò)信息完整性，導(dǎo)致部分社區(qū)結(jié)構(gòu)信息的損失。

本文深入分析了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對節(jié)點(diǎn)LFVC 值的影響，提出一種節(jié)點(diǎn)LFVC 差值社區(qū)發(fā)現(xiàn)算法（community detection algorithm with difference of node-LFVC，CDDN）。該算法主要考慮了以下兩條信息：（1）聯(lián)系不同社區(qū)間的關(guān)鍵節(jié)點(diǎn)與關(guān)鍵邊存在著的必然鄰接關(guān)系；（2）關(guān)鍵節(jié)點(diǎn)的鄰邊并非都是關(guān)鍵邊。CDDN 算法在圖分割過程中綜合利用這兩條信息，設(shè)計(jì)了一種僅移除LFVC最大節(jié)點(diǎn)的部分關(guān)鍵鄰邊的邊移除規(guī)則，可以有效解決GCDN 算法僅考慮節(jié)點(diǎn)LFVC、忽略邊的LFVC 所造成的關(guān)鍵節(jié)點(diǎn)錯(cuò)誤識(shí)別問題。此外，由于本文算法僅移除該節(jié)點(diǎn)部分關(guān)鍵鄰邊，可以規(guī)避GCDN 算法在圖分割時(shí)不加區(qū)別地刪除LFVC 最大的前q個(gè)節(jié)點(diǎn)的全部鄰邊所產(chǎn)生的大量孤立節(jié)點(diǎn)現(xiàn)象。

在真實(shí)網(wǎng)絡(luò)上的對比實(shí)驗(yàn)結(jié)果表明，與已有算法相比，改進(jìn)算法在各規(guī)模的網(wǎng)絡(luò)上均保證了較好的時(shí)間效率，同時(shí)具有較高的準(zhǔn)確性，性能明顯優(yōu)于已有算法。

3 基于LFVC的社區(qū)發(fā)現(xiàn)算法

3.1 局部Fiedler向量中心性

令G=(V,E)表示一個(gè)復(fù)雜網(wǎng)絡(luò)構(gòu)成的無向無權(quán)圖，其中V、E分別表示節(jié)點(diǎn)集合與邊集合。具有n個(gè)節(jié)點(diǎn)的圖G可由其鄰接矩陣An×n表示，其中：

令

表示節(jié)點(diǎn)i的度，Dn×n為G的度矩陣，其中：

矩陣L=D-A稱為G的Laplace 矩陣，L是半正定矩陣，有[29]：

令λi(L)表示L的第i小特征值，其中λ1(L)=0。λ2(L)則有如下兩個(gè)定義：

定義1（代數(shù)連通度）λ2(L) 稱為G的代數(shù)連通度。

定義2（Fiedler向量與Fiedler值）λ2(L)對應(yīng)的特征向量稱為G的Fiedler向量，其第i個(gè)分量稱為對應(yīng)節(jié)點(diǎn)的Fiedler值。

令G′表示從圖G中移除一條邊(i,j)所得到的新圖，G的Laplace矩陣增量表示為ΔL=ΔD-ΔA，其中ΔD和ΔA分別表示度矩陣D的增量和鄰接矩陣A的增量。G′的Laplace矩陣表示為。令ei表示第i個(gè)元素為1，其余元素全為0的n維常向量，則G′的Laplace矩陣為：

根據(jù)Courant-Fischer定理，任意連接圖的代數(shù)連通度可表示為：

令y表示L的Fiedler向量，則根據(jù)式（3）～式（5）有：

基于上述理論，將LFVC定義如下：

定義3（邊LFVC）設(shè)(i,j)為圖G=(V,E)中的一條邊，即(i,j)∈E，y為G的Fiedler 向量，yi表示節(jié)點(diǎn)i在y中對應(yīng)的分量，則邊(i,j)的LFVC為：

定義4（節(jié)點(diǎn)LFVC）設(shè)i為圖G=(V,E)中的一個(gè)節(jié)點(diǎn)，即i∈V，Ni表示i的鄰接節(jié)點(diǎn)集，y為G的Fiedler向量，yi表示i在y中對應(yīng)的分量，則節(jié)點(diǎn)i的LFVC為：

為了避免概念混淆，本文將連接著兩個(gè)社區(qū)的邊定義為關(guān)鍵邊，將負(fù)責(zé)與不同社區(qū)進(jìn)行聯(lián)系的節(jié)點(diǎn)定義為關(guān)鍵節(jié)點(diǎn)。

3.2 基于LFVC的貪心社區(qū)發(fā)現(xiàn)算法

Chen 和Alfred[28]在2015年提出基于LFVC 的貪心社區(qū)發(fā)現(xiàn)算法（GCDN）。該算法的核心思想是依次移除LFVC最大的節(jié)點(diǎn)及其全部鄰邊，使圖G的代數(shù)連通度以最快速度減小。GCDN 算法分為兩步：（1）找到當(dāng)前圖的最大連通子圖，計(jì)算其中每個(gè)節(jié)點(diǎn)的LFVC 值，給定常數(shù)q，依次刪除LFVC 值最大的q個(gè)節(jié)點(diǎn)及其鄰邊，將該q個(gè)節(jié)點(diǎn)認(rèn)定為關(guān)鍵節(jié)點(diǎn)，記為集合R；（2）將R中的所有節(jié)點(diǎn)加入到它們相應(yīng)鄰接節(jié)點(diǎn)最多的社區(qū)。

3.3 基于LFVC的貪心社區(qū)發(fā)現(xiàn)算法問題分析

GCDN 算法存在兩個(gè)問題：（1）會(huì)將一些非關(guān)鍵節(jié)點(diǎn)與邊錯(cuò)誤地識(shí)別為關(guān)鍵節(jié)點(diǎn)與關(guān)鍵邊；（2）會(huì)產(chǎn)生大量的孤立節(jié)點(diǎn)，且并未對這些孤立節(jié)點(diǎn)進(jìn)行處理。這兩個(gè)問題會(huì)降低社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確性，破壞網(wǎng)絡(luò)的信息完整性，造成社區(qū)結(jié)構(gòu)信息的損失。

如圖1所示的網(wǎng)絡(luò)由{1，2，3，4，5，6}、{7，8，9，10，11}、{12，13，14，15，16}3個(gè)社區(qū)構(gòu)成。其中，{1，2，5，7，8，12，13}是7個(gè)聯(lián)系不同社區(qū)的關(guān)鍵節(jié)點(diǎn)，稱為邊緣節(jié)點(diǎn)（margin nodes）。節(jié)點(diǎn)6和11的度為1，稱為懸掛節(jié)點(diǎn)（dangling node），連接懸掛節(jié)點(diǎn)的邊稱為懸掛邊（dangling edge）。為了將該網(wǎng)絡(luò)劃分為3個(gè)不相連的社區(qū)，最合理的策略是移除連接3個(gè)社區(qū)的6條關(guān)鍵邊{(1，8)，(1，12)，(2，13)，(5，7)，(7，13)，(8，12)}。

Fig.1 Network of 3 communities圖1 由3個(gè)社區(qū)構(gòu)成的示例網(wǎng)絡(luò)

表1為圖1網(wǎng)絡(luò)中各節(jié)點(diǎn)的Fiedler值。由定義3和定義4可知，節(jié)點(diǎn)的LFVC值與其自身及其鄰接節(jié)點(diǎn)的Fiedler 值有關(guān)。社區(qū)中的節(jié)點(diǎn)越接近邊緣節(jié)點(diǎn)，其Fiedler值的絕對值越小[30]。若一個(gè)節(jié)點(diǎn)的鄰點(diǎn)集包含懸掛節(jié)點(diǎn)，則該節(jié)點(diǎn)Fiedler 值的絕對值大于同級(jí)別節(jié)點(diǎn)。因此，懸掛邊、懸掛節(jié)點(diǎn)及其鄰點(diǎn)往往具有較高的LFVC 值。由表1可知，LFVC 最大的節(jié)點(diǎn)和邊分別為節(jié)點(diǎn)3和邊（3，6）。

采用GCDN 算法移除LFVC 最大的1個(gè)節(jié)點(diǎn)后所得社區(qū)劃分結(jié)果如圖2所示，其中紅色節(jié)點(diǎn)表示算法識(shí)別出的關(guān)鍵節(jié)點(diǎn)，綠色節(jié)點(diǎn)和黑色節(jié)點(diǎn)分別代表劃分后獲得的兩個(gè)社區(qū)。顯然，這樣的社區(qū)劃分結(jié)果并不合理。

Table 1 Fiedler values of network depicted in Fig.1表1 圖1中各節(jié)點(diǎn)對應(yīng)的Fiedler值

Fig.2 Result of removing one node by GCDN圖2 根據(jù)GCDN算法移除1個(gè)節(jié)點(diǎn)的結(jié)果

Fig.3 Result of removing 5 nodes by GCDN圖3 根據(jù)GCDN算法移除5個(gè)節(jié)點(diǎn)的結(jié)果

采用GCDN算法移除圖1網(wǎng)絡(luò)LFVC最大的5個(gè)節(jié)點(diǎn)后所得的社區(qū)劃分結(jié)果如圖3所示。由圖3可知，GCDN 算法將節(jié)點(diǎn)3誤識(shí)別為關(guān)鍵節(jié)點(diǎn)，并且將懸掛節(jié)點(diǎn)6和11移除，導(dǎo)致形成兩個(gè)孤立節(jié)點(diǎn)。同時(shí)由圖論可知，給定連通圖G，α(G)表示G的代數(shù)連通度，v為G中一個(gè)懸掛節(jié)點(diǎn)，有α(G)≤α(G-v)[31]。這表示從G中移除懸掛節(jié)點(diǎn)會(huì)增加其代數(shù)連通度，不符合GCDN算法“以最快速度減小代數(shù)連通度”的目的。

針對上述問題，本文改進(jìn)GCDN社區(qū)發(fā)現(xiàn)算法，構(gòu)建了新的關(guān)鍵節(jié)點(diǎn)識(shí)別與邊移除規(guī)則。

4 節(jié)點(diǎn)LFVC差值社區(qū)發(fā)現(xiàn)算法

4.1 改進(jìn)的關(guān)鍵節(jié)點(diǎn)識(shí)別與邊移除策略

基于LFVC 的貪心社區(qū)發(fā)現(xiàn)算法的本質(zhì)是依據(jù)節(jié)點(diǎn)LFVC移除網(wǎng)絡(luò)的邊。表2給出圖1示例網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)與關(guān)鍵邊的LFVC值。

Table 2 LFVC of key nodes and edges in Fig.1表2 圖1網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)與邊的LFVC

由圖1和表2可知，節(jié)點(diǎn)1的度為6，（1，8）與（1，12）兩條邊的LFVC 占節(jié)點(diǎn)1的LFVC 的64.74%，其余4條邊僅占35.26%。由此可見：LFVC 最大節(jié)點(diǎn)i*的鄰邊并非全都具有很高的LFVC 值，且i*的LFVC值由少數(shù)幾條重要鄰邊的LFVC 值構(gòu)成。移除非關(guān)鍵鄰邊無法有效減少圖的代數(shù)連通度，還會(huì)產(chǎn)生大量孤立節(jié)點(diǎn)。為保證網(wǎng)絡(luò)結(jié)構(gòu)信息的完整性，提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確率，在進(jìn)行邊移除時(shí)，應(yīng)當(dāng)僅移除LFVC較大的邊。此外，由于移除懸掛邊并不符合使圖G的代數(shù)連通度以最快速度減小的目的，在進(jìn)行邊移除操作時(shí)應(yīng)保留懸掛邊。

由于關(guān)鍵邊必然是關(guān)鍵節(jié)點(diǎn)的鄰邊。在算法進(jìn)行循環(huán)時(shí)，每移除一條邊，都會(huì)引起網(wǎng)絡(luò)中所有節(jié)點(diǎn)與邊的LFVC 值的變化。若當(dāng)前LFVC 最大節(jié)點(diǎn)i*是關(guān)鍵節(jié)點(diǎn)，在與其連接的全部關(guān)鍵邊移除之前會(huì)保持較高的LFVC值，則該節(jié)點(diǎn)在之后的循環(huán)中容易被再次識(shí)別；若i*是非關(guān)鍵節(jié)點(diǎn)，則希望通過犧牲最少的網(wǎng)絡(luò)結(jié)構(gòu)信息，即移除最小數(shù)量的邊來跳過此次循環(huán)，確保該節(jié)點(diǎn)在之后的循環(huán)中不易被識(shí)別，以尋找真正的關(guān)鍵節(jié)點(diǎn)。本文算法將LFVC 最大的兩個(gè)節(jié)點(diǎn)的LFVC 值之差作為決定每一次循環(huán)中所移除邊的數(shù)量的依據(jù)。

綜上所述，本文為避免GCDN 算法因移除懸掛邊與過多非關(guān)鍵邊而導(dǎo)致的關(guān)鍵節(jié)點(diǎn)識(shí)別錯(cuò)誤與效率低下問題，提出如下改進(jìn)的關(guān)鍵節(jié)點(diǎn)識(shí)別與邊移除策略：

當(dāng)且僅當(dāng)(i,j)*是i*的鄰邊，將i*識(shí)別為關(guān)鍵節(jié)點(diǎn)；計(jì)算LFVC 最大節(jié)點(diǎn)i*與LFVC 次大節(jié)點(diǎn)的差值，即，按LFVC 從大到小依次移除i*的k條鄰邊。k的計(jì)算公式如下：

其中，(i*,nj)表示i*的LFVC值第j大的鄰邊，，表示i*的鄰接節(jié)點(diǎn)集；表示i*的度，din與dout分別表示與節(jié)點(diǎn)i*在同一個(gè)社區(qū)內(nèi)部的鄰邊數(shù)目和不在同一個(gè)社區(qū)中的鄰邊數(shù)目，由于復(fù)雜網(wǎng)絡(luò)普遍具有“同一社區(qū)內(nèi)節(jié)點(diǎn)聯(lián)系緊密，不同社區(qū)間節(jié)點(diǎn)聯(lián)系稀疏”的特性，則有，因而。

若(i,j)*不是i*的鄰邊，則僅移除(i,j)*。

由于孤立節(jié)點(diǎn)是因圖中懸掛邊被移除而產(chǎn)生，上述邊移除策略使得本文算法規(guī)避了產(chǎn)生孤立節(jié)點(diǎn)的情況。

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

依據(jù)上述改進(jìn)策略，本文提出節(jié)點(diǎn)局部Fiedler向量中心性差值社區(qū)發(fā)現(xiàn)算法（CDDN）。該算法分兩個(gè)階段：

階段1計(jì)算LFVC。給定循環(huán)次數(shù)q，在每次循環(huán)中識(shí)別當(dāng)前規(guī)模最大的連通子圖，計(jì)算子圖的Fiedler 向量和各節(jié)點(diǎn)與邊的LFVC 值，找出LFVC 最大節(jié)點(diǎn)i*、LFVC次大節(jié)點(diǎn)和LFVC最大邊(i,j)*，其中i,j∈(i,j)*，di≠1且dj≠1。

階段2識(shí)別關(guān)鍵節(jié)點(diǎn)，依據(jù)邊移除策略對圖進(jìn)行分割。

綜合上述兩個(gè)階段，本文CDDN 算法的偽代碼如下所示：

輸入：圖G，循環(huán)次數(shù)q。

輸出：社區(qū)劃分g。

4.3 算法分析

4.3.1 有效性分析

由于CDDN算法在進(jìn)行邊移除時(shí)主動(dòng)忽略了懸掛邊，因此可以有效避免孤立節(jié)點(diǎn)的生成。對圖1網(wǎng)絡(luò)，采用CDDN算法分別進(jìn)行1次、6次循環(huán)的結(jié)果如圖4、圖5所示。其中，紅色節(jié)點(diǎn)是CDDN算法識(shí)別出的關(guān)鍵節(jié)點(diǎn)，虛線邊表示算法移除的關(guān)鍵邊。CDDN算法識(shí)別出的關(guān)鍵節(jié)點(diǎn)與關(guān)鍵邊均與實(shí)際相符，且不存在孤立節(jié)點(diǎn)。

Fig.4 Result of one turn by CDDN圖4 CDDN算法進(jìn)行1次循環(huán)的結(jié)果

Fig.5 Result of 6 turns by CDDN圖5 CDDN算法進(jìn)行6次循環(huán)的結(jié)果

當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)較為稀疏時(shí)，CDDN算法在發(fā)現(xiàn)小粒度社區(qū)方面具有一定的優(yōu)勢。這是由于遠(yuǎn)離邊緣節(jié)點(diǎn)的節(jié)點(diǎn)往往具有絕對值較大的LFVC，因而對于懸掛點(diǎn)較多，結(jié)構(gòu)較為稀疏的網(wǎng)絡(luò)，CDDN 算法的邊移除策略傾向于為遠(yuǎn)離較大規(guī)模社區(qū)邊緣并與懸掛點(diǎn)相連接的節(jié)點(diǎn)分配較大的LFVC，因此這些節(jié)點(diǎn)易被識(shí)別為LFVC最大點(diǎn)，它們的非懸掛鄰邊易被優(yōu)先移除，使其及其懸掛鄰點(diǎn)成為一個(gè)細(xì)粒度的小社區(qū)。

當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)較為緊密時(shí)，CDDN算法通常可以發(fā)現(xiàn)更多的社區(qū)。CDDN 算法與GCDN 算法往往通過增加循環(huán)次數(shù)以發(fā)現(xiàn)更多數(shù)目的社區(qū)。一方面，在迭代過程中，GCDN 算法移除的邊大多為對圖的代數(shù)連通度影響極小的邊，而CDDN 算法在每一次循環(huán)中則是移除對圖的代數(shù)連通度影響最大的1條或k條邊。因而，在移除相同邊數(shù)的情況下，CDDN 算法發(fā)現(xiàn)的社區(qū)數(shù)量通常多于GCDN 算法。另一方面，由于GCDN 存在節(jié)點(diǎn)合并階段，導(dǎo)致GCDN 算法無法有效分割聯(lián)系緊密的大型網(wǎng)絡(luò)。相對而言由于CDDN 算法不需要節(jié)點(diǎn)合并的步驟，可以有效提升圖分割效率，理論上能發(fā)現(xiàn)更多的社區(qū)。

4.3.2 時(shí)間復(fù)雜度分析

在CDDN 算法中，步驟1為圖G的復(fù)制過程，其時(shí)間主要花費(fèi)在對G中n個(gè)節(jié)點(diǎn)與m條邊進(jìn)行復(fù)制的過程中，時(shí)間復(fù)雜度為O(n+m)。步驟3為尋找G中最大連通子圖的過程，最壞情況下其時(shí)間復(fù)雜度為O(n)。步驟4計(jì)算最大連通子圖的Fiedler 向量，基于Lanczos算法計(jì)算Fiedler向量的時(shí)間復(fù)雜度為O(m1×n)，其中m1為根據(jù)Lanczos 算法計(jì)算Laplace 矩陣的Fiedler向量的迭代次數(shù)，通常需要上百次。步驟5為計(jì)算G′中所有節(jié)點(diǎn)與邊的LFVC 的過程，其時(shí)間復(fù)雜度為O(m+n)。步驟6與步驟7為尋找LFVC 最大、次大非懸掛節(jié)點(diǎn)的過程，時(shí)間復(fù)雜度分別為O(n)和O(m)。步驟8～10為判斷并移除LFVC最大非懸掛邊的過程，時(shí)間復(fù)雜度為O(m)。步驟12、13的時(shí)間復(fù)雜度均為O(1)。步驟14～17的時(shí)間復(fù)雜度為O(r×(m+1+m))，r為 從diff=0到LFVCremove＜diff的循環(huán)次數(shù)。綜上所述，常數(shù)r,q＜＜m，CDDN 算法的最終時(shí)間復(fù)雜度為O(m1n+m)。

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

為了驗(yàn)證CDDN算法與其他現(xiàn)有算法在準(zhǔn)確率和效率方面的性能，實(shí)驗(yàn)用到的算法有：（1）基于全局中心性的GN算法[1]；（2）基于局部中心性的CNE算法[26]；（3）GCDN算法[28]；（4）本文所提出的CDDN算法。

表3為4種算法的時(shí)間復(fù)雜度，其中m1為Lanczos算法計(jì)算Fiedler向量所需的迭代次數(shù)，通常需要上百次。因此對于小規(guī)模網(wǎng)絡(luò)，CNE與GN算法可能擁有更高的效率。但對于大規(guī)模網(wǎng)絡(luò)，CDDN算法與GCDN算法在效率上具有明顯優(yōu)勢。

Table 3 Time complexity of 4 algorithms表3 4種算法的時(shí)間復(fù)雜度

5.1 數(shù)據(jù)集

如表4所示，本文采用了4個(gè)不同規(guī)模、不同結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集（Karate、Dolphin、Football、Last.fm）進(jìn)行對比實(shí)驗(yàn)。其中前3個(gè)網(wǎng)絡(luò)已知其真實(shí)社區(qū)劃分。Karate網(wǎng)絡(luò)數(shù)據(jù)集[32]來自Zachary對某空手道俱樂部成員的社會(huì)關(guān)系研究。該俱樂部由于人事糾紛，最終分裂成了兩個(gè)俱樂部。Dolphin 網(wǎng)絡(luò)數(shù)據(jù)集[33]來自1994年至2001年期間，Lusseau及其團(tuán)隊(duì)對62只寬吻海豚的觀察數(shù)據(jù)。Football網(wǎng)絡(luò)數(shù)據(jù)集[1]來自于2000賽季美國12個(gè)大學(xué)橄欖球隊(duì)聯(lián)盟的比賽時(shí)間表，其中節(jié)點(diǎn)代表球隊(duì)，邊代表兩個(gè)球隊(duì)之間進(jìn)行的常規(guī)賽。Last.fm 網(wǎng)絡(luò)數(shù)據(jù)集來自文獻(xiàn)[34]所提供的在線音樂系統(tǒng)Last.fm的交友狀況數(shù)據(jù)。

Table 4 Real network dataset表4 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

5.2 評(píng)價(jià)指標(biāo)

對于已知真實(shí)社區(qū)劃分的數(shù)據(jù)集，由于對比實(shí)驗(yàn)的算法評(píng)價(jià)涉及孤立節(jié)點(diǎn)識(shí)別問題，本文采用標(biāo)準(zhǔn)化互信息（normalized mutual information，NMI）、準(zhǔn)確率(Acc)以及忽略孤立節(jié)點(diǎn)時(shí)的準(zhǔn)確率Accr、將孤立節(jié)點(diǎn)視為同一個(gè)社區(qū)時(shí)的準(zhǔn)確率Accm作為社區(qū)發(fā)現(xiàn)算法的評(píng)價(jià)指標(biāo)。給定網(wǎng)絡(luò)中真實(shí)社區(qū)U以及算法劃分的社區(qū)V，真實(shí)社區(qū)數(shù)為CU，劃分的社區(qū)數(shù)為CV，4個(gè)指標(biāo)計(jì)算方式如下：

標(biāo)準(zhǔn)化互信息NMI(U,V)定義為[35]：

其中，N代表混淆矩陣，行表示真實(shí)社區(qū)，數(shù)目為CU，列表示劃分社區(qū)，數(shù)目為CV。Ni?表示矩陣N中第i行的和，N?j表示矩陣N中第j列的和。

算法劃分結(jié)果V的準(zhǔn)確率（Acc）定義為：

其中，Interkt表示劃分出的某一社區(qū)vk∈V,k=1,2,…,CV與某個(gè)真實(shí)社區(qū)ut∈U,t=1,2,…,CU的交集元素的個(gè)數(shù)。

劃分的社區(qū)與真實(shí)社區(qū)的吻合程度越高，NMI和Acc的值越高。根據(jù)式（10）和式（11）可知，NMI與Acc對孤立節(jié)點(diǎn)具有偏好，即孤立節(jié)點(diǎn)的存在將提高劃分結(jié)果的NMI與準(zhǔn)確率Acc。因而，本文針對孤立節(jié)點(diǎn)采取了兩種識(shí)別方式：（1）忽略所有孤立節(jié)點(diǎn)；（2）將所有孤立節(jié)點(diǎn)視為同一社區(qū)。分別計(jì)算兩種識(shí)別方式下的準(zhǔn)確率，記為Accr和Accm。

由于無法知曉Last.fm 網(wǎng)絡(luò)的真實(shí)社區(qū)劃分，本文利用最大社區(qū)節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)之比（proportion of largest community size，Plcs）與發(fā)現(xiàn)的社區(qū)數(shù)（detected communities，DC）來比較兩種算法在網(wǎng)絡(luò)劃分上的效果。

5.3 實(shí)驗(yàn)結(jié)果

5.3.1 Karate網(wǎng)絡(luò)

該數(shù)據(jù)集包含34個(gè)節(jié)點(diǎn)，真實(shí)社區(qū)數(shù)為2，為了分析算法發(fā)現(xiàn)更小粒度社區(qū)的表現(xiàn)，圖6～圖8顯示了4種算法分別發(fā)現(xiàn)2～5個(gè)社區(qū)時(shí)的NMI、忽略所有孤立節(jié)點(diǎn)時(shí)的算法準(zhǔn)確率Accr、將孤立節(jié)點(diǎn)視為同一社區(qū)時(shí)的算法準(zhǔn)確率Accm。CNE算法在該數(shù)據(jù)集上僅能發(fā)現(xiàn)兩個(gè)社區(qū)，使用其發(fā)現(xiàn)兩個(gè)社區(qū)時(shí)的數(shù)據(jù)對其發(fā)現(xiàn)3～5個(gè)社區(qū)時(shí)的數(shù)據(jù)進(jìn)行填補(bǔ)。

Fig.6 NMI on Karate network圖6 在Karate網(wǎng)絡(luò)上的NMI

Fig.7 Acc and Accr on Karate network圖7 在Karate網(wǎng)絡(luò)上的Acc與Accr

如圖6所示，由于Karate 網(wǎng)絡(luò)規(guī)模較小，在該數(shù)據(jù)集上GN 算法與CNE 算法的準(zhǔn)確性均優(yōu)于CDDN算法與GCDN 算法。將Karate 網(wǎng)絡(luò)劃分為兩個(gè)社區(qū)時(shí)，CDDN算法的NMI略低于GCDN算法，當(dāng)將網(wǎng)絡(luò)劃分為更多細(xì)粒度的社區(qū)時(shí)，CDDN 算法的NMI高于GCDN算法。由于NMI和準(zhǔn)確率Acc對孤立節(jié)點(diǎn)具有偏好性，而GCDN 算法會(huì)隨著劃分社區(qū)數(shù)的增多產(chǎn)生越來越多的孤立節(jié)點(diǎn)，因而在圖7、圖8中，當(dāng)不對孤立節(jié)點(diǎn)產(chǎn)生的影響進(jìn)行處理時(shí)，GCDN算法的準(zhǔn)確率Acc相對較高。而在考慮孤立節(jié)點(diǎn)帶來的影響并進(jìn)行相應(yīng)處理之后，CDDN 算法所獲得的Accr和Accm明顯優(yōu)于GCDN算法。

Fig.8 Acc and Accm on Karate network圖8 在Karate網(wǎng)絡(luò)上的Acc與Accm

5.3.2 Dolphin網(wǎng)絡(luò)

該網(wǎng)絡(luò)具有兩個(gè)真實(shí)社區(qū)，圖9展示了CDDN算法將該網(wǎng)絡(luò)劃分為兩個(gè)社區(qū)時(shí)的結(jié)果。其中黃色代表劃分錯(cuò)誤的節(jié)點(diǎn)，紅色代表算法發(fā)現(xiàn)的關(guān)鍵節(jié)點(diǎn)，藍(lán)色與綠色節(jié)點(diǎn)分別代表兩個(gè)不同的社區(qū)。與真實(shí)社區(qū)相比，CDDN 算法僅有一個(gè)節(jié)點(diǎn)劃分錯(cuò)誤，說明了使用CDDN算法進(jìn)行社區(qū)劃分的有效性。

Fig.9 Partition Dolphin network to 2 communities by CDDN圖9 CDDN算法將Dolphin網(wǎng)絡(luò)劃分為兩個(gè)社區(qū)的結(jié)果

圖10～圖12給出了4種算法在Dolphin網(wǎng)絡(luò)上發(fā)現(xiàn)2～7個(gè)社區(qū)時(shí)的NMI、Accr和Accm。需要說明的是，由于GCDN 算法無法發(fā)現(xiàn)數(shù)量為5和7的社區(qū)，為了填補(bǔ)缺失值，繪圖時(shí)分別用數(shù)量為4和6時(shí)的數(shù)據(jù)替代。由圖10所示，CDDN 算法在發(fā)現(xiàn)2～7個(gè)社區(qū)時(shí)，所獲得的NMI均大于其他3種算法。如圖11、圖12所示，CDDN算法與GN算法在發(fā)現(xiàn)兩個(gè)社區(qū)時(shí)已經(jīng)具有很高的準(zhǔn)確率，當(dāng)發(fā)現(xiàn)社區(qū)數(shù)目為2～7個(gè)時(shí)所獲得的準(zhǔn)確率Acc值均較高，且呈現(xiàn)穩(wěn)定狀態(tài)。而GCDN 算法和CNE 算法準(zhǔn)確率不僅低于CDDN 和GN算法，而且曲線呈現(xiàn)一定波動(dòng)性。當(dāng)考慮孤立節(jié)點(diǎn)所帶來的影響并進(jìn)行相應(yīng)處理之后，CDDN算法的優(yōu)勢更為明顯。

Fig.10 NMI on Dolphin network圖10 在Dolphin網(wǎng)絡(luò)上的NMI

Fig.11 Acc and Accr on Dolphin network圖11 在Dolphin網(wǎng)絡(luò)上的Acc與Accr

Fig.12 Acc and Accm on Dolphin network圖12 在Dolphin網(wǎng)絡(luò)上的Acc與Accm

5.3.3 Football網(wǎng)絡(luò)

較前兩個(gè)網(wǎng)絡(luò)而言，F(xiàn)ootball網(wǎng)絡(luò)規(guī)模更大，真實(shí)社區(qū)數(shù)更多。GCDN 算法對該網(wǎng)絡(luò)進(jìn)行劃分沒有產(chǎn)生孤立節(jié)點(diǎn)。表5展示了4種算法劃分出同樣數(shù)量社區(qū)時(shí)所需移除的最小邊數(shù)。由表5可知，當(dāng)劃分出相同數(shù)量社區(qū)時(shí)，CDDN 算法所移除的邊數(shù)略多于GN算法，且遠(yuǎn)遠(yuǎn)小于GCDN算法與CNE算法所移除的邊數(shù)。這說明CDDN 算法顯著提升了圖分割效率。圖13、圖14給出了實(shí)驗(yàn)對比4種算法在發(fā)現(xiàn)4～12個(gè)社區(qū)時(shí)的NMI與Acc。表6給出了4種算法對Football 網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)時(shí)，發(fā)現(xiàn)各個(gè)數(shù)量的社區(qū)所需的運(yùn)算時(shí)間。由圖13、圖14可知，在發(fā)現(xiàn)各數(shù)量的社區(qū)時(shí)，CDDN 算法的NMI值和準(zhǔn)確率Acc均明顯優(yōu)于GCDN 算法與CNE 算法，略優(yōu)于GN 算法。結(jié)合表6可得，雖然CDDN算法的準(zhǔn)確率與GN算法大致相同，但算法花費(fèi)時(shí)間遠(yuǎn)少于GN 算法，效率上明顯優(yōu)于GN算法。此外值得注意的是，GCDN算法與CNE 算法至多只能發(fā)現(xiàn)該網(wǎng)絡(luò)中的9個(gè)社區(qū)，無法發(fā)現(xiàn)全部社區(qū)，而CDDN與GN算法卻可以獲得全部社區(qū)結(jié)構(gòu)。圖15展示了使用CDDN 算法劃分Football網(wǎng)絡(luò)所獲得的12個(gè)社區(qū)。

Table 5 Number of edges removed by 4 algorithms on Football network表5 在Football網(wǎng)絡(luò)上4種算法移除的邊數(shù)

Fig.13 NMI on Football network圖13 在Football網(wǎng)絡(luò)上的NMI

Fig.14 Acc on Football network圖14 在Football網(wǎng)絡(luò)上的準(zhǔn)確率Acc

Table 6 Running time of 4 algorithms on Football network表6 在Football網(wǎng)絡(luò)上4種算法的運(yùn)行時(shí)間

5.3.4 Last.fm網(wǎng)絡(luò)

表7展示了4種算法對Last.fm 網(wǎng)絡(luò)進(jìn)行劃分所需的時(shí)間，由于GN算法需要將網(wǎng)絡(luò)中的每一條邊均移除后才可得出結(jié)果，故只有一個(gè)時(shí)間數(shù)據(jù)；CNE算法無法在限定時(shí)間內(nèi)運(yùn)行完畢，導(dǎo)致了數(shù)據(jù)的缺失。從表7中可看出，CDDN算法在處理大規(guī)模網(wǎng)絡(luò)時(shí)，效率明顯優(yōu)于其余3種算法。此處僅用運(yùn)行時(shí)間與本文提出的CDDN算法相近的GCDN算法進(jìn)行社區(qū)發(fā)現(xiàn)結(jié)果的比較。圖16展示了CDDN 算法與GCDN算法在移除相同邊數(shù)時(shí)，網(wǎng)絡(luò)中最大社區(qū)規(guī)模占總規(guī)模之比Plcs。如圖16所示，相對于GCDN 算法，CDDN 算法對應(yīng)的曲線下降速度更快，說明CDDN 算法可以在移除較少邊數(shù)的情況下就達(dá)到GCDN算法的社區(qū)劃分效果，其分割網(wǎng)絡(luò)的效率高于GCDN算法。圖17展示了兩種算法在移除相同邊數(shù)時(shí)發(fā)現(xiàn)的社區(qū)數(shù)量的對比結(jié)果。如圖17所示，CDDN 與GCDN 算法在移除相同邊時(shí)，CDDN 算法發(fā)現(xiàn)社區(qū)數(shù)目明顯多于GCDN 算法，且能發(fā)現(xiàn)更多細(xì)粒度的社區(qū)，說明CDDN 算法的社區(qū)發(fā)現(xiàn)能力優(yōu)于GCDN 算法，同時(shí)也印證了相對于GCDN 算法，CDDN算法在社區(qū)劃分效率上更具優(yōu)勢。

Table 7 Running time of 4 algorithms on Last.fm network表7 在Last.fm網(wǎng)絡(luò)上4種算法的運(yùn)行時(shí)間

Fig.15 Partition Football network to 12 communities by CDDN圖15 CDDN算法將Football網(wǎng)絡(luò)劃分為12個(gè)社區(qū)

Fig.16 Proportion of largest community size to total size(Plcs)圖16 最大社區(qū)規(guī)模占總規(guī)模之比（Plcs）

Fig.17 Number of detected communities(DC)圖17 發(fā)現(xiàn)的社區(qū)數(shù)量（DC）

6 結(jié)束語

本文通過分析復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對局部Fiedler向量中心性的影響，提出了節(jié)點(diǎn)局部Fiedler 向量中心性差值社區(qū)發(fā)現(xiàn)算法，有效解決了GCDN 算法中存在的關(guān)鍵節(jié)點(diǎn)和關(guān)鍵邊的識(shí)別失誤問題以及孤立節(jié)點(diǎn)問題。在Karate、Dolphin、Football、Last.fm 四個(gè)真實(shí)網(wǎng)絡(luò)上的對比實(shí)驗(yàn)表明，相對于其他三種相關(guān)算法，本文算法的效率與準(zhǔn)確率均有顯著提升。