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 (13)

• Self-similar community structure in organisations
• Dynamical and correlation properties of the Internet
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• First-passage times in complex scale-invariant media
• Functional modularity of background activities in normal and epileptic brain networks
• Entropy Rate of Diffusion Processes on Complex Networks
• Localization of maximal entropy random walk
• Synchronization in networks of mobile oscillators
• Biased random walks on complex networks: the role of local navigation rules
• 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

Cited by in corpus (48)

• Random walks and diffusion on networks
• Random Walks on Multiplex Networks
• Memory in network flows and its effects on spreading dynamics and community detection
• The synchronized dynamics of time-varying networks
• Collective phenomena emerging from the interactions between dynamical processes in multiplex networks
• Characteristic times of biased random walks on complex networks
• Flow graphs: interweaving dynamics and structure
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Efficient exploration of multiplex networks
• The origins of Zipf's meaning-frequency law
• Link prediction based on path entropy
• Extreme events and event size fluctuations in biased random walks on networks
• Degree Correlations in Random Geometric Graphs
• Entropy and the Predictability of Online Life
• Mean first-passage time for maximal-entropy random walks in complex networks
• Epidemic spreading driven by biased random walks
• Maximal entropy random walk in community finding
• Large deviations of random walks on random graphs
• Hopping in the crowd to unveil network topology
• EvoLearner: Learning Description Logics with Evolutionary Algorithms
• Motion-induced synchronization in metapopulations of mobile agents
• Simplex2Vec embeddings for community detection in simplicial complexes
• Mean encounter times for multiple random walkers on networks
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Information sharing in Quantum Complex Networks
• Reactive random walkers on complex networks
• Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees
• Entropy rate of non-equilibrium growing networks
• From random walks on networks to nonlinear diffusion
• Dynamics of Nonlinear Random Walks on Complex Networks
• Maximal-entropy random walk unifies centrality measures
• Diffusion on hierarchical systems of weakly-coupled networks
• Smart random walkers: the cost of knowing the path
• Random walks on networks with preferential cumulative damage: Generation of bias and aging
• Entropy rate of random walks on complex networks under stochastic resetting
• Social Diffusion and Global Drift on Networks
• Dynamical fluctuations of random walks in higher-order networks
• Reactive explorers to unravel network topology
• Chaos in Nonlinear Random Walks with Non-Monotonic Transition Probabilities
• Quasi-periodic dynamics and a Neimark-Sacker bifurcation in nonlinear random walks on complex networks
• Maximal dispersion of adaptive random walks
• Scoring Anomalous Vertices Through Quantum Walks
• Can Spatiality Promote Diversity?
• Maximum Entropy Random Walks: the Infinite Setting and the Example of Spider Networks with their Scaling Limits
• Community Structure aware Embedding of Nodes in a Network
• Uncovering hidden flows in physical networks
• Evanescent random walker on networks: Hitting times, budget renewal, and survival dynamics
• Stationary Schrödinger Equation and Darwin Term from Maximal Entropy Random Walk