Apr, 2013

在近似线性时间内找到大小为 $\sqrt {N/e}$ 的隐藏团

PDF
TL;DR本文提出了一种新的算法，能在近线性时间内解决 Erdos-Renyi 随机图中的大小不小于 (1+eps) sqrt (N/e) 的 clique 识别问题，并在大环正则图的情况下通过 “local” 算法成功识别大小不小于 (1+eps) N/sqrt (eDelta) 的 clique。
erdos-renyi random graphclique identificationlinear time algorithmhidden clique problemlocal algorithms
发现论文，激发创造
  • 随机图上社区检测的计算下界

    研究检测大型 Erdős-Rényi 随机图中种植的小型密集社区的问题，并探究其计算复杂性及相变现象，结果可应用于恢复密集社区和逼近最密 $K$- 子图。

    Jun, 2014

  • 隐含圈与隐含子矩阵问题的改进平方和下界

    提出一种基于低阶半正定松弛和矩阵谱的方法，用于在特定条件下解决隐含团问题的下界证明。

    Feb, 2015

  • 检测植入团的统计算法和下限

    介绍了一个用于证明计算问题下界的框架，其中算法可使用对统计查询的访问来实现，并应用于检测种植的双部分图团分布中的统计查询算法的复杂性的近乎最优下界。

    Jan, 2012

  • 子线性时间下的谱聚类预测器

    本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法，该算法可以将图按照展开器分簇，并可以提高聚类的准确性，同时通过估计图中节点的随机游走的分布，实现对谱嵌入的点积访问，并使用谱嵌入进行超平面划分，从而实现聚类。

    Jan, 2021

  • Erdős-Rényi 图的谱统计 I: 本地半圆定律

    本文研究了 Erdős-Rényi 随机图的邻接矩阵集合，证明了该集合的密度满足长于 $N^{-1}$ 的谱窗口的 Wigner 半圆律，证明了所有特征向量均被证明是完全分散的。

    Mar, 2011

  • 近似扩张剖面和几乎最优局部图聚类

    本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

    Apr, 2012

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

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

    Apr, 2013

  • 从顶点邻居中挖掘具有质量保证的大型拟团

    本文探讨了通过扫描顶点邻域，计算每个顶点的聚类系数并输出最佳子图来提取大的准簇的简单方法，证明了现实世界图的两个重要特征意味着存在具有高边密度的大型顶点邻域。这种方法的实现需要对图中的三角形进行计数，这在图挖掘中是一个被深入研究的问题。经过实际测试，该方法揭示了一个惊人的事实：顶点邻域包括中等大小的极大团，而最佳邻域的密度往往比用于最大化子图密度的专用算法产生的子图优越。对于聚类系数较小的图，我们证明可以使用局部搜索方法来 “增长” 更大的团和准团。与最坏情况理论结果相反，从实际图中挖掘中等大小的团和准团通常不是一个困难问题，并且激励了进一步研究这些实证成功的更好解释。

    Aug, 2020

  • 带符号图的亚线性时间聚类神谕

    针对具有清晰社区结构的有符号图，我们提供了本地聚类算法，可以在只读取图形的一小部分的情况下，在亚线性时间中回答会员查询并正确分类节点。

    Jun, 2022

  • 子线性时间内的三角形约计数

    设计一种子线性时间算法以估算一个图中三角形的数量，使用度查询、顶点对查询和邻居查询作为对图的查询，并证明该算法的查询复杂度是最优的。

    Apr, 2015