Hostname: page-component-7b7567c8c-mnklg Total loading time: 0 Render date: 2026-11-12T19:37:10.446Z Has data issue: false hasContentIssue false
  • English
  • Français

Typical Distances in Ultrasmall Random Networks

Part of:Graph theoryCombinatorial probabilityOperations research and management science

Published online by Cambridge University Press:  04 January 2016

Steffen Dereich,
Christian Mönch and
Peter Mörters
Steffen Dereich*
Affiliation:
Philipps-Universität Marburg
Christian Mönch*
Affiliation:
University of Bath
Peter Mörters*
Affiliation:
University of Bath
*
∗ Postal address: Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Hans-Meerwein-Straβe, 35032 Marburg, Germany.
∗∗ Postal address: Department of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, UK.
∗∗ Postal address: Department of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that in preferential attachment models with power-law exponent τ ∈ (2, 3) the distance between randomly chosen vertices in the giant component is asymptotically equal to (4 + o(1))log log N / (-log(τ − 2)), where N denotes the number of nodes. This is twice the value obtained for the configuration model with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.

Keywords

Scale-free networkpreferential attachmentconfiguration modelpower-law graphconditionally Poissonian graphgraph distancediameter

MSC classification

Primary:05C80: Random graphs
Secondary:60C05: Combinatorial probability90B15: Network models, stochastic

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 44 , Issue 2 , June 2012, pp. 583 - 601
Copyright
© Applied Probability Trust 

References

Bennett, G. (1962). Probability inequalities for the sum of independent random variables. J. Amer. Statist. Assoc. 57, 33–45.CrossRefGoogle Scholar
Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 24, 5–34.CrossRefGoogle Scholar
Cohen, R. and Havlin, S. (2003). Scale-free networks are ultrasmall. Phys. Rev. Lett. 90, 058701, 4 pp.Google Scholar
Chung, F. and Lu, L. (2003). The average distance in a random graph with given expected degrees. Internet Math. 1, 91–113.CrossRefGoogle Scholar
Chung, F. and Lu, L. (2006). Complex Graphs and Networks (CBMS Regional Conf. Math. 107). American Mathematical Society, Providence RI.CrossRefGoogle Scholar
Dommers, S., van der Hofstad, R. and Hooghiemstra, G. (2010). Diameters in preferential attachment models. J. Statist. Phys. 139, 72–107.Google Scholar
Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Prob. 14, 1222–1267.CrossRefGoogle Scholar
Dereich, S. and Mörters, P. (2011). Random networks with concave preferential attachment rule. Jahresber. Deutschen Math. Ver. 113, 21–40.CrossRefGoogle Scholar
Dereich, S. and Mörters, P. (2012). Random networks with sublinear preferential attachment: the giant component. To appear in Ann. Prob..Google Scholar
Dorogovtsev, S. N., Mendes, J. F. F. and Samukhin, A. N. (2003). Metric strucure of random networks. Nuclear Phys. B 653, 307–338.CrossRefGoogle Scholar
Mönch, C. (2012). Distances in preferential attachment networks. Doctoral Thesis, University of Bath.Google Scholar
Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. Appl. Prob. 38, 59–75.CrossRefGoogle Scholar
Norros, I. and Reittu, H. (2008). Network models with a ‘soft hierarchy’: a random graph construction with loglog scalability. IEEE Network 22, 40–46.Google Scholar
Reittu, H. and Norros, I. (2002). On the effect of very large nodes in internet graphs. In GLOBECOM '02, Vol. III (Proc. Global Telecommun. Conf., Taipei, 2002), pp. 2624–2628.Google Scholar
Resnick, S. I. (2008). Extreme Values, Regular Variation and Point Processes. Springer, New York.Google Scholar
Van der Hofstad, R. (2010). Random graphs and complex networks. Lecture Notes, Eindhoven University of Technology.Google Scholar
Van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2007). Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Prob. 12, 703–766.Google Scholar
Van der Hofstad, R. and Hooghiemstra, G. (2008). Universality for distances in power-law random graphs. J. Math. Phys. 49, 125209, 14 pp.Google Scholar