Title: On the Emergence of Highly Variable Distributions in the Autonomous System Topology

Author: Fayed, Marwan; Krapivsky, Paul; Byers, John; Crovella, Mark; Finkel, David; Redner, Sid

Date: March 1, 2003

Abstract: 

Recent studies have noted that vertex degree in the autonomous system
(AS) graph exhibits a highly variable distribution \cite{fff,MP01}.
The most prominent explanatory model for this phenomenon is the
Barabasi-Albert (B-A) model [BA99,AB00]. A central feature of
the B-A model is preferential connectivity --- meaning that the
likelihood a new node in a growing graph will connect to an existing
node is proportional to the existing node's degree.  In this paper we
ask whether a more general explanation than the B-A model, and absent
the assumption of preferential connectivity, is consistent with
empirical data.  We are motivated by two observations: first, AS
degree and AS size are highly correlated [CHEN02]; and second,
highly variable AS size can arise simply through exponential growth.
We construct a model incorporating exponential growth in the size of
the Internet, and in the number of ASes.  We then show via analysis
that such a model yields a size distribution exhibiting a power-law
tail.  In such a model, if an AS's link formation is roughly
proportional to its size, then AS degree will also show high
variability.  We instantiate such a model with empirically derived
estimates of growth rates and show that the resulting degree
distribution is in good agreement with that of real AS graphs.