Add to Cal
  • Speaker: Can Le
  • Host Department: Statistics
  • Date: 01/21/2013
  • Time: 1:00 PM

  • Location: 438 West Hall

  • Description:

    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. 

  • Event Flyer