Clustering fully and partially observable graphs via nonconvex optimization

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The problem of clustering unweighted graphs either in the case of fully or partially observable adjacency matrices is considered in this paper. Both these subproblems have been recently considered in the literature and have been tackled based on convex optimization techniques related to the problems of matrix completion and robust principal component analysis that fall into the general compressive sensing framework. We revisit these approaches and extend them by proposing ways to obtain more accurate clustering results based on better approximations for the l0-norm of a matrix than the l1-norm. The current state-of-art methods correspond to special instances of the proposed extensions. Although nonconvex, the proposed methods can be approximately decomposed into sequences of l1-norm minimization problems, thus pertaining the efficiency of convex formulations. The methods are compared using graphs that are built upon the classical stochastic blockmodel. These comparisons provide a good indication that the proposed methods can improve the accuracy of state-of-art clustering methods applied to currently popular applications such as that of community detection in social networks.

Original languageEnglish (US)
Title of host publication2016 American Control Conference, ACC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781467386821
StatePublished - Jul 28 2016
Event2016 American Control Conference, ACC 2016 - Boston, United States
Duration: Jul 6 2016Jul 8 2016

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Other2016 American Control Conference, ACC 2016
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Clustering fully and partially observable graphs via nonconvex optimization'. Together they form a unique fingerprint.

Cite this