Apr, 2015

一种高效的空间和时间复杂度算法：在一遍动态流上维护稠密子图

PDF
TL;DR本研究针对图挖掘应用中的稠密子图问题，提出了一种动态算法，能够同时实现时间和空间效率，它是首个通过一遍流处理即可维护最稠密子图的算法。
发现论文，激发创造
  • 动态图数据流中的密度最大子图

    本文提出了一种单遍算法，在动态图流模型下使用少量的空间和多项式时间精确地找到图中最大密度的 $(1+\epsilon)$ 近似值，进一步对算法的最小空间使用量进行了界定。

    Jun, 2015

  • 流处理和 MapReduce 中的最密子图

    本文提出了针对流模型的新算法，用于发现图的局部密集组件，该算法在经过 O ((log n)/log (1+epsilon)) 次输入后，可以找到一个子图，其密度保证是最优解的 2 (1+epsilon) 倍。

    Jan, 2012

  • 实时故事识别中基于流边权重更新的密集子图维护

    本文研究了如何有效处理海量社交媒体数据，提出了 DYNDENS 算法，能够及时识别新兴的、备受关注的事件，这在真实场景中具有实际应用价值。

    Mar, 2012

  • 寻找密集子图的本地算法

    本文提出一种用于寻找二分图中密集子图的本地算法，通过 Kannan 和 Vinay 提出的密度定义来衡量，在最多 O (Dk^2) 个顶点上，在密度 theta / O (log n) 的情况下找到最接近指定起始点的密集子图，算法的时间复杂度为 O (Dk^2)，与图中的顶点数无关。

    Feb, 2007

  • 高密度子图发现的高效算法

    本文提出了一种新的解决模式来找到具有最高密度的图 G 的亚图 D，并通过 k-core 的方法开发了一些有效的解决方案来寻找包括基于团和一般模式定义密度的各种图的最密亚图，实验结果表明该算法比现有方法快四个数量级。

    Jun, 2019

  • 探测高密度日志 -- 密度最大的 k - 子图的 O (n^1/4) 近似算法

    本文提出了一种算法，可以在时间 n^O (log n) 内，在 n^(1/4+epsilon) 的近似比内近似求解密度最大 k - 子图问题，该算法源于研究图的平均情况，其关键思想在于计数常数大小的树并使用这些计数来识别密集子图的节点。

    Jan, 2010

  • 滑动窗口上的次模优化

    本文在数据流的上下文中，提供了一种基于滑动窗口模型的次模优化的近似算法，该算法维护了一个解决方案，考虑的仅是最后 $W$ 个元素，使用空间多项式对元素值的传播速度的对数级别，线性大小的解决方案，并保持高品质的解，实际表现远超理论界限。

    Oct, 2016

  • 动态流中的单遍谱稀疏化

    我们提出了一种动态半流模型下用于计算图形谱稀疏化的首个单趟算法，该算法使用线性素描将 G 的入射矩阵维护为 O ((1/epsilon^2) n*.polylog (n)) 维，可以输出高概率下 G 的 (1+/-epsilon) 谱稀疏化。该方法利用了 G 的粗略稀疏器和 G 的入射矩阵的线性素描，通过等效电阻抽样边缘以得到任意精度的谱稀疏化。

    Jul, 2014

  • 稠密子图问题及其变体的综述

    本文对最密子图问题进行了全面的调查和概述，涵盖了多种变体和应用，并重点介绍了最近的成果和开放问题。

    Mar, 2023

  • 亚线性时更新的动态相关聚类

    在动态节点流中，我们研究了相关聚类的经典问题。我们提出了一种算法，通过维护 $O (1)$ 的逼近精度和 $O$(polylog $n$) 的摊销更新时间，不断寻找最小化穿越簇的正边和簇内负边之和的分区。最后，我们用实际数据实验证明了我们的理论分析。

    Jun, 2024