負責網(wǎng)絡抽樣研究.pdf

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

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

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

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

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

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

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

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