The laplacian spectrum of complex networks

A Jamakovic, PFA Van Mieghem

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


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.
Original languageUndefined/Unknown
Title of host publicationEuropean conference on complex systems
EditorsJ Jost, F Reed-Tsochas, P Schuster
PublisherOxford Said business school
Number of pages6
ISBN (Print)0-9554123-0-7
Publication statusPublished - 2006

Publication series

PublisherOxford Said business school


  • conference contrib. refereed
  • Conf.proc. > 3 pag

Cite this