Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks

Abstract

Various real-life networks exhibit degree correlations and heterogeneous structure, with the latter being characterized by power-law degree distribution $P(k)\sim k^{-\gamma }$, where the degree exponent $\gamma$ describes the extent of heterogeneity. In this paper, we study analytically the average path length (APL) of and random walks (RWs) on a family of deterministic networks, recursive scale-free trees (RSFTs), with negative degree correlations and various $\gamma \in (2,1+\frac{\ln 3}{\ln 2}]$, with an aim to explore the impacts of structure heterogeneity on APL and RWs. We show that the degree exponent $\gamma$ has no effect on APL $d$ of RSFTs: In the full range of $\gamma$, $d$ behaves as a logarithmic scaling with the number of network nodes $N$ (i.e. $d\sim \ln N$), which is in sharp contrast to the well-known double logarithmic scaling ($d\sim \ln \ln N$) previously obtained for uncorrelated scale-free networks with $2\le \gamma <3$. In addition, we present that some scaling efficiency exponents of random walks are reliant on degree exponent $\gamma$.

arXiv commentThe definitive verion published in Journal of Mathematical Physics

References in corpus (26)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• Evolution of networks
• Specificity and stability in topology of protein networks
• Evolutionary games on graphs
• Dynamical and correlation properties of the Internet
• Scale-Free Networks are Ultrasmall
• First-passage times in complex scale-invariant media
• Origins of fractality in the growth of complex networks
• Pseudofractal Scale-free Web
• Scaling theory of transport in complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• 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
• First Passage Properties of the Erdos-Renyi Random Graph
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Random walks on complex trees
• Evolving small-world scale-free networks consist of cliques
• Degree-dependent intervertex separation in complex networks
• Recursive weighted treelike networks
• Transition from fractal to non-fractal scalings in growing scale-free networks
• Random walks and diameter of finite scale-free networks
• Border trees of complex networks
• Synchronous and Asynchronous Recursive Random Scale-Free Nets

Cited by in corpus (11)

• Global mean first-passage times of random walks on complex networks
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Trapping in scale-free networks with hierarchical organization of modularity
• 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
• Anomalous behavior of trapping on a fractal scale-free network
• Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks
• Exact encounter times for many random walkers on regular and complex networks
• Fast solver for diffusive transport times on dynamic intracellular networks