Computing Spectral Distributions for Graph Analysis and Classification

现代网络科学分析和解释诸如社交网络中人与人之间的友谊、生物网络中蛋白质之间的相互作用或计算机网络中机器之间的连接等关系。大规模网络分析的一个关键挑战是理解网络是如何由基本的构件或基序组成的，例如社会网络中的社区或在生物网络中共同发挥功能的蛋白质组。一旦确定了这样的构建块，人们就会想要确定网络中的哪些东西在其中扮演着关键角色。这个项目将创造新的方法，利用图谱的数学工具将网络分解成基本的构建块。就像物理学家使用物体吸收或发射的光频率的光谱来确定材料的原子组成一样，图形光谱让网络科学家可以确定网络是如何由基本的原子构件组成的。该项目将开发快速的软件工具来计算涉及数百万实体之间关系的网络的图谱，以及从这些谱信号中提取网络构件的新的分析技术。这项研究的主要目的是扩展谱几何和物理中常见的谱密度分析方法，以获得对复杂网络的结构和组成的新见解。这项研究扩展了计算材料科学的先前工作，引入了关于成本和精度的不同权衡的局部和全局谱密度的新的随机和确定性估计器。这些方法将利用复杂网络频谱中与内部特征值相关联的局域特征向量的结构来寻找网络基元。基于这些局部谱密度估计的新的图分解技术将为图分析提供新的实用工具，而基于该方法的谱节点分类技术将推广当前基于中心度的节点重要性度量，以提供对节点在网络中所起作用的更详细的洞察。除了提供新的数学见解外，该项目还将产生新的软件工具，供广大网络科学家使用，并将使本科生研究人员接触到网络科学中的光谱理论。

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.