 |
|
|||
| Authors: | Danica Vukadinovic-Greetham, Polly Huang, Thomas Erlebach |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | On the Spectrum and Structure of Internet Topology Graphs |
| Year: | 2002 |
| Month: | June |
| Pub-Key: | VHE02 |
| Book Titel: | Lecture Notes in Computer Science. Innovative Internet Computing Systems (I2CS 2002) |
| Volume: | 2346 |
| Pages: | 83-95 |
| Publisher: | Springer-Verlag |
| Abstract: | In this paper we study properties of the Internet topology on the autonomous system (AS) level. We find that the normalized Laplacian spectrum (nls) of a graph provides a concise fingerprint of the corresponding network topology. The nls of AS graphs remains stable over time in spite of the explosive growth of the Internet, but the nls of synthetic graphs obtained using the state-of-the-art topology generator Inet-2.1 is significantly different, in particular concerning the multiplicity of eigenvalue 1. We relate this multiplicity to the sizes of certain subgraphs and thus obtain a new structural classification of the nodes in the AS graphs, which is also plausible in networking terms. These findings as well as new power-law relationships discovered in the interconnection structure of the subgraphs may lead to a new generator that creates more realistic topologies by combining structural and power-law properties. |
| Location: | Kühlungsborn, Germany |
| Resources: | [BibTeX] |
