Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Abstract

A lot of previous work showed that the sectional mean first-passage time (SMFPT), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order $N$ (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the partial mean first-passage time (PMFPT) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the PMFPT grows with network order as $N\ln N$, which is larger than the linear scaling of SMFPT to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the entire mean first-passage time (EMFPT), namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of PMFPT. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that the location of information sender has little effect on the transmission efficiency. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.

arXiv commentDefinitive version published in European Physical Journal B

References in corpus (26)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Epidemic spreading in scale-free networks
• Synchronization in complex networks
• Evolution of networks
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• First-passage times in complex scale-invariant media
• Geometry-controlled kinetics
• Scaling theory of transport in complex networks
• Probing microscopic origins of confined subdiffusion by first-passage observables
• Global mean first-passage times of random walks on complex networks
• Optimal reaction time for surface-mediated diffusion
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• 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
• Trapping in complex networks
• Random walks on the Apollonian network with a single trap
• Ring structures and mean first passage time in networks
• Effective target arrangement in a deterministic scale-free graph
• Mapping Koch curves into scale-free small-world networks
• 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

Cited by in corpus (4)

• Efficiency analysis of diffusion on T-fractals in the sense of random walks
• Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
• Effects of node position on diffusion and trapping efficiency for random walks on fractal scale-free trees
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network