趙富強,張 爍,何 麗,邢恩軍

1 引言

隨著近 10年來許多社會網(wǎng)絡(luò)媒體的迅猛發(fā)展，例如Twitter、Facebook和Google+等社交網(wǎng)站，社會網(wǎng)絡(luò)擁有更龐大的數(shù)據(jù)量，節(jié)點個數(shù)達到百萬甚至上億的龐大數(shù)據(jù)[1]。龐大數(shù)據(jù)的處理也促使了復(fù)雜網(wǎng)絡(luò)模型和方法的發(fā)展。復(fù)雜網(wǎng)絡(luò)混合度上升，復(fù)雜網(wǎng)絡(luò)社區(qū)的個數(shù)不易確定，社區(qū)不平衡性問題也顯現(xiàn)出來。雖然一些社團發(fā)現(xiàn)算法通過一定的割邊模型可有效識別復(fù)雜網(wǎng)絡(luò)中的社區(qū)，但算法的復(fù)雜度依然很高，割邊效率不高，例如，經(jīng)典社區(qū)發(fā)現(xiàn)算法Girvan-Newman，該算法的主要缺點是每次迭代只能刪除一條邊，算法復(fù)雜度較高，GN算法的總時間復(fù)雜度為O(m2n)；對于稀疏網(wǎng)絡(luò)，GN算法的復(fù)雜度為O(n3) ，其中n為節(jié)點數(shù)，m為邊數(shù)。Radicchi等人從提高算法運行效率和如何選擇 GN算法層次劃分結(jié)果中的最優(yōu)劃分出發(fā)[2]，提出了一種自包含的GN算法變種[3]。Wilkinson、Huberman和 Tyler在通過采樣部分結(jié)點來計算邊的最短路徑介數(shù)的方法，提高了算法的計算速度，但計算精度有所降低。Chen和Yuan指出，因為在計算邊介數(shù)時考慮了所有可能的結(jié)點間最短路徑，GN算法給出的社團劃分往往是不均衡的，據(jù)此提出了一種只考慮結(jié)點間結(jié)點不相交的所有最短路徑來計算邊的介數(shù)的GN算法變種[4]。Fortunato等人則提出利用信息中心度（information centrality）的方法來判斷社團之間的邊，信息中心度高的結(jié)點往往對應(yīng)于社團之間的邊[5]。雖然該 GN算法變種在網(wǎng)絡(luò)社團結(jié)構(gòu)比較模糊的情況下有較好的劃分準(zhǔn)確性，但其時間復(fù)雜度非常高，為O(m3n)，即稀疏網(wǎng)絡(luò)上為O(n4)。一些學(xué)者提出的社團分割模型，但時間復(fù)雜度都相對較高，Clauset et al.[6]時間復(fù)雜度為O(n log2n)，Duch & Arenas[7]時間復(fù)雜度為O(n2logn)，Eckmann & Moses[8]時間復(fù)雜度為O(m＜k2＞)，Capocci et al.[9]時間復(fù)雜度為O(n2)；Zhou & Lipowsky[10]時間復(fù)雜度為O(n3)。如何在保證分割結(jié)果準(zhǔn)確的基礎(chǔ)上，改進割邊模型效率，有效降低復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的時間復(fù)雜度，快速有效地將網(wǎng)絡(luò)中的社區(qū)挖掘出來，基于代數(shù)連通性提出了貪婪譜優(yōu)化割邊模型（Greedy Algorithm Spectral Optimal Cut Edge Model, GACEM）和基于邊中心性測度的割邊模型（Edge Centrality Cut Model，ECCM）。

2 貪婪譜優(yōu)化割邊模型

圖的拉普拉斯矩陣的第二小特征值2λ被定義為代數(shù)連通性，如果圖是連通的則代數(shù)連通性大于零，該值為零時，圖被二分；為了改善該方法一次只能把圖二分，文獻[11]提出了選擇頭兩個特征向量，一次劃分三個社區(qū)。代數(shù)連通性反應(yīng)了網(wǎng)絡(luò)中節(jié)點間連接的緊密程度，可以用于計算網(wǎng)絡(luò)的健壯性和系統(tǒng)的可靠性。與傳統(tǒng)的連通性測量函數(shù)不同，代數(shù)連通性函數(shù)依賴于網(wǎng)絡(luò)中連通節(jié)點的數(shù)量。在隨機網(wǎng)絡(luò)中，代數(shù)連通性函數(shù)值與節(jié)點的個數(shù)和平均度負相關(guān)。

