利用二階馬爾可夫模型研究了復(fù)雜網(wǎng)絡(luò)上非回溯隨機游走,推導(dǎo)出節(jié)點穩(wěn)態(tài)占據(jù)概率的精確表達式和任意兩個節(jié)點之間的平均首達時間的計算公式。通過與一般隨機游走的結(jié)果比較,發(fā)現(xiàn)兩種隨機游走模型中節(jié)點穩(wěn)態(tài)占據(jù)概率是完全一致的,而非回溯隨機游走的平均首達時間比一般隨機游走的要短。這意味著非回溯隨機游走在網(wǎng)絡(luò)搜索、路由等問題上更具有高效性。 

【文章來源】：安慶師范大學(xué)學(xué)報(自然科學(xué)版). 2020,26(04)

【文章頁數(shù)】：5 頁

【部分圖文】：

非回溯隨機游走的二階馬爾可夫表示圖

和從節(jié)點i出發(fā)、首次返回到節(jié)點i的平均時間圖3給出了一個平均度為4，節(jié)點數(shù)目N=30的BA無標(biāo)度網(wǎng)絡(luò)（圖3(a））上非回溯隨機游走的平均首達時間的理論結(jié)果和模擬結(jié)果（圖3(b））�？梢钥闯�，理論結(jié)果和模擬結(jié)果吻合得非常好，平均首達時間按到達節(jié)點的度呈現(xiàn)臺階的分布。也就是說，平均首達時間主要依賴于到達節(jié)點的度，到達節(jié)點的度越大，平均首達時間一般也越短。為比較起見，圖3(c）給出了一般隨機游走的平均首達時間的理論和模擬結(jié)果。與非回溯隨機游走相比，一般隨機游走的平均首達時間要更長，同樣呈現(xiàn)類似的臺階分布，但漲落變大了。

(a)BA網(wǎng)絡(luò)；(b)非回溯隨機游走的平均首達時間；(c)一般隨機游走的平均首達時間


本文編號：3545889