1202.1160 (Jeremi K. Ochab)

Maximal Entropy Random Walk: solvable cases of dynamics    [PDF]

Jeremi K. Ochab

We focus on the study of dynamics of two kinds of random walk: generic random
walk (GRW) and maximal entropy random walk (MERW) on two model networks: Cayley
trees and ladder graphs. The stationary probability distribution for MERW is
given by the squared components of the eigenvector associated with the largest
eigenvalue \lambda_0 of the adjacency matrix of a graph, while the dynamics of
the probability distribution approaching to the stationary state depends on the
second largest eigenvalue \lambda_1.
Firstly, we give analytic solutions for Cayley trees with arbitrary branching
number, root degree, and number of generations. We determine three regimes of a
tree structure that result in different statics and dynamics of MERW, which are
due to strongly, critically, and weakly branched roots. We show how the
relaxation times, generically shorter for MERW than for GRW, scale with the
graph size.
Secondly, we give numerical results for ladder graphs with symmetric defects.
MERW shows a clear exponential growth of the relaxation time with the size of
defective regions, which indicates trapping of a particle within highly
entropic intact region and its escaping that resembles quantum tunneling
through a potential barrier. GRW shows standard diffusive dependence
irrespective of the defects.

View original: http://arxiv.org/abs/1202.1160