復(fù)雜網(wǎng)絡(luò)代數(shù)連通性函數(shù)λ2(L(x))是單調(diào)凸函數(shù)，如果G1=(V，E1)和G2=(V，E2)中E1?E2，則λ2(L1)≤λ2(L2)。在一個復(fù)雜網(wǎng)絡(luò)中如果邊越少，則代數(shù)連通性越差?？梢酝ㄟ^利用L的第二特征向量最小化RatioCut[12]近似求得λ2(L(x)),公式如下：

但其時間復(fù)雜度較高，可以通過Gossip算法[13]近似計算代數(shù)連通性函數(shù)，有效降低時間復(fù)雜度。由于第二特征值與復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)有直接關(guān)系，如果網(wǎng)絡(luò)相對稀疏則第二特征值較小，網(wǎng)絡(luò)連通性較差，相反則第二特征值較大，網(wǎng)絡(luò)連通性較好。模型將λ2定義為網(wǎng)絡(luò)連通性函數(shù)2(())L xλ。將通過優(yōu)化模型選擇使網(wǎng)絡(luò)連通性下降最快的邊集。所以最優(yōu)化問題定義如下：

對于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題，主要算法細節(jié)如下。給出網(wǎng)絡(luò)的原始圖G=(V,E)和一個常數(shù)k，我們將通過模型從E集合中選擇k條對代數(shù)連通性影響最大的邊，假設(shè)。公式2被定義為：

這個模型可以被構(gòu)造為一個布爾函數(shù)。圖G的每條邊可以用一個布爾變量x∈{0,1}m表示。如果邊，則相應(yīng)的xl= 1，否則為0。使L為G對應(yīng)的拉普拉斯矩陣。公式3被重新定義，變量為x向量：

公式(5)給出了公式(4)的上確界，如果公式(5)的最優(yōu)解是布爾向量，則其結(jié)果也是公式(4)的最優(yōu)解；否則選擇x向量中最大的k個值為模型最優(yōu)解。

邊的權(quán)重計算可有效用于社區(qū)分割中，社區(qū)內(nèi)部的邊連接相對密集，社區(qū)間的邊連接相對稀疏[14]。當(dāng)復(fù)雜網(wǎng)絡(luò)被分割為兩個非連通子圖時，是模型本次迭代的結(jié)束標(biāo)志，但復(fù)雜網(wǎng)絡(luò)中節(jié)點的度符合冪律分布，大量節(jié)點的度小于k，所以刪除該節(jié)點的邊可將該節(jié)點剝離出來，形成兩個極不對稱的非連通子圖，從而影響模型社區(qū)發(fā)現(xiàn)的結(jié)果。所以模型根據(jù)每條邊符權(quán)重wl，0≤wl≤1，該權(quán)重使連接不同社區(qū)間的邊權(quán)重較大，連接同社區(qū)內(nèi)部節(jié)點的邊權(quán)重較小。在模型優(yōu)化過程中保持復(fù)雜網(wǎng)絡(luò)的連通特性。權(quán)重定義如下所示：

其中l(wèi)～(i,j)，fi與fj為費德勒向量第i和j分量。

兩個社區(qū)之間節(jié)點的鄰接節(jié)點往往均勻分布于兩個不同社區(qū)內(nèi)部，其對應(yīng)費德勒向量的值相對較小，所以模型對邊l取權(quán)重wl與該邊連接的兩個節(jié)點對應(yīng)費德勒向量的值（fi和fj）成反比，當(dāng)邊l連接兩個不同社區(qū)內(nèi)的節(jié)點時，則該值權(quán)重較小，相反權(quán)重較大?？紤]權(quán)重的優(yōu)化模型為：

半正定規(guī)劃（SDP）[15]可以解模型(7)求最優(yōu)解，但其時間復(fù)雜度較高，采用貪婪策略來解決大規(guī)模的復(fù)雜網(wǎng)絡(luò)分割問題。

