Papers /

D Souza-PNAS 2007

Reading

Outdoors

Games

Hobbies

LEGO

Food

Code

Events

Nook

sidebar

D Souza-PNAS 2007

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:

Recent Changes (All) | Edit SideBar Page last modified on December 13, 2008, at 08:50 AM Edit Page | Page History