Finding Dense Clusters via "Low Rank + Sparse" Decomposition

Details Finding Dense Clusters via "Low Rank + Sparse" Decomposition Finding Dense Clusters via "Low Rank + Sparse" Decomposition

2011-04-27

arxiv.org/abs/1104.5186v1

Statistics

Machine Learning

19 pages, 2 figures

Scientific paper

Finding "densely connected clusters" in a graph is in general an important and well studied problem in the literature \cite{Schaeffer}. It has various applications in pattern recognition, social networking and data mining \cite{Duda,Mishra}. 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 \cite{Ames, Ames2}. Also, there has been recent advances in decomposing a given matrix into its "low rank" and "sparse" components \cite{Candes, Chandra}. 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 \emph{dense} clusters in a graph, as long as the clusters are sufficiently large. We conclude by discussing possible extensions and future research directions.

Affiliated with

Also associated with

No associations

Rating

Finding Dense Clusters via "Low Rank + Sparse" Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Dense Clusters via "Low Rank + Sparse" Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Dense Clusters via "Low Rank + Sparse" Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-476016