Speidel Leo, Lambiotte Renaud, Aihara Kazuyuki, Masuda Naoki
Department of Mathematical Informatics, University of Tokyo, Tokyo, Japan and JST, ERATO, Kawarabayashi Large Graph Project, Tokyo, Japan.
Department of Mathematics/Naxys, University of Namur, Namur, Belgium.
Phys Rev E Stat Nonlin Soft Matter Phys. 2015 Jan;91(1):012806. doi: 10.1103/PhysRevE.91.012806. Epub 2015 Jan 8.
Random walks are basic diffusion processes on networks and have applications in, for example, searching, navigation, ranking, and community detection. Recent recognition of the importance of temporal aspects on networks spurred studies of random walks on temporal networks. Here we theoretically study two types of event-driven random walks on a stochastic temporal network model that produces arbitrary distributions of interevent times. In the so-called active random walk, the interevent time is reinitialized on all links upon each movement of the walker. In the so-called passive random walk, the interevent time is reinitialized only on the link that has been used the last time, and it is a type of correlated random walk. We find that the steady state is always the uniform density for the passive random walk. In contrast, for the active random walk, it increases or decreases with the node's degree depending on the distribution of interevent times. The mean recurrence time of a node is inversely proportional to the degree for both active and passive random walks. Furthermore, the mean recurrence time does or does not depend on the distribution of interevent times for the active and passive random walks, respectively.
随机游走是网络上的基本扩散过程，在搜索、导航、排名和社区检测等方面有应用。最近对网络时间方面重要性的认识激发了对时间网络上随机游走的研究。在这里，我们从理论上研究了在一个产生事件间时间任意分布的随机时间网络模型上的两种事件驱动随机游走。在所谓的主动随机游走中，每当游走者移动时，所有链接上的事件间时间都会重新初始化。在所谓的被动随机游走中，事件间时间仅在最后一次使用的链接上重新初始化，它是一种相关随机游走。我们发现，对于被动随机游走，稳态始终是均匀密度。相比之下，对于主动随机游走，它会根据事件间时间的分布随节点度增加或减少。对于主动和被动随机游走，节点的平均返回时间都与度成反比。此外，主动和被动随机游走的平均返回时间分别取决于或不取决于事件间时间的分布。
