Local Algorithms for Finding Densely Connected Clusters
Local Algorithms for Finding Densely Connected Clusters
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Peter Macgregor;He Sun
中科院分区：
文献类型：
--
作者：
Peter Macgregor;He Sun
局部图聚类是分析海量图的一种重要算法技术，在数据科学的许多研究领域得到了广泛的应用。虽然大多数（局部）图聚类算法的目标是找到一个低电导的顶点集，但最近有一系列研究强调了在分析现实世界数据集时聚类之间相互连接的重要性。沿着这条研究路线，在这项工作中，我们研究了寻找一对顶点集的局部算法，这些顶点集是根据它们的相互联系以及它们与图中其余部分的关系来定义的。我们分析的关键是一种新的约简技术，它将多个集的结构与约简图中的单个顶点集联系起来。在许多潜在的应用中，我们展示了我们的算法成功地恢复了州际纠纷数据集和美国移民数据集中密集连接的集群。
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.