SI767 Paper Presentation

Heuristically Optimized Trade-offs:

A New Paradigm for Power Laws in the Internet

• Authors:
• Alex Fabrikant (Berkeley)
• Elias Koutsoupias (U. Athens/UCLA)
• Christor H. Papadimitriou (Berkeley)

Topic: Power Laws

• What are they?
• Where do they come from?
• Why do we care?
• What was the paper about again?

A quick look at distributions

• Distribution: Standard (Gaussian)
• Tells us that observations cluster around some central point.
• Mathematical Result: Central Limit Theorem (Sum of lots of IID's is normal.)
• Real-World Interpretation: Characterizes things in the world that do not tend to deviate heaviliy from some expected value.
• We see this in nature in:
  • Physiology/Bio: Logs of heights/weights of living things (per category)
  • Finance: Logs of Interest Rates, Exchange Rates, Inflation, etc (Returns on equities?)
  • Physics: Intensity of Laser Light

A quick look at distributions

• Distribution: Poisson
• Similar to Normal, but discrete and characterized by processes over time
• Computes probability of occurrences
• Mathematical Underpinnings: Law of rare events (result of Binomial model)
• Helps us estimate unlikely things
• E.g., Given that 1/500 (on aggregate) insurance policy holders die in a car accident per year...
• What is the prob that there will be no fatal accidents (out of 500 policies) in any year?
• P(X=0) ~ e^-1 / 0!

A quick look at distributions

• Distribution: Power Law
• "Signature of human activity": Rare in nature
• Shows up in:
  • Wealth/Income Distributions
  • City Populations
  • Term Frequencies (Zipf!)
  • Web Graph
  • Internet Graph

Generative Power-Law Models

Two Major Classes of Models

• Scale-Free Growth/Preferential Attachment/Rich-Get-Richer
  • New members attach to most central members
  • Stochastic process where growth is independent of population size
• HOT: Highly Optimized Tolerance
  • Power Law is the result of an optimal/reliable design in the presence of a hazard.
  • Can model by optimizing an objective function
• HOT is the class of model in this paper.

Internet Growth Model as Optimization

The Model: Motivating Observations

• When we add a new router/node is added, we want to optimize over two constriants:
  1. Minimize the geodesics to other nodes (connect to central nodes) in the interest of communications costs
  2. Minimize the last-mile costs: connect to those geographically closest to you (local hubs/providers)
• Thus, we want to minimize the weight of two objectives:

Internet Growth Model as Optimization

The Model: Mathematical Formulation

• Nodes in our tree have a euclidean value in a unit polygon
• Thus, we can compute distances
• Nodes also know the centrality of other nodes ("global information")
• At each iteration, we add node i, looking for the best j to connect to
• i's position is uniformly distributed over the polygon
• In our objective function:
• d_ij is the euclidean distance between i and j
• h_j is a centrality measure of j
• alpha chooses a relative weighting of the parameters
• Also cast as a "file-creation" model: "centrality" is the popularity of a data item, "distance" is the overhead of creating the file.

Internet Growth Model as Optimization

The Model: Results and Prooven Concepts

• Alpha:
  • if alpha is l.t. 1/sqrt(2), graph is a star
  • if alpha is omega(sqrt(2)), degree dist is exponential
  • if alpha g.e. 4 and o(sqrt(n)), degree dist is power law
• Every point after point i w/in radius r(i)/4 will connect to i
• Bottom-Line: Trade-offs (constrained optimization) between multiple fitness measures can result in power-law behavior

My Personal Critiques

• Basically, a pref attach model cast as function optimization
• alpha is a hack - depends on the shape of the region
• requires global knowledge (centrality measures)