Title: A Compressive Sensing Approach to Community Detection with Applications,
Abstract: The community detection problem for graphs asks one to partition the n
vertices V of a graph G into k communities, or clusters, such that there are
many intracluster edges and few intercluster edges. Of course this is
equivalent to finding a permutation matrix P such that, if A denotes the
adjacency matrix of G, then PAP^T is approximately block diagonal. As there are
k^n possible partitions of n vertices into k subsets, directly determining the
optimal clustering is clearly infeasible. Instead one seeks to solve a more
tractable approximation to the clustering problem. In this paper we reformulate
the community detection problem via sparse solution of a linear system
associated with the Laplacian of a graph G and then develop a two-stage
approach based on a thresholding technique and a compressive sensing algorithm
to find a sparse solution which corresponds to the community containing a
vertex of interest in G. Crucially, our approach results in an algorithm which
is able to find a single cluster of size n_0 in O(nlog(n)n_0) operations and
all k clusters in fewer than O(n^2ln(n)) operations. This is a marked
improvement over the classic spectral clustering algorithm, which is unable to
find a single cluster at a time and takes approximately O(n^3) operations to
find all k clusters. Moreover, we are able to provide robust guarantees of
success for the case where G is drawn at random from the Stochastic Block
Model, a popular model for graphs with clusters. Extensive numerical results
are also provided, showing the efficacy of our algorithm on both synthetic and
real-world data sets.