負(fù)責(zé)網(wǎng)絡(luò)抽樣研究.pdf

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

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

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

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

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

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

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

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