复杂网络上最大熵随机游走的平均首达时间

林苑 章忠志

摘要：本文对复杂网络上最大熵随机游走的平均首达时间（Mean first-passage time, MFPT）进行深入系统地研究。MFPT是衡量随机游走效率的重要指标，同时具有重要而广泛的应用。对于一般网络上的最大熵随机游走，通过网络邻接矩阵的特征值与特征向量给出了MFPT的精确表达式。对于度不相关网络上的最大熵随机游走，基于平均场理论给出了MFPT的一个解析表达式，并基于这一表达式，进一步研究了度不相关无标度网络上的最大熵随机游走，给出了不同目标节点情况下MFPT的阶，并与对应的无偏好随机游走MFPT的阶进行了比较。研究发现，当目标节点为度最大的节点时，最大熵随机游走MFPT的阶明显低于无偏好随机游走MFPT的阶；而当目标节点为度最小的节点，或者目标节点在网络中均匀分布时，最大熵随机游走MFPT的阶高于无偏好随机游走MFPT的阶。由于目标节点均匀分布时的MFPT可作为网络搜索效率的衡量指标，本文为复杂网络上的搜索过程提供了更深入的理解。

相关结果已在Scientific Reports上正式发表。

文章发表的PDF版本：

Mean first-passage time for maximal-entropy random walks in complex networks.pdf