Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect

Abstract

A vast variety of real-life networks display the ubiquitous presence of scale-free phenomenon and small-world effect, both of which play a significant role in the dynamical processes running on networks. Although various dynamical processes have been investigated in scale-free small-world networks, analytical research about random walks on such networks is much less. In this paper, we will study analytically the scaling of the mean first-passage time (MFPT) for random walks on scale-free small-world networks. To this end, we first map the classical Koch fractal to a network, called Koch network. According to this proposed mapping, we present an iterative algorithm for generating the Koch network, based on which we derive closed-form expressions for the relevant topological features, such as degree distribution, clustering coefficient, average path length, and degree correlations. The obtained solutions show that the Koch network exhibits scale-free behavior and small-world effect. Then, we investigate the standard random walks and trapping issue on the Koch network. Through the recurrence relations derived from the structure of the Koch network, we obtain the exact scaling for the MFPT. We show that in the infinite network order limit, the MFPT grows linearly with the number of all nodes in the network. The obtained analytical results are corroborated by direct extensive numerical calculations. In addition, we also determine the scaling efficiency exponents characterizing random walks on the Koch network.

12 pages, 8 figures. Definitive version published in Physical Review E

References in corpus (43)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Assortative mixing in networks
• Evolution of networks
• Specificity and stability in topology of protein networks
• Network robustness and fragility: Percolation on random graphs
• Characterization of complex networks: A survey of measurements
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Hierarchical Organization in Complex Networks
• Dynamical and correlation properties of the Internet
• Breakdown of the Internet under intentional attack
• Large-scale topological and dynamical properties of Internet
• First-passage times in complex scale-invariant media
• Pseudofractal Scale-free Web
• Self-organization of collaboration networks
• 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
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Self-similar disk packings as model spatial scale-free networks
• Exact mean first-passage time on the T-graph
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Recursive graphs with small-world scale-free properties
• First Passage Properties of the Erdos-Renyi Random Graph
• High Dimensional Apollonian Networks
• Random walks on complex trees
• Evolving Apollonian Networks with Small-world Scale-free topologies
• A general geometric growth model for pseudofractal scale-free web
• Exact analytical solution of average path length for Apollonian networks
• Random walks on the Apollonian network with a single trap
• Evolving small-world scale-free networks consist of cliques
• Fractal scale-free networks resistant to disease spread
• Walks on Apollonian networks
• Correlations in random Apollonian network
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Random walks and diameter of finite scale-free networks
• The rigorous solution for the average distance of a Sierpinski network

Cited by in corpus (25)

• Global mean first-passage times of random walks on complex networks
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
• Mean first-passage time for random walks on undirected networks
• Weighted Fractal Networks
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Trapping in dendrimers and regular hyperbranched polymers
• Fractal and multifractal properties of a family of fractal networks
• Mapping Koch curves into scale-free small-world networks
• Trapping in scale-free networks with hierarchical organization of modularity
• Influence of trap location on the efficiency of trapping in dendrimers and regular hyperbranched polymers
• 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
• Random walks in modular scale-free networks with multiple traps
• Counting spanning trees in self-similar networks by evaluating determinants
• Role of fractal dimension in random walks on scale-free networks
• Mean first-passage time for random walks in general graphs with a deep trap
• Impact of degree heterogeneity on the behavior of trapping in Koch networks
• Controlling the efficiency of trapping in treelike fractals
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Origin of the hub spectral dimension in scale-free networks
• Constructions and properties of a class of random scale-free networks
• Complete escape from localization on a hierarchical lattice: A Koch fractal with all states extended
• Stochastic Weighted Fractal Networks
• Extended corona product as an exactly tractable model for weighted heterogeneous networks