复杂网络上非回溯随机游走

发布时间：2021-12-22 06:04

　　利用二阶马尔可夫模型研究了复杂网络上非回溯随机游走,推导出节点稳态占据概率的精确表达式和任意两个节点之间的平均首达时间的计算公式。通过与一般随机游走的结果比较,发现两种随机游走模型中节点稳态占据概率是完全一致的,而非回溯随机游走的平均首达时间比一般随机游走的要短。这意味着非回溯随机游走在网络搜索、路由等问题上更具有高效性。 

【文章来源】：安庆师范大学学报(自然科学版). 2020,26(04)

【文章页数】：5 页

【部分图文】：

非回溯随机游走的二阶马尔可夫表示图

和从节点i出发、首次返回到节点i的平均时间图3给出了一个平均度为4，节点数目N=30的BA无标度网络（图3(a））上非回溯随机游走的平均首达时间的理论结果和模拟结果（图3(b））。可以看出，理论结果和模拟结果吻合得非常好，平均首达时间按到达节点的度呈现台阶的分布。也就是说，平均首达时间主要依赖于到达节点的度，到达节点的度越大，平均首达时间一般也越短。为比较起见，图3(c）给出了一般随机游走的平均首达时间的理论和模拟结果。与非回溯随机游走相比，一般随机游走的平均首达时间要更长，同样呈现类似的台阶分布，但涨落变大了。

(a)BA网络；(b)非回溯随机游走的平均首达时间；(c)一般随机游走的平均首达时间


本文编号：3545889