It has long been thought that the Internet, and its constituent
networks, are hierarchical in nature. Consequently, the network
topology generators most widely used by the Internet research
community, GT-ITM and Tiers, create networks with a deliberately
hierarchical structure. However, recent work by Faloutsos et
al. revealed that the Internet's degree distribution --- the
distribution of the number of connections routers or Autonomous
Systems (ASs) have --- is a power-law. The degree distributions
produced by the GT-ITM and Tiers generators are not power-laws.
To rectify this problem, several new network generators have recently
been proposed that produce more realistic degree distributions; these
new generators do not attempt to create a hierarchical structure but
instead focus solely on the degree distribution. There are thus two
families of network generators, structural generators that treat
hierarchy as fundamental and degree-based generators that treat
the degree distribution as fundamental.
In this paper we use several topology metrics to compare the networks
produced by these two families of generators to current measurements
of the Internet graph. We find that the degree-based generators
produce better models, at least according to our topology metrics, of
both the AS-level and router-level Internet graphs. We then seek to
resolve the seeming paradox that while the Internet certainly has
hierarchy, it appears that the Internet graphs are better modeled by
generators that do not explicitly construct hierarchies. We conclude
our paper with a brief study of other network structures, such as the
pointer structure in the web and the set of airline routes, some of
which turn out to have metric properties similar to that of the
Internet.
Copyright. All Rights Reserved.