Ring structures and mean first passage time in networks

Abstract

In this paper we address the problem of the calculation of the mean first passage time (MFPT) on generic graphs. We focus in particular on the mean first passage time on a node 's' for a random walker starting from a generic, unknown, node 'x'. We introduce an approximate scheme of calculation which maps the original process in a Markov process in the space of the so-called rings, described by a transition matrix of size O(ln N / ln<k> X ln N / ln<k>), where N is the size of the graph and <k> the average degree in the graph. In this way one has a drastic reduction of degrees of freedom with respect to the size N of the transition matrix of the original process, corresponding to an extremely-low computational cost. We first apply the method to the Erdos-Renyi random graph for which the method allows for almost perfect agreement with numerical simulations. Then we extend the approach to the Barabasi-Albert graph, as an example of scale-free graph, for which one obtains excellent results. Finally we test the method with two real world graphs, Internet and a network of the brain, for which we obtain accurate results.

8 pages, 8 figures

References in corpus (12)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Scale-free brain functional networks
• Dynamical and correlation properties of the Internet
• Search in Power-Law Networks
• Exploring complex networks by walking on them
• Scale-Free Networks Generated By Random Walkers
• First Passage Properties of the Erdos-Renyi Random Graph
• Scaling Properties of Random Walks on Small-World Networks
• Scale Free Networks from Self-Organisation
• Random walk and trapping processes on scale-free networks

Cited by in corpus (32)

• Random walks and diffusion on networks
• Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
• Exact mean first-passage time on the T-graph
• Spectral coarse-graining of complex networks
• Structure of shells in complex networks
• The unreasonable effectiveness of tree-based theory for networks with clustering
• Linking the Network Centrality Measures Closeness and Degree
• Characteristic times of biased random walks on complex networks
• Mean-field diffusive dynamics on weighted networks
• Random walks on complex trees
• Random walks on activity-driven networks with attractiveness
• Trapping in complex networks
• Asymptotic analysis of first passage time in complex networks
• Modularity produces small-world networks with dynamical time-scale separation
• Distance distribution in random graphs and application to networks exploration
• Bosonic reaction-diffusion processes on scale-free networks
• Trapping in scale-free networks with hierarchical organization of modularity
• Hitting and Trapping Times on Branched Structures
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs
• Anomalous biased diffusion in networks
• NIAPU: network-informed adaptive positive-unlabeled learning for disease gene identification
• Spectral coarse graining for random walk in bipartite networks
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Temporal-varying failures of nodes in networks
• The joint distribution of first return times and of the number of distinct sites visited by a 1D random walk before returning to the origin
• Mean First Passage Time in Periodic Attractors
• Optimal search strategies on complex networks
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Mass-Scale Analysis of In-the-Wild Conversations Reveals Complexity Bounds on LLM Jailbreaking
• Controlling the shape of small clusters with and without macroscopic fields