A spectral analysis of the internet topology

Abstract

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 (nls) 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 nls is an excellent candidate as a concise fingerprint of Internet-like graphs. Further analysis into the theory of nls leads us to a new structural classification of AS graphs with plausible interpretations in networking terms. Extensive analysis by AS-level 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 power-law properties. We think that these new insights may hava a profound impact on future protocol evaluation and design.