Exact calculations of first-passage quantities on recursive networks

Abstract

We present general methods to exactly calculate mean-first passage quantities on self-similar networks defined recursively. In particular, we calculate the mean first-passage time and the splitting probabilities associated to a source and one or several targets; averaged quantities over a given set of sources (e.g., same-connectivity nodes) are also derived. The exact estimate of such quantities highlights the dependency of first-passage processes with respect to the source-target distance, which has recently revealed to be a key parameter to characterize transport in complex media. We explicitly perform calculations for different classes of recursive networks (finitely ramified fractals, scale-free (trans)fractals, non-fractals, mixtures between fractals and non-fractals, non-decimable hierarchical graphs) of arbitrary size. Our approach unifies and significantly extends the available results in the field.

16 pages, 10 figures

References in corpus (11)

• Critical phenomena in complex networks
• Intermittent search strategies
• First-passage times in complex scale-invariant media
• Scaling theory of transport in complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Exact mean first-passage time on the T-graph
• Percolation in Hierarchical Scale-Free Nets
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Average distance in a hierarchical scale-free network: an exact solution
• Flexible construction of hierarchical scale-free networks with general exponent
• Random Walks on Complex Networks

Cited by in corpus (40)

• Restart could optimize the probability of success in a Bernoulli trial
• Random walks on weighted networks
• Characteristic times of biased random walks on complex networks
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Trapping in dendrimers and regular hyperbranched polymers
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• Mean first-passage time for maximal-entropy random walks in complex networks
• Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
• Mean first-passage time for random walks in general graphs with a deep trap
• Scaling laws for diffusion on (trans)fractal scale-free networks
• Slow Encounters of Particle Pairs in Branched Structures
• Deterministic hierarchical networks
• Controlling the efficiency of trapping in treelike fractals
• Exact results for the first-passage properties in a class of fractal networks
• Hitting and Trapping Times on Branched Structures
• Efficiency analysis of diffusion on T-fractals in the sense of random walks
• Origin of the hub spectral dimension in scale-free networks
• Contact Kinetics in Fractal Macromolecules
• Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Multitarget search on complex networks: A logarithmic growth of global mean random cover time
• Local orientational mobility in regular hyperbranched polymers
• Mean trapping time for an arbitrary node on regular hyperbranched polymers
• Effects of reciprocity on random walks in weighted networks
• Topological dimension tunes activity patterns in hierarchical modular network models
• Diffusion on hierarchical systems of weakly-coupled networks
• First-passage properties of mortal random walks: ballistic behavior, effective reduction of dimensionality, and scaling functions for hierarchical graphs
• Analysis of fluctuations in the first return times of random walks on regular branched networks
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Counting spanning trees on fractal graphs and their asymptotic complexity
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• Effects of node position on diffusion and trapping efficiency for random walks on fractal scale-free trees
• Anomalous behavior of trapping in extended dendrimers with a perfect trap
• From Maximum of Intervisit Times to Starving Random Walks
• Average trapping time on a type of horizontally segmented 3 dimensional Sierpinski gasket network with two types of locally self-similar structures
• Topology-dependent density optima for efficient simultaneous network exploration
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• First-passage times to a fractal boundary: local persistence exponent and its log-periodic oscillations