On the Origin of Power Laws in Internet Topologies

Medina, Alberto
Matta, Ibrahim
Byers, John

Abstract

Recent empirical studies [6] have shown that Internet topologies exhibit power laws of the form y = x for the following relationships: (P1) outdegree of node (domain or router) versus rank; (P2) number of nodes versus outdegree; (P3) number of node pairs within a neighborhood versus neighborhood size (in hops); and (P4) eigenvalues of the adjacency matrix versus rank. However, causes for the appearance of such power laws have not been convincingly given. In this paper, we examine four factors in the formation of Internet topologies. These factors are (F1) preferential connectivity of a new node to existing nodes; (F2) incremental growth of the network; (F3) distribution of nodes in space; and (F4) locality of edge connections. In synthetically generated network topologies, we study the relevance of each factor in causing the aforementioned power laws as well as other properties, namely diameter, average path length and clustering coefficient. Different kinds of network topologies a...

Keywords

power law
topology
topology generator
network generator

Notes

Compares some generators.

Related Papers

Bibtex

 @article{medina.matta.byers_origin00,
    author = "Alberto Medina and Ibrahim Matta and John Byers",
    title = "On the Origin of Power Laws in Internet Topologies",
    journal = "ACM Computer Communication Review",
    month = "Apr.",
    year = "2000"
}

Back to Intro By Author By Importance By Keyword By Title By Reference