Finding Dense Clusters via "Low Rank + Sparse" Decomposition
- Creators
- Oymak, Samet
- Hassibi, Babak
Abstract
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.
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.Attached Files
Submitted - Finding_dense_clusters.pdf
Files
Name | Size | Download all |
---|---|---|
md5:d161c0d83f734b63305cd663c07ea7d0
|
318.4 kB | Preview Download |
Additional details
- Eprint ID
- 54114
- Resolver ID
- CaltechAUTHORS:20150127-073728199
- NSF
- CCF-0729203
- NSF
- CNS-0932428
- NSF
- CCF-1018927
- Office of Naval Research (ONR)
- N00014-08-1-0747
- Caltech's Lee Center for Advanced Networking.
- Created
-
2015-01-28Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field