Higher-Order Spectral Clustering of Directed Graphs
Higher-Order Spectral Clustering of Directed Graphs
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Steinar Laenen;He Sun
中科院分区：
文献类型：
--
作者：
Steinar Laenen;He Sun
聚类是算法中的一个重要主题，在机器学习、计算机视觉、统计学和其他几个研究学科中有许多应用。图聚类的传统目标是找到具有低传导性的簇。这些目标不仅适用于无向图，它们也无法考虑聚类之间的关系，这对许多应用程序来说可能是至关重要的。为了克服这些缺点，我们研究了有向图（有向图），其簇彼此之间表现出进一步的“结构”信息。基于有向图的Hermitian矩阵表示，提出了一种近似线性时间的有向图聚类算法，并进一步证明了在合理的假设下，该算法可以在次线性时间内实现.我们的理论工作的意义是证明了广泛的实验结果在联合国商品贸易统计数据集：我们的算法的输出聚类不仅展示了集群（国家集）如何相互关联的进出口记录，而且这些集群如何随着时间的推移，根据国际贸易中已知的事实。
Clustering is an important topic in algorithms, and has a number of applications in machine learning, computer vision, statistics, and several other research disciplines. Traditional objectives of graph clustering are to find clusters with low conductance. Not only are these objectives just applicable for undirected graphs, they are also incapable to take the relationships between clusters into account, which could be crucial for many applications. To overcome these downsides, we study directed graphs (digraphs) whose clusters exhibit further "structural" information amongst each other. Based on the Hermitian matrix representation of digraphs, we present a nearly-linear time algorithm for digraph clustering, and further show that our proposed algorithm can be implemented in sublinear time under reasonable assumptions. The significance of our theoretical work is demonstrated by extensive experimental results on the UN Comtrade Dataset: the output clustering of our algorithm exhibits not only how the clusters (sets of countries) relate to each other with respect to their import and export records, but also how these clusters evolve over time, in accordance with known facts in international trade.