Limits...
A scaling law for random walks on networks.

Perkins TJ, Foxall E, Glass L, Edwards R - Nat Commun (2014)

Bottom Line: 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.The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution.

View Article: PubMed Central - PubMed

Affiliation: Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario, Canada K1H 8L6.

ABSTRACT
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.

No MeSH data available.


Related in: MedlinePlus

The path distribution for a random walk on a network may be finite, stretched exponential or power law.(a–c) Graphical depiction of three different random walks on networks, all having the same set of nodes and transitions probabilities, but with some arcs having different endpoints. Arcs without numbers are probablity-one transitions. (d) A log–log plot of the probabilities of different paths from S to E, under the walks shown in a–c, where Pr denotes the probability of the rth most probable path from S to E. Walk A allows only four possible paths from S to E, so its distribution is finite. For walk C, the approximate linearity of Pr with r on the log–log plot suggests that the path distribution is power law. The curvature of the points for walk B is inconsistent with a power law path probability distribution. (e) When log probabilities are plotted against the square root of rank, the points for walk B are approximately collinear, indicating a stretched exponential path probability distribution.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4214407&req=5

f1: The path distribution for a random walk on a network may be finite, stretched exponential or power law.(a–c) Graphical depiction of three different random walks on networks, all having the same set of nodes and transitions probabilities, but with some arcs having different endpoints. Arcs without numbers are probablity-one transitions. (d) A log–log plot of the probabilities of different paths from S to E, under the walks shown in a–c, where Pr denotes the probability of the rth most probable path from S to E. Walk A allows only four possible paths from S to E, so its distribution is finite. For walk C, the approximate linearity of Pr with r on the log–log plot suggests that the path distribution is power law. The curvature of the points for walk B is inconsistent with a power law path probability distribution. (e) When log probabilities are plotted against the square root of rank, the points for walk B are approximately collinear, indicating a stretched exponential path probability distribution.

Mentions: To see that different types of path distributions may arise from random walks on networks, consider the three networks shown in Fig. 1a–c. Walk A allows only four paths from start node S to end node E. The other networks, which allow a walk to loop back to a node that it has visited before, allow for infinitely many possible paths. For walks B and C, longer paths generally have a lower probability than shorter ones, but there is no strict relationship between path length and path probability, because different steps occur with different probabilities. Suppose we rank the paths in order of decreasing probability, P1, P2, P3,..., where Pr is the probability of the rth most probable path. Figure 1d shows how the probabilities Pr relate to the ranks r for the three walks. For walk C, the relationship is approximately linear on the log–log plot, implying that the path distribution is approximately power law: log Pr≈a+b log r or Pr≈crb. However, for walk B, the relationship is clearly curvilinear on the log–log plot, inconsistent with a power law path probability distribution. Instead, the approximately linear relationship between the logarithm of Pr and the square root of r for walk B (Fig. 1e) indicates a stretched exponential path distribution: , or .


A scaling law for random walks on networks.

Perkins TJ, Foxall E, Glass L, Edwards R - Nat Commun (2014)

The path distribution for a random walk on a network may be finite, stretched exponential or power law.(a–c) Graphical depiction of three different random walks on networks, all having the same set of nodes and transitions probabilities, but with some arcs having different endpoints. Arcs without numbers are probablity-one transitions. (d) A log–log plot of the probabilities of different paths from S to E, under the walks shown in a–c, where Pr denotes the probability of the rth most probable path from S to E. Walk A allows only four possible paths from S to E, so its distribution is finite. For walk C, the approximate linearity of Pr with r on the log–log plot suggests that the path distribution is power law. The curvature of the points for walk B is inconsistent with a power law path probability distribution. (e) When log probabilities are plotted against the square root of rank, the points for walk B are approximately collinear, indicating a stretched exponential path probability distribution.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4214407&req=5

f1: The path distribution for a random walk on a network may be finite, stretched exponential or power law.(a–c) Graphical depiction of three different random walks on networks, all having the same set of nodes and transitions probabilities, but with some arcs having different endpoints. Arcs without numbers are probablity-one transitions. (d) A log–log plot of the probabilities of different paths from S to E, under the walks shown in a–c, where Pr denotes the probability of the rth most probable path from S to E. Walk A allows only four possible paths from S to E, so its distribution is finite. For walk C, the approximate linearity of Pr with r on the log–log plot suggests that the path distribution is power law. The curvature of the points for walk B is inconsistent with a power law path probability distribution. (e) When log probabilities are plotted against the square root of rank, the points for walk B are approximately collinear, indicating a stretched exponential path probability distribution.
Mentions: To see that different types of path distributions may arise from random walks on networks, consider the three networks shown in Fig. 1a–c. Walk A allows only four paths from start node S to end node E. The other networks, which allow a walk to loop back to a node that it has visited before, allow for infinitely many possible paths. For walks B and C, longer paths generally have a lower probability than shorter ones, but there is no strict relationship between path length and path probability, because different steps occur with different probabilities. Suppose we rank the paths in order of decreasing probability, P1, P2, P3,..., where Pr is the probability of the rth most probable path. Figure 1d shows how the probabilities Pr relate to the ranks r for the three walks. For walk C, the relationship is approximately linear on the log–log plot, implying that the path distribution is approximately power law: log Pr≈a+b log r or Pr≈crb. However, for walk B, the relationship is clearly curvilinear on the log–log plot, inconsistent with a power law path probability distribution. Instead, the approximately linear relationship between the logarithm of Pr and the square root of r for walk B (Fig. 1e) indicates a stretched exponential path distribution: , or .

Bottom Line: 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.The form of the distribution depends only on the structure of the network, while the stepping probabilities control the parameters of the distribution.

View Article: PubMed Central - PubMed

Affiliation: Ottawa Hospital Research Institute, 501 Smyth Road, Ottawa, Ontario, Canada K1H 8L6.

ABSTRACT
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.

No MeSH data available.


Related in: MedlinePlus