局部偏置图算法的优化方法

Jul, 2016

An optimization approach to locally-biased graph algorithms

Kimon Fountoulakis, David Gleich, Michael Mahoney

TL;DR本文综述了最近几年来几个研究社区对局部偏差图算法的发展和应用，以及这些算法和算法论和统计理论的相互关系。

Abstract

locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of →

locally-biased graph algorithms locality constraint algorithmic theory statistical theory

发现论文，激发创造

稀疏随机图上本地算法的限制

本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小，而且通过聚类属性，我们强调了在随机图上的局部算法存在局限性。

Apr, 2013

社交网络中本地信息的力量

本文研究了局部信息算法在社交网络上的优化问题的能力，重点探讨了顺序算法，其中网络拓扑初始状态未知，并且仅在已不可逆地添加到输出集合的顶点的本地邻域内显示。我们研究了各种问题，并解决了拓扑网络中的一个开放问题，同时还研究了在线网络招聘过程中的最小支配集的问题，并且发现网络提供商的决策会影响用户的战略互动。

Feb, 2012

一种用于图形的本地频谱方法：在改善图划分和本地探索数据图中的应用

本文介绍了拉普拉斯矩阵的第二特征值和相关特征向量在无向图中的基本特征，并提出了第二特征向量的局部偏差模型，用于半监督方式下确定数据图的本地性质和优化问题，从而可以在近线性时间内计算最优解，并提供了在社交和信息网络中找到具有局部偏差的稀疏线性切割的详细实证评价。

Dec, 2009

寻找密集连接聚类的本地算法

本文研究了一种基于局部算法的图聚类方法，通过引入新的缩减技术来分析多个集合间的相互关系，并在多个实际数据集上通过恢复密集连接簇来展示算法的有效性。

Jun, 2021

大规模图的本地聚类算法及其在近似线性时间图分割中的应用

本文研究了大规模图的本地算法设计并提出了一种本地聚类算法，该算法可在几乎线性的时间内找到较好的簇，并基于该聚类算法提出了一种划分算法，进而设计了求解对称对角占优矩阵中线性系统的近线性算法，还提出了其他相关结果。

Sep, 2008

有效局部搜索增强平衡图边划分

本文研究了图分区中的边划分问题，提出了可调节的边和块的两个新概念，基于此发展了一种贪心启发式和一个利用最大流模型的改进搜索算法，可以大幅度提高图分区的质量和近似比。