兩階段抽樣法在無標度網絡結構特征量估計中的應用

鄧光明，蘇 健，陳玟宇，賈 貞

(1.桂林理工大學 理學院；2.廣西空間信息與測繪重點實驗室,廣西 桂林 541004)

0 引言

無標度網絡是由美國圣母大學的Barabási和Albert在1999年提出的一個重要網絡模型[1，2]，他們在研究了電力網絡和線粒蟲神經網絡的統計時發現這些網絡的度分布均可用冪律分布來描述，稱此性質為無標度特性。其后的許多研究發現，許多網絡都具有無標度特性，如Internet、WWW、科研合作網絡、在線社交網絡等等。無標度網絡的主要特性是其度分布極不均勻，其少數節點具有很高的度，多數節點的度很低，而這些少數度高的節點（在技術網絡中也稱為hub節點）在網絡中卻十分重要，對網絡中病毒或信息的傳播具有舉足輕重的作用。對這類無標度網絡的抽樣，若采用隨機抽樣法可能導致入樣的節點均為度低的節點，忽略了度高的節點；若采用滾雪球抽樣法、廣度優先算法、隨機游走等抽樣方法，則會導致樣本網絡中的節點偏向于度高的節點，而忽略了度低節點，這樣獲得的樣本網絡難以估計完全網絡的真實特征。本文對上述抽樣方法進行改進，針對BA無標度網絡的度分布不均勻特性，設計一種改進的兩階段抽樣方法[3，4]。用此方法進行抽樣，使得原始網絡中的高度節點和低度節點都以一定比例入樣，因此能根據網絡的結構特點控制不同度的節點的入樣率，從而所得到的樣本網絡能更好地估計完全無標度網絡的結構特性。

1 兩階段抽樣方法

由于BA無標度網絡中大部分節點為低度節點，為了避免抽樣時僅抽到低度的節點，而忽略了網絡中具有重要地位的高度節點，本文提出使用兩階段抽樣法，將低度節點和高度節點都以一定比例選入樣本網絡，具體算法如下：

第一步，在規模為N的初始網絡G中不重復隨機抽取ρN個節點為第一階段抽樣，其中ρ為第一階段抽樣率，得到的樣本記為樣本Ⅰ；

第二步，在樣本Ⅰ中隨機取δρN個節點進行向前一步隨機游走，得到新的δρN個節點作為樣本Ⅱ，這為第二階段抽樣；

第三步，將樣本Ⅰ與樣本Ⅱ節點合并為為兩階段抽樣的樣本節點，加上這些節點之間的原始邊，即得到兩階段抽樣的樣本網絡Gs，樣本容量不超過(1+δ)ρN。

根據此算法可知，樣本Ⅰ代表網絡中度較低的節點。根據Cohen等[5]提出的，在給定網絡中，沿著隨機選擇的一條邊到達某特殊節點的概率與此特殊節點的度數成正比，度越高的節點選入樣本Ⅱ的概率越大，因此樣本Ⅱ代表網絡中度較高的節點。所以，低度節點入選的比例約為ρ，高度節點入選的比例約為δρ。我們可以用參數ρ和δ來控制兩類節點的入樣率。由于樣本Ⅱ的節點是原節點進行向前一步隨機游走得到的節點，因此樣本Ⅱ的節點可能為ρN個節點外的節點，也可能是樣本Ⅰ中的節點，即有少數節點可能被重復抽中，因此最終得到的樣本的樣本量n≤(1 +δ) ρN 。

2 網絡的生成與結構參量

2.1 初始BA無標度網絡的生成

初始網絡為BA無標度網絡，其構造算法[6]為：

（1）增長：從一個具有m0個節點的連通網絡開始，每次引入一個新的節點并且連到m個已存在的節點上。

（2）優先連接：一個新節點與一個已存在的節點i相連接的概率∏i與節點i的度ki之間滿足如下關系

