Jun, 2012

在大型图形中查找最接近的截断通勤时间邻居的一种可解决方法

PDF
TL;DR通过加速随机游走算法计算截断通勤时间，不需要计算所有配对，本文在模拟和真实图表上进行了实验，结果显示计算时间近线性缩放。
graph-based learningrandom walkproximity measuresapproximate nearest neighborscomputation time
发现论文，激发创造
  • 利用随机游走算法在大型网络中计算社区（长版）

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

    Dec, 2005

  • 大型图中的命中和通勤时间经常是具有误导性的

    本文研究了大型随机图中击中时间和通勤距离的行为，证明了随着顶点数的增加，击中时间和通勤距离趋于某些表达式，这些表达式不考虑图的全局结构。在随机几何图和具有预期度数的随机图中得出的结论在击中和通勤时间等方面会导致误导性。

    Mar, 2010

  • 求解配对和列交通时间以及 Katz 分数的快速矩阵计算

    本研究利用数值线性代数方法，采用基于矩阵、矩估计和求积公式的方法，探讨了评估节点对之间的通勤时间和 Katz 得分的算法，并提出了一种从一个节点到图中所有其他节点的通勤时间和 Katz 得分近似估计方法。在 17 个真实图上的测试结果表明，所提出的算法在理论性能和实际效能上都有很好的表现。

    Apr, 2011

  • 使用随机游走的稀疏近似进行网络嵌入

    提出一种基于交通时间的网络嵌入的高效数值实现，使用扩散小波算法得到的网络上的扩散过程的稀疏逼近。通过随机梯度下降法，并对绿函数的低维表示进行采样，计算节点嵌入，并通过多个示例展示了该方法在数据聚类和多标签分类方面的有效性，并比较了其在效率和准确性方面相对于现有方法的性能。还讨论了理论问题来证明该方案的合理性。

    Aug, 2023

  • 网络中近似最近社区搜索

    本文针对社交网络和信息网络的社区搜索问题，提出了一种基于 k-truss 的算法模型，并采用贪心算法框架进行求解，最终实现了在时间效率和搜索准确度之间的平衡。

    May, 2015

  • 从随机游走到无权图上的距离

    本研究通过随机微积分分析了基于拉普拉斯变换的击中时间度量法，并将其与布朗运动上的击中时间对应，证明该方法在处理几何图的基础度量、保留聚类倾向以及抗随机添加非几何性边缘方面具有优越性。

    Nov, 2015

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

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

    Jan, 2024

  • 利用深度学习技术进行最短路径距离近似计算

    本文提出使用深度学习中的向量嵌入来近似计算大型网络的最短路径距离，结果表明，使用向量嵌入的前馈神经网络可以比较低的失真误差实现距离计算。该方法在 Facebook、BlogCatalog、Youtube 和 Flickr 等社交网络上进行了评估。

    Feb, 2020

  • 图元修正随机游走错过的拓扑信息

    通过引入轨道连接来捕捉所有拓扑邻域信息，我们提出了一个新的网络嵌入方法，与基于随机游走的方法相比，能够更好地预测节点标签，证明了包括随机游走无法捕捉到的拓扑邻域信息的重要性。

    May, 2024

  • 一个可简易处理的图距离家族

    本研究主要探讨了在度量空间中的对象，如最近邻搜索和聚类等重要数据挖掘问题，以及在图上聚类和分类等的应用。研究发现，虽然一些流行的大规模图距离量度并非度量空间，但可以定义一类包含多种距离度量且具有可计算性和可扩展性的图距离度量方法。此外，研究人员还探讨了如何将节点的属性信息融入度量中。

    Jan, 2018