GraphDoS

Analyzing graphs based on global and local Density of States

• GitHub

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

@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}
}

Talks