May, 2016

排除子图的分布式测试

PDF
TL;DR在基于 CONGEST 模型的分布式计算中，我们研究了属性测试。我们证明，对于每个联通的 4 节点图 H，测试一个图是否是 H-free 也可以在恒定数量的回合中完成。同时，我们探讨了两种用于测试 H-freeness 的通用算法类型，并证明 DFS 和 BFS 测试程序无法在 k>4 的情况下在恒定数量的回合内测试 K_k-freeness 和 C_k-freeness。
property testingdistributed computingcongest modelgraph theoryalgorithm
发现论文，激发创造
  • 测试图的聚类能力：算法和下限

    本文提出了一种利用角度信息和奇异值分解的子线性时间图聚类算法，并在其基础上给出了测试聚类可行性的查询复杂度下界，并且通过这些技术，也实现了新的子线性时间下界近似最大割价值的问题。

    Aug, 2018

  • 测试图的聚类结构

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

    Apr, 2015

  • 广播 CONGEST 网络中确定性子图检测

    本文提出了一种对于分布式计算中的广播 CONGEST 模型进行子图查找和枚举的简单确定性算法，并且给出了性能上限及其紧密性的证明。

    May, 2017

  • 使用小子图概率关系测试网络结构

    研究使用小子图的观察频率之间的关系来测试网络结构的问题，证明了在 Erdős-Rényi 空模型下的 T2，T3 的中心极限定理，并分析了与一般类别的替代模型相关的 χ2 检验统计量的功率。

    Apr, 2017

  • 稀疏图的任何小闭性质都是可检测的

    研究了具有度数限制的图形，证明了其局部邻域统计与 “平面图” 不同，并由此推断出很多图形的特性和性质可以通过少量的查询进行测试。

    Jan, 2008

  • 非确定性图形属性测试

    该论文研究了在密集图中，基于节点的一元和 / 或二元关系的证书是否能够使图的有限属性进行非确定性和确定性测试。通过图限定理，证明了非确定性可测试属性也是确定性可测试的。

    Feb, 2012

  • 路径抽样：一种快速可证明的估计 4 元子图数量的方法

    本文介绍一种基于三路径采样和特殊剪枝技术的采样算法，可准确估算所有 4 个顶点模式子图的频率，并在容易实现和计算效率上优于传统枚举和采样算法。

    Nov, 2014

  • 利用小子图统计量测试全局网络结构

    使用小子图的观察频率之间的关系，提出了一种基于三节点子图频率的社区结构存在简单检验方法，该方法能够在网络引导模型的零假设下，显示出渐近正态的检验统计量，并在纠正度量复合备选假设下具有接近于一的功率，此外，该方法亦可用于多元高斯数据的检验，并应用于社交网络、科学文章的引用网络和标普 500 公司之间的股票回报率的检测。

    Oct, 2017

  • 有限查询图连接性测试

    提出了一种组合优化模型，可以在限定次数的查询下寻找图中两点的连通性，创新性地提出了一种较为可扩展的精确算法以及适用于大规模数据的启发式算法。

    Feb, 2023

  • 无钻石图的着色

    对于五个及以下顶点的所有图 H，我们分类了（钻石，H）- 免费图的颜色问题的计算复杂性。我们的技术是将问题图归约到一个非常特殊的 k - 部分图上，其特定分解使得（钻石，P1+2P2）- 免费图具有有界的团宽。我们还能够证明其他四个新的（H1，H2）- 免费图案例的团宽有界。

    Dec, 2015