復(fù)雜網(wǎng)絡(luò)中的隨機(jī)游走研究.pdf

1、如今，我們對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)的研究日益廣泛，如蛋白質(zhì)相互作用網(wǎng)，社會(huì)聯(lián)系網(wǎng)，英特網(wǎng)等。很多情況下我們只對(duì)這些網(wǎng)絡(luò)中的部分內(nèi)容有所了解和利用。即使我們可以得到完整的網(wǎng)絡(luò)信息，只對(duì)整體網(wǎng)絡(luò)中的一部分進(jìn)行研究也更為“經(jīng)濟(jì)”。為了得到完整網(wǎng)絡(luò)的子網(wǎng)，我們以隨機(jī)節(jié)點(diǎn)抽樣和隨機(jī)連邊抽樣等方法對(duì)整體網(wǎng)絡(luò)進(jìn)行抽樣。當(dāng)隨機(jī)節(jié)點(diǎn)和隨機(jī)連邊抽樣存在一定的偏差時(shí)，尋找一種更為準(zhǔn)確的抽樣策略就成為了重要的研究課題。許多情況下，探索網(wǎng)絡(luò)的過(guò)程類似于隨機(jī)游走的過(guò)程，因此，研

2、究、刻畫(huà)不同的隨機(jī)游走抽樣策略對(duì)網(wǎng)絡(luò)抽樣效果的影響就十分重要。
　　本文中，我們?cè)谝延械臒o(wú)限制的隨機(jī)游走（URW）的基礎(chǔ)上發(fā)展出選擇種子節(jié)點(diǎn)的隨機(jī)游走（CSNRW），及不返回上一步的隨機(jī)游走（NRRW），并探討了這三種類型的隨機(jī)游走在加權(quán)的美國(guó)航空網(wǎng)，ER，BA和WS網(wǎng)絡(luò)中的抽樣情況。通過(guò)模擬研究了它們的抽樣效率、度分布、抽樣子網(wǎng)的平均度和平均聚類系數(shù)隨抽樣步數(shù)的改變，得到了一系列的相關(guān)結(jié)果：三類抽樣策略在具有相同尺度