论文标题
用于聚类的有向图的偏度对称邻接矩阵
Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs
论文作者
论文摘要
基于剪切的有向图（DIGRAPH）聚类通常集中在查找集群内或稀疏之间的群集之间的连接，类似于基于剪切的基于剪切的无向图聚类方法。相反，对于基于流的聚类，簇之间的边缘往往会以一个方向为导向，并且在迁移数据，食物网和贸易数据中已发现。在本文中，我们介绍了一种用于查找基于流的聚类的光谱算法。拟议的算法基于最近的工作，该工作使用复杂值的赫米尔式矩阵来代表挖掘物。通过建立复杂价值的Hermitian表示与相关的实现的偏斜矩阵之间的代数关系，提出的算法会产生聚类，同时完全保留在现实领域中。我们的算法使用较少的内存和渐近的计算，同时可以保留解决方案质量。我们还显示，可以使用标准计算构建块可以轻松地实现该算法，具有更好的数值属性，并通过客观函数放松参数将其本身借给自然解释。
Cut-based directed graph (digraph) clustering often focuses on finding dense within-cluster or sparse between-cluster connections, similar to cut-based undirected graph clustering methods. In contrast, for flow-based clusterings the edges between clusters tend to be oriented in one direction and have been found in migration data, food webs, and trade data. In this paper we introduce a spectral algorithm for finding flow-based clusterings. The proposed algorithm is based on recent work which uses complex-valued Hermitian matrices to represent digraphs. By establishing an algebraic relationship between a complex-valued Hermitian representation and an associated real-valued, skew-symmetric matrix the proposed algorithm produces clusterings while remaining completely in the real field. Our algorithm uses less memory and asymptotically less computation while provably preserving solution quality. We also show the algorithm can be easily implemented using standard computational building blocks, possesses better numerical properties, and loans itself to a natural interpretation via an objective function relaxation argument.
