大規(guī)模網(wǎng)絡(luò)圖中4節(jié)點(diǎn)子圖數(shù)量快速估計(jì)算法

覃遵穎,孫雨,李國棟,齊懷睿,陶敬

(1.西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室,710049,西安;2.西安交通大學(xué) 網(wǎng)絡(luò)信息中心,710049,西安;3.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

在大型復(fù)雜網(wǎng)絡(luò)的子圖集合中,存在著大量包含3～5個節(jié)點(diǎn)的小型無向子圖,這類子圖能夠反映復(fù)雜網(wǎng)絡(luò)的一些基礎(chǔ)結(jié)構(gòu)特性,對此類子圖的數(shù)量進(jìn)行挖掘分析,在生物學(xué)[1-2]、社會學(xué)、社交網(wǎng)絡(luò)[3-6]和萬維網(wǎng)分析[7-8]等領(lǐng)域都有著重要作用。例如,可以將具有特定功能的氨基酸團(tuán)定義為蛋白質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)圖中的一類小型無向子圖[1-2],對這類子圖進(jìn)行數(shù)量統(tǒng)計(jì),是認(rèn)定蛋白結(jié)構(gòu)、推定未知蛋白功能性質(zhì)等工作的前提;類似地,將小規(guī)模用戶之間的關(guān)系抽象為在線社交網(wǎng)絡(luò)中的一類小型無向子圖[9],對這類子圖的數(shù)量進(jìn)行統(tǒng)計(jì),可以為分析在線社交網(wǎng)絡(luò)中社團(tuán)演化、用戶聚類等工作提供思路。特別地,對于惡意代碼網(wǎng)絡(luò)圖[10-12],研究人員可以將任意小規(guī)模的模塊間的調(diào)用關(guān)系抽象為小型無向子圖,對這些子圖進(jìn)行數(shù)量統(tǒng)計(jì),可以推定未知軟件中存在惡意代碼的可能性,且響應(yīng)速度和準(zhǔn)確性都優(yōu)于傳統(tǒng)的文本檢測方法。

Wang等的算法[13]對3節(jié)點(diǎn)子圖數(shù)量的估計(jì)已經(jīng)取得了比較好的性能,然而對于4節(jié)點(diǎn)子圖數(shù)量的估計(jì)仍面臨著較大的挑戰(zhàn),4節(jié)點(diǎn)子圖定義結(jié)構(gòu)如圖1所示。現(xiàn)有的大部分4節(jié)點(diǎn)子圖數(shù)量估計(jì)算法時(shí)間與空間復(fù)雜度過高,在實(shí)際使用中難以實(shí)現(xiàn)。為了解決這一問題,Jha等提出了3PS和C3PS算法[14],該算法使用節(jié)點(diǎn)采樣估計(jì)的方法減小了計(jì)算量,然而卻并未對估算結(jié)果的誤差范圍進(jìn)行嚴(yán)謹(jǐn)?shù)胤治?未能從理論上嚴(yán)謹(jǐn)?shù)淖C明C3PS算法一定能提高3PS算法的估算精度。

圖1 4節(jié)點(diǎn)子圖定義結(jié)構(gòu)圖

1 C3PS算法和3PS算法的誤差分析

1.1 3PS算法及其誤差分析

3PS算法的一次采樣過程主要為5個步驟。

步驟1根據(jù)節(jié)點(diǎn)權(quán)重密度分布π={πv:v∈D},從節(jié)點(diǎn)集D中采樣出節(jié)點(diǎn)v;

(1)

步驟3從節(jié)點(diǎn)v鄰居集合剩下的元素Nv-{u}中隨機(jī)采樣出節(jié)點(diǎn)w;

步驟4從節(jié)點(diǎn)u鄰居集合剩下的元素Nu-{v}中隨機(jī)采樣出節(jié)點(diǎn)r;

步驟5判斷節(jié)點(diǎn)u、v、w、r能夠構(gòu)成的連通生成子圖的種類。

在3PS算法的一次采樣過程中,樣本中節(jié)點(diǎn)u、v的度均要大于等于2,這說明一個4節(jié)點(diǎn)子圖若要被3PS算法采樣到,則其中至少要包含兩個度大于等于2的點(diǎn)。根據(jù)圖1中6種4節(jié)點(diǎn)子圖的結(jié)構(gòu),第2種4節(jié)點(diǎn)子圖中僅包含1個度為3與3個度為1的點(diǎn),不符合采樣條件,因此重復(fù)以上步驟K次得到網(wǎng)絡(luò)圖的K子圖采樣,可對第1,3,4,5,6種4節(jié)點(diǎn)子圖的頻數(shù)進(jìn)行采樣估計(jì),估算結(jié)果為

(2)