模型首先根據(jù) Newman給出的邊介數(shù)（edge betweenness）計算每條連接邊的中心性，然后根據(jù)邊中心性值選出前mc個邊作為候選刪除邊，其中k?mc?m 。利用模型(7)在mc中選擇k條對網(wǎng)絡(luò)代數(shù)連通性影響最大的邊。在解模型(7)時，可以采取梯度下降法求得最優(yōu)解，目標(biāo)函數(shù)的梯度為，代數(shù)連通性函數(shù)λ2(L(xl))對 xl的偏導(dǎo)數(shù)為，其中l(wèi)～(i, j)。

貪婪策略的啟發(fā)性步驟如下：

(1) 計算復(fù)雜網(wǎng)絡(luò)中邊的介數(shù)；

(2) 根據(jù)中心性測度選出mc條邊作為候選刪除邊，通過刪邊學(xué)習(xí)器模型刪除k條邊。

由于算法需要計算邊的介數(shù)，只是在一次刪除邊的數(shù)量上有不同，算法的時間復(fù)雜度較高。

3 基于邊中心性測度的割邊模型

定義1 社會網(wǎng)絡(luò)的邊集中刪除一個使該網(wǎng)絡(luò)代數(shù)連通性下降最快的邊稱為中心邊，邊所具有的性質(zhì)稱為邊中心性（Edge Centrality）。

定義2 社會網(wǎng)絡(luò)中處于每個社區(qū)核心位置的節(jié)點稱為中心節(jié)點。

基于邊中心性測度的割邊模型（ECCM）與傳統(tǒng)的社會網(wǎng)絡(luò)發(fā)現(xiàn)算法不同，模型采取譜分析方法對每條邊定義邊中心性測度，與傳統(tǒng)的利用最短距離，隨機游走和節(jié)點間的阻抗不同，速度更快，更適合處理大規(guī)模社區(qū)結(jié)構(gòu)。刪除譜中心性最高的節(jié)點，然后重新計算剩余節(jié)點的譜中心性?？焖購?fù)雜網(wǎng)絡(luò)割邊模型算法描述如下：

(1) 計算G中每條邊的譜中心性測度；

(2) 找到譜中心性最高的邊l，刪除那條邊；更新復(fù)雜網(wǎng)絡(luò)為Gnew。

本模型邊的中心性測度是基于代數(shù)連通性函數(shù)給出的。代數(shù)連通性函數(shù)的梯度為，其中l(wèi)～(i, j)，與第二節(jié)方法相同。

4 實證分析

(1)真實網(wǎng)絡(luò)實驗

在實驗中，采用了真實網(wǎng)絡(luò)中的football網(wǎng)絡(luò)，115個節(jié)點、613條邊。分別采用隨機刪除一條邊、GN方法刪除介數(shù)值最大的邊、GACEM方法刪除k條邊和ECCM方法；實驗結(jié)果如圖3所示。football網(wǎng)絡(luò)的初始λ2為1.459001，隨機刪除120條邊，λ2仍然大于1；GN方法，刪除60條介數(shù)值最大的邊后λ2為 0，網(wǎng)絡(luò)被成功分割，但割邊時間較長；GACEM 方法刪除 23次后λ2為 0，網(wǎng)絡(luò)被成功分割，割邊時間較GN短，ECCM方法時間更快，后三種方法的分割結(jié)果完全一致，即準(zhǔn)確率得到驗證；實驗結(jié)果如圖1所示。

圖1 真實網(wǎng)絡(luò)割邊模型比較

圖2 模擬網(wǎng)絡(luò)割邊模型比較

(2)模擬網(wǎng)絡(luò)實驗

模擬網(wǎng)絡(luò)的pout值為0.1，1000個節(jié)點，7572條邊。網(wǎng)絡(luò)的初始λ2為0.919444，隨機刪除80條邊，λ2仍然大于0.8；GN方法，刪除25條介數(shù)值最大的邊后λ2為0，網(wǎng)絡(luò)被成功分割，但割邊時間較長；GACEM方法刪除8次后λ2為0，網(wǎng)絡(luò)被成功分割，割邊時間較GN短，ECCM方法時間最快，分割結(jié)果一致；實驗結(jié)果如圖2所示。

(3)模型復(fù)雜度分析

