Emergence of tempered preferential attachment from optimization

doi:10.1073/pnas.0606779104

Emergence of tempered preferential attachment from optimization

*Department of Mechanical and Aeronautical Engineering, University of California, Davis, CA 95616;
^‡Microsoft Research, Redmond, WA 98052;
^§Department of Mathematics, University of California, Los Angeles, CA 90095; and
^¶Department of Computer Science, Cornell University, Ithaca, NY 14853

Edited by H. Eugene Stanley, Boston University, Boston, MA, and approved February 2, 2007 (received for review August 6, 2006)

Abstract

We show how preferential attachment can emerge in an optimization framework, resolving a long-standing theoretical controversy. We also show that the preferential attachment model so obtained has two novel features, saturation and viability, which have natural interpretations in the underlying network and lead to a power-law degree distribution with exponential cutoff. Moreover, we consider a generalized version of this preferential attachment model with independent saturation and viability, leading to a broader class of power laws again with exponential cutoff. We present a collection of empirical observations from social, biological, physical, and technological networks, for which such degree distributions give excellent fits. We suggest that, in general, optimization models that give rise to preferential attachment with saturation and viability effects form a good starting point for the analysis of many networks.

Footnotes

^†To whom correspondence should be addressed. E-mail: raissa{at}cse.ucdavis.edu
Author contributions: R.M.D. designed research; R.M.D., C.B., J.T.C., N.B., and R.D.K. performed research; R.M.D. and C.B. analyzed data; and R.M.D., C.B., and J.T.C. wrote the paper.
The authors declare no conflict of interest.
This article is a PNAS Direct Submission.
This article contains supporting information online at www.pnas.org/cgi/content/full/0606779104/DC1.
Abbreviations:

PA,

preferential attachment;

TPA,

tempered PA;

AS,

autonomous system.
Freely available online through the PNAS open access option.