Graph annotations in modeling complex network topologies

DOI10.1145/1596519.1596522zbMATH Open1390.90134arXiv0708.3879OpenAlexW2145102203WikidataQ59939638 ScholiaQ59939638MaRDI QIDQ4565415FDOQ4565415

Authors: Xenofontas Dimitropoulos, Dmitri Krioukov, Amin Vahdat, George F. Riley 

Publication date: 12 June 2018

Published in: ACM Transactions on Modeling and Computer Simulation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0708.3879

Recommendations

• Hypergraph modeling and visualisation of complex co-occurence networks
• Topological modelling of large networks
• An algorithmic framework for labeling network maps
• An algorithmic framework for labeling network maps
• Graph embedding and interconnection networks
• Complex graphs and networks
• Graph theory for complex networks. I
• Exploring complex networks with Graph Investigator research application

zbMATH Keywords

complex networksnetwork topologyannotationsAS relationships

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15)

Cited In (5)

• Topological modelling of large networks
• Policy relationship annotations of predefined AS-level topologies
• Graphical models for complex networks: an application to Italian museums
• On the number of non-zero elements of joint degree vectors
• Catastrophic event phenomena in communication networks: a survey

This page was built for publication: Graph annotations in modeling complex network topologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4565415)