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 nor-malized 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 prop-erties 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 inter-pretations 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 have a profound impact on future protocol evaluation and design