Online Sparsification of Bipartite-Like Clusters in Graphs
By: Joyentanuj Das, Suranjan De, He Sun
Potential Business Impact:
Finds groups of connected things faster.
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.
Similar Papers
Clustering of Incomplete Data via a Bipartite Graph Structure
Machine Learning (CS)
Finds groups in tricky financial data.
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Data Structures and Algorithms
Makes computer grouping work faster on big data.
An Improved and Generalised Analysis for Spectral Clustering
Machine Learning (CS)
Finds hidden groups in connected information.