Skip to Content
[CAIDA - Center for Applied Internet Data Analysis logo]
Center for Applied Internet Data Analysis
www.caida.org > research : topology : evolutionmodels
Internet Evolution Models
To increase our fundamental understanding of the laws of evolution of large scale networks, we build and analyze models for Internet topology evolution. We attempt to not only faithfully reproduce observed data, but also to develop sound methodologies for evaluating and validating various classes of formal network growth models.

Models of complex networks can be roughly split into two classes: static and growth models. Static models, such as classical random graphs and their generalizations, generate a whole network at once, trying to directly reproduce some properties observed in real network snapshots. Growth models construct networks by adding a node at a time, attempting to provide some insight into the laws governing network evolution. These models usually use some version of a so called 'preferential attachment' process to simulate probabilities of a link between a new node and nodes in the existing network. Compared to static models, it is generally more difficult to closely match observed network properties with growth models, because in this case one usually has less direct control over the properties of modeled networks.

In our recent work, we focused on the following network growth models.

Multiclass Attraction Model

We developed an analytically tractable model of Internet evolution at the level of Autonomous Systems (ASes). Our Multiclass Attraction (MA) model describes the evolution of AS graphs over time, including the emergence of new ASes, peering links formation, bankruptcies, multihoming, and consolidation of providers under certain circumstances.

Most notably, all parameters used by the MA model are derived from actual measurements of the Internet topology. Given the best estimates of these parameters, our analytic results accurately predict a definitive set of statistics characterizing the observed AS topology structure. Since these statistics are not parts of model formulation, the MA model closes the measure-model-validate-predict loop. To validate our model, we compare measured and simulated AS topologies using the dK-series formalism.

The MA model can form a basis for a topology generator, as well create a simulation environment for testing various realistic "what-if" scenarios. Possible simulations may target specific questions such as:

  • How will Internet topology look if ISP business realities change in a certain way?
  • Can we influence the Internet economy so that it would result in a more desirable Internet topology?

Preasymptotic Regimes of Superlinear Preferential Attachment

We demonstrate that scale-free networks, including the Internet, may exist in pre-asymptotic regimes of network evolution processes that do not produce scale-free, self-similar structures as their asymptotes.

Specifically, we study the positive-feedback preference (PFP) model by Zhou and Mondragon that is the first growth model matching the observed Internet topology surprisingly well. In this model, at each time step, one node is added to the network, and connected to the existing nodes by two or three links, choosing different link placement options with different probabilities. The most important property of the model is that the probability to connect a new node to the existing nodes of degree k is a superlinear function of k.

The PFP model gives rise to the following paradox. On one hand, the model matches perfectly the observed Internet, as it reproduces almost exactly not only the observed power-law degree distribution, but also a long list of other important network properties. On the other hand, being explicitly based on preferential attachment with a superlinear preference kernel, this model cannot produce, in the thermodynamic limit, any scale-free networks, including the Internet. Instead, in the limit of large sizes, the networks are indeed degenerate, i.e., graphs become star-like with almost all nodes having low degrees.

We resolve this paradox by showing that the PFP model has a vast pre-asymptotic regime, where, according to our analysis confirmed by extensive simulations, it does produce scale-free networks with power-law node degree distribution. The asymptotic, star-like graph regime starts, given the specific set of model parameters (close to those of the real Internet), only at network sizes of the order of 10^17.

These findings have potential to impact both practice and theory of network science. In practice, if we want to construct topology generators of growing Internet-like networks, we no longer have to limit ourselves to mechanisms, such as preferential attachment, that quickly, for small network sizes, achieve power laws as their asymptotes. In theory, our proven result that certain growth mechanisms produce scale-free networks not in their asymptotic but in the pre-asymptotic regimes opens up an entirely new area of research.

An interesting open question is whether the dynamics of the world economy supports our findings. Specifically, will the ongoing process of consolidation among ISPs result in a very small number of giant super-providers while wiping out providers of medium sizes? More generally, does the superlinear growth of wealth contribute to such effects as the "shrinking middle class" and growing wealth inequality? In mathematical terms, is the Pareto distribution preasymptotic?

  Last Modified: Wed Mar-18-2009 13:41:15 PDT
  Page URL: http://www.caida.org/research/topology/evolutionmodels/index.xml