摘要：通过两种不同的方法导出了一般无向网络上任意两点间平均首次到达时间（MFPT）的一个明确公式，该公式由一个矩阵的特征值与特征向量表出，这一矩阵与随机游走的概率转移矩阵相似。然后，利用所得的MFPT公式，推导出了部分节点对间的MFPT加权平均的一个下界。所求的MFPT加权平均实际上是关于终点为某一给定节点，起点是从平稳分布的节点集当中任意选取的随机游走MFPT的平均。特别地，对于一个节点数为N、度分布为P(d)~d^(-γ)的无标度网络，这一MFPT加权平均值下界的度量与网络规模N关系服从N^(1-1/γ)这一形式。此外，给出了随机游走特征时间的一个简单推导方法。这一工作提供了关于网络上随机游走的一个一般框架，可以加深对最近所报道的关于复杂网络、特别是无标度网络上随机游走结果的理解。

相关结果已发表在近期的《European Physical Journal B》上。

发表的PDF版本：

Mean first-passage time for random walks on undirected networks.pdf