6038581

Summary

de Montgolfier, F., Soto, M. and Viennot, L. (2011) Treewidth and Hyperbolicity of the Internet. In Network Computing and Applications (NCA), 2011 10th IEEE International Symposium on. aug., pages 25 -32. ((URL))

Abstract

We study the measurement of the Internet according to two graph parameters: tree width and hyper bolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocket fuel and Strasbourg University, at the AS or at the router level. On the one hand, the tree width of the Internet appears to be quite large and being far from a tree with that respect, reflecting some high degree of connectivity. This proves the existence of a well linked core in the Internet. On the other hand, the hyper bolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the tree width and hyper bolicity obtained for classical Internet models and compare with the snapshots. #6038581Bib

Bibtex entry

@INPROCEEDINGS { 6038581,
    AUTHOR = { de Montgolfier, F. and Soto, M. and Viennot, L. },
    BOOKTITLE = { Network Computing and Applications (NCA), 2011 10th IEEE International Symposium on },
    TITLE = { Treewidth and Hyperbolicity of the Internet },
    YEAR = { 2011 },
    MONTH = { aug. },
    VOLUME = { },
    NUMBER = { },
    PAGES = { 25 -32 },
    ABSTRACT = { We study the measurement of the Internet according to two graph parameters: tree width and hyper bolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocket fuel and Strasbourg University, at the AS or at the router level. On the one hand, the tree width of the Internet appears to be quite large and being far from a tree with that respect, reflecting some high degree of connectivity. This proves the existence of a well linked core in the Internet. On the other hand, the hyper bolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the tree width and hyper bolicity obtained for classical Internet models and compare with the snapshots. },
    KEYWORDS = { Internet models;graph parameters;hyperbolicity;tree-like structure;treewidth;Internet;trees (mathematics); },
    URL = { http://dx.doi.org/10.1109/NCA.2011.11 },
    ISSN = { },
}