大規(guī)模網(wǎng)絡(luò)中k-點連通分量發(fā)現(xiàn)算法研究

何瀛龍 王夢博 白雨 李源

（北方工業(yè)大學(xué)信息學(xué)院 北京市 100144）

1 引言

在大規(guī)模的網(wǎng)絡(luò)分析中，分量檢測是非常重要的問題之一。發(fā)現(xiàn)高度連通的分量可以幫助我們解決許多現(xiàn)實生活中的實際問題，例如，社會網(wǎng)絡(luò)群體的結(jié)構(gòu)凝聚力是研究社會群體凝聚力的重要的社會學(xué)指標(biāo)；從城市網(wǎng)絡(luò)中發(fā)現(xiàn)了凝聚子群進而研究影響因素以及措施；在信息傳播中能描述出網(wǎng)絡(luò)核心位置，有助于發(fā)現(xiàn)信息傳播中的關(guān)鍵節(jié)點。

本文主要研究k-點連通分量（k-VCC），k-VCC 和社會學(xué)中的結(jié)構(gòu)凝聚力概念是等價的，除此之外k-VCC 還有許多重要的特征。首先根據(jù)惠特尼定理，k-VCC 被包含在k-核（k-core）和k-邊連通分量（k-ECC）之中，因此k-VCC擁有著k-core 和k-ECC 的所有結(jié)構(gòu)特性，更具有凝聚力。k-VCC 允許分量之間允許重疊，在真實復(fù)雜網(wǎng)絡(luò)中分量重疊也是重要且自然的特征。

給定圖G 和一個整數(shù)k，如何計算出G 的所有k-VCCs?，F(xiàn)有算法一般思路是，將圖G 遞歸地劃分為重疊的子圖。若G 不是k-VCC，則找到一組小于k 的點割集對G 進行劃分。這種自頂向下的框架的關(guān)鍵在于最小點割集的計算，可以轉(zhuǎn)化為對局部連通度的測試，也就是判斷兩個頂點u,v 是否能從G 中移除最多k-1 個點使得u,v 之間不連通。局部連通度的測試?yán)镁W(wǎng)絡(luò)流算法可以實現(xiàn)。而為了找到圖中一組小于k 的點割集，在最壞情況下將對圖G 的每對頂點都進行局部連通度的測試，若在規(guī)模較大的圖中，這樣做在時間上的開銷是高昂的。Dong等人提出了一種減少局部連通度測試次數(shù)的優(yōu)化。Li等人提出了一種基于自底向上框架的近似解。Sinkovits等人針對于k 為2 或3 的小參數(shù)設(shè)計了特殊的算法。

事實上，通過觀察發(fā)現(xiàn)，在大規(guī)模的網(wǎng)絡(luò)分析中，往往沒有必要得到完全正確的結(jié)果，很多時候一個近似解便已經(jīng)能很好的完成任務(wù)。在現(xiàn)有算法的框架上，本文設(shè)計了一種基于蒙特卡羅（概率采樣）的近似算法，可以高效計算出所有k-VCCs，并且結(jié)合實驗對誤差進行了分析。

2 基本概念及相關(guān)定義

本節(jié)主要介紹一些基本概念及其符號表達(dá)，闡述了k-點連通圖的相關(guān)定義，并對要解決的主要問題給出具體定義。

2.1 基本概念

本文中給定一個無向圖G(V,E)，V 表示圖的頂點集合，E 表示圖的邊集合，n 表示圖的頂點數(shù)即|V|，m 表示圖的邊數(shù)即|E|。

定義1 (點割集)：對于連通圖G，若V'?V 且G[VV']不是連通圖，則V'是圖G 的一個點割集。基于點割集的大小，提出了點連通度的定義。

定義2 (點連通度)：圖G 的點連通度定義為最小的點割集的大小，記作κ(G)。接來下給出局部點連通度的定義。

