Systematic Topology Analysis and Generation Using Degree Correlations

Abstract

We present a new, systematic approach for analyzing network topologies. We first introduce the dK-series of probability distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Increasing values of d capture progressively more properties of G at the cost of more complex representation of the probability distribution. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the dK-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for d=0,1,2,3 and demonstrate that these graphs reproduce, with increasing accuracy, important properties of measured and modeled Internet topologies. We find that the d=2 case is sufficient for most practical purposes, while d=3 essentially reconstructs the Internet AS- and router-level topologies exactly. We hope that a systematic method to analyze and synthesize topologies offers a significant improvement to the set of tools available to network topology and protocol researchers.

Final version

References in corpus (9)

• Assortative mixing in networks
• Large-scale topological and dynamical properties of Internet
• Class of correlated random networks with hidden variables
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Cut-offs and finite size effects in scale-free networks
• The Internet AS-Level Topology: Three Data Sources and One Definitive Metric
• Tuning clustering in random networks with arbitrary degree distributions
• Compact Routing on Internet-Like Graphs
• Clustering of correlated networks

Cited by in corpus (26)

• Hyperbolic Geometry of Complex Networks
• The Statistical Physics of Real-World Networks
• Topological strata of weighted complex networks
• Quantifying randomness in real networks
• Collective dynamics of social annotation
• Evolution of a large online social network
• Uncovering disassortativity in large scale-free networks
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Multifractal Network Generator
• A critical look at power law modelling of the Internet
• Evolution of the Internet k-dense structure
• Scale-free networks as preasymptotic regimes of superlinear preferential attachment
• Randomizing hypergraphs preserving degree correlation and local clustering
• Degree Correlations Amplify the Growth of Cascades in Networks
• Separating Polarization from Noise: Comparison and Normalization of Structural Polarization Measures
• Second-Order Assortative Mixing in Social Networks
• Testing biological network motif significance with exponential random graph models
• The Network Impact of Hijacking a Quantum Repeater
• Evolution of the Internet AS-Level Ecosystem
• Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
• Rotated multifractal network generator
• Higher-order distributions and nongrowing complex networks without multiple connections
• Learning the mechanisms of network growth
• Fingerprint for Network Topologies
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Network Sparsification via Degree- and Subgraph-based Edge Sampling