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

Quantitative analyses of power law scaling in folk songs and in protein-folding dynamics.(a) First line of the song ‘Gedenk Mit Hochgefuehl An Jene’ with accession code ‘elsass15’. Names of notes are underneath, along with the division into segments based on every occurrence on the note C. (b) Empirical frequencies of different segments showing clear evidence of power law scaling along with the theoretical slope predicted by a fifth-order random walk model. (c) Diagram of a first order random walk model built based on all 8,466 songs. Grey lines indicate possible transitions, while the lengths of outgoing arrows are proportional to transition probabilities. The notes and rest are also labelled with their overall frequencies in the data. (d) Predicted slope of the scaling relationship according to random walk models of different orders. An order-five model provides the best match to the empirical slope of the relationship, as obtained by linear regression. (e) Diagram of a 3,683-node random walk model of G-protein folding31. Nodes represent protein conformations and links are possible transitions, with stepping probabilities estimated by molecular dynamics simulations. Colours indicate different basins of the energy landscape (see next panel). (f) Nodes are ranked by their mean first passage time to the native state, and the cut-based free energy is calculated. These were manually separated into seven different energy basins (red, orange,..., grey) between which there is a sharp increase in free energy. (g) Although all seven power law distributions have slopes close to −1, they are not all the same. Intriguingly, the slopes appear strongly related to the activation free energies of each basin.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f3: Quantitative analyses of power law scaling in folk songs and in protein-folding dynamics.(a) First line of the song ‘Gedenk Mit Hochgefuehl An Jene’ with accession code ‘elsass15’. Names of notes are underneath, along with the division into segments based on every occurrence on the note C. (b) Empirical frequencies of different segments showing clear evidence of power law scaling along with the theoretical slope predicted by a fifth-order random walk model. (c) Diagram of a first order random walk model built based on all 8,466 songs. Grey lines indicate possible transitions, while the lengths of outgoing arrows are proportional to transition probabilities. The notes and rest are also labelled with their overall frequencies in the data. (d) Predicted slope of the scaling relationship according to random walk models of different orders. An order-five model provides the best match to the empirical slope of the relationship, as obtained by linear regression. (e) Diagram of a 3,683-node random walk model of G-protein folding31. Nodes represent protein conformations and links are possible transitions, with stepping probabilities estimated by molecular dynamics simulations. Colours indicate different basins of the energy landscape (see next panel). (f) Nodes are ranked by their mean first passage time to the native state, and the cut-based free energy is calculated. These were manually separated into seven different energy basins (red, orange,..., grey) between which there is a sharp increase in free energy. (g) Although all seven power law distributions have slopes close to −1, they are not all the same. Intriguingly, the slopes appear strongly related to the activation free energies of each basin.

