Towards a spectral characterization of signals supported on small-world networks

We study properties of the family of small-world random graphs introduced in Watts & Strogatz (1998), focusing on the spectrum of the normalized graph Laplacian. This spectrum influences the extent to which a signal supported on the vertices of the graph can be simultaneously localized on the graph and in the spectral domain (the surrogate of the frequency domain for signals supported on a graph). This characterization has implications for inferring or interpolating functions supported on such graphs when observations are only available at a subset of nodes.