Trapping in scale-free networks with hierarchical organization of modularity

Abstract

A wide variety of real-life networks share two remarkable generic topological properties: scale-free behavior and modular organization, and it is natural and important to study how these two features affect the dynamical processes taking place on such networks. In this paper, we investigate a simple stochastic process--trapping problem, a random walk with a perfect trap fixed at a given location, performed on a family of hierarchical networks that exhibit simultaneously striking scale-free and modular structure. We focus on a particular case with the immobile trap positioned at the hub node having the largest degree. Using a method based on generating functions, we determine explicitly the mean first-passage time (MFPT) for the trapping problem, which is the mean of the node-to-trap first-passage time over the entire network. The exact expression for the MFPT is calculated through the recurrence relations derived from the special construction of the hierarchical networks. The obtained rigorous formula corroborated by extensive direct numerical calculations exhibits that the MFPT grows algebraically with the network order. Concretely, the MFPT increases as a power-law function of the number of nodes with the exponent much less than 1. We demonstrate that the hierarchical networks under consideration have more efficient structure for transport by diffusion in contrast with other analytically soluble media including some previously studied scale-free networks. We argue that the scale-free and modular topologies are responsible for the high efficiency of the trapping process on the hierarchical networks.

Definitive version accepted for publication in Physical Review E

References in corpus (24)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Comparing community structure identification
• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Classes of complex networks defined by role-to-role connectivity profiles
• Scaling theory of transport in complex networks
• Probing microscopic origins of confined subdiffusion by first-passage observables
• Fractal and Transfractal Recursive Scale-Free Nets
• Exact mean first-passage time on the T-graph
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• A deterministic small-world network created by edge iterations
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Random Walks on deterministic Scale-Free networks: Exact results
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Random walks on complex trees
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Ring structures and mean first passage time in networks
• Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
• Anomalous behavior of trapping on a fractal scale-free network
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Random Walks on Complex Networks

Cited by in corpus (19)

• Random walks and diffusion on networks
• Random walks on weighted networks
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Exact calculations of first-passage quantities on recursive networks
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Mean first-passage time for random walks on undirected networks
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Trapping in dendrimers and regular hyperbranched polymers
• Effective target arrangement in a deterministic scale-free graph
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• Random walks in modular scale-free networks with multiple traps
• 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
• Counterexample: scale-free networked graphs with invariable diameter and density feature
• Effects of reciprocity on random walks in weighted networks
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• An alternative approach to determining average distance in a class of scale-free modular networks
• Dynamics Motivated by Sierpinski Fractals