何瀛龍 王夢(mèng)博 白雨 李源

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

1 引言

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

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

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

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

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

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

2.1 基本概念

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

定義1 (點(diǎn)割集)：對(duì)于連通圖G，若V'?V 且G[VV']不是連通圖，則V'是圖G 的一個(gè)點(diǎn)割集?；邳c(diǎn)割集的大小，提出了點(diǎn)連通度的定義。

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

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

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

（1）|V|≥k+1；

（2）圖G 不存在大小為k-1 的點(diǎn)割集。

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

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

（1）g 是k-點(diǎn)連通的；

（2）不存在g 的超圖是k-點(diǎn)連通的。

本文以k-VCC 作為縮寫。

2.2 問(wèn)題定義

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

3 精確算法

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

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

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

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

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

4 近似算法

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

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

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

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

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

如果僅僅對(duì)s,t?S 進(jìn)行局部連通度測(cè)試還不能發(fā)現(xiàn)這個(gè)點(diǎn)割集w，因?yàn)榭赡躶,t?G[VS]中的同一連通塊之中，也就是說(shuō)去掉點(diǎn)割集S 并沒(méi)有使得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。

證明 因?yàn)閳DG 被包含在k-core 之中，每個(gè)頂點(diǎn)的度數(shù)至少為k，所以去掉點(diǎn)割集S 后產(chǎn)生的最小連通分量大小為k-w+1。在最壞情況下，G[VS]只有兩個(gè)連通分量設(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。因?yàn)镋與E相互獨(dú)立，則有：

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

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

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

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

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

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

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

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

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

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

5.2 算法運(yùn)行效率分析

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

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

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

5.3 算法有效性分析

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

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

6 結(jié)束語(yǔ)

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