The laplacian spectrum of complex networks

Conference paper (2006)

Authors

A Jamakovic International Research Centre for Telecommunication and Radar
P.F.A. Van Mieghem Network Architectures and Services - EEMCS
Research Group
International Research Centre for Telecommunication and Radar
More Info
expand_more

Published Date

2006

Language

Undefined/Unknown

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Research Group

International Research Centre for Telecommunication and Radar

Abstract

The set of all eigenvalues of a characteristic matrix of a graph, also referred to as the spectrum, is a well-known topology retrieval method. In this paper, we study the spectrum of the Laplacian matrix of an observable part of the internet graph at the IP-level, extracted from traceroute measurements performed via RIPE NSS and PlanetLab. In order to investigate the factors influencing the Laplacian spectrum of the observed graphs, we study the following complex network models: the random graph of Erdos-Renyi, the smallworld of watts and strogatz and the scale-free graph, derived from a Havel-Hakimi powerlaw degree sequence. Along with these complex network models, we also study the corresponding minimum spanning tree (MST). Extensive simulations show that the Laplacian spectra of complex network models differ substantially from the spectra of the observed graphs. However, the Laplacian spectra of the MST in the Erdos-Renyi random graph with uniformly distributed link weights does bear resemblance to it. Furthermore, we discuss an extensive set of topological charateristics extracted from the Laplacian spectra of the observed real-world graphs as well as from complex network models.