Network Topology Generators: Degree-Based vs. Structural

Following the long-held belief that the Internet is hierarchical, the network topology generators most widely used by the Internet re-search 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 distri-bution 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 im-portant 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 distribu-tion). 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 cap-ture the large-scale structure of measured topologies. We then seek an explanation for this result by examining the nature of hierarchy At USC-ISI, this work was supported in part by the Defense Ad-vanced Research Projects Agency under grant F30602-00-2-055. Any opinions, findings, and conclusions or recommendations ex-pressed in this material are those of the authors and do not neces-sarily reflect the views of the Defence Advanced Research Project