A scaling law for random walks on networks.

The dynamics of many natural and artificial systems are well described as random walks on a network: the stochastic behaviour of molecules, traffic patterns on the internet, fluctuations in stock prices and so on. The vast literature on random walks provides many tools for computing properties such as steady-state probabilities or expected hitting times. Previously, however, there has been no general theory describing the distribution of possible paths followed by a random walk. Here, we show that for any random walk on a finite network, there are precisely three mutually exclusive possibilities for the form of the path distribution: finite, stretched exponential and power law. The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution. We use our theory to explain path distributions in domains such as sports, music, nonlinear dynamics and stochastic chemical kinetics. Random walks on a network describe the dynamics of many natural and artificial systems. Here, Perkins et al. study the path distribution—characterizing how the walker moves—and find that it is either finite, stretched exponential or power law for any random walk on a finite network.

许多自然和人工系统的动力学可以很好地描述为网络上的随机游走：分子的随机行为、互联网上的流量模式、股票价格的波动等等。大量关于随机游走的文献提供了许多计算诸如稳态概率或预期到达时间等特性的工具。然而，在此之前，还没有通用的理论来描述随机游走可能遵循的路径分布。在此，我们表明对于有限网络上的任何随机游走，路径分布的形式恰好有三种相互排斥的可能性：有限型、拉伸指数型和幂律型。分布的形式仅取决于网络的结构，而步移概率控制着分布的参数。我们用我们的理论来解释诸如体育、音乐、非线性动力学和随机化学动力学等领域的路径分布。 网络上的随机游走描述了许多自然和人工系统的动力学。在此，珀金斯等人研究了路径分布——表征游走者如何移动——并发现对于有限网络上的任何随机游走，它要么是有限型、拉伸指数型，要么是幂律型。