Spectral Algorithms for Massive Graphs

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.