Degree-dependent intervertex separation in complex networks

We study the mean length (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, (k)=A0.2em0exln[N∕k^(γ-1)∕2]-Ck^γ-1∕N+⋯ in a wide range of network sizes. Here N is the number of vertices in the network, γ is the degree distribution exponent, and the coefficients A and C depend on a network. We compare this law with a corresponding (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, (k)A0.2em0exln0.2em0exN-Ck. We compare our findings for growing networks with those for uncorrelated graphs.