Distances in scale free networks at criticality

Steffen Dereich, Christian Mönch, Peter Morters

Research output: Contribution to journalArticlepeer-review

2 Citations (SciVal)


Scale-free networks with moderate edge dependence experience a phase transition between ultrasmall and small world behaviour when the power law exponent passes the critical value of three. Moreover, there are laws of large numbers for the graph distance of two randomly chosen vertices in the giant component. When the degree distribution follows a pure power law these show the same asymptotic distances of logN/log logN at the critical value three, but in the ultrasmall regime reveal a difference of a factor two between the most-studied rank-one and preferential attachment model classes. In this paper we identify the critical window where this factor emerges. We look at models from both classes when the asymptotic proportion of vertices with degree at least k scales like k-2(log k)2α+o(1) and show that for preferential attachment networks the typical distance is (1/1+α + o(1)) logN/log logN in probability as the number N of vertices goes to infinity. By contrast the typical distance in a rank one model with the same asymptotic degree sequence is (1/1+2α + o(1)) logN/log logN. As α → ∞ we see the emergence of a factor two between the length of shortest paths as we approach the ultrasmall regime
Original languageEnglish
Article number77
Number of pages38
JournalElectronic Journal of Probability
Publication statusPublished - 31 Dec 2017


Dive into the research topics of 'Distances in scale free networks at criticality'. Together they form a unique fingerprint.

Cite this