网络上含有单个陷阱的随机游走的平均吸收时间

林苑，阿拉法特•居来提，章忠志

摘要：给出了一般网络上含有单个陷阱、且陷阱放在任意节点上的随机游走全局平均首达时间(Global mean first-passage time, GMFPT)的一个精确公式，其中GMFPT表示从网络任意节点出发首次到达陷阱的平均期望时间，这一公式是通过网络拉普拉斯矩阵的特征值与特征向量表示出来的。之后，利用这一表达式研究了GMFPT的下界，得到了利用网络的节点数、边数、以及陷阱点的度表示出来的关于GMFPT的一个紧的下界，并证明了该下界在完全图与星状图可以达到。特别地，我们还发现：对于具有N个节点、且节点度服从P(d)~d^{-γ}分布的稀疏的无标度网络，当陷阱点置于网络中度最大的节点上时，GMFPT下界的阶为N^{1-1/γ}。最后，证明了GMFPT上界的阶为N^3，并证明了这一上界的阶在哑铃图可以达到。这项研究工作有助于全面地理解过去关于特定网络上陷阱位于特定节点的随机游走问题的研究结果。

相关结果已在《The Journal of Chemical Physics (JCP)》正式发表。JCP创刊于1933年，其创刊标志着化学物理这一学科的正式诞生。JCP在33个化学物理期刊中的影响排名第一，为中科院SCI分区列表二区中的Top期刊，近五年的平均影响因子为3.238，2011年影响因子为3.333。

文章发表的PDF版本：

Mean first-passage time for random walks in general graphs with a deep trap.pdf