根據上述算法，本文生成3個初始網絡 G1，G2，G3，取每個網絡的網絡規模N=10000，m0=100，m分別取m=20，m=50，m=80。m越大初始網絡中，節點的平均度越大，且相比于m較小的初始網絡，其度小的節點數越少。

2.2 網絡的結構特征量

本文選取下面三個典型的網絡結構特征量來進行樣本估計并評價估計結果。

（1）冪率度分布：完全BA無標度網絡的度分布是服從冪率分布的[7,8]，即度分布具有形式 P(k)～k-γ，其中 P(k)是度為k的節點的經驗概率，也就是網絡中一個隨機選擇的節點的度為k的概率，γ＞0為冪指數，許多實際的無標度網絡的冪指數一般介于2與3之間，網絡的度分布圖在雙對數坐標下大致呈線性形式。下文中我們將進行抽樣模擬，用樣本網絡來估計完全網絡的冪率度分布的冪指數。

（2）聚類系數：網絡的聚類系數C定義為：

（3）節點度相關性：網絡的度相關性是衡量網絡中任意兩個節點之間連邊概率是否與這兩個節點的度值有關的指標。一般地，網絡的度相關性可以使用圖形來描繪，即在雙對數二維坐標中繪制度為k的節點的相鄰節點的平均度數knn隨k的變化情況。當knn隨k的增大而增大時，稱網絡是度正相關的，即總體上度大的節點傾向于連接度大的節點；當knn隨k的增大而減小，則稱網絡是度負相關的，即度大的節點傾向于連接度小的節點；當knn不隨k的變化而顯著變化時，稱網絡不具有度相關性。平均度數knn定義為：

其中ki指的是度為k的節點的第i個鄰居節點的度。

3 抽樣模擬與結果分析

在抽樣模擬中，對于每個初始網絡，設置抽樣率ρ分別為ρ=0.2，ρ=0.5，ρ=0.8高度節點入樣控制δ分別取δ=0.2，δ=0.5δ=0.8?？紤]到抽樣隨機因素的影響，對每個初始網絡在每一組參數(ρ，δ)下重復抽樣50次取平均結果。

圖1考察網絡的冪率度分布的估計效果。圖1（a）—（c）是在固定δ（δ=0.5），而 ρ取不同值，在不同的初始網絡中進行抽樣的子網絡度分布圖。圖1（d）—（f）是固定ρ（ρ=0.5），而δ取不同值下抽樣所得子樣本網絡的度分布圖。從圖1可以看出，每個圖中的4條線基本都呈平行狀態，表明各參數組合下的樣本網絡都能估計出初始網絡服從冪率度分布。我們進下用最小二乘法獲得各分布的冪指數的估計值，見表1所示。需要指出的是，通常很難看到在度的整個取值范圍內都很好地服從冪律分布的網絡，我們提到某個網絡具有冪率分布時，往往指的是當度值較大時分布近似具有冪律形式[9]。因此本文估計的是線性部分的冪律指數。結果顯示，所有樣本的γ值都在2與3之間，能很好地反映初始網絡的度分布情況，且隨著ρ的增加，樣本對冪指數的估計越接近于初始樣本。樣本網絡尾部呈現“波浪”狀態，這取決于初始網絡的形態。取其它參數組合所得樣本的結論一樣?？偟膩碚f，對于冪率度分布，兩階段抽樣能較好地估計初始網絡的總體形態，尤其是對網絡的中度節點的估計。隨著ρ和δ增加，樣本網絡對冪率度分布的估計效果更好。

圖1 樣本網絡與初始網絡的度分布比較圖

