Graph Annotations in Modeling Complex Network Topologies - Computer Science > Networking and Internet ArchitectureReport as inadecuate

Graph Annotations in Modeling Complex Network Topologies - Computer Science > Networking and Internet Architecture - Download this document for free, or read online. Document in PDF available to download.

Abstract: The coarsest approximation of the structure of a complex network, such as theInternet, is a simple undirected unweighted graph. This approximation, however,loses too much detail. In reality, objects represented by vertices and edges insuch a graph possess some non-trivial internal structure that varies across anddifferentiates among distinct types of links or nodes. In this work, weabstract such additional information as network annotations. We introduce anetwork topology modeling framework that treats annotations as an extendedcorrelation profile of a network. Assuming we have this profile measured for agiven network, we present an algorithm to rescale it in order to constructnetworks of varying size that still reproduce the original measured annotationprofile.Using this methodology, we accurately capture the network propertiesessential for realistic simulations of network applications and protocols, orany other simulations involving complex network topologies, including modelingand simulation of network evolution. We apply our approach to the AutonomousSystem AS topology of the Internet annotated with business relationshipsbetween ASs. This topology captures the large-scale structure of the Internet.In depth understanding of this structure and tools to model it are cornerstonesof research on future Internet architectures and designs. We find that ourtechniques are able to accurately capture the structure of annotationcorrelations within this topology, thus reproducing a number of its importantproperties in synthetically-generated random graphs.

Author: Xenofontas Dimitropoulos, Dmitri Krioukov, Amin Vahdat, George Riley


Related documents