Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees

Abstract

We provide analytical solutions for two types of random walk: generic random walk (GRW) and maximal entropy random walk (MERW) on a Cayley tree with arbitrary branching number, root degree, and number of generations. For MERW, we obtain the stationary state given by the squared elements of the eigenvector associated with the largest eigenvalue ${\lambda }_0$ of the adjacency matrix. We discuss the dynamics, depending on the second largest eigenvalue ${\lambda }_1$, of the probability distribution approaching to the stationary state. We find different scaling of the relaxation time with the system size, which is generically shorter for MERW than for GRW. We also signal that depending on the initial conditions there are relaxations associated with lower eigenvalues which are induced by symmetries of the tree. In general, we find that there are three regimes of a tree structure resulting in different statics and dynamics of MERW; these correspond to strongly, critically, and weakly branched roots.

17 pages, 6 figures

References in corpus (4)

• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• Maximal-entropy random walks in complex networks with limited information
• Topologically biased random walk with application for community finding in networks
• Random elastic networks : strong disorder renormalization approach

Cited by in corpus (11)

• Mean first-passage time for maximal-entropy random walks in complex networks
• Explicit construction of the eigenvectors and eigenvalues of the graph Laplacian on the Cayley tree
• Maximal entropy random walk in community finding
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Maximal-entropy random walk unifies centrality measures
• Paths counting on simple graphs: from escape to localization
• Spectral Renormalization Group for the Gaussian model and ${\psi }^4$ theory on non-spatial networks
• Maximal Entropy Random Walk: solvable cases of dynamics
• Maximum Entropy Random Walks: the Infinite Setting and the Example of Spider Networks with their Scaling Limits
• Path Counting on Tree-like Graphs with a Single Entropic Trap: Critical Behavior and Finite Size Effects
• Non-Backtracking Centrality Based Random Walk on Networks