傳統(tǒng)的GN分割算法在每次迭代過程中刪除一條邊中心性最高的邊，每次迭代算法的時間復(fù)雜度為O(n2m)，其中n為節(jié)點數(shù)量，m為邊數(shù)量。與之相較，復(fù)雜網(wǎng)絡(luò)被分割為兩個非連通子圖前，譜優(yōu)化社區(qū)發(fā)現(xiàn)模型每次迭代通過割邊學(xué)習(xí)模型刪除k條邊，基于Lanczos算法計算拉普拉斯矩陣第二小特征值對應(yīng)的特征向量（費德勒向量），時間復(fù)雜度為O(m1×n)，其中m1為算法迭代的次數(shù)，通常要上百次，該算法空間復(fù)雜度較高，需要存儲m1個n維的 Lanczos向量；然后基于費德勒向量為每條邊計算其譜中心性測度，算法時間復(fù)雜度為O(m)；從中刪除一條譜中心性最高的邊時間復(fù)雜度為O(m)；使用代數(shù)連通性函數(shù)λ2(L(Gnew))計算更新后網(wǎng)絡(luò)的代數(shù)連通函數(shù)，基于Gossip算法的時間復(fù)雜度為O(m2×log(n))，其中m2為算法迭代次數(shù)m2為常數(shù)。所以割邊學(xué)習(xí)模型執(zhí)行一次操作的時間復(fù)雜度為當(dāng)復(fù)雜網(wǎng)絡(luò)被分割為兩個非連通子圖時，算法在每個非連通子圖中遞歸執(zhí)行，如果并行地在每個子圖中執(zhí)行割邊模型，算法執(zhí)行效率更會顯著提升。

5 結(jié)論

拉普拉斯矩陣的第二小特征值決定復(fù)雜網(wǎng)絡(luò)的連通性，當(dāng)該值為零時，網(wǎng)絡(luò)被二分。傳統(tǒng)的割邊模型時間復(fù)雜度高，為了降低時間復(fù)雜度，基于代數(shù)連通性提出了貪婪譜優(yōu)化割邊模型和基于邊中心性測度的割邊模型，通過對真實網(wǎng)絡(luò)和模擬網(wǎng)絡(luò)的實驗，割邊模型使得時間復(fù)雜度降低同時，分割結(jié)果與GN一致。但模型是否適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)、如何把兩個模型結(jié)合起來進一步降低時間復(fù)雜度，值得今后進一步深入研究。

[1]Charu, C., Aggarwal. Social Network Data Analytics[M].Springer Science + Business Media, LLC (2011).

[2]Girvan M, Newman M E J. Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[3]Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9):2658-2663.

[4]Chen J, Yuan B. Detecting functional modules in the yeast protein–protein interaction network[J]. Bioinformatics,2006, 22(18):2283-2290.

[5]Fortunato S, Latora V, Marchiori M. Method to find community structures based on information centrality[J].Phys. Rev. E, 2004, 70(5):056104.

[6]Clauset, M.E.J. Newman, C. Moore, Finding community structure in very large networks, Phys. Rev. E 70 (6),2004, 066111.

[7]J. Duch, A. Arenas, Community detection in complex networks using extremal optimization, Phys. Rev. E 72(2), 2005, 027104.

[8]J.-P. Eckmann, E. Moses, Curvature of co-links uncovers hidden thematic layers in the World Wide Web, Proc. Natl.Acad. Sci. USA 99 (2002) 5825-5829.

[9]Capocci, V.D.P. Servedio, G. Caldarelli, F. Colaiori, Detecting communities in large networks[J], Physica A 352,2005, 669-676.

[10]H. Zhou, R. Lipowsky, Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities[J], Lect. Notes Comput. Sci. 3038, 2004, 1062-1069.

[11]Thomas Richardson, Peter J. Mucha, and Mason A. Porter.Spectral tripartitioning of networks[J]. Physical Review E,2009, 80(3):036111:89.

[12]Ren-Cang Li. Accuracy of Computed Eigenvectors via Optimizing a Rayleigh Quotient[J]. BIT Numerical Mathematics 2004,44(3) :585-593.

[13]S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Gossip algorithms: Design, analysis and applications[J], Proceedings of IEEE Infocom ,2005, 3:1653-1664.

[14]Z. Xia, Z. Bu, Community detection based on a semantic network[J], Knowledge Based Systems, 2012, 26:30-39.

[15]Y. Kim and M. Mesbahi, On maximizing the second smallest eigenvalue of a state-dependent graph laplacian[J], IEEE Transactions on Automatic Control, 2006,51(1):116-120.