New Model of Internet Topology Using k-shell Decomposition

Abstract

We introduce and use k-shell decomposition to investigate the topology of the Internet at the AS level. Our analysis separates the Internet into three sub-components: (a) a nucleus which is a small (~100 nodes) very well connected globally distributed subgraph; (b) a fractal sub-component that is able to connect the bulk of the Internet without congesting the nucleus, with self similar properties and critical exponents; and (c) dendrite-like structures, usually isolated nodes that are connected to the rest of the network through the nucleus only. This unique decomposition is robust, and provides insight into the underlying structure of the Internet and its functional consequences. Our approach is general and useful also when studying other complex networks.

4 pages, 4 figures

References in corpus (12)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Resilience of the Internet to random breakdowns
• Self-similarity of complex networks
• Breakdown of the Internet under intentional attack
• k-core organization of complex networks
• Problems with Fitting to the Power-Law Distribution
• Modularity and Extreme Edges of the Internet
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Accuracy and Scaling Phenomena in Internet Mapping
• Traceroute sampling makes random graphs appear to have power law degree distributions
• Competition and adaptation in an Internet evolution model

Cited by in corpus (129)

• Identification of influential spreaders in complex networks
• Link Prediction in Complex Networks: A Survey
• Critical phenomena in complex networks
• Vital nodes identification in complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• k-core organization of complex networks
• The Dynamics of Protest Recruitment through an Online Network
• Ranking spreaders by decomposing complex networks
• Percolation on complex networks: Theory and application
• Searching for superspreaders of information in real-world social media
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A k-shell decomposition method for weighted networks
• The entropy of network ensembles
• Ranking the spreading influence in complex networks
• Spreading dynamics in complex networks
• Absence of influential spreaders in rumor dynamics
• The entropy of randomized network ensembles
• Ranking in evolving complex networks
• Towards designing robust coupled networks
• Combining complex networks and data mining: why and how
• The k-core as a predictor of structural collapse in mutualistic ecosystems
• Worldwide spreading of economic crisis
• Resilience and rewiring of the passenger airline networks in the United States
• Cascading Failures in Complex Networks
• k-Core percolation on multiplex networks
• Locating privileged spreaders on an Online Social Network
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• WiFi Epidemiology: Can Your Neighbors' Router Make Yours Sick?
• Path diversity improves the identification of influential spreaders
• A Clarified Typology of Core-Periphery Structure in Networks
• Rich-cores in networks
• The structural role of weak and strong links in a financial market network
• The Impact of Heterogeneous Thresholds on Social Contagion with Multiple Initiators
• Organization of modular networks
• An In-Depth Analysis of Stochastic Kronecker Graphs
• The evolution of interdisciplinarity in physics research
• Network Sampling: From Static to Streaming Graphs
• Fractal Boundaries of Complex Networks
• Networking - A Statistical Physics Perspective
• Generalization of core percolation on complex networks
• A critical look at power law modelling of the Internet
• Spatial super-spreaders and super-susceptibles in human movement networks
• Identifying Geographic Clusters: A Network Analytic Approach
• K-shell decomposition reveals hierarchical cortical organization of the human brain
• Predicting epidemic outbreak from individual features of the spreaders
• Transport in networks with multiple sources and sinks
• Superspreading k-cores at the center of COVID-19 pandemic persistence
• Analytical results for bond percolation and k-core sizes on clustered networks
• The jamming transition is a k-core percolation transition
• The nature of hypergraph $k$-core percolation problems
• Density-friendly Graph Decomposition
• Spontaneous Self-Assembly of Transcription Factor Based Gene Regulation Networks
• Interconnections between networks act like an external field in first-order percolation transitions
• Energy-landscape network approach to the glass transition
• A network approach for the scientific collaboration in the European Framework Programs
• A complex network description of thermal quantum states in the Ising spin chain
• A Network Science perspective of Graph Convolutional Networks: A survey
• Bootstrap percolation on geometric inhomogeneous random graphs
• Generalized model for $k$-core percolation and interdependent networks
• Transport of multiple users in complex networks
• Incremental Graph Computation: Anchored Vertex Tracking in Dynamic Social Networks
• Axiomatic Ranking of Network Role Similarity
• Finding influential spreaders from human activity beyond network location
• Impact of natural disasters on consumer behavior: case of the 2017 El Nino phenomenon in Peru
• Color-avoiding percolation
• Optimal redundancy against disjoint vulnerabilities in networks
• K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
• Hierarchical core-periphery structure in networks
• Border trees of complex networks
• Impact of edge-removal on the centrality betweenness of the best spreaders
• Automatic Network Fingerprinting through Single-Node Motifs
• Spreaders in the Network SIR Model: An Empirical Study
• Literature Survey on Interplay of Topics, Information Diffusion and Connections on Social Networks
• Centrality Measures in Complex Networks: A Survey
• Partition of Networks into Basins of Attraction
• Stratification in the Preferential Attachment Network
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• Switchover phenomenon induced by epidemic seeding on geometric networks
• Percolation on spatial anisotropic networks
• Exotic phase transitions of k-cores in clustered networks
• Anomalous electrical and frictionless flow conductance in complex networks
• A computationally-efficient sandbox algorithm for multifractal analysis of large-scale complex networks with tens of millions of nodes
• Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
• Fast asynchronous updating algorithms for k-shell indices
• Randomly Evolving Idiotypic Networks: Structural Properties and Architecture
• Truss Decomposition in Massive Networks
• Identification of highly susceptible individuals in complex networks
• Network science Ising states of matter
• The Strength of Structural Diversity in Online Social Networks
• K-Core Minimization: A Game Theoretic Approach
• Efficient Core Maintenance in Large Dynamic Graphs
• The Graph Structure of the Internet at the Autonomous Systems Level during Ten Years
• Random node reinforcement and $K$-core structure of complex networks
• Generalized $k$-core pruning process on directed networks
• Rank-Refining Seed Selection Methods for Budget Constrained Influence Maximisation in Multilayer Networks under Linear Threshold Model
• Filtering of complex systems using overlapping tree networks
• Priority diffusion model in lattices and complex networks
• Probing models of information spreading in social networks
• Understanding edge-connectivity in the Internet through core-decomposition
• The Atlas for the Aspiring Network Scientist
• Quantifying Policy Responses to a Global Emergency: Insights from the COVID-19 Pandemic
• Inferring Multiple Relationships between ASes using Graph Convolutional Network
• Fast Hierarchy Construction for Dense Subgraphs
• A Self-Learning Information Diffusion Model for Smart Social Networks
• Content-Based Features to Rank Influential Hidden Services of the Tor Darknet
• On the Geometry and Extremal Properties of the Edge-Degeneracy Model
• D-chain tomography of networks: a new structure spectrum and an application to the SIR process
• Core-Periphery Segregation in Evolving Prisoner's Dilemma Networks
• A combined network and machine learning approaches for product market forecasting
• Topological Trends of Internet Content Providers
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Parallel Algorithms for Core Maintenance in Dynamic Graphs
• Random walk with priorities in communication-like networks
• Large Social Networks can be Targeted for Viral Marketing with Small Seed Sets
• On the categorization of scientific citation profiles in computer sciences
• Collective Influence of Multiple Spreaders Evaluated by Tracing Real Information Flow in Large-Scale Social Networks
• Estimating Shell-Index in a Graph with Local Information
• K-core in percolated dense graph sequences
• Fast computation of distance-generalized cores using sampling
• Quantifying Women's Marginalisation in Ibero-American Film Culture During the First Half of the Twentieth Century: A Network-Science Proposal
• Network structure and disease risk for an endemic infectious disease
• Calibratable Hetero-NodeRank for measuring node influence
• Improving the accuracy of the k-shell method by removing redundant links-from a perspective of spreading dynamics
• Core Maintenance in Dynamic Graphs: A Parallel Approach based on Matching
• Measuring multiple evolution mechanisms of complex networks
• Target Privacy Preserving for Social Networks
• Asymptotic Traffic Flow in a Hyperbolic Network: Non-uniform Traffic
• Discovering Key Nodes in a Temporal Social Network
• Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm