Random Walks on Complex Networks

Abstract

We investigate random walks on complex networks and derive an exact expression for the mean first passage time (MFPT) between two nodes. We introduce for each node the random walk centrality $C$, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.

published version (4 pages, 2 eps figures)

References in corpus (20)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• The diameter of the world wide web
• Hierarchical organization of modularity in metabolic networks
• Evolution of networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Resilience of the Internet to random breakdowns
• Hierarchical Organization in Complex Networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Search in Power-Law Networks
• Optimal network topologies for local search with congestion
• Ising Model on Networks with an Arbitrary Distribution of Connections
• Classification of scale-free networks
• First- and second-order phase transitions in scale-free networks
• Relaxation Properties of Small-World Networks
• Exact scaling properties of a hierarchical network model
• Stability of shortest paths in complex networks with random edge weights
• Adaptive Random Walks on the Class of Web Graph

Cited by in corpus (225)

• Epidemic processes in complex networks
• Analysis of weighted networks
• Mathematical Formulation of Multi-Layer Networks
• Voter Model on Heterogeneous Graphs
• Random walks and diffusion on networks
• Social physics
• Link Prediction Based on Local Random Walk
• Random Walks on Multiplex Networks
• Centrality in Interconnected Multilayer Networks
• Networks in Cognitive Science
• Consistency and differences between centrality measures across distinct classes of networks
• Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
• Localization of maximal entropy random walk
• Global mean first-passage times of random walks on complex networks
• Biased random walks on complex networks: the role of local navigation rules
• LinkRank: Finding communities in directed networks
• Quantifying the effect of temporal resolution on time-varying networks
• Collective phenomena emerging from the interactions between dynamical processes in multiplex networks
• Cluster Explosive Synchronization in Complex Networks
• First-passage times for random walks in bounded domains
• Towards real-world complexity: an introduction to multiplex networks
• First passage time for random walks in heterogeneous networks
• Exploring complex networks by walking on them
• A spectrum of routing strategies for brain networks
• Separating internal and external dynamics of complex systems
• Complex Networks from Classical to Quantum
• Transport on Complex Networks: Flow, Jamming and Optimization
• Extreme events in dynamical systems and random walkers: A review
• Random walk centrality in interconnected multilayer networks
• Efficient routing on scale-free networks based on local information
• First Passage Properties of the Erdos-Renyi Random Graph
• Random walks on networks with stochastic resetting
• Characteristic times of biased random walks on complex networks
• Anomalous Transport in Complex Networks
• Flow graphs: interweaving dynamics and structure
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Mean-field diffusive dynamics on weighted networks
• Exact calculations of first-passage quantities on recursive networks
• Quantum walk-based search and centrality
• Eigenvalue Spectra of Modular Networks
• Efficient exploration of multiplex networks
• Random walk centrality for temporal networks
• Mean first-passage time for random walks on undirected networks
• Self-avoiding walks on scale-free networks
• Node-weighted measures for complex networks with spatially embedded, sampled, or differently sized nodes
• Eigenvalues of normalized Laplacian matrices of fractal trees and dendrimers: Analytical results and applications
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Complete Condensation in a Zero Range Process on Scale-Free Networks
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Random walks on activity-driven networks with attractiveness
• Machine Learning in Network Centrality Measures: Tutorial and Outlook
• The origins of Zipf's meaning-frequency law
• Uncovering the community structure associated with the diffusion dynamics of networks
• Asymptotic analysis of first passage time in complex networks
• Statistical physics of complex information dynamics
• Extreme events and event size fluctuations in biased random walks on networks
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Networking - A Statistical Physics Perspective
• Scaling of human behavior during portal browsing
• Network Evolution Based on Centrality
• Centrality scaling in large networks
• Multi-layer graph analysis for dynamic social networks
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Counting spanning trees in a small-world Farey graph
• Trapping in scale-free networks with hierarchical organization of modularity
• Close or connected? Distance and connectivity effects on transport in networks
• Border Detection in Complex Networks
• Load distribution in weighted complex networks
• Random walks in modular scale-free networks with multiple traps
• Mutually-Antagonistic Interactions in Baseball Networks
• Exploring Maps with Greedy Navigators
• How Many Nodes are Effectively Accessed in Complex Networks?
• Counting spanning trees in self-similar networks by evaluating determinants
• Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
• Laplacian paths in complex networks: information core emerges from entropic transitions
• Network Inference from TraceRoute Measurements: Internet Topology `Species'
• Heterogeneous continuous time random walks
• Communities and beyond: mesoscopic analysis of a large social network with complementary methods
• Extreme first passage times for random walks on networks
• Mapping from Architecture to Dynamics: A Unified View of Dynamical Processes on Networks
• Effects of long-range hopping and interactions on quantum walk in ordered and disordered lattices
• A phase transition in the first passage of a Brownian process through a fluctuating boundary: implications for neural coding
• Enhancing transport properties in interconnected systems without altering their structure
• Information transport in multiplex networks
• Role of fractal dimension in random walks on scale-free networks
• Walks on weighted networks
• Walks on Apollonian networks
• Random walks on complex networks with first-passage resetting
• Upstream reciprocity in heterogeneous networks
• Diffusion in scale-free networks with annealed disorder
• A simple model of epidemic dynamics with memory effects
• From classical to quantum walks with stochastic resetting on networks
• Switcher-random-walks: a cognitive-inspired mechanism for network exploration
• Complex networks with tuneable dimensions as a universality playground
• Hopping in the crowd to unveil network topology
• Levy random walks on multiplex networks
• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• Random walks on complex networks under time-dependent stochastic resetting
• Accessibility Measure for Eternal Inflation: Dynamical Criticality and Higgs Metastability
• Controlling the efficiency of trapping in treelike fractals
• Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
• Nonlocal biased random walks and fractional transport on directed networks
• Condensation phase transitions of symmetric conserved-mass aggregation model on complex networks
• Optimality of spatially inhomogeneous search strategies
• Universal exploration dynamics of random walks
• Mean encounter times for multiple random walkers on networks
• Biased diffusion on Japanese inter-firm trading network: Estimation of sales from network structure
• A path-based approach to random walks on networks characterizes how proteins evolve new function
• Continuous time random walk and diffusion with generalized fractional Poisson process
• Classical and quantum random-walk centrality measures in multilayer networks
• Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks
• Transport of multiple users in complex networks
• Network Discovery by Generalized Random Walks
• Random walks with long-range steps generated by functions of Laplacian matrices
• Generalized open quantum walks on Apollonian networks
• An ensemble of random graphs with identical degree distribution
• Analysis of node2vec random walks on networks
• Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs
• Reactive random walkers on complex networks
• On Discrete Time Prabhakar-Generalized Fractional Poisson Processes and Related Stochastic Dynamics
• Manipulation of extreme events on scale-free networks
• Extreme events in stochastic transport on networks
• Aging in transport processes on networks with stochastic cumulative damage
• Anomalous biased diffusion in networks
• Random walks in small-world exponential treelike networks
• Multitarget search on complex networks: A logarithmic growth of global mean random cover time
• Tweaking Synchronisation by Link Addition
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Cross-domain Network Representations
• Kinetic growth walks on complex networks
• Jamming and Correlation Patterns in Traffic of Information on Sparse Modular Networks
• Activation thresholds in epidemic spreading with motile infectious agents on scale-free networks
• Exact encounter times for many random walkers on regular and complex networks
• Weak ties: Subtle role of information diffusion in online social networks
• Network meta-analysis and random walks
• Dynamics of Nonlinear Random Walks on Complex Networks
• Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
• Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• Tutte polynomial of a small-world farey graph
• Routes Obey Hierarchy in Complex Networks
• On node ranking in graphs
• Phase-Space Networks of Geometrical Frustrated Systems
• Diffusion on hierarchical systems of weakly-coupled networks
• Degree Landscapes in Scale-Free Networks
• Smart random walkers: the cost of knowing the path
• Anomalous electrical and frictionless flow conductance in complex networks
• Quantum Approach to Fast Protein-Folding Time
• Complex networks and glassy dynamics: walks in the energy landscape
• Inter-arrival times of message propagation on directed networks
• A geometric entropy detecting the Erdös-Rényi phase transition
• Random Walk with Memory on Complex Networks
• Random walks on networks with preferential cumulative damage: Generation of bias and aging
• Riemannian-geometric entropy for measuring network complexity
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Uncovering hidden dependency in weighted networks via information entropy
• Random walks in directed modular networks
• Can car density in a two-lane section depend on the position of the latter in a single-lane road?
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Entropy rate of random walks on complex networks under stochastic resetting
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• PageRank and rank-reversal dependence on the damping factor
• Rounding of first-order phase transitions and optimal cooperation in scale-free networks
• Evolution of transport under cumulative damage in metro systems
• Biased random walkers and extreme events on the edges of complex networks
• The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks
• Delocalization-localization dynamical phase transition of random walks on graphs
• Vulnerability of Networks Against Critical Link Failures
• Fractional dynamics on circulant multiplex networks: optimal coupling and long-range navigation for continuous-time random walks
• MeshWalker: Deep Mesh Understanding by Random Walks
• Anomalous behavior of trapping in extended dendrimers with a perfect trap
• Static Pairwise Annihilation in Complex Networks
• Reactive explorers to unravel network topology
• Anomaly Detection of Complex Networks Based on Intuitionistic Fuzzy Set Ensemble
• Criterions for locally dense subgraphs
• Quantum walk on a chimera graph
• Segregation in the annihilation of two-species reaction-diffusion processes on fractal scale-free networks
• Target Searches of Interacting Brownian Particles
• Intermittent exploration on a scale-free network
• Chaos in Nonlinear Random Walks with Non-Monotonic Transition Probabilities
• Theoretical approach and impact of correlations on the critical packet generation rate in traffic dynamics on complex networks
• A Random Walk Perspective on Hide-and-Seek Games
• Pathlength scaling in graphs with incomplete navigational information
• Geometry of Complex Networks and Topological Centrality
• Quantum Intelligence on Protein Folding Pathways
• "Conjectural" links in complex networks
• Maximal dispersion of adaptive random walks
• Deterministic Random Walk Model in NetLogo and the Identification of Asymmetric Saturation Time in Random Graph
• Unexpected advantages of exploitation for target searches in complex networks
• Optimal Searcher Distribution for Parallel Random Target Searches
• Networks and Our Limited Information Horizon
• Imbalance of pairwise efficiency in urban street network
• Vibrational modes and spectrum of oscillators on a scale-free network
• Detecting Structure of Complex Network by Quantum Bosonic Dynamics
• Symmetry-based coarse-graining of evolved dynamical networks
• A measure of dissimilarity between diffusive processes on networks
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• Scale-free tree network with an ultra-large diameter
• Network Meta-Analysis: A Statistical Physics Perspective
• Temporal-varying failures of nodes in networks
• Full counting statistics of random transition-rate matrices
• Rapid Bayesian Inference of Global Network Statistics Using Random Walks
• Probing Black Hole Microstate Evolution with Networks and Random Walks
• Structural instability of large-scale functional networks
• Reconstruction of evolved dynamic networks from degree correlations
• Random Walk Fundamental Tensor and Its Applications to Network Analysis
• Mean field approximation for biased diffusion on Japanese inter-firm trading network
• Reaction-diffusion on random spatial networks with scale-free jumping rates via effective medium theory
• Non-equilibrium random walks on multiplex networks
• Slow dynamics of Zero Range Process in the Framework of Traps Model
• Random walk with priorities in communication-like networks
• Catching homologies by geometric entropy
• Prabhakar discrete-time generalization of the time-fractional Poisson process and related random walks
• Multiple predator based capture process on complex networks
• Exact mean first-passage time on generalized Vicsek fractal
• Sampling Graphlets of Multi-layer Networks: A Restricted Random Walk Approach
• Traffic properties for stochastic routings on scale-free networks
• Symbolic walk in regular networks
• Controlling the shape of small clusters with and without macroscopic fields
• Characterizing network topology using first-passage analysis
• Superdiffusion on complex networks: the role of shortcuts and long-range interactions
• Random walks on stochastic uniform growth trees: Analytical formula for mean first-passage time