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.
%0 Generic
%1 Dimitropoulos2007Graph
%A Dimitropoulos, Xenofontas
%A Krioukov, Dmitri
%A Vahdat, Amin
%A Riley, George
%D 2007
%K internet, networks
%T Graph Annotations in Modeling Complex Network Topologies
%U http://arxiv.org/abs/0708.3879
%X 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.
@misc{Dimitropoulos2007Graph,
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.},
added-at = {2009-09-24T14:55:30.000+0200},
archiveprefix = {arXiv},
author = {Dimitropoulos, Xenofontas and Krioukov, Dmitri and Vahdat, Amin and Riley, George},
biburl = {https://www.bibsonomy.org/bibtex/275c2be8276ad0cc7327bdcda1e675221/andreacapocci},
citeulike-article-id = {1607130},
citeulike-linkout-0 = {http://arxiv.org/abs/0708.3879},
citeulike-linkout-1 = {http://arxiv.org/pdf/0708.3879},
eprint = {0708.3879},
interhash = {3a68ee24d5cabfc0b8c6c59238bb5d64},
intrahash = {75c2be8276ad0cc7327bdcda1e675221},
keywords = {internet, networks},
month = Aug,
posted-at = {2007-08-30 12:26:25},
priority = {5},
timestamp = {2009-09-24T14:55:36.000+0200},
title = {Graph Annotations in Modeling Complex Network Topologies},
url = {http://arxiv.org/abs/0708.3879},
year = 2007
}