标题： 一种用于有向图聚类的迭代谱算法 显示英文标题

标题： An iterative spectral algorithm for digraph clustering

摘要： 图聚类是数据分析中的基本技术，具有在许多不同领域的应用。 尽管有关于聚类无向图的大量研究工作，但聚类有向图的问题却远未被充分理解。 在有向图的情况下，分析更为复杂，原因有两个：聚类必须保留集群之间关系的方向信息，且有向图具有非厄米特邻接矩阵，其性质不利于传统的谱方法。 本文我们考虑将有向图的顶点集划分为$k\ge 2$个簇，使得不同簇之间的边倾向于遵循相同的方向。 我们提出了一种基于谱方法的迭代算法，该方法应用于有向图的新厄米特表示。 我们的算法在合成和真实数据集上均优于最先进方法。 此外，它能够识别一个包含$k$个顶点的“元图”，该图表示有向图中簇之间的高阶关系。 我们在涉及食物网、生物神经网络和在线卡牌游戏《炉石传说》的数据集上展示了这一能力。 显示英文摘要

摘要： Graph clustering is a fundamental technique in data analysis with applications in many different fields. While there is a large body of work on clustering undirected graphs, the problem of clustering directed graphs is much less understood. The analysis is more complex in the directed graph case for two reasons: the clustering must preserve directional information in the relationships between clusters, and directed graphs have non-Hermitian adjacency matrices whose properties are less conducive to traditional spectral methods. Here we consider the problem of partitioning the vertex set of a directed graph into $k\ge 2$ clusters so that edges between different clusters tend to follow the same direction. We present an iterative algorithm based on spectral methods applied to new Hermitian representations of directed graphs. Our algorithm performs favourably against the state-of-the-art, both on synthetic and real-world data sets. Additionally, it is able to identify a "meta-graph" of $k$ vertices that represents the higher-order relations between clusters in a directed graph. We showcase this capability on data sets pertaining food webs, biological neural networks, and the online card game Hearthstone.