定 義3 ( 局 部 連 通 度)：對 于 圖G 以 及u,v∈V 滿 足u ≠v，u 可達(dá)v，若V'?V，u,v?V'，且在G[VV']中u 和v不連通，則V'被稱作u 到v 的點割集。u 到v 的最小點割集的大小被稱作u 到v 的局部連通度，記作κ(u,v)。當(dāng)不存在這樣的點割集時κ(u,v)=+∞。局部連通度和點連通度的關(guān)系為對于所有頂點u,v∈V,κ(G)≤κ(u,v)。 接來下給出k-點連通的定義。

定義4 (k-點連通)：圖G 是k-點連通圖如果滿足條件：

（1）|V|≥k+1；

（2）圖G 不存在大小為k-1 的點割集。

顯然有κ(G)≥k 成立。接下來給出k-點連通分量的定義。

定義5 (k-點連通分量)：圖G 的子圖g 是G 的k-點連通分量如果滿足條件：

（1）g 是k-點連通的；

（2）不存在g 的超圖是k-點連通的。

本文以k-VCC 作為縮寫。

2.2 問題定義

問題1：給定一個無向圖G(V,E)，近似計算出它的所有k-VCCs。

3 精確算法

本節(jié)將詳細(xì)介紹自頂向下檢測框架，該框架的主要思想如下。如果圖G 是k-點連通的，那么圖G 是一個k-VCC，否則存在一個符合條件的點割集S，S 的大小小于k。在這種情況下，可以計算出這個S 并用S 對G 劃分。劃分的過程重復(fù)迭代進行直到剩余的每一個子圖全都是k-VCC。

首先根據(jù)文獻證明了這種重疊劃分以及k-VCC 的數(shù)量上界為n/2，這表明這種算法是多項式時間復(fù)雜度的。

根據(jù)惠特尼定理，一個k-VCC 是必須被包含在一個k-core（圖中最小度不小于k）之中的，所以在算法開始前先預(yù)先計算出k-core 以減小圖的規(guī)模。

一個重要的問題是，如何計算出圖G 的最小點割集。根據(jù)文獻可以將問題轉(zhuǎn)化為有向圖上求最大流的問題。這個過程首先需要確定源點s 和匯點t，然后將原圖轉(zhuǎn)化為有2n 個頂點n+2m 的邊且邊的容量都為1 的有向流圖，這樣求出的最大流即κ(s,t),s 與t 的局部連通度。若對于?s,t∈V，κ(G)=min(κ(s,t) )。根據(jù)文獻可以找出圖中有最小度為δ的點u，然后討論u 不在最小點割集與在最小點割集中的兩種情況，前者固定u 為源點，枚舉其余頂點作為匯點即可。后者將源點和匯點在u 的鄰居中兩兩枚舉即可。

總的時間復(fù)雜度為O(n·(n+δ)·min(n,k)·m)。其中O(n)是重疊劃分的次數(shù)，O(n+δ)是調(diào)用局部連通度計算的次數(shù)，O(min(n,k)·m)是計算局部連通度的時間。

4 近似算法

現(xiàn)有算法的瓶頸之處在于：在大規(guī)模圖發(fā)現(xiàn)一個小于k的點割集的時間開銷中非常高，根源便在于需要測試的局部連通度次數(shù)為O(n+δ)，這個次數(shù)很多并且非常依賴于圖的最小度，最壞情況下精確算法會退化到暴力枚舉頂點對的情況。在基于現(xiàn)有精確算法的框架上，筆者采用蒙特卡羅的思想，對源點s 和匯點t 進行均勻采樣。當(dāng)采樣的次數(shù)足夠多時，可以發(fā)現(xiàn)這樣的點割集的概率也就越大，后面將說明當(dāng)k 與n 相差較大時，這個概率是非常優(yōu)秀的。

如果圖G 是一個k-VCC，則不存在小于k 的點割集，所以本節(jié)討論如果圖G 不是一個k-VCC 的情況。假設(shè)圖G只有一個點割集S 大小為w 且w

定理1 單次采樣中s 與t 都不屬于S 的概率為：Pr(s,t?S)=(n-w)/n。證明 令E為從V 中隨機選取一個頂點的事件，E為頂點不屬于S 的事件。根據(jù)條件概率公式，隨機選取一個頂點不屬于S 的概率為Pr(E|E)=Pr(EE)/Pr(E)。由于是本節(jié)采用均勻采樣，則每個點被采樣到的概率是相同的。顯然E與E之間相互獨立，有Pr(E|E)=Pr(E)。根據(jù)古典概率易得：

(Pr(E|E)=Pr(E)=((n-w))/n （1）

單次采樣中s 和t 也是相互獨立的，則Pr(s,t?S)=Pr(E|E)=(n-w)/n成立。

如果僅僅對s,t?S 進行局部連通度測試還不能發(fā)現(xiàn)這個點割集w，因為可能s,t?G[VS]中的同一連通塊之中，也就是說去掉點割集S 并沒有使得s,t 不連通，κ(u,v)不小于k。令E 為單次采樣中，s,t?S 且在G[VS]中s 不可達(dá)t 的事件。

定理2 單次采樣中s 和t 屬于G[VS]中不同連通分量的最小概率為：Pr(E)=4(n-k-1)/n。

證明 因為圖G 被包含在k-core 之中，每個頂點的度數(shù)至少為k，所以去掉點割集S 后產(chǎn)生的最小連通分量大小為k-w+1。在最壞情況下，G[VS]只有兩個連通分量設(shè)為C,C大 小分別為k-w+1 和n-k-1。令E為s 屬于C的事件，E為t 屬于C的事件。根據(jù)公式（2）同理可得Pr(E)=(k-w+1)/n、Pr(E)=(n-k-1)/n。因為E與E相互獨立，則有：

其中C為組合數(shù)。令w=k-1，代入公式（4）即可得到公式（3）。易證，當(dāng)圖G 存在多個點割集或者G[VS]有多個連通分量，s,t 屬于G[VS]不同連通分量的概率不會小于Pr(E)。

表1： 統(tǒng)計數(shù)據(jù)集

對屬于G[VS]中不同連通分量的s 和t 進行局部連通度測試可以發(fā)現(xiàn)點割集S，所以單次采樣可以判定出圖G 不是一個k-VCC 的最小概率就是4(n-k-1)/n。

定理 3 采樣T 次后都不能發(fā)現(xiàn)點割集S 的最小概率為ε=(1-Pr(E) )。

將ε 固定，近似算法框架為，在判定圖G 是否為一個k-VCC 時，T 為近似算法計算局部連通度的次數(shù)，T'為精確算法計算局部連通度的次數(shù)，則min(T,T')可作為計算局部連通度的次數(shù)上界。當(dāng)T

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

本節(jié)通過在不同真實數(shù)據(jù)集上進行實驗評估概率采樣算法的效率和有效性。本文提出的所有算法均采用C++語言實現(xiàn)，以用-O3 等級優(yōu)化的GCC 9.20 編譯。所有實驗均在Windows 機器上運行，機器的配置為AMD Ryzen 3.20 GHz，16GB 內(nèi)存。

5.1 實驗數(shù)據(jù)集和參數(shù)設(shè)定

本節(jié)用VCCE 表示第3 節(jié)中提出的精確算法，VCCE表示第4 節(jié)中提出的近似算法。

在實驗中本節(jié)設(shè)近似算法的ε 為0.05，即最壞情況下會將一個不是k-VCC 的圖誤判為k-VCC 的概率為5%。

5.2 算法運行效率分析

本小節(jié)研究VCCE 和VCCE在不同的真實網(wǎng)絡(luò)上發(fā)現(xiàn)k-VCC 的運行效率。圖1 給出了兩種算法對于不同的k 的總體運行時間。從圖1 中可以發(fā)現(xiàn)，VCCE在所有數(shù)據(jù)集中的運行效率都高于VCCE，并且運行時間差距很大。如果遇到近似算法退化時，即n,k 相差很小時所需計算局部連通度的次數(shù)可能會超過精確算法，近似算法框架便采用精確算法。由此可見，VCCE的運行時間不會超過VCCE。

圖1： 不同真實數(shù)據(jù)集的運行效率

隨著k 的增加，這些算法的運行時間呈下降趨勢。這是因為，首先如果給定一個較大的k 值，由于受到k-core 的約束，有許多節(jié)點會在預(yù)處理階段被過濾掉，所以圖的規(guī)模會減小。其次是k 增大這表明更容易發(fā)現(xiàn)一組小于k 的點割集，這意味著圖更有可能被分割為更小的子圖。

5.3 算法有效性分析

本小節(jié)研究VCCE在不同真實網(wǎng)絡(luò)上發(fā)現(xiàn)k-VCC 的有效性。對于同一個圖G 和參數(shù)k，筆者以VCCE 計算出的所有k-VCCs 作為標(biāo)準(zhǔn)，然后與VCCE的計算結(jié)果進行對比。實驗結(jié)果如表2，其中k～k為5.2 節(jié)中參數(shù)k 的設(shè)定。大量實驗的結(jié)果表明VCCE發(fā)現(xiàn)的k-VCCs 正確率基本與理論相符，并且表現(xiàn)非常優(yōu)異。這是因為，雖然最壞情況下會有5%的概率會將一個不是k-VCC 的圖誤判，但是當(dāng)樣本集巨大時，圖的形態(tài)均勻分布，Pr(E)的概率會上升，所以在一般情況下誤判的概率其實遠(yuǎn)低于5%，這也說明了VCCE能夠應(yīng)用于大規(guī)模圖分析中。

表2： 不同真實數(shù)據(jù)集下的有效性分析

6 結(jié)束語

本文旨在損失少許精度的情況下高效發(fā)現(xiàn)大規(guī)模網(wǎng)絡(luò)中的所有k-VCCs。首先歸納了現(xiàn)有的算法框架，指出了其瓶頸所在。其次在現(xiàn)有框架上提出了一種基于概率采樣的近似算法，給出了誤差分析與證明，結(jié)論得出在k 與n 相差較大的時候效率很高。最后筆者在三個真實網(wǎng)絡(luò)數(shù)據(jù)集上進行了大量的實驗，運行效率分析中近似算法均高于精確算法，而且在大規(guī)模網(wǎng)絡(luò)中k 較小時即k 與n 相差較大，這恰巧是精確算法最薄弱的地方，精確算法花費的時間是巨大的。而近似算法卻能很好的完成任務(wù)。有效性分析中，近似算法所發(fā)現(xiàn)的k-VCCs 幾乎與精確算法的一致。實驗說明了本文提出的近似算法在實際應(yīng)用中具有巨大的實踐價值。