Lin Yuan, Zhang Zhongzhi
School of Computer Science, Fudan University, Shanghai 200433, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2013 Jun;87(6):062140. doi: 10.1103/PhysRevE.87.062140. Epub 2013 Jun 28.
Trapping processes constitute a primary problem of random walks, which characterize various other dynamical processes taking place on networks. Most previous works focused on the case of binary networks, while there is much less related research about weighted networks. In this paper, we propose a general framework for the trapping problem on a weighted network with a perfect trap fixed at an arbitrary node. By utilizing the spectral graph theory, we provide an exact formula for mean first-passage time (MFPT) from one node to another, based on which we deduce an explicit expression for average trapping time (ATT) in terms of the eigenvalues and eigenvectors of the Laplacian matrix associated with the weighted graph, where ATT is the average of MFPTs to the trap over all source nodes. We then further derive a sharp lower bound for the ATT in terms of only the local information of the trap node, which can be obtained in some graphs. Moreover, we deduce the ATT when the trap is distributed uniformly in the whole network. Our results show that network weights play a significant role in the trapping process. To apply our framework, we use the obtained formulas to study random walks on two specific networks: trapping in weighted uncorrelated networks with a deep trap, the weights of which are characterized by a parameter, and Lévy random walks in a connected binary network with a trap distributed uniformly, which can be looked on as random walks on a weighted network. For weighted uncorrelated networks we show that the ATT to any target node depends on the weight parameter, that is, the ATT to any node can change drastically by modifying the parameter, a phenomenon that is in contrast to that for trapping in binary networks. For Lévy random walks in any connected network, by using their equivalence to random walks on a weighted complete network, we obtain the optimal exponent characterizing Lévy random walks, which have the minimal average of ATTs taken over all target nodes.
捕获过程是随机游走的一个主要问题，随机游走刻画了网络上发生的各种其他动态过程。此前的大多数工作都集中在二元网络的情况，而关于加权网络的相关研究则少得多。在本文中，我们针对加权网络上的捕获问题提出了一个通用框架，其中一个完美陷阱固定在任意节点上。通过利用谱图理论，我们给出了从一个节点到另一个节点的平均首次通过时间（MFPT）的精确公式，在此基础上，我们根据与加权图相关的拉普拉斯矩阵的特征值和特征向量推导出平均捕获时间（ATT）的显式表达式，其中ATT是所有源节点到陷阱的MFPT的平均值。然后，我们进一步仅根据陷阱节点的局部信息推导出ATT的一个严格下界，这在某些图中是可以得到的。此外，我们推导了陷阱在整个网络中均匀分布时的ATT。我们的结果表明，网络权重在捕获过程中起着重要作用。为了应用我们的框架，我们使用得到的公式研究了两个特定网络上的随机游走：具有深陷阱的加权不相关网络中的捕获，其权重由一个参数表征；以及在具有均匀分布陷阱的连通二元网络中的 Lévy 随机游走，这可以看作是加权网络上的随机游走。对于加权不相关网络，我们表明到任何目标节点的ATT取决于权重参数，也就是说，通过修改该参数，到任何节点的ATT可能会发生巨大变化，这一现象与二元网络中的捕获情况形成对比。对于任何连通网络中的 Lévy 随机游走，通过利用它们与加权完全网络上随机游走的等价性，我们得到了表征 Lévy 随机游走的最优指数，该指数在所有目标节点上的ATT平均值最小。
