Emergence of tempered preferential attachment from optimization

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.

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.

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

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.