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

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

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

【部分圖文】：

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

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

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


本文編號(hào)：3545889