May, 2016

大规模图中奇异子结构的快速准确挖掘：摇摆随机游走

PDF
TL;DR本文提出了一种新的算法 Waddling Random Walk（WRW），用于估计任意大小的图相对浓度，并通过在可访问的节点路径上进行随机游走来采样子图以提高计算效率、精度与准确性。通过使用广泛使用的图形数据集，该算法在速度、精度和准确性方面都优于当前最先进的挖掘子图统计算法。
graph miningnetwork motifsrandom walkscomputational efficiencyaccuracy
发现论文，激发创造
  • 高效估计大型网络的基序统计量

    本文提出了一种基于抽样的算法，有效地从大规模网络中准确估算子图统计量，并展示实验结果表明其能更加快速地完成与现行技术相同准确度的查询量（样本量）

    Jun, 2013

  • 通过随机游走估算图形统计量的通用框架

    本文提出了一种基于随机游走的框架，通过优化技术和收集样本来估算任何规模的图形统计数据，并取得了在准确性和时间成本方面都优于现有技术的效果。

    Mar, 2016

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

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

    Feb, 2018

  • 利用随机游走算法在大型网络中计算社区（长版）

    本篇研究提出了一种基于随机游走的顶点相似度度量，使用该度量可以高效地计算网络的社区结构，并提出了一种名为 Walktrap 的聚合算法，该算法提高了社区结构计算的准确性。经过全面的比较测试，表明该算法在质量和运行时间方面都优于以前提出的算法。

    Dec, 2005

  • 多网络随机游走

    本文提出了一种基于多网络的随机游走算法 RWM，可用于网络嵌入、链路预测和局部社区检测，试验证明其在合成和真实数据集上的有效性和高效性。

    Jul, 2023

  • 受挫随机漫步：一种在超图上计算节点距离的快速方法

    我们提出了一种基于随机游走的新方法，用于超图上的标签传播，其中我们将节点距离估计为随机游走的预期命中时间，并引入了困惑随机游走来更好地描述高度复杂的实际超图。我们还将我们的方法与 DeepWalk 进行了基准测试，结果显示在目标数量较小的情况下，FRW 在运行时间上具有明显的计算优势。最后，我们分析了我们方法的时间复杂度，并表明对于大型稀疏的超图，复杂度近似为线性，优于 DeepWalk 的替代方案。

    Jan, 2024

  • 通用图随机特征

    我们提出了一种新的准蒙特卡洛机制，用于改进基于图的采样，称为斥力随机游走。通过在相互作用的集合中引入轨迹之间的相关性，使其边际转移概率不变，我们能够更高效地探索图，并提高统计估计量的集中度，同时保持其无偏性。该机制具有简单易用的实现方法。我们展示了斥力随机游走在估计图核、PageRank 向量和图图案集中度等各种环境中的有效性，并提供了详细的实验评估和稳健的理论保证。据我们所知，斥力随机游走是第一个对图上行走者的方向进行严格研究的准蒙特卡洛方案，在这个令人兴奋的初创领域中引发了新的研究。

    Oct, 2023

  • 多维随机游走估计和采样图

    本文提出一种新的 $m$- 维随机游走采样方法，称为前沿采样，该方法在大规模实际网络图中表现出更低的估计误差，并且比随机顶点采样更适合采样图的度数分布尾部。

    Feb, 2010

  • 基于图的表示学习方法泛化框架

    本论文介绍了带标记的随机游走的概念，以此为基础对现有的一些利用随机游走的算法如 DeepWalk、node2vec 等进行了推广，可适用于传导学习、归纳学习以及具备属性的图形数据，并在多个领域的各种图形上验证了该算法的有效性。

    Sep, 2017

  • 一般图上的自我排斥随机游走 - 通过非线性马尔可夫链实现最小采样方差

    通过自反随机游走（SRRW）设计的随机游走者，结合采样和邻域探索的马尔可夫链蒙特卡罗（MCMC）过程，近似目标分布，并在一定程度上提高采样方差

    May, 2023