Local Algorithms for Finding Densely Connected Clusters

Peter Macgregor, He Sun
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7268-7278, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-macgregor21a, title = {Local Algorithms for Finding Densely Connected Clusters}, author = {Macgregor, Peter and Sun, He}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {7268--7278}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/macgregor21a/macgregor21a.pdf}, url = {https://proceedings.mlr.press/v139/macgregor21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Local Algorithms for Finding Densely Connected Clusters %A Peter Macgregor %A He Sun %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-macgregor21a %I PMLR %P 7268--7278 %U https://proceedings.mlr.press/v139/macgregor21a.html %V 139 %X 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.
APA
Macgregor, P. & Sun, H.. (2021). Local Algorithms for Finding Densely Connected Clusters. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:7268-7278 Available from https://proceedings.mlr.press/v139/macgregor21a.html.

Related Material