Statistics of remote regions of networks

Abstract

We delve into the statistical properties of regions within complex networks that are distant from vertices with high centralities, such as hubs or highly connected clusters. These remote regions play a pivotal role in shaping the asymptotic behaviours of various spreading processes and the features of associated spectra. We investigate the probability distribution $P_{\ge m}(s)$ of the number $s$ of vertices located at distance $m$ or beyond from a randomly chosen vertex in an undirected network. Earlier, this distribution and its large $m$ asymptotics $1/s^2$ were obtained theoretically for undirected uncorrelated networks [S. N. Dorogovtsev, J. F. F. Mendes, A. N. Samukhin, Nucl. Phys. B 653 (2003) 307]. Employing numerical simulations and analysing empirical data, we explore a wide range of real undirected networks and their models, including trees and loopy networks, and reveal that the inverse square law is valid even for networks with strong correlations. We observe this law in the networks demonstrating the small-world effect and containing vertices with degree $1$ (so-called leaves or dead ends). We find the specific classes of networks for which this law is not valid. Such networks include the finite-dimensional networks and the networks embedded in finite-dimensional spaces. We notice that long chains of nodes in networks reduce the range of $m$ for which the inverse square law can be spotted. Interestingly, we detect such long chains in the remote regions of the undirected projection of a large Web domain.

arXiv comment13 pages, 10 figures, 2 tables, 1 ancillary file

References in corpus (18)

• Finding and evaluating community structure in networks
• Evolution of networks
• Subgraph Centrality in Complex Networks
• Organization of Growing Random Networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Localization and centrality in networks
• Spectral centrality measures in complex networks
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Directed network modules
• Metric structure of random networks
• Organization of modular networks
• Analytical results for the distribution of shortest path lengths in random networks
• Degree-dependent intervertex separation in complex networks
• The Network of Scientific Collaborations within the European Framework Programme
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• The interplay of university and industry through the FP5 network