Local Algorithms for Finding Densely Connected Clusters
  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.
