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)

View larger version:
- In this window
- In a new window
- Download as PowerPoint Slide
Fig. 1.
The one-parameter TPA model. (A) An example of the growth process on the line, with 1/α = 4. Node t arrives and wants to minimize the cost function αn _tj + h _j, where n _tj is the number of existing nodes in the interval between t and j, and h _j is the hop-count of node j to the root. The minimization can only be achieved by connecting to the adjacent node i (so that n _ti = 0), or to the parent of i (which has h _p = h _i − 1). If n _tp ≥ 1/α (as is the case illustrated), i gains the new attachment, otherwise p does. Thus as soon as there are 1/α children of node p, node p's attractiveness saturates. (B) The equivalent network structure resulting from the growth process on the line.
View larger version:
- In this window
- In a new window
- Download as PowerPoint Slide
Fig. 2.
CCDF of the “Whois” AS-level connectivity of the Internet. The circles are data compiled by CAIDA from the RIPE WHOIS database (5, 6). The line is the theoretical TPA CCDF with A1 = 187 and A2 = 90 (resulting in the power law portion of the distribution having exponent γ = 1.83).
View larger version:
- In this window
- In a new window
- Download as PowerPoint Slide
Fig. 3.
Comparison of PA and TPA graphs. Both graphs are grown to n = 1,000 nodes. The oldest N/4 nodes are colored blue, the next quarter green, then red, and finally orange. (A) PA graph. (B) TPA with A ₁ = 17, A ₂ = 10, thus γ = 1.83. Note the effects of aging in TPA; in contrast to PA, very few of the newest nodes attach to the root. Also, due to the minimization of hop-count, the diameter of the TPA graph is much smaller than that of the PA graph. By varying the choice of parameters A ₁ and A ₂, it is possible to achieve graphs of appearance intermediate between A and B, or even more extreme than B with respect to the diameter and the number of new nodes attaching to the root.