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

• Activity Number: 568
• Type: Contributed
• Date/Time: Wednesday, August 6, 2014 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Can Le*+ and Elizaveta Levina and Roman Vershynin
• Companies: University of Michigan and University of Michigan and University of Michigan
• Keywords: Social networks ; Block models ; Community detection ; Spectral clustering

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 many of these methods have to deal with is the optimization problem over a discrete set of labels. In this paper we introduce a general approach for solving the problem of maximizing a network criterion by projecting the set of labels onto a subspace spanned by leading eigenvectors of the network adjacency matrix. The main idea is that projection onto a low-dimensional space makes the feasible set of labels much smaller and the optimization problem much easier. By applying our method to maximize network likelihoods, we also provide insight into the connection between spectral clustering and likelihood-based methods. Simulations and application to real-world data show that our method performs well over a wide range of parameters.