有效局部搜索增强平衡图边划分
本文研究了大规模图的本地算法设计并提出了一种本地聚类算法,该算法可在几乎线性的时间内找到较好的簇,并基于该聚类算法提出了一种划分算法,进而设计了求解对称对角占优矩阵中线性系统的近线性算法,还提出了其他相关结果。
Sep, 2008
本文介绍了一种名为 LocalImprove 的算法,应用于设计更好的本地图分区算法,该算法是首个切割改进算法,具有局部性质,可以在更短的时间内运行,同时与 Andersen 和 Lang 的全局算法具有相同的理论保证,解决了先前基于随机行走算法的图谱划分局部算法存在的问题。
Jul, 2013
本篇文章提出了一种自适应分区方法,可应对大规模知识图谱中查询工作量变化的需求,通过动态适应知识图谱三元组的分区,可以提高查询处理时间的性能。
Mar, 2022
本文探讨了 k-Balanced Partitioning 问题的两类近似算法:快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明,这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架,以证明了该问题的困难性。本文是该问题的第一次双层次不可近似结果。
Nov, 2011
介绍了一种新型的基于 restreaming 的算法,使用带有乘性权重的约束管理策略来优化流式过程的排序,同时借鉴了平衡标签传播的优先级概念来进行分区优化,得到了与现有算法相比在真实世界图上具有更好性能的结果。
Jul, 2020
提出了一种使用边平衡来实现社交网络公平图分区的方法,并通过使用线性图转换和协同嵌入框架来学习图分区的双节点和边公平感知表征,并提出了一种公平分区可用作伪标签以促进图神经网络在节点分类和链接预测任务中表现公平。
Jun, 2023
本文提出了一种基于马尔可夫链的随机局部分区算法,通过模拟有相偏差的演化集过程,找到具有小导纳的节点集合,进而生成一个稀疏的分割,该算法的计算复杂度与输出大小有关,具有很好的输出质量和较低的计算复杂度,因此可以有效地用于构建快速的平衡切割算法。
Nov, 2008