DSCAN：有向图上的结构聚类

《IEEE Transactions on Knowledge and Data Engineering》：DSCAN: Structural Clustering on Directed Graphs

　　**摘要：**结构聚类（SCAN）是最流行的图聚类范式之一，被广泛应用于理解和分析社交网络的结构。SCAN假设输入的图为无向图，无法对 directed 图进行聚类。然而，现实应用中的许多图都是有向图，例如金融交易网络和引用网络。为了解决这一问题，本文提出了一种新的结构聚类模型，用于对有向图进行聚类。基于该新模型，我们提出了一种基于索引的方法，以支持对给定图的高效聚类。为了进一步提升查询处理的效率，我们提出了一种优化的二维索引和近似查询方法，在保持聚类质量的同时，实现了最高20倍的速度提升。我们在九个真实有向图上进行了大量实验，其中一个图包含超过6800万个顶点和20亿条边。实验结果表明了我们所提方法的有效性和高效性。**I. 引言**图聚类是图数据分析中的基本问题，已被广泛研究。直观地说，一个聚类是由一组"相似"顶点组成的群体，群体内部的顶点连接紧密，而与群体外部顶点的连接稀疏。图聚类旨在检测图中的聚类，并确定图中每个顶点对应的角色。图聚类可应用于广泛的场景，例如社交网络和生物网络分析、分布式系统中的负载均衡、自然语言处理以及推荐系统等。