式中:mi為樣本集K中第i種4節(jié)點(diǎn)子圖的數(shù)量;pi為一次采樣中第i種4節(jié)點(diǎn)子圖能被采樣到的概率,pi=φi/Γ,其中φ1=1,φ2=0,φ3=4,φ4=2,φ5=6,φ6=1,φi為第i種4節(jié)點(diǎn)子圖能被3PS算法采樣到的次數(shù);Λ3為網(wǎng)絡(luò)圖中度為3的點(diǎn)的數(shù)量。

3PS算法的估算誤差滿足如下定理。

(3)

(4)

證明記P(X)為事件X成立的概率,Gsk為樣本sk中4節(jié)點(diǎn)所能構(gòu)成的連通生成子圖的種類。當(dāng)事件Y為真時(shí),記A(Y)=1,當(dāng)事件Y為假時(shí),記A(Y)=0,則對于i∈{1,3,4,5,6},且k≤K,有

(5)

由于樣本sk由隨機(jī)采樣而得,因此mi服從二項(xiàng)分布

x=0,…,K

(6)

mi的期望與方差分別為

(7)

(8)

Λ3-n4-2n5-6n6=n2

(9)

(10)

其中

C(A(Gsk=i),A(Gsl=j))=

E(A(Gsk=i)A(Gsl=j))-

E(A(Gsk=i))E(A(Gsl=j))=

0-pinipjnj=-pinipjnj

(11)

(12)

(13)

1.2 C3PS算法及其誤差分析

C3PS算法的一次采樣過程同樣為5個步驟。

(14)

步驟3從Nv,u中隨機(jī)采樣出節(jié)點(diǎn)w;

步驟4從Nu,v中隨機(jī)采樣出節(jié)點(diǎn)r;

步驟5獲取節(jié)點(diǎn)u,v,w,r構(gòu)成連通的生成子圖種類。

在C3PS算法的一次采樣過程中若要采樣到一個4節(jié)點(diǎn)子圖,則其中至少要有兩個點(diǎn)滿足其Nu,v集合不為空。根據(jù)圖1中4節(jié)點(diǎn)子圖的結(jié)構(gòu),僅有第3,5,6種4節(jié)點(diǎn)子圖符合采樣條件。因此,C3PS算法通過重復(fù)以上步驟得到K子圖采樣,對第3,5,6種4節(jié)點(diǎn)子圖數(shù)量估計(jì)如下

(15)

C3PS算法的估算誤差滿足如下定理。

(16)

其證明與定理1類似,不再贅述。

1.3 復(fù)雜度分析

3PS算法的復(fù)雜度主要來自于采樣算法的前4個步驟。步驟1中,為了計(jì)算出所有節(jié)點(diǎn)的采樣權(quán)重,其復(fù)雜度為O(|L|),L為網(wǎng)絡(luò)圖中邊的集合。步驟2中,為了能夠根據(jù)節(jié)點(diǎn)的采樣權(quán)重采樣出節(jié)點(diǎn)v,其復(fù)雜度為O(lg|D|),D為網(wǎng)絡(luò)圖中節(jié)點(diǎn)的集合。步驟3中,從v的鄰居集中采樣出節(jié)點(diǎn)u,所需要的計(jì)算復(fù)雜度是O(lg|dv|)。最后,對節(jié)點(diǎn)w進(jìn)行采樣的計(jì)算復(fù)雜度為O(1)。因此,3PS算法的計(jì)算復(fù)雜度為O(|L|+Klg|D|),K為樣本集的大小。

2 C3PS和3PS算法的準(zhǔn)確度比較

(17)

3 SmartMoss優(yōu)化算法

本文設(shè)計(jì)了一種性能更好的4節(jié)點(diǎn)子圖數(shù)量估計(jì)SmartMoss算法。

首先介紹本文算法對i=3,5,6這3種4節(jié)點(diǎn)子圖數(shù)量的估計(jì)算法。由于3PS和C3PS兩個采樣器均可以對這3種4節(jié)點(diǎn)子圖數(shù)量進(jìn)行估計(jì),定義如下

(18)

(19)

步驟1讀入網(wǎng)絡(luò)圖G;

步驟2設(shè)定最大誤差參數(shù)Smax,最大樣本集參數(shù)Kmax;

步驟6若2|L|2/lg|L|≥Kp,則采用3PS算法對圖G進(jìn)行采樣,跳轉(zhuǎn)至步驟8;

步驟8若對圖G的采樣未完成,跳轉(zhuǎn)至步驟4;

步驟9根據(jù)3PS算法和C3PS算法的估計(jì)結(jié)果,混合估計(jì)網(wǎng)絡(luò)圖中各4節(jié)點(diǎn)子圖數(shù)量,并計(jì)算相應(yīng)估計(jì)誤差。

