LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » الروابـط » مخـبرمـخـبر LIP6

RSS

A Basis for Systematic Analysis of Network Topologies


آخر أجل للاستلام 22/06/2006
22/06/2006
المتدخلون) المتدخل) : Dmitri Krioukov, Chercheur CAIDA (USA)
We present a new, systematic approach to analyzing network topologies. We first introduce a series of distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Using this series, we can quantitatively evaluate how close synthetic topologies are to G, construct graphs that accurately reproduce the values of commonly-used graph metrics of G, and provide a rigorous basis for capturing any future metrics that may be of interest. We show that the d=0 and d=1 cases reduce to the known classical (Erdos-Renyi) random graphs and random graphs with prescribed degree distributions respectively. We then construct random 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.
لمعلومات أكـثر أنقـر هنا
bamba.gueye (at) nulllip6.fr
 Mentions légales
| خـريـطـة المـوقـع