Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 12 (2007) > Paper 25 open journal systems 


Distances in random graphs with finite mean and infinite variance degrees

Remco W. van der Hofstad, Eindhoven University of Technology
Gerard Hooghiemstra, Delft University of Technology
Dmitri Znamenski, EURANDOM


Abstract
In this paper we study typical distances in random graphs with i.i.d. degrees of which the tail of the common distribution function is regularly varying with exponent 1-τ. Depending on the value of the parameter τ we can distinct three cases: (i) τ>3, where the degrees have finite variance, (ii) τ in (2,3), where the degrees have infinite variance, but finite mean, and (iii) τ in (1,2), where the degrees have infinite mean. The distances between two randomly chosen nodes belonging to the same connected component, for τ>3 and τ in (1,2), have been studied in previous publications, and we survey these results here. When τ in (2,3), the graph distance centers around 2 log log{N}/| log(τ-2)|. We present a full proof of this result, and study the fluctuations around this asymptotic means, by describing the asymptotic distribution. The results presented here improve upon results of Reittu and Norros, who prove an upper bound only. The random graphs studied here can serve as models for complex networks where degree power laws are observed; this is illustrated by comparing the typical distance in this model to Internet data, where a degree power law with exponent τ approximately 2.2 is observed for the so-called Autonomous Systems (AS) graph.


Full text: PDF

Pages: 703-766

Published on: May 28, 2007
Bibliography
  1. R. Albert; A.-L. Barabási. Statistical mechanics of complex networks. Rev. Modern Phys. 74 (2002), 47-97. Math. Review 2003d:82055
  2. N. Alon; J. Spencer. The probabilistic method. Second edition. Wiley-Interscience, New York (2000). Math. Review 2003f:60003
  3. B. Bollobás. Random Graphs, 2nd edition. Cambridge University Press, Cambridge (2001). Math. Review 2002j:05132
  4. B. Bollobás; S. Janson; O. Riordan. The phase transition in inhomogeneous random graphs. To appear in Random Structures Algorithms. Available on http://arxiv.org/abs/math.PR/0504589
  5. T. Britton; M. Deijfen; M. Martin-Löf. Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124 (2006), no. 6, 1377--1397. Math. Review MR2266448
  6. F. Chung; L. Lu. The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99 (2002), no. 25, 15879--15882 (electronic). Math. Review 2003k:05124
  7. R. Cohen; S. Havlin. Scale free networks are ultrasmall. Phys. Rev. Lett., 90(2003), 058701, 1--4. Math. Review number not available.
  8. P.L. Davies. The simple branching process: a note on convergence when the mean is infinite. J. Appl. Probab. 15 (1978), no. 3, 466--480. Math. Review MR0483050
  9. R. Durrett. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2006). Math. Review MR2271734
  10. H. van den Esker; R. van der Hofstad; G. Hooghiemstra; D. Znamenski. Distances in random graphs with infinite mean degrees. Extremes 8 (2005), 111--141. Math. Review MR2275914
  11. A. Gut. Probability: a graduate course. Springer, New York (2005). Math. Review MR2125120
  12. C. Faloutsos, P. Faloutsos and M. Faloutsos. On power-law relationships of the internet topology. Comp. Comm. Rev., 29(1999), 251-262. Math. Review number not available.
  13. W. Feller, William. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons, New York (1971) Math. Review MR0270403
  14. R. van der Hofstad; G. Hooghiemstra; P. Van Mieghem. Distances in random graphs with finite variance degrees. Random Structures Algorithms 27 (2005), 76--123. Math. Review 2006d:60019
  15. R. van der Hofstad, G. Hooghiemstra, and D. Znamenski. Random graphs with arbitrary i.i.d. degrees. Preprint (2005). Math. Review number not available.
  16. S. Janson. On concentration of probability. Contemporary Combinatorics, ed. B. Bollobás, Bolyai Soc. Math. Stud., János Bolyai Mathematical Society, Budapest,10 (2002), 289--301. Math. Review MR1919574
  17. S. Janson; T. L uczak; A. Rucinski. Random Graphs. John Wiley & Sons, New York (2000). Math. Review 2001k:05180
  18. M.E.J. Newman. The structure and function of complex networks. SIAM Rev. 45 (2003), 167--256. Math. Review 2005a:05206
  19. M.E.J. Newman; S.H. Strogatz; D.J. Watts. Random graphs with arbitrary degree distribution and their application. Phys. Rev. E 64 (2002), 026118. Math. Review number not available.
  20. I. Norros; H. Reittu. On a conditionally Poissonean graph process. Adv. Appl. Prob. 38 (2006), 59--75. Math. Review 2006m:05227
  21. H. Reittu; I. Norros. On the power law random graph model of massive data networks. Performance Evalution 55 (2004), 3--23. Math. Review number not available.
  22. H-J. Schuh; A.D. Barbour. On the asymptotic behaviour of branching processes with infinite mean. Adv. Appl. Probab. 9 (1977), 681--723. Math. Review MR0478378
  23. E. Seneta. The simple branching processes with infinite mean.I. J. Appl. Probab. 10 (1973), 206--212. Math. Review MR0413293
  24. H. Tangmunarunkit; R. Govindan; S. Jamin; S. Shenker; W. Willinger. Network topology generators: Degree-based vs. structural. Proceedings of ACM Sigcomm, Pittsburgh, Pennsylvania, USA (2002), 147--159. Math. Review number not available.
  25. D.J. Watts. Small Worlds, The Dynamics of Networks between Order and Randomness. Princeton University Press, Princeton, New Jersey (1999). Math. Review 2001a:91064
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489