A spectral analysis of the internet topology
Vukadinović, Danica, Huang, Polly, Erlebach, Thomas · Repository for Publications and Research Data (ETH Zurich) · 2001
In this paper we investigate properties of the Internet topology on the AS (autonomous system) level.Among techniques in spectral graph theory, we find the normalized Laplacian spectrum ( ) of AS graphs 1) unique in spite of the explosive growth of the Internet and 2) distinctive in setting AS graphs apart from synthetic ones.These properties suggest that is an excellent candidate as a concise fingerprint of Internet-like graphs.Further analysis into the theory of leads us to a new structural classification of AS graphs with plausible interpretations in networking terms.Extensive analysis by ASlevel data supports this claim.More importantly, along the way, new power-law relationships are unveiled, giving rise to a hybrid model encompassing both structural and powerlaw properties.We think that these new insights may have a profound impact on future protocol evaluation and design.