Mentions: Our theory also leads to a more detailed and quantitative understanding in cases of power law scaling. As mentioned above, the most widely known previous result is that constructing paths by, at each step, choosing uniformly randomly from N nodes produces a power law path distribution with slope bunif=−log(N)/log(N−1) (ref. 16). However, are real-world examples of power law scaling quantitatively consistent with a uniform random walk model? To test this, we turned to the field of music. Like natural language, where the uniform N-node model originated, music contains considerable long-range correlations262728 and complex structures29. Moreover, several recent analyses have uncovered various forms of power law scaling in large music corpora2728. We downloaded the ‘Essen’ collection of 8,473 folk songs, primarily of European and Chinese origins, from the Humdrum online musical archive ( http://kern.humdrum.org). After omitting seven songs with unclear notations, we transposed the remaining 8,466 songs into the key of C. Notes such as C# and D♭ were considered as one, so that we had 13 distinct symbols: A, A#/B♭, B, C, C#/D♭, D, D#/E♭, E, F, F#/G♭, G, G#/A♭ and R (for rest). We divided each song into segments based on every occurrence of the note C, resulting in 83,436 song segments departing from and returning to the natural (tonic) tone (Fig. 3a). The empirical probabilities of the 19,449 distinct musical segments are shown plotted against their ranks in Fig. 3b, which clearly indicates power law scaling. However, the slope of the relationship is not at all consistent with a uniform-probability model. With N=13 distinct symbols, the predicted slope would be bunif=−1.0322, whereas the empirical best-fit line has a much steeper slope of bemp=−1.1515.


A scaling law for random walks on networks.

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

Quantitative analyses of power law scaling in folk songs and in protein-folding dynamics.(a) First line of the song ‘Gedenk Mit Hochgefuehl An Jene’ with accession code ‘elsass15’. Names of notes are underneath, along with the division into segments based on every occurrence on the note C. (b) Empirical frequencies of different segments showing clear evidence of power law scaling along with the theoretical slope predicted by a fifth-order random walk model. (c) Diagram of a first order random walk model built based on all 8,466 songs. Grey lines indicate possible transitions, while the lengths of outgoing arrows are proportional to transition probabilities. The notes and rest are also labelled with their overall frequencies in the data. (d) Predicted slope of the scaling relationship according to random walk models of different orders. An order-five model provides the best match to the empirical slope of the relationship, as obtained by linear regression. (e) Diagram of a 3,683-node random walk model of G-protein folding31. Nodes represent protein conformations and links are possible transitions, with stepping probabilities estimated by molecular dynamics simulations. Colours indicate different basins of the energy landscape (see next panel). (f) Nodes are ranked by their mean first passage time to the native state, and the cut-based free energy is calculated. These were manually separated into seven different energy basins (red, orange,..., grey) between which there is a sharp increase in free energy. (g) Although all seven power law distributions have slopes close to −1, they are not all the same. Intriguingly, the slopes appear strongly related to the activation free energies of each basin.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f3: Quantitative analyses of power law scaling in folk songs and in protein-folding dynamics.(a) First line of the song ‘Gedenk Mit Hochgefuehl An Jene’ with accession code ‘elsass15’. Names of notes are underneath, along with the division into segments based on every occurrence on the note C. (b) Empirical frequencies of different segments showing clear evidence of power law scaling along with the theoretical slope predicted by a fifth-order random walk model. (c) Diagram of a first order random walk model built based on all 8,466 songs. Grey lines indicate possible transitions, while the lengths of outgoing arrows are proportional to transition probabilities. The notes and rest are also labelled with their overall frequencies in the data. (d) Predicted slope of the scaling relationship according to random walk models of different orders. An order-five model provides the best match to the empirical slope of the relationship, as obtained by linear regression. (e) Diagram of a 3,683-node random walk model of G-protein folding31. Nodes represent protein conformations and links are possible transitions, with stepping probabilities estimated by molecular dynamics simulations. Colours indicate different basins of the energy landscape (see next panel). (f) Nodes are ranked by their mean first passage time to the native state, and the cut-based free energy is calculated. These were manually separated into seven different energy basins (red, orange,..., grey) between which there is a sharp increase in free energy. (g) Although all seven power law distributions have slopes close to −1, they are not all the same. Intriguingly, the slopes appear strongly related to the activation free energies of each basin.
Mentions: Our theory also leads to a more detailed and quantitative understanding in cases of power law scaling. As mentioned above, the most widely known previous result is that constructing paths by, at each step, choosing uniformly randomly from N nodes produces a power law path distribution with slope bunif=−log(N)/log(N−1) (ref. 16). However, are real-world examples of power law scaling quantitatively consistent with a uniform random walk model? To test this, we turned to the field of music. Like natural language, where the uniform N-node model originated, music contains considerable long-range correlations262728 and complex structures29. Moreover, several recent analyses have uncovered various forms of power law scaling in large music corpora2728. We downloaded the ‘Essen’ collection of 8,473 folk songs, primarily of European and Chinese origins, from the Humdrum online musical archive ( http://kern.humdrum.org). After omitting seven songs with unclear notations, we transposed the remaining 8,466 songs into the key of C. Notes such as C# and D♭ were considered as one, so that we had 13 distinct symbols: A, A#/B♭, B, C, C#/D♭, D, D#/E♭, E, F, F#/G♭, G, G#/A♭ and R (for rest). We divided each song into segments based on every occurrence of the note C, resulting in 83,436 song segments departing from and returning to the natural (tonic) tone (Fig. 3a). The empirical probabilities of the 19,449 distinct musical segments are shown plotted against their ranks in Fig. 3b, which clearly indicates power law scaling. However, the slope of the relationship is not at all consistent with a uniform-probability model. With N=13 distinct symbols, the predicted slope would be bunif=−1.0322, whereas the empirical best-fit line has a much steeper slope of bemp=−1.1515.

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