何瀛龍 王夢(mèng)博 白雨 李源
(北方工業(yè)大學(xué)信息學(xué)院 北京市 100144)
在大規(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)行了分析。
本節(jié)主要介紹一些基本概念及其符號(hào)表達(dá),闡述了k-點(diǎn)連通圖的相關(guān)定義,并對(duì)要解決的主要問(wèn)題給出具體定義。
本文中給定一個(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 作為縮寫。
問(wèn)題1:給定一個(gè)無(wú)向圖G(V,E),近似計(jì)算出它的所有k-VCCs。
本節(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í)間。
現(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 本節(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)存。 本節(jié)用VCCE 表示第3 節(jié)中提出的精確算法,VCCE表示第4 節(jié)中提出的近似算法。 在實(shí)驗(yàn)中本節(jié)設(shè)近似算法的ε 為0.05,即最壞情況下會(huì)將一個(gè)不是k-VCC 的圖誤判為k-VCC 的概率為5%。 本小節(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)割集,這意味著圖更有可能被分割為更小的子圖。 本小節(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ù)集下的有效性分析 本文旨在損失少許精度的情況下高效發(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à)值。5 實(shí)驗(yàn)結(jié)果與分析
5.1 實(shí)驗(yàn)數(shù)據(jù)集和參數(shù)設(shè)定
5.2 算法運(yùn)行效率分析
5.3 算法有效性分析
6 結(jié)束語(yǔ)