Can Le

Optimization via Low-rank Approximation with Application to Network Community Detection

Title: Optimization via Low-rank Approximation with Application to Network Community Detection
Advisor: Associate Professor Elizaveta Levina, Professor Roman Vershynin
Committee Member: Professor Ji Zhu

Abstract: The community detection is an important problem in network analysis. Several methods have been proposed to solve the problem, including spectral clustering, modularity, and likelihood-based methods. One issue that most of such methods have to deal with is the optimization problem over a discrete set of labels. In this proposal we introduce a new approach for solving the problem of maximizing the log-likelihood function of the network. By replacing the network adjacency matrix with a low-rank approximation, we reduce the maximization problem over labels to the maximization problem over a convex set in a low-dimensional space. The later problem turns out to have its solution on the boundary and can be solved efficiently. We show that our method performs well over a wide range of parameters. The method may be applied to solve general problems involving functions of adjacency matrices.