Modeling the Internet's large-scale topology

By Soon-Hyung Yook, Hawoong Jeong, Albert-László Barabási. Proceedings of the National Academy of Sciences of the United States of America, 2001

698 citations recorded by the source corpus.

Network generators that capture the Internet's large-scale topology are crucial for the development of efficient routing protocols and modeling Internet traffic. Our ability to design realistic generators is limited by the incomplete understanding of the fundamental driving forces that affect the Internet's evolution. By combining several independent databases capturing the time evolution, topology, and physical layout of the Internet, we identify the universal mechanisms that shape the Internet's router and autonomous system level topology. We find that the physical layout of nodes form a fractal set, determined by population density patterns around the globe. The placement of links is driven by competition between preferential attachment and linear distance dependence, a marked departure from the currently used exponential laws. The universal parameters that we extract significantly restrict the class of potentially correct Internet models and indicate that the networks created by all available topology generators are fundamentally different from the current Internet.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/31ab07c00e979e6c38a5faf5ca29c3399ead9613

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

The “New” Science of Networks (2004, neutral): “Faloutsos et al. (1999) claim that both networks (Yook et al. 2002).”
Evolution and Structure of the Internet: Index (2004, background): “Further empirical evidence for the heavy-tailed behavior of the degree distribution has since been collected both at the IR and AS level in several studies (Govindan and Tangmunarunkit, 2000; Tangmunarunkit, Doyle, Govindan, Jamin, Shenker and Willinger, 2001; Broido and Claffy, 2001; Pastor-Satorra”
Geographic routing in social networks (2005, background): “(The proportion of links in a network that are between two entities separated by a particular geographic distance has been studied in a number of different contexts: the infrastructure of the Internet [14, 15, 37], small-scale email networks within a company [3, 4], transportation networks [14], and”
The spatial structure of networks (2004, background): “Empirical studies of networks, even networks in which geography plays a pivotal role, have, with some exceptions [6, 18, 19, 20], similarly focused almost exclusively on topology [4, 21, 22].”
Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (2005, background): “In the context of the Internet, where SF graphs have been proposed as models of the routerlevel Internet [106], this has been touted “the Achilles’ heel of the Internet” [6], a vulnerability that has presumably been overlooked by networking engineers.”
Popularity versus similarity in growing networks (2011, background): “A wider class of models augment PA not with similarity information per se , but with some spatial information [62– 64], see also Section 4.4 in [65].”
The Internet Topology Zoo (2011, methodology): “On the one hand lie the random graph models (starting with Erdos-Renyi and Gilbert [14] and going forward through Waxman [15], and more recently power-law graphs [16], [17], [18], [19]).”
Effect of sampling on topology predictions of protein-protein interaction networks (2005, methodology): “These partial networks are then used to infer the topology of the whole networ”