DSCAN: Structural Clustering on Directed Graphs

doi:10.1109/tkde.2026.3717285

DSCAN: Structural Clustering on Directed Graphs

2026-07-27

0

PRE

AI

DOI：10.1109/tkde.2026.3717285

原文链接

原文求助

摘要

En 中文

结构聚类（$\mathsf{SCAN}$）是最流行的图聚类范式之一，广泛应用于理解和分析社交网络的结构。$\mathsf{SCAN}$假设输入图为无向图，无法对有向图进行聚类。然而，现实应用中的许多图是有向的，例如金融交易网络和引文网络。为解决此问题，本文提出了一种新的结构聚类模型用于聚类有向图。在该模型的基础上，我们提出了一种基于索引的方法以支持给定图的高效聚类。为进一步提高查询处理效率，我们提出了优化的二维索引和近似查询方法，在保持聚类质量的同时最高可提升20倍速度。我们在九个真实有向图上进行了大量实验，其中一个图包含超过6800万个顶点和20亿条边。实验结果证明了我们所提出方法的有效性和高效性。

Keyword:

Structural clustering

graph data management

big data

DSCAN: Structural Clustering on Directed Graphs

摘要

期刊

机构

引用论文