Random walks in modular scale-free networks with multiple traps

Abstract

Extensive empirical investigation has shown that a plethora of real networks synchronously exhibit scale-free and modular structure, and it is thus of great importance to uncover the effects of these two striking properties on various dynamical processes occurring on such networks. In this paper, we examine two cases of random walks performed on a class of modular scale-free networks with multiple traps located at several given nodes. We first derive a formula of the mean first-passage time (MFPT) for a general network, which is the mean of the expected time to absorption originating from a specific node, averaged over all non-trap starting nodes. Although the computation is complex, the expression of the formula is exact; moreover, the computational approach and procedure are independent of the number and position of the traps. We then determine analytically the MFPT for the two random walks being considered. The obtained analytical results are in complete agreement with the numerical ones. Our results show that the number and location of traps play an important role in the behavior of the MFPT, since for both cases the MFPT grows as a power-law function of the number of nodes, but their exponents are quite different. We demonstrate that the root of the difference in the behavior of MFPT is attributed to the modular and scale-free topologies of the networks. This work can deepen the understanding of diffusion on networks with modular and scale-free architecture and motivate relevant studies for random walks running on complex random networks with multiple traps.

Definitive version accepted for publication in Physical Review E

References in corpus (27)

• 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
• 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
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Random walks on complex trees
• Mean first-passage time for random walks on undirected networks
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Hierarchical, Regular Small-World Networks
• Mean first-passage time for random walks on the T-graph
• Close or connected? Distance and connectivity effects on transport in networks
• Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
• Average distance in a hierarchical scale-free network: an exact solution
• 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
• Contact graphs of disk packings as a model of spatial planar networks
• Random Walks on Complex Networks

Cited by in corpus (11)

• Random walks on weighted 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
• 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
• Levy random walks on multiplex networks
• Spectral coarse graining for random walk in bipartite 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
• Fast Computation of Kemeny's Constant for Directed Graphs