Following the long-held belief that the Internet is hierarchical, the
network topology generators most widely used by the Internet research
community, Transit-Stub and Tiers, create networks with
a deliberately hierarchical structure. However, in 1999 a seminal
paper by Faloutsos et al. revealed that the Internet's degree distribution
is a power-law. Because the degree distributions produced
by the Transit-Stub and Tiers generators are not power-laws, the
research community has largely dismissed them as inadequate and
proposed new network generators that attempt to generate graphs
with power-law degree distributions.
Contrary to much of the current literature on network topology
generators, this paper starts with the assumption that it is more important
for network generators to accurately model the large-scale
structure of the Internet (such as its hierarchical structure) than to
faithfully imitate its local properties (such as the degree distribution).
The purpose of this paper is to determine, using various
topology metrics, which network generators better represent this
large-scale structure. We find, much to our surprise, that network
generators based on the degree distribution more accurately capture
the large-scale structure of measured topologies. We then seek
an explanation for this result by examining the nature of hierarchy
in the Internet more closely; we find that degree-based generators
produce a form of hierarchy that closely resembles the loosely hierarchical
nature of the Internet.
|