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} }
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
Understanding Graphs through Spectral Densities
CS Colloquium, William and Mary
spechist
•
colloquium external invited
Understanding Graphs through Spectral Densities
Math Colloquium, Virginia Tech
spechist
•
colloquium external invited
Understanding Graphs through Spectral Densities
LANS Seminar, Argonne National Lab
spechist
•
seminar local
Understanding Graphs through Spectral Densities
SIAM Network Science, Portland
spechist
•
meeting external invited plenary
Understanding Graphs through Spectral Densities
Seminar at Huazhong University of Science and Tech
spechist
•
seminar external invited
Understanding Graphs through Spectral Densities
ZY-INS Colloquium, Shanghai Jiao Tong University
spechist
•
colloquium external invited
Density of States for Graph Analysis
SIAM Annual Meeting, Boston
spechist
•
meeting external poster
Understanding graphs through spectral densities
Cornell SCAN Seminar
spechist
•
seminar local
Spectral Densities and Social Networks
NYCAM
spechist
•
meeting local organizer
A Tale of Two Eigenvalue Problems
Cornell Brownbag Seminar
gyro mems spechist
•
seminar local