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. © 2011 IEEE.

De Montgolfier, F., Soto, M., Viennot, L. (2011). Treewidth and hyperbolicity of the internet. In 2011 IEEE 10th International Symposium on Network Computing and Applications (pp. 25-32). IEEE Computer Soc [10.1109/NCA.2011.11].

Treewidth and hyperbolicity of the internet

Soto, M
;
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. © 2011 IEEE.
Capitolo o saggio
Computer Networks and Communications; Computer Science Applications1707, Computer Vision and Pattern Recognition
English
2011 IEEE 10th International Symposium on Network Computing and Applications
2011
978-0-7695-4489-2
IEEE Computer Soc
25
32
6038581
De Montgolfier, F., Soto, M., Viennot, L. (2011). Treewidth and hyperbolicity of the internet. In 2011 IEEE 10th International Symposium on Network Computing and Applications (pp. 25-32). IEEE Computer Soc [10.1109/NCA.2011.11].
none
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/220905
Citazioni
  • Scopus 44
  • ???jsp.display-item.citation.isi??? 24
Social impact