May, 2016

稀疏网络中分布式距离计算的近线性下界

PDF
TL;DR本篇研究提出了一种构建稀疏图的新技术，能够证明计算 CONGEST 模型中距离的轮廓复杂度的近似线性下界，它能够计算直径、半径和所有偏心距的近似值，并且这些下界能够比以前的下界有所改善。
发现论文，激发创造
  • 分布式最小割近似

    本文通过分布式算法研究了在标准同步消息传递模型下，计算近似的最小边割问题，提出了随机分层技术作为分析随机边采样的一种简单方法，并给出了两个分布式算法的时间复杂度，同时还强化了上一篇研究的下界。

    May, 2013

  • CONGEST 模型二次和接近二次的下界

    该研究给出在 CONGEST 模型中自然图问题的第一个超线性下界，并回答了长期以来的一个开放性问题，特别地，证明任何精确计算最小顶点覆盖或最大独立集的算法都需要在最坏情况下花费 Ω(n²/log²n) 轮，这样强的下界不仅局限于 NP 困难问题。

    May, 2017

  • 核范数中的快速谱密度估计与稀疏化

    利用一种随机算法和核稀疏化的方法，该研究提出了一种新的图谱估计方法，可在线性时间和多项式查询复杂度下，准确估计归一化邻接矩阵的谱密度。这一方法在复杂度和准确性方面均具有优势，且创造性地解决了图的稀疏化和添加谱稀疏化的相关问题。

    Jun, 2024

  • 简化谱半径以控制流行病传播的近似算法

    本文提出了一套可证明的逼近算法，通过删除最小成本的边（建立隔离区）或节点（建立疫苗接种）来减少网络的谱半径，主要算法基于敲定特定长度封闭路径的思想，性能较之前的启发式算法更优，实验证明了算法的可行性和解的属性。

    Jan, 2015

  • 分布式功能监测的严格界限

    通过新的直接求和定理，我们解决了数据流模型中估计频率矩阵和其它问题时的基础问题，并通过改进算法显著提高了界限。

    Dec, 2011

  • 测试图的聚类结构

    在有界度模型的性质测试框架中研究了识别图的集群结构问题，提出了一个亚线性算法，可识别由参数 k, phi, epsilon 制定的 (d) 有界度图，并且是渐近最优的，关键是集群内外的 conductance。

    Apr, 2015

  • 稀疏网络社区检测的信息论门限

    论文提出了信息论阈值的上下界，并进一步证明了当组数较大且特定参数取值时，物理条件下的凝聚阈值是具有严格界限的，若邻居间与组间边缘概率不同，则分配问题可以解决，否则无算法可优于随机。

    Jan, 2016

  • 利用 Grothendieck 不等式在稀疏网络中进行社区检测

    本研究提出一种基于 Grothendieck inequality 的方法，旨在证明随机图上半定规划问题的一致性，可适用于众多的网络随机模型和半定规划问题，并具有普适性。同时通过应用该方法于稀疏网络中的社交圈问题，可利用各种简单和自然的半定规划方案恢复社交圈结构。

    Nov, 2014

  • 有向无权图中的度量恢复

    本文展示了在至少需要 ω(n^(2/(d+2))) 的节点度时（其中 d 为维度），可以从有向无权图中恢复欧几里得度量和相关密度的估计，其中我们的估计器基于有向图上的随机游走的特征化和相应连续极限。

    Nov, 2014

  • 对数直径轮并行图连通性

    研究在 MPC 模型下对图连通性问题进行优化，通过图直径参数化时间复杂度，得到了对于直径为 D 的图的时间复杂度为 O (logDloglog (m/n) n)、总内存为 Θ(m) 的连通性算法，并扩展到生成森林、DFS 序列、最小生成森林和瓶颈生成森林等相关图问题，并指出这些问题的类似界限推导可以应用于更快的布尔矩阵乘法算法。

    May, 2018