Remote Access Electronic Research Announcements

Electronic Research Announcements

ISSN 1079-6762



A stochastic complex network model

Author: David J. Aldous
Translated by:
Journal: Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 152-161
MSC (2000): Primary 60K35; Secondary 05C80, 90B15, 94C15
Published electronically: December 18, 2003
MathSciNet review: 2029476
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a stochastic model for complex networks possessing three qualitative features: power-law degree distributions, local clustering, and slowly growing diameter. The model is mathematically natural, permits a wide variety of explicit calculations, has the desired three qualitative features, and fits the complete range of degree scaling exponents and clustering parameters.

References [Enhancements On Off] (What's this?)

  • 1. R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002), 47-97. MR 2003d:82055
  • 2. D.J. Aldous and A.G. Percus, Scaling and universality in continuous length combinatorial optimization, Proc. Natl. Acad. Sci. USA 100 (2003), 11211-11215.
  • 3. D.J. Aldous, A tractable complex network model based on the stochastic mean-field model of distance, arXiv:cond-mat/0304701, 2003.
  • 4. D.J. Aldous and J.M. Steele, The objective method: Probabilistic combinatorial optimization and local weak convergence, in Probability on Discrete Structures, H. Kesten (ed.), 1-72, Springer, 2003.
  • 5. A.L. Barabási, Linked: the new science of networks, Perseus Press, Cambridge, MA, 2002.
  • 6. B. Bollobás and O. Riordan, Mathematical results on scale-free random graphs, Handbook of Graphs and Networks (S. Bornholdt and H.G. Schuster, eds.), Wiley, 2002.
  • 7. M. Buchanan, Nexus: Small worlds and the groundbreaking science of networks, W.W. Norton, 2002.
  • 8. S.N. Dorogovtsev and J.F.F. Mendes, Evolution of networks, Adv. Phys. 51 (2002), 1079-1187.
  • 9. A. Fabrikant, E. Koutsoupias, and C.H. Papadimitriou, Heuristically optimized trade-offs: a new paradigm for power laws in the internet, International Colloq. Automata, Languages and Programming, 2002.
  • 10. J. Jost and M.P. Joy, Evolving networks with distance preferences, Physical Review E 66 (2002), 036126. MR 2002i:37133
  • 11. F. Menczer, Growing and navigating the small world web by local content, Proc. Natl. Acad. Sci. USA 99 (2002), 14014-14019.
  • 12. J.F.F. Mendes and S.N. Dorogovtsev, Evolution of networks: From biological nets to the internet and WWW, Oxford Univ. Press, 2003.
  • 13. M.E.J. Newman, The structure and function of complex networks, SIAM Review 45 (2003), 167-256.
  • 14. E. Ravasz and A.L. Barabási, Hierarchical organization in complex networks, Physical Review E 67 (2003), 026112.
  • 15. D.J. Watts, Six degrees: the science of a connected age, W.W. Norton, 2003.
  • 16. G.U. Yule, A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, Philos. Trans. Roy. Soc. London Ser. B 213 (1924), 21-87.

Similar Articles

Retrieve articles in Electronic Research Announcements of the American Mathematical Society with MSC (2000): 60K35, 05C80, 90B15, 94C15

Retrieve articles in all journals with MSC (2000): 60K35, 05C80, 90B15, 94C15

Additional Information

David J. Aldous
Affiliation: Department of Statistics, 367 Evans Hall, U.C. Berkeley, CA 94720

Keywords: Complex network, Poisson process, PWIT, random graph, scale-free, small worlds, Yule process
Received by editor(s): July 22, 2003
Published electronically: December 18, 2003
Additional Notes: The author was supported in part by NSF Grant DMS-0203062.
Communicated by: Ronald L. Graham

American Mathematical Society