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 (55)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Hierarchical organization of modularity in metabolic networks
• Evolution of networks
• Comparing community structure identification
• Critical phenomena in complex networks
• Hierarchical Organization in Complex Networks
• Scale-Free Networks are Ultrasmall
• First-passage times in complex scale-invariant media
• Pseudofractal Scale-free Web
• Deterministic Scale-Free Networks
• Optimal search strategies for hidden targets
• Scaling theory of transport in complex networks
• Probing microscopic origins of confined subdiffusion by first-passage observables
• Fractal and Transfractal Recursive Scale-Free Nets
• Random walks on graphs: ideas, techniques and results
• Global mean first-passage times of random walks on complex networks
• A Geometric Fractal Growth Model for Scale Free Networks
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• 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
• First Passage Properties of the Erdos-Renyi Random Graph
• 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
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Random walks on complex trees
• Random spread on the family of small-world networks
• Mean first-passage time for random walks on undirected networks
• Exact scaling properties of a hierarchical network model
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Hierarchical, Regular Small-World Networks
• Effective target arrangement in a deterministic scale-free graph
• Trapping in scale-free networks with hierarchical organization of modularity
• Mean first-passage time for random walks on the T-graph
• Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
• 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
• Exactly solvable scale-free network model
• 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
• Planar unclustered scale-free graphs as models for technological and biological networks
• Contact graphs of disk packings as a model of spatial planar networks
• An alternative approach to determining average distance in a class of scale-free modular networks
• Order statistics of Rosenstock's trapping problem in disordered media
• 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