4 實(shí)驗(yàn)設(shè)計(jì)

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

本文在多個真實(shí)數(shù)據(jù)集上對理論分析結(jié)果以及本文算法的性能進(jìn)行了測試,實(shí)驗(yàn)數(shù)據(jù)集來自Standard大學(xué)網(wǎng)絡(luò)數(shù)據(jù)分析平臺(SNAP)。表1詳細(xì)給出了實(shí)驗(yàn)所用數(shù)據(jù)集的性質(zhì)和特點(diǎn)。

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

4.2 性能指標(biāo)

(20)

此外,本文根據(jù)定理1和2分析的理論結(jié)果,計(jì)算估計(jì)值的標(biāo)準(zhǔn)方差為

(21)

4.3 本文算法應(yīng)用及準(zhǔn)確度評估

為了驗(yàn)證本文算法的性能,在SOC-Epinions、SOC-Slashdot08和COM-Amazon這3個網(wǎng)絡(luò)圖上對本文算法進(jìn)行了檢驗(yàn)并對其準(zhǔn)確度進(jìn)行了評估。這3個網(wǎng)絡(luò)圖中分別包含有2.58×1010、2.17×1010和1.78×108個4節(jié)點(diǎn)子圖,且第3,5,6種4節(jié)點(diǎn)子圖的數(shù)量明顯小于其他幾種4節(jié)點(diǎn)子圖。

(a)6種4節(jié)點(diǎn)子圖數(shù)量真實(shí)值

(b)本文算法測量誤差

圖2a中分別給出了實(shí)驗(yàn)所用網(wǎng)絡(luò)圖中6種4節(jié)點(diǎn)子圖數(shù)量的真實(shí)值,圖2b給出了使用本文算法對6種4節(jié)點(diǎn)子圖數(shù)量估算時(shí)的R和S。可以發(fā)現(xiàn),出現(xiàn)頻率較高的4節(jié)點(diǎn)子圖擁有更小的S。在本實(shí)驗(yàn)中,參數(shù)設(shè)定為Smax=0.1,Kmax=105,且實(shí)驗(yàn)重復(fù)1 000次,計(jì)算平均結(jié)果和誤差。實(shí)驗(yàn)結(jié)果表明,本文算法具有較高的準(zhǔn)確性,而且誤差分析的理論結(jié)果S可以準(zhǔn)確地描述實(shí)際的估計(jì)誤差。

4.4 本文算法與3PS和C3PS算法對比

本文算法可以根據(jù)中心極限定理及定理1和2給出的方差分析結(jié)論,估計(jì)達(dá)到預(yù)期的估計(jì)誤差所需要的最小采樣數(shù)。對比3PS算法和C3PS算法中最小采樣數(shù)的估計(jì),實(shí)驗(yàn)證明,本文算法更為準(zhǔn)確。

本文在SOC-Epinions、SOC-Slashdot08和COM-Amazon這3個網(wǎng)絡(luò)圖上對兩種算法進(jìn)行了對比。當(dāng)本文算法滿足S≤0.01時(shí),記預(yù)估所需的最小樣本集大小為Ks,記滿足相同條件時(shí)C3PS和3PS算法所需的最小樣本集大小為Kp。對于SOC-Epinions、SOC-Slashdot08和COM-Amazon這3個網(wǎng)絡(luò)圖,Kp/Ks的值分別為38.6、20.9和17.0,這說明相對本文算法,C3PS和3PS算法的采樣成本高出數(shù)十倍。本文算法性能優(yōu)于3PS算法和C3PS算法。

5 結(jié) 論

本文研究了大型網(wǎng)絡(luò)圖中4節(jié)點(diǎn)子圖的采樣估計(jì)問題,提出了一種新的4節(jié)點(diǎn)子圖采樣估計(jì)SmartMoss算法,并通過實(shí)驗(yàn)對該算法性能進(jìn)行了驗(yàn)證。通過理論分析與實(shí)驗(yàn)驗(yàn)證得出:首先,前沿算法C3PS能否提升3PS算法估算精度以及能提升多少取決于被測網(wǎng)絡(luò)圖的結(jié)構(gòu)特征,C3PS算法并不一定能夠提升3PS算法的估算精度;其次,本文算法通過被測網(wǎng)絡(luò)的結(jié)構(gòu)特性判斷是否有必要使用C3PS算法提升子圖數(shù)量估計(jì)的準(zhǔn)確度,進(jìn)而基于3PS和C3PS兩種算法估算結(jié)果混合估計(jì)網(wǎng)絡(luò)圖中4節(jié)點(diǎn)子圖的數(shù)量。對比實(shí)驗(yàn)同時(shí)證明,本文算法的準(zhǔn)確率顯著高于C3PS算法和3PS算法。