Sep, 2018

挖掘演化图中的频繁模式

PDF
TL;DR本文研究了具有标签的图中的频繁子图挖掘问题，提出了适用于增量和完全动态流设置的算法，以提取给定阈值下的高质量近似频繁 $k$- 顶点子图，通过保持一个均匀采样 $k$- 顶点子图组，并优化围绕更新的邻域探索过程，以及理论分析的支持，我们证明了所提出的算法相对于现有的最先进的解决方案可以产生高质量的结果。
frequent-subgraph miningevolving graphstreaming$k$-vertex subgraphsapproximation
发现论文，激发创造
  • 频繁子图挖掘的表示学习

    通过组合图神经网络、顺序嵌入空间和高效搜索策略，Subgraph Pattern Miner (SPMiner) 实现了在大型目标图中近似查找频繁子图模式，并相较于现有方法和可能的神经替代方案具有更高准确性、更快速度和更好的可扩展性。

    Feb, 2024

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

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

    Nov, 2014

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

    本研究针对图挖掘应用中的稠密子图问题，提出了一种动态算法，能够同时实现时间和空间效率，它是首个通过一遍流处理即可维护最稠密子图的算法。

    Apr, 2015

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

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

    Jan, 2012

  • 利用差分隐私挖掘频繁图模式

    本文提出了一种用于挖掘频繁图模式的不同隐私算法，并基于 Markov Chain Monte Carlo 采样方法解决了挖掘频繁图模式的难题，同时保证了隐私和效用保障。

    Jan, 2013

  • 使用图采样计算模体数量

    本文从统计学角度研究了网络采样和子图统计中的几个问题，提出了一些估算方法，并给出了理论与实验结果。

    Feb, 2018

  • 动态网络中的自适应社群搜索

    本文研究了在时态动态网络中进行社区搜索的问题，定义了最小时态不效率子图问题和最短最快路径距离，并利用最小定向斯坦纳树的逼近算法，将时态网络转换为静态定向加权图，最后将该框架推广到流式情景。

    Nov, 2020

  • 多重测试校正下的重要子图挖掘

    通过对八个流行图形基准数据集进行实证调查，本文回答了一个开放性问题，即排除无法测试的假设是否也会提高子图挖掘的统计功率，并提出了一种新的高效搜索策略，极大地提高了统计功率。

    Jul, 2014

  • 少样本重采样高效发现显著模式

    FSR 算法通过使用少量重采样数据集来识别统计显著模式，并在发现显著模式时提供严格的假阳性概率保证。

    Jun, 2024

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

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

    Jun, 2019