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

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

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

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

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

圖1 4節(jié)點子圖定義結構圖

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

1.1 3PS算法及其誤差分析

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

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

(1)

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

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

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

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

(2)

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

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

(3)

(4)

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

(5)

由于樣本sk由隨機采樣而得,因此mi服從二項分布

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中隨機采樣出節(jié)點w;

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

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

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

(15)

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

(16)

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

1.3 復雜度分析

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

2 C3PS和3PS算法的準確度比較

(17)

3 SmartMoss優(yōu)化算法

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

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

(18)

(19)

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

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

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

步驟8若對圖G的采樣未完成,跳轉至步驟4;

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

4 實驗設計

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

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

表1 實驗數(shù)據(jù)集參數(shù)

4.2 性能指標

(20)

此外,本文根據(jù)定理1和2分析的理論結果,計算估計值的標準方差為

(21)

4.3 本文算法應用及準確度評估

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

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

(b)本文算法測量誤差

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

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

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

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

5 結 論

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