Skip to main content

Scaling of Random Walks on Networks

Consider a random walk on a finite network, starting at a given START state and ending at a given END (or target) state. Imagine all possible paths are sorted by decreasing probability. What is the probability of the r-th most probable path? It turns out there are only three choices for the form of this distribution: (1) it is finite, (2) it is stretched exponential, (3) it is powerlaw. Given a network, the Matlab code below in "MarkovChainScaling.m" compute the type and parameters of the distribution. The script "Mat01.m" gives some demonstrations of how it can be used, and shows computations on some simple networks. That script can also, using the other functions provided below, compute the exact probabilities of the N most probable paths, for comparison purposes.
AttachmentSize
Mat01.m3.54 KB
MarkovChainScaling.m6.66 KB
PathLogProbs_NLargest.m858 bytes
PathLogProbsAbove.m1.06 KB
PathLogProbsAbove_Helper.m770 bytes