Summary

Researchers from many disciplines study spectra to understand the structure and composition of mathematical objects and physical systems. For large systems, complete spectral information costs too much, whether it is gathered computationally or measured experimentally; hence, most spectral analysis methods use partial information about the eigenvalues or eigenvectors of some matrix or operator. Broadly speaking, these methods use either

  • A few (extreme) eigenvalues and associated eigenvectors
  • Invariants that are simple functions of all the eigenvalues
  • Densities of eigenvalues (a.k.a. density of states), possibly weighted by local importance.

All three approaches are used in spectral geometry an in applications to physics and engineering systems. But distributional information is much less used in the study of complex networks. Indeed, though Weyl’s law for eigenvalue distributions was introduced to spectral geometry six decades prior to Cheeger’s inequality, within spectral graph theory the latter is universally taught as part of spectral graph theory while the former is nearly unknown, though related concepts having to do with the heat kernel have started to be more widely used.

In this project, we explore the computation and interpretation of the density of states and local density of states for different network-related matrices.

Papers

K. Dong and D. Bindel, “Modified Kernel Polynomial Method for Estimating Graph Spectra,” in SIAM Network Science 2015 (poster), 2015.
@inproceedings{2015-siam-ns,
  author = {Dong, Kun and Bindel, David},
  title = {Modified Kernel Polynomial Method for Estimating Graph Spectra},
  booktitle = {SIAM Network Science 2015 (poster)},
  month = may,
  year = {2015}
}

Abstract:

The kernel polynomial method (KPM) is a standard tool in condensed matter physics to estimate the density of states for a quantum system. We use the KPM to instead estimate the eigenvalue densities of the normalized adjacency matrices of “natural” graphs. Because natural graph spectra often include high-multiplicity eigenvalues corresponding to certain motifs in the graph, we introduce a pre-processing phase that counts just these special eigenvalues, leaving the rest of the eigenvalue distribution to be estimated by the standard KPM.

Talks

Density of States for Graph Analysis

SIAM Annual Meeting, Boston
spechistmeeting external poster

Understanding graphs through spectral densities

Cornell SCAN Seminar
spechistseminar local

Spectral Densities and Social Networks

NYCAM
spechistmeeting local organizer

A Tale of Two Eigenvalue Problems

Cornell Brownbag Seminar
gyro mems spechistseminar local