Degree-dependent intervertex separation in complex networks

Abstract

We study the mean length $\ell (k)$ of the shortest paths between a vertex of degree $k$ and other vertices in growing networks, where correlations are essential. In a number of deterministic scale-free networks we observe a power-law correction to a logarithmic dependence, $\ell (k)=A\ln [N/k^{(\gamma -1)/2}]-C{k}^{\gamma -1}/N+...$ in a wide range of network sizes. Here $N$ is the number of vertices in the network, $\gamma$ is the degree distribution exponent, and the coefficients $A$ and $C$ depend on a network. We compare this law with a corresponding $\ell (k)$ dependence obtained for random scale-free networks growing through the preferential attachment mechanism. In stochastic and deterministic growing trees with an exponential degree distribution, we observe a linear dependence on degree, $\ell (k)\cong A\ln N-Ck$. We compare our findings for growing networks with those for uncorrelated graphs.

8 pages, 3 figures

References in corpus (8)

• Average path length in uncorrelated random networks with hidden variables
• Self-similar disk packings as model spatial scale-free networks
• Recursive graphs with small-world scale-free properties
• Universal scaling of distances in complex networks
• Statistics of Cycles: How Loopy is your Network?
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Minimal models of weighted scale-free networks
• Dependence of the average to-node distance on the node degree for random graphs and growing networks

Cited by in corpus (20)

• Public transport networks: empirical analysis and modeling
• Random walks on complex trees
• Exact solution of mean geodesic distance for Vicsek fractals
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Exact analytical solution of average path length for Apollonian networks
• The Workshop on Internet Topology (WIT) Report
• Fractal Boundaries of Complex Networks
• Fractal scale-free networks resistant to disease spread
• Average distance in a hierarchical scale-free network: an exact solution
• Topologies and Laplacian spectra of a deterministic uniform recursive tree
• Recursive solutions for Laplacian spectra and eigenvectors of a class of growing treelike networks
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Random walks in small-world exponential treelike networks
• Structural and spectral properties of a family of deterministic recursive trees: Rigorous solutions
• The rigorous solution for the average distance of a Sierpinski network
• The interplay of university and industry through the FP5 network
• An alternative approach to determining average distance in a class of scale-free modular networks
• Degree and component size distributions in generalized uniform recursive tree
• Deterministic simplicial complexes
• Statistics of remote regions of networks