圖2考察的是聚類系數的估計效果。圖2中的星形點為各抽樣參數組合(ρ，δ)下在不同的m所對應的初始網絡中，抽取的50個樣本網絡的聚類系數的均值，水平虛線為初始網絡的聚類系數。當m=20，50，80時，初始網絡的聚類系數分別為：0.0218，0.0296,0.0387，即隨著m的增大，初始網絡的聚類系數也增大。抽樣結果表明，當ρ較小時，隨著δ的增加，樣本網絡會大大高估初始網絡的聚類系數；當ρ較大時，樣本網絡隨著δ的增加，其聚類系數則越接近于初始網絡的聚類系數，估計效果顯著增強。綜合來看，提高第一階段抽樣率更有利于樣本對初始網絡聚類系數的估計，且隨著總抽樣率的增加，樣本網絡的聚類系數越接近于初始網絡。此外，樣本網絡的聚類系數都大于初始網絡，這是因為兩階段抽樣法能使hub節點更易入樣，某個節點的任意兩個鄰居節點的連邊概率更高，因此樣本網絡的聚類系數略高于初始網絡的聚類系數。

圖2 樣本網絡與初始網絡的平均聚類系數比較圖

圖3考察的是節點度相關性的估計效果。圖3（a）—（c）和（d）—（f）分別為 δ=0.5和 ρ=0.5時，不同 ρ和 δ在不同初始網絡下得到的樣本網絡的度相關圖。圖3顯示，3個初始網絡的knn都近似常數，即節點的連邊概率和節點的度沒有明顯的正負相關關系。在m=20的初始網絡中，knn出現“斷層”，表明網絡中有部分孤立節點。模擬結果表明，不論何種參數組合下的樣本，都能大致估計初始樣本不具有度相關性。但樣本對初始網絡knn值的估計效果對于ρ值的變動較敏感，尤其當ρ=0.2時，樣本會大大低估初始網絡的knn值，而 ρ=0.5和 ρ=0.8的估計效果相差不大，因此，當考慮抽樣成本時，取ρ=0.5便可以得到較好的knn值估計。相比而言，樣本對knn值的估計效果對于δ的變動則不是十分敏感?？偟膩碚f，兩階段抽樣法能較準確地估計初始網絡的度相關性，但樣本網絡的估計值略低于初始網絡的knn值。

圖3 樣本網絡與初始網絡的度相關性比較圖

4 樣本穩定性評價

方差的大小決定著樣本的穩定性，抽樣平均誤差的大小決定著樣本對總體推斷結論的準確程度。本文在m=50的初始網絡中，計算各參數組合下50個樣本網絡的冪指數γ的方差和抽樣平均誤差，用以評價不同參數組合的樣本對總體的估計效果。修正樣本方差定義為：

其中n為樣本個數，γi為第i個樣本網絡的冪指數，為50個樣本網絡的冪指數均值。抽樣平均誤差定義為：

從計算結果（表2）中可以看出，(0.8，0.5)組合下的樣本方差和抽樣平均誤差最小，抽樣最穩定，結合表1也看出，該組合下的冪指數估計也較接近初始網絡，(0.5，0.8)組合下的樣本穩定性次之。評價結果表明，樣本的穩定性較好，而且穩定性與樣本量的大小呈較明顯的正相關關系。實際抽樣中，我們可以根據實際條件參照上述估計效果對參數組合(ρ，δ)進行取值。

表2 樣本網絡的樣本方差和抽樣平均誤差

[1]Barabási A-L,Albert R.Emergence of Scaling in Eandom Networks[J].Science,1999,286(5439).

[2]Barabási A-L:Scale-free Networks:A Decade and Beyond[J].Science,2009,325(5939).

[3]李勇，黃霞，侯志強.兩階段抽樣調查的平衡兩層次樣本輪換研究[J].統計與決策，2009,（19）.

[4]賀建風.基于二階段抽樣的雙重抽樣框估計量設計[J].統計與決策，2011,（15）.

[5]Cohen R,Havlin S,Avraham D B.Efficient Immunization Strategies for Computer Networks and Populations[J].Physical Review Letters,2003,91(24).

[5]汪小帆，李翔，陳關榮.網絡科學導論[M].北京：高等教育出版社，2012.

[6]Albert R,Jeong H,Barabási A-L:Diameter of the World Wide Web[J].Nature,1999,401(6749).

[7]Barabási A-L,Albert R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439).