Spectral Algorithms for Massive Graphs

谱图算法利用图矩阵的代数性质来解决图的各种问题。在过去的二十年中，一系列的突破表明，光谱技术可以应用于为许多优化问题设计近线性时间算法。随着网络的规模随着时间的推移而显著增加，为大规模图形开发高效的算法将是科学界的重大兴趣，并且可能在长期内具有许多工业应用。在我的博士学习期间，我计划通过以下三个方向推进这一研究方向：(1)开发新的有向图和超图的谱方法；(2)针对目前没有光谱解的问题设计新的光谱算法；(3)开发已开发的光谱算法的开源实现。这些目标的完成将扩大谱图算法可以解决的问题集，并可能产生大规模图问题的高效解决方案。

Spectral graph algorithms leverage algebraic properties of graph matrices to solve a variety of problems for graphs. Over the past two decades, a sequence of breakthroughs have shown that spectral techniques can be applied to design nearly-linear time algorithms for many optimisation problems. As the size of networks of interest has increased significantly over time, developing highly efficient algorithms for massive graphs would be of significant interest in the scientific community, and might have a number of industrial applications in the long term. During my PhD studies I plan to advance this line of research through the following three directions: (1) develop new spectral methods for directed graphs and hypergraphs; (2) design new spectral algorithms for problems in which no spectral solutions are currently known; (3) develop an open-source implementation of the developed spectral algorithms. The completion of these objectives will broaden the set of problems that spectral graph algorithms can solve and may produce highly efficient solutions to large scale graph problems.