Emergence of Tempered Preferential Attachment from Optimization
D'Souza, Borgs, Chayes, Berger, and Kleiberg
networks scaling scale-free small-world graph theory structure
@article{dsouza:pnas-2007,
title={Emergence of Tempered Preferential Attachment from Optimization},
author={R.M. D'Souza and C. Borgs and J.T. Chayes and N. Berger and R.D. Kleinberg},
journal={Proceedings of the National Academy of Sciences},
pages={6112--6117},
year={2007},
volume={104},
number={15},
publisher={National Academy of Sciences}
}
Debate over whether or not preferential attachment and basic variants are fundamental, or are by-products of an optimization process
Presents an example of a simple optimization model that results in a realistic form of preferential attachment
- Incorporates viability, which seems very similar to aging in Amaral 2000, though with a slightly different world interpretation
- E.g., Fertility or productivity rather than aging
- Incorporates saturation, which seems very similar to cost/capacity constraints in Amaral 2000
- Saturation produces an exponential dropoff in connectivity distribution
Simple optimization model based on Autonomous System peering on Internet
- Each new node t, randomly placed on a line, chooses to peer with another node j based on distance between them, distance of peer to core
- Results in: $c_t = min_j[\alpha n_{tj} | h_j]$
- $n_{ij}$ is hops (fiber transits) between new node t and j
- $h_j$ is hops from j to core (start of one-dimensional network)
- $\alpha$ is a weighting between the two, capturing the tradeoff preference between cost and performance
- Model can be easily applied to other systems with two opposing metrics
Optimization process produces a tree
- Each node connects either to node on left, or its parent depending on whether or not $n_{tp} < 1/\alpha$
- In other terms, a node's attractiveness is proportional to its degree
- Nodes will prefer to connect to a parent up to $ceil(1/\alpha)$ children away, marking the saturation point
Degree distribution is scale-free within a region, then drops off
- Has exponent has exponent 2 (rather than 3) up to saturation point
- Decays exponentially afterward
Although this model has one parameter, can be generalized to include independent viability and saturation thresholds
- Choices these interpolates between standard preferential attachment, preferential attachment with cutoff, and uniform attachment
This model fits a wide variety of data better than standard preferential attachment
Can make models even more realistic by making thresholds a random variable rather than fixed constants
Of note: