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

DOI:
https://doi.org/10.1090/S1079-6762-03-00123-9

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.

**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.

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

Email:
aldous@stat.berkeley.edu

DOI:
https://doi.org/10.1090/S1079-6762-03-00123-9

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