Modern network science analyzes and interprets relationships such as friendships between people in a social network, interactions between proteins in a biological network, or connections between machines in a computer network. A key challenge in large-scale network analysis is understanding how the network is composed of basic building blocks or motifs, such as communities in social networks or groups of proteins that function together in a biological network. Once such building blocks have been identified, one would like to identify what things in the network play key roles in them. This project will create novel methods for decomposing networks into basic building blocks using the mathematical tool of graph spectra. Just as physical scientists use the spectrum of light frequencies absorbed or emitted by an object to determine the atomic composition of the material, graph spectra let network scientists determine how networks are composed from basic atomic building blocks. The project will produce fast software tools to compute graph spectra for networks involving relations between millions of entities, along with new analysis techniques to extract network building blocks from these spectral signals.
The main objective of this research is to extend spectral density analysis methods common in spectral geometry and physics to gain new insights into the structure and composition of complex networks. The research extends prior work in computational material science, introducing novel stochastic and deterministic estimators of local and global spectral densities with different tradeoffs with respect to cost and accuracy. These methods will take advantage of the structure of localized eigenvectors associated with interior eigenvalues in the spectra of complex networks and to find network motifs. New graph decomposition techniques based on these local spectral density estimates will enable new and practical tools for graph analysis, and spectral node classification techniques based on this approach will generalize current centrality-based measures of node importance to provide more detailed insights into the role nodes play in a network. In addition to providing new mathematical insights, the project will result in new software tools for use by a broad audience of network scientists, and will expose undergraduate researchers to spectral theory in network science.
