Graph Annotations in Modeling Complex Network Topologies

Abstract

The coarsest approximation of the structure of a complex network, such as the Internet, is a simple undirected unweighted graph. This approximation, however, loses too much detail. In reality, objects represented by vertices and edges in such a graph possess some non-trivial internal structure that varies across and differentiates among distinct types of links or nodes. In this work, we abstract such additional information as network annotations. We introduce a network topology modeling framework that treats annotations as an extended correlation profile of a network. Assuming we have this profile measured for a given network, we present an algorithm to rescale it in order to construct networks of varying size that still reproduce the original measured annotation profile. Using this methodology, we accurately capture the network properties essential for realistic simulations of network applications and protocols, or any other simulations involving complex network topologies, including modeling and simulation of network evolution. We apply our approach to the Autonomous System (AS) topology of the Internet annotated with business relationships between ASs. This topology captures the large-scale structure of the Internet. In depth understanding of this structure and tools to model it are cornerstones of research on future Internet architectures and designs. We find that our techniques are able to accurately capture the structure of annotation correlations within this topology, thus reproducing a number of its important properties in synthetically-generated random graphs.

References in corpus (18)

• Topology of evolving networks: local events and universality
• Highly Optimized Tolerance: Robustness and Power Laws in Complex Systems
• 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
• A General Formalism for Inhomogeneous Random Graphs
• The Internet AS-Level Topology: Three Data Sources and One Definitive Metric
• AS Relationships: Inference and Validation
• Accuracy and Scaling Phenomena in Internet Mapping
• Traceroute sampling makes random graphs appear to have power law degree distributions
• Generalized percolation in random directed networks
• On Compact Routing for the Internet
• Exploring networks with traceroute-like probes: theory and simulations
• Random Graphs with Hidden Color
• Revealing the Autonomous System Taxonomy: The Machine Learning Approach
• Properties of Random Graphs with Hidden Color
• Inferring AS Relationships: Dead End or Lively Beginning?
• Random Feynman Graphs

Cited by in corpus (9)

• Quantifying randomness in real networks
• Privacy in Social Media: Identification, Mitigation and Applications
• Evolution of the Internet AS-Level Ecosystem
• Statistical Models for Degree Distributions of Networks
• On the Privacy of dK-Random Graphs
• Game Theoretic Iterative Partitioning for Dynamic Load Balancing in Distributed Network Simulation
• Performance Rescaling of Complex Networks
• Construction of Directed 2K Graphs
• Time series of Internet AS-level topology graphs: four patterns and one model