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

Apr, 2013

Limits of local algorithms over sparse random graphs

David Gamarnik, Madhu Sudan

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

Abstract

local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using

local algorithms independent sets random graphs clustering property belief propagation algorithm

发现论文，激发创造

最大独立集合的最佳低阶硬度

研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务，其中低次多项式算法可以找到半优大小的独立集，但不大于此规模。

Oct, 2020

随机图中的独立集

本研究证明：在随机图中，最大独立集问题的组合结构会在独立集大小 k 超过 k nln (d)/d 这个点时发生相变，形成一个错综复杂的景象，局部搜索算法难以摆脱。这一现象通过 Metropolis 过程，即一个用于采样独立集的马尔可夫链实现了指数下界。

Jul, 2010

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

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

Sep, 2008

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

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

Feb, 2012

超越 Cheeger 不等式的本地图聚类

本文提出了一种基于随机游走的局部聚类算法，通过将内部连接性参数考虑入内，改进了先前结果，得到更优秀的聚类精度和 conductance，并探讨了其与全局谱算法之间的联系。

Apr, 2013

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

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

Jun, 2021

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

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

Jul, 2016

具有聚类特性的稀疏随机图

本文介绍了一种扩展了边远离独立性的稀疏随机图的一般模型，并且通过构造非齐性随机超图来替代每个超边，再通过与某个积分算子的范数相关来解释巨型连通性的临界点，并将该巨型连通量与某些（非 Poisson）多类型分支过程的生存概率关联起来，同时研究度分布和数量小子图的细节。

Jul, 2008

图上简单随机游走序列的局部极限定理

本文研究了基于随机图模型的简单随机游走序列的局部极限定理，提出适用于超临界渗透簇、趋向于连续随机树的图树和嵌套分形的均一化问题等的相关结果，并给出了关于推广 Sierpinski 地毯图上简单随机游走的一些后续局部极限定理。

Oct, 2012

基于流的局部图聚类算法

本文介绍了一种名为 LocalImprove 的算法，应用于设计更好的本地图分区算法，该算法是首个切割改进算法，具有局部性质，可以在更短的时间内运行，同时与 Andersen 和 Lang 的全局算法具有相同的理论保证，解决了先前基于随机行走算法的图谱划分局部算法存在的问题。

Jul, 2013