負責網絡抽樣研究.pdf

1、自然界中存在的大量復雜系統(tǒng)都可以通過形形色色的網絡加以描述。一個典型的網絡由許多結點與連接結點的邊組成的，其中結點用來代表真實系統(tǒng)中的不同個體，而邊則用來表示個體之間的關系，往往是兩個結點之間具有某種特定的關系則連一條邊，反之則不連邊，有邊相連的兩個結點在網絡中被看作是相鄰的。例如，神經系統(tǒng)可以看作大量神經細胞通過神經纖維相互連接形成的網絡；計算機網絡可以看作是自主工作的計算機通過通信介質如光纜，雙絞線，同軸電纜等相互連接形成的網絡。類

2、似的還有電力網絡，社會關系網絡，科研工作者合作網絡，交通網絡等等。 復雜網絡近年來受到來自科學與工程各個領域研究者越來越多的關注，成為近年來研究的一個熱點。目前，復雜網絡的研究方法包括圖論，隨機圖，平均場等。復雜網絡的研究，例如小世界網絡和BA 網絡等等主要集中于網絡的拓撲結構，研究的問題一般包括：1）給定網絡的生成過程，網絡的拓撲結構特性，比如：度分布，聚集系數等會涌現什么性質？網絡的拓撲結構的相變有哪些？發(fā)生相變的臨界參數值

3、是什么？2）反之，為使網絡的拓撲結構具有某種性質，如何構建網絡？ 由于現實中的復雜系統(tǒng)的數據一般都是非常大的，所以通常對一個真實的復雜系統(tǒng)進行研究是要耗費大量的人力和物力，有時候甚至不太可行，故大部分研究真實復雜系統(tǒng)的文獻都只是對真實系統(tǒng)的一個很小的子系統(tǒng)進行研究，但子系統(tǒng)的復雜性質有時候與真實的系統(tǒng)復雜性質是非常不同的，因此人們希望能夠根據真實系統(tǒng)的一部分數據的研究結果推導出整個復雜系統(tǒng)的數據特性。近幾年，國內外有些學者開始研

4、究如何利用抽樣技術對真實系統(tǒng)數據進行抽樣，分析抽樣后的子系統(tǒng)與原系統(tǒng)的數據特性的差異及變化趨勢。 一方面，現有的文獻只是對抽樣后的子系統(tǒng)進行分析，看子系統(tǒng)與原系統(tǒng)的數據特性差異，并沒有能通過子系統(tǒng)的數據特性來得出原真實系統(tǒng)的復雜特性，從而提高復雜網絡研究的可行性和準確性。利用分析抽樣后的子系統(tǒng)的復雜特性來做研究更加符合實際，同時也是復雜網絡研究的一個前沿方向。 另一方面，復雜網絡分為隨機網絡、小世界網絡和無標度網絡，不同

5、種網絡有不同的網絡屬性。如隨機網絡的度分布呈泊松分布，平均路徑長度L～InN/-k較小，簇系數C<<1；小世界網絡具有和隨機網絡一樣的度分布，但是它具有較高的簇系數和較小的最短路徑；而無標度網絡的結點度服從冪律分布。如何根據所研究網絡的具體特征采用不同的抽樣方法來進行抽樣，使抽樣后的子系統(tǒng)在最大程度上符合原始系統(tǒng)的屬性特征也是一個重要的研究課題。 針對以上討論，本論文的研究重點是：首先,利用抽樣技術對大型的復雜網絡系統(tǒng)進行抽樣，

6、并通過分析抽樣網絡的性質來推導出原始復雜網絡的復雜特征參數，如對平均度、平均最短路徑長度以及聚類系數等作了分析研究；然后，針對不同的網絡具有不同的網絡特性，根據所研究的網絡特征使用不同的抽樣方法來對所研究的網絡進行抽樣。本文主要進行了以下幾個方面的工作： 1. ER網絡的抽樣研究。主要運用隨機抽樣技術對生成的ER 網絡進行抽樣，研究樣本網絡與原ER 網絡的內在邏輯聯系，并通過對抽樣網絡的復雜特性的分析來推導出原ER 網絡的復雜性

7、質。 2. BA網絡的抽樣研究。主要根據BA 網絡的特征（結點度的不均勻性），運用分層抽樣技術對模擬的BA 網絡進行分層抽樣，比較不同的抽樣方法對抽樣精度的影響。并通過抽樣網絡的復雜特性推導出原網絡的復雜特性度量參數的置信區(qū)間。 3. 根據BA網絡的度分布呈現冪律分布的特性，提出一種對復雜網絡的邊進行抽樣的邊抽樣算法。并對抽樣所得的樣本網絡進行分析，研究樣本網絡與原BA 網絡的內在邏輯聯系，并通過對抽樣網絡的復雜特性的分

8、析來推導出原BA 網絡的復雜性質。 基于以上的研究工作和詳盡的實驗分析，本論文的主要貢獻是： ·提出了基于簡單隨機抽樣的ER 網絡抽樣ABS 算法；對樣本ER 網絡與原始ER 網絡相對應的可靠性度量參數變化情況進行了推導并給出了一些有用的性質； · 根據BA 網絡結點度的分布性質，首次提出了基于2-8 分層的分層抽樣SSBA 算法； · 在推導樣本ER 網絡與原始ER 網絡有關可靠性度量參數變化關系的基礎