带符号图的亚线性时间聚类神谕
本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法,该算法可以将图按照展开器分簇,并可以提高聚类的准确性,同时通过估计图中节点的随机游走的分布,实现对谱嵌入的点积访问,并使用谱嵌入进行超平面划分,从而实现聚类。
Jan, 2021
我们设计了一个次线性时间的谱聚类预处理方法来解决在具有强聚类性的图中的问题。我们的算法通过在次线性时间内进行预处理和查询回答,得到与实际聚类接近的 $k$-partition。我们的实验证明了我们的理论性能。
Oct, 2023
本文提出一种基于离散特征值问题的谱算法,以发现有极性社群的有符号网络中两个极化社群,证明所提出的问题是 NP-hard 的,同时在真实世界现象的情况下验证了算法的有效性并证明其比非平凡基线更好、更快、能够扩展到更大的网络。
Oct, 2019
本文研究如何通过建立一个索引来实现针对具有 n 个顶点和 m 个正边的完整带符号图的相关聚类问题的复杂度降低,从而达到 $ O (m + n)$ 的复杂度,同时考虑动态改变环境和非协议度量的结构特性。通过对七个真实数据集进行实验,结果表明相比无索引的算法,我们的基于索引的算法的平均时间减少了 34%。
Jan, 2023
本文系统地介绍了图割方法,着重介绍了归一化图割方法及其在加权无向图和有向图聚类中的应用,并提出了解决带符号图的问题的方法。此外,本文还表明了比率割方法是归一化割方法的特例。
Jan, 2016
本文提出了一种利用角度信息和奇异值分解的子线性时间图聚类算法,并在其基础上给出了测试聚类可行性的查询复杂度下界,并且通过这些技术,也实现了新的子线性时间下界近似最大割价值的问题。
Aug, 2018
本文介绍了一种在带符号图中进行 $k$ 路分簇的原则性和理论上可靠的谱方法。我们的方法受到社会平衡理论的启发,旨在将网络分解为不相交的群体,使得同一组中的个体通过尽可能多的正边相连接,而不同组中的个体则尽可能多地连接负边。我们的算法依靠广义特征问题公式,为带符号的随机块模型提供了理论保证。数值实验表明,我们的方法在带符号聚类中比现有方法表现得更好,特别是在大量簇和稀疏测量图的情况下。
Apr, 2019
在有界度模型的性质测试框架中研究了识别图的集群结构问题,提出了一个亚线性算法,可识别由参数 k, phi, epsilon 制定的 (d) 有界度图,并且是渐近最优的,关键是集群内外的 conductance。
Apr, 2015
本文提出了一种基于随机游走的局部聚类算法,通过将内部连接性参数考虑入内,改进了先前结果,得到更优秀的聚类精度和 conductance,并探讨了其与全局谱算法之间的联系。
Apr, 2013