Local graph clustering is an important algorithmic technique for analysing
massive graphs, and has been widely applied in many research fields of data
science. While the objective of most (local) graph clustering algorithms is to
find a vertex set of low conductance, there has been a sequence of recent
studies that highlight the importance of the inter-connection between clusters
when analysing real-world datasets. Following this line of research, in this
work we study local algorithms for finding a pair of vertex sets defined with
respect to their inter-connection and their relationship with the rest of the
graph. The key to our analysis is a new reduction technique that relates the
structure of multiple sets to a single vertex set in the reduced graph. Among
many potential applications, we show that our algorithms successfully recover
densely connected clusters in the Interstate Disputes Dataset and the US
Migration Dataset.

本文研究了一种基于局部算法的图聚类方法，通过引入新的缩减技术来分析多个集合间的相互关系，并在多个实际数据集上通过恢复密集连接簇来展示算法的有效性。

寻找密集连接聚类的本地算法

Local Algorithms for Finding Densely Connected Clusters

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.

本文基于凸优化和矩阵分解的最新成果，将 “密集连接群集” 视为不完美的团，利用概率性方法分析问题并旨在检测孤立的种植群集。我们的主要结论基本上是，只要群集足够大，就可以在图中找到密集的群集。