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

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

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

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

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

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

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

1.1 3PS算法及其誤差分析

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

步驟1根據節(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的點。根據圖1中6種4節(jié)點子圖的結構,第2種4節(jié)點子圖中僅包含1個度為3與3個度為1的點,不符合采樣條件,因此重復以上步驟K次得到網絡圖的K子圖采樣,可對第1,3,4,5,6種4節(jié)點子圖的頻數進行采樣估計,估算結果為

(2)

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

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集合不為空。根據圖1中4節(jié)點子圖的結構,僅有第3,5,6種4節(jié)點子圖符合采樣條件。因此,C3PS算法通過重復以上步驟得到K子圖采樣,對第3,5,6種4節(jié)點子圖數量估計如下

(15)

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

(16)

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

1.3 復雜度分析

3PS算法的復雜度主要來自于采樣算法的前4個步驟。步驟1中,為了計算出所有節(jié)點的采樣權重,其復雜度為O(|L|),L為網絡圖中邊的集合。步驟2中,為了能夠根據節(jié)點的采樣權重采樣出節(jié)點v,其復雜度為O(lg|D|),D為網絡圖中節(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é)點子圖數量估計SmartMoss算法。

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

(18)

(19)

步驟1讀入網絡圖G;

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

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

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

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

4 實驗設計

4.1 數據集

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

表1 實驗數據集參數

4.2 性能指標

(20)

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

(21)

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

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

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

(b)本文算法測量誤差

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

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

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

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

5 結 論

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