When is a scale-free graph ultra-small?
arXiv:1611.03639 · doi:10.1007/s10955-017-1864-1
Abstract
In this paper we study typical distances in the configuration model, when the degrees have asymptotically infinite variance. We assume that the empirical degree distribution follows a power law with exponent , up to value for some and . This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law distributions where the (possibly exponential) truncation happens at . We show that the graph distance between two uniformly chosen vertices centers around , with tight fluctuations. Thus, the graph is an \emph{ultrasmall world} whenever . We determine the distribution of the fluctuations around this value, in particular we prove that these are non-converging tight random variables that show -periodicity. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order , where is a random variable that oscillates with . The two end-segments of any shortest path have length +tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length +tight, and it contains only vertices with degree at least of order , thus all the degrees on this segment are comparable to the maximal degree. Our theorems also apply when instead of truncating the degrees, we start with a configuration model and we remove every vertex with degree at least , and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.
arXiv comment36 pages, 1 figure
References in corpus (21)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Power-law distributions in empirical data
- Error and attack tolerance of complex networks
- Power laws, Pareto distributions and Zipf's law
- The structure of scientific collaboration networks
- The large-scale organization of metabolic networks
- Classes of behavior of small-world networks
- Attack vulnerability of complex networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Breakdown of the Internet under intentional attack
- The Web of Human Sexual Contacts
- Scale-Free Networks are Ultrasmall
- Average path length in random networks
- Average path length in uncorrelated random networks with hidden variables
- Truncation of power law behavior in "scale-free" network models due to information filtering
- Metric structure of random networks
- Universal scaling of distances in complex networks
- First passage percolation on random graphs with finite mean degrees
- Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models