Radial structure of the Internet
Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesPublished 13 February 2007Open access
Petter Holme, Josh Karlin, Stephanie Forrest
Citations8
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A clear distinction between the highly connected core and a sparse periphery is found, and it is found that the periphery has a more complex structure than that predicted by degree distribution or the two generative models.
Abstract
The structure of the Internet at the autonomous system (AS) level has been studied by the physics, mathematics and computer science communities. We extend this work to include features of the core and the periphery, taking a radial perspective on AS network structure. New methods for plotting AS data are described, and they are used to analyse datasets that have been extended to contain edges missing from earlier collections. The average distance from one vertex to the rest of the network is used as the baseline metric for investigating radial structure. Common vertex-specific quantities are plotted against this metric to reveal distinctive characteristics of central and peripheral vertices. Two datasets are analysed using these measures as well as two common generative models (Barabási–Albert and Inet). We find a clear distinction between the highly connected core and a sparse periphery. We also find that the periphery has a more complex structure than that predicted by degree distribution or the two generative models.
Keywords
Computer SciencePhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
SIAM ReviewThe Structure and Function of Complex Networks
18,742 Citations2003Michael Newman
Developments in this field are reviewed, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
NatureError and attack tolerance of complex networks
7,218 Citations2000Réka Albert, Hawoong Jeong +1 more
It is found that scale-free networks, which include the World-Wide Web, the Internet, social networks and cells, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsScientific collaboration networks. II. Shortest paths, weighted networks, and centrality
2,612 Citations2001M. E. J. Newman
It is argued that simple networks such as these cannot capture variation in the strength of collaborative ties and proposed a measure of collaboration strength based on the number of papers coauthored by pairs of scientists, and thenumber of other scientists with whom they coauthored those papers.
ACM SIGCOMM Computer Communication ReviewOn power-law relationships of the Internet topology
2,599 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsAttack vulnerability of complex networks
1,835 Citations2002Petter Holme, Beom Jun Kim +2 more
It is found that the removals by the recalculated degrees and betweenness centralities are often more harmful than the attack strategies based on the initial network, suggesting that the network structure changes as important vertices or edges are removed.
Physical Review LettersDynamical and Correlation Properties of the Internet
1,452 Citations2001Romualdo Pastor‐Satorras, Alexei Vázquez +1 more
It is found that the Internet is characterized by non-trivial correlations among nodes and different dynamical regimes, and the importance of node hierarchy and aging in the Internet structure and growth is pointed out.
Cambridge University Press eBooksEvolution and Structure of the Internet
1,335 Citations2004Romualdo Pastor‐Satorras, Alessandro Vespignani
Viewed in this analysis from a statistical physics perspective, the Internet is perceived as a developing system that evolves through the addition and removal of nodes and links, allowing the authors to outline the dynamical theory that can appropriately describe the Internet's macroscopic evolution.
Characterizing the Internet hierarchy from multiple vantage points
565 Citations2003L. Subramanian, Sharad Agarwal +2 more
The topological structure of the Internet in terms of customer-provider and peer-peer relationships between autonomous systems, as manifested in BGP routing policies, is investigated and a five-level classification of AS is proposed.
Proceedings of the National Academy of SciencesThe “robust yet fragile” nature of the Internet
473 Citations2005John C. Doyle, David Alderson +6 more
This article aims to make recent results of this process accessible beyond Internet specialists to the broader scientific community and to clarify several sources of basic methodological differences that are relevant beyond either the Internet or the two specific approaches focused on here (i.e., scale-free networks and highly optimized tolerance networks).
ACM SIGCOMM Computer Communication ReviewOn the origin of power laws in Internet topologies
407 Citations2000Alberto Medina, Ibrahim Matta +1 more
Four factors in the formation of Internet topologies are examined and it is observed that some generated topologies may not obey power laws P1 and P2, and the value of α in P3 and P4 can be used as a litmus test for the representativeness of a generated topology.
Physica A Statistical Mechanics and its ApplicationsDetection of topological patterns in complex networks: correlation profile of the internet
359 Citations2003Sergei Maslov, Kim Sneppen +1 more
It is demonstrated that the clustering in a network is very sensitive to both the degree distribution and its correlation profile and compared to the appropriate null model.
ACM SIGCOMM Computer Communication ReviewThe internet AS-level topology
245 Citations2006Priya Mahadevan, Dmitri Krioukov +4 more
An extensive set of characteristics for Internet AS topologies extracted from the three data sources most frequently used by the research community: traceroutes, BGP, and WHOIS is calculated.
To Peer or Not to Peer: Modeling the Evolution of the Internet's AS-Level Topology
146 Citations2006Hyunseok Chang, Sugih Jamin +1 more
A new framework for modeling this evolutionary process of Internet connectivity at the AS level is presented by identifying a set of criteria that ASs consider either in establishing a new peering relationship or in reassessing an existing relationship.
Physical Review LettersHierarchy Measures in Complex Networks
138 Citations2004Ala Trusina, Sergei Maslov +2 more
This work proposes a simple dynamical process used to construct networks which are either maximally or minimally hierarchical, and shows the extent of topological hierarchy to smoothly decline with gamma, the exponent of a degree distribution.
Social NetworksSimple methods for simulating sociomatrices with given marginal totals
92 Citations2000John M. Roberts
This paper discusses an approach based on Markov chain Monte Carlo techniques, and shows how to apply it to distributions in which all sociomatrices with other given totals are equally likely.
Towards capturing representative AS-level Internet topologies
77 Citations2002Hyunseok Chang, Ramesh Govindan +3 more
The main objective in this paper is to quantify the completeness of Internet AS maps constructed from the Oregon route-views and to attempt to capture more representative AS-level Internet topology.
The European Physical Journal BAn internet graph model based on trade-off optimization
18 Citations2004J. Ignacio Alvarez-Hamelin, Nicolas Schabanel
A generalization of the heuristic trade-off optimization approach introduced by Fabrikant, Koutsoupias and Papadimitriou to generate a general graph, as a candidate for modeling the Internet, is proposed.
Internet MathematicsA Detailed Study of the Attachment Strategies of New Autonomous Systems in the AS Connectivity Graph
3 Citations2005Ingrid Daubechies, Konstantinos Drakakis +1 more
This paper uses real BGP data to study some properties of the AS connectivity graph and its evolution in time, and builds a simple model that is inspired by observations made in the first part, and discusses simulations of this model.