Local Algorithms for Finding Densely Connected Clusters

  • 2021-06-09 17:40:45
  • Peter Macgregor, He Sun
  • 1

Abstract

Local graph clustering is an important algorithmic technique for analysingmassive graphs, and has been widely applied in many research fields of datascience. While the objective of most (local) graph clustering algorithms is tofind a vertex set of low conductance, there has been a sequence of recentstudies that highlight the importance of the inter-connection between clusterswhen analysing real-world datasets. Following this line of research, in thiswork we study local algorithms for finding a pair of vertex sets defined withrespect to their inter-connection and their relationship with the rest of thegraph. The key to our analysis is a new reduction technique that relates thestructure of multiple sets to a single vertex set in the reduced graph. Amongmany potential applications, we show that our algorithms successfully recoverdensely connected clusters in the Interstate Disputes Dataset and the USMigration Dataset.

 

Quick Read (beta)

loading the full paper ...