一般网络上随机行走的平均首到达时间

摘要

平均首到达时间（Mean First-Passage Time，MFPT）是衡量复杂网络上随机行走效率的一个重要统计指标，一直是复杂网络领域研究的重点、难点。本文提出了一种新的、简便的计算方法，得出了一般网络上任意两点间随机行走的平均首到达时间的精确解。首先运用图谱理论的相关知识，推导出平均首到达时间的数学解析公式，在求解过程上优于已有的方法，并能给出了这一解析解的下界。以无标度网络（BA网络）为例进行了计算机仿真，其结果与解析结果一致。%As an important index for evaluating the efficiency of random walks on complex network,mean first-passage time (MFPT) has always been a key and difficult points in the field of complex networks. In this paper, a new and easy method is given to calculate the exact formula of MFPT for random walks between any pair of nodes on a gener-al network. Firstly, an explicit mathematical formula for the mean first-passage time (MFPT) is derived by using the knowledge of spectral graph theory. The solving process in this paper is superior to the existing others. Then a lower bound for the MFPT is given. Finally, some simulations on scale-free network (BA network) results are presented, which is same with the analysis results.