A Caltech Library Service

Finding Dense Clusters via "Low Rank + Sparse" Decomposition

Oymak, Samet and Hassibi, Babak (2011) Finding Dense Clusters via "Low Rank + Sparse" Decomposition. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Finding "densely connected clusters" in a graph is in general an important and well studied problem in the literature. It has various applications in pattern recognition, social networking and data mining. Recently, Ames and Vavasis have suggested a novel method for finding cliques in a graph by using convex optimization over the adjacency matrix of the graph. Also, there has been recent advances in decomposing a given matrix into its "low rank" and "sparse" components. In this paper, inspired by these results, we view "densely connected clusters" as imperfect cliques, where imperfections correspond missing edges, which are relatively sparse. We analyze the problem in a probabilistic setting and aim to detect disjointly planted clusters. Our main result basically suggests that, one can find dense clusters in a graph, as long as the clusters are sufficiently large. We conclude by discussing possible extensions and future research directions.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Additional Information:This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CCF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0747
Caltech’s Lee Center for Advanced Networking.UNSPECIFIED
Record Number:CaltechAUTHORS:20150127-073728199
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54114
Deposited By: Shirley Slattery
Deposited On:28 Jan 2015 18:11
Last Modified:03 Oct 2019 07:55

Repository Staff Only: item control page