Clustering fully and partially observable graphs via nonconvex optimization

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

Abstract

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.
Pages4930-4935
Number of pages6
ISBN (Electronic)9781467386821
DOIs
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
Volume2016-July
ISSN (Print)0743-1619

Other

Other2016 American Control Conference, ACC 2016
Country/TerritoryUnited States
CityBoston
Period7/6/167/8/16

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

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

Cite this