We study the measurement of the Internet according to two graph parameters: treewidth and hyperbolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocketfuel and Strasbourg University, at the AS or at the router level. On the one hand, the treewidth 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 hyperbolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the treewidth and hyperbolicity obtained for classical Internet models and compare with the snapshots.
Treewidth and hyperbolicity of the internet / F. De Montgolfier, M. Soto Gomez, L. Viennot - In: 2011 IEEE 10th International Symposium on Network Computing and Applications[s.l] : IEEE, 2011. - ISBN 978-1-4577-1052-0. - pp. 25-32 (( Intervento presentato al 10. convegno International Symposium on Network Computing and Applications tenutosi a Cambridge nel 2011 [10.1109/NCA.2011.11].
Treewidth and hyperbolicity of the internet
M. Soto GomezSecondo
;
2011
Abstract
We study the measurement of the Internet according to two graph parameters: treewidth and hyperbolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocketfuel and Strasbourg University, at the AS or at the router level. On the one hand, the treewidth 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 hyperbolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the treewidth and hyperbolicity obtained for classical Internet models and compare with the snapshots.File | Dimensione | Formato | |
---|---|---|---|
14_2011_Treewidth and Hyperbolicity of the Internet.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
138.85 kB
Formato
Adobe PDF
|
138.85 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Treewidth_and_Hyperbolicity_of_the_Internet.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
324.77 kB
Formato
Adobe PDF
|
324.77 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.