提出在线稀疏化算法，高效发现图中类二分簇结构。
Online Sparsification of Bipartite-Like Clusters in Graphs
- 设计在线稀疏化方法，动态识别类二分簇。
- 实验显示速度提升显著，且保持原有聚类效果。
- 适合大规模图数据的实时聚类分析场景。
图聚类是分析大规模图的重要算法技术，广泛应用于数据科学多个领域。尽管多数图聚类算法旨在寻找低导通率的顶点集，近期研究强调了顶点集间连接关系在真实数据集分析中的重要性。本文聚焦于类二分簇，提出了适用于无向图和有向图的高效在线稀疏化算法。在合成数据集和真实数据集上进行了实验，结果表明该算法显著加快了现有聚类算法的运行时间，同时保持了其有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。