机构名称：
¥ 1.0
聚类是算法中的一个重要主题，在机器学习、计算机视觉、统计学和其他几个研究学科中有着广泛的应用。图聚类的传统目标是找到具有低电导性的聚类。这些目标不仅适用于无向图，而且无法考虑聚类之间的关系，而这对于许多应用来说可能是至关重要的。为了克服这些缺点，我们研究了有向图（有向图），其聚类彼此之间展示了更多的“结构”信息。基于有向图的 Hermitian 矩阵表示，我们提出了一种近线性时间的有向图聚类算法，并进一步表明我们提出的算法可以在合理的假设下以亚线性时间实现。我们的理论工作的意义通过对联合国商品贸易统计数据集的大量实验结果得到证明：我们算法的输出聚类不仅展示了聚类（国家集合）在进出口记录方面如何相互关联，还展示了这些聚类如何随着时间的推移而演变，这与已知的国际贸易事实一致。
有向图的高阶谱聚类
主要关键词
相关文件推荐
![b“极值图论的一个核心问题是确定给定图 H 在 \xef\xac\x81x 大小的图中诱导副本的最大数量。这个问题最早由 Pippenger 和 Golumbic [13] 研究，近年来已成为广泛研究的主题 [2, 3, 7, 8, 11, 18]。本文重点关注有向图的类似问题。准确地说，设 H 是有向图。有向图 G 中 H 的诱导密度，表示为 i ( H, G )，是 G 中 H 的诱导副本数量除以 | V ( G ) | | V ( H ) | 。对于整数 n ，设 i ( H, n ) 为所有 n 顶点有向图 G 中 i ( H, G ) 的最大值。H 的诱导性定义为为 i ( H ) = lim n \xe2\x86\x92\xe2\x88\x9e i ( H, n )。当 i ( H, n ) 对于 n \xe2\x89\xa5 2 递减时，此极限存在。只有极少数有向图的可诱导性是已知的。一类重要的例子是有向星号。对于非负整数 k 和 \xe2\x84\x93 ，让有向星号 S k,\xe2\x84\x93 为通过对具有 k + \xe2\x84\x93 叶子的星号的边进行有向图，使得中心具有出度 k 和入度 \xe2\x84\x93 。有向星形是所有边都具有相同方向的定向星形，即星形 S k,\xe2\x84\x93 ，使得 k = 0 或 \xe2\x84\x93 = 0。S 2 , 0 和 S 3 , 0 的可诱导性由 Falgas-Ravry 和 Vaughan [5] 确定。为了解决 [5] 中的一个猜想，Huang [10] 扩展了他们的结果，确定了对所有 k \xe2\x89\xa5 2 的 S k, 0 的可诱导性，表明它是通过对入度为 0 的部分进行不平衡的弧爆破而渐近获得的。注意，由于任何有向图的可诱导性等于通过反转所有弧得到的有向图的可诱导性，因此可以考虑有向星号 S k,\xe2\x84\x93 ，使得 k \xe2\x89\xa5 \xe2\x84\x93 。特别地，Huang 的结果还确定了对所有 \xe2\x84\x93 的 S 0 ,\xe2\x84\x93 的可诱导性。 [10] 的结果未涵盖的最小定向星是 S 1 , 1 ，即三个顶点上的有向路径。Thomass\xc2\xb4e [16，猜想 6.32] 猜想 i ( S 1 , 1 ) = 2 / 5，这是通过四个顶点上的有向环的迭代爆炸获得的。](/simg/b/ba28460dd1b06d9996628290aa73355077ae7e14.webp)