Online Sparsification of Bipartite-Like Clusters in Graphs
This work addresses the need for efficient graph clustering in real-world datasets, though it appears incremental as it builds on prior research on inter-connection analysis.
The paper tackles the problem of finding bipartite-like clusters in graphs by developing online sparsification algorithms for both undirected and directed graphs, resulting in significant speedups for existing clustering algorithms while maintaining effectiveness.
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 graph clustering algorithms is to find a vertex set of low conductance, a sequence of recent studies highlights the importance of the inter-connection between vertex sets when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online sparsification algorithms that find such clusters in both undirected graphs and directed ones. We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.