Maximal-entropy random walks in complex networks with limited information

Abstract

Maximization of the entropy rate is an important issue to design diffusion processes aiming at a well-mixed state. We demonstrate that it is possible to construct maximal-entropy random walks with only local information on the graph structure. In particular, we show that an almost maximal-entropy random walk is obtained when the step probabilities are proportional to a power of the degree of the target node, with an exponent $\alpha$ that depends on the degree-degree correlations, and is equal to 1 in uncorrelated graphs.

4 pages, 1 figure, 1 table + 1 page supplementary material

References in corpus (7)

• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• First-passage times in complex scale-invariant media
• Entropy Rate of Diffusion Processes on Complex Networks
• Approximating the largest eigenvalue of network adjacency matrices
• Spectral coarse-graining of complex networks
• Topologically biased random walk with application for community finding in networks
• Correlations between structure and dynamics in complex networks