Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Lincoln Lu

UCSD Visitor

Spectra of random power law graphs

Abstract:

Many graphs arising in various information networks exhibit the power law behavior the number of vertices of degree $k$ is proportional to $k^{-eta}$ for some positive $eta$. Such graphs are called power law graphs. In the study of the spectra of power law graphs, there are basically two competing approaches. One is to prove analogues of Wigner`s semi-circle law while the other predicts that the eigenvalues follow a power law distributions. We will show that both approaches are essentially correct if one considers the appropriate matrices. We will prove that (under certain mild conditions) the eigenvalues of the (normalized) Laplacian of a random power law graph follow the semi-circle law while the spectrum of the adjacency matrix of a power law graph obeys the power law. Our results are based on the analysis of random graphs with given expected degrees and their relations to several key invariants. These results have implications on the usage of spectral techniques in many areas related to pattern detection and information retrieval. This is a joint work with Prof. Fan Chung and Prof. Van Vu.

Host:

February 3, 2004

3:00 PM

AP&M 6438

****************************