Apr, 2011

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

PDF
TL;DR本研究利用数值线性代数方法，采用基于矩阵、矩估计和求积公式的方法，探讨了评估节点对之间的通勤时间和 Katz 得分的算法，并提出了一种从一个节点到图中所有其他节点的通勤时间和 Katz 得分近似估计方法。在 17 个真实图上的测试结果表明，所提出的算法在理论性能和实际效能上都有很好的表现。
发现论文，激发创造
  • 在大型图形中查找最接近的截断通勤时间邻居的一种可解决方法

    通过加速随机游走算法计算截断通勤时间，不需要计算所有配对，本文在模拟和真实图表上进行了实验，结果显示计算时间近线性缩放。

    Jun, 2012

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

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

    Mar, 2010

  • 图顶点之间的相似度度量

    该研究介绍了一种相似度概念和其在有向图中的运用，并指出其可用于自动提取单语言词典中的同义词。

    Jul, 2004

  • 压缩矩阵乘法

    介绍一种利用哈希函数、多项式乘法和误差纠正编码的简单算法来近似计算两个实数矩阵的乘积、计算精确的乘积矩阵，并可以以近线性时间内恢复其显著项。

    Aug, 2011

  • 个性化 PageRank 的高效算法

    本文介绍了一种新的双向算法来估计随机游走得分，其中结合了更高效的 Monte Carlo 和线性代数方法，使速度提高了 70 倍以上，可以用于社交网络、用户 - 项目网络和网页等网络上的个性化搜索和推荐。此外，文章还提出了其他相关算法，可用于无向图、任意步长和马尔可夫链、个性化搜索排名和从给定源到给定目标集的随机路径抽样。

    Dec, 2015

  • 统计排名与组合霍奇理论

    使用图 Helmholtzian 和组合 Hodge 理论，基于边缘流的成对排名可以解析为两个正交成分，其中一个表示 L2 最优全局排名，而另一个表示无旋转流，同时还可以通过线性最小二乘回归计算离散的 Hodge 分解。

    Nov, 2008

  • 普通图和局部图的成对比较排名

    本文关注 Bradley-Terry-Luce 模型中的成对比较问题，并通过对图论的分析，提出了能够在有限条件下对排名进行准确估计的算法，并在大规模实验中证实了该算法的可行性。

    Apr, 2023

  • 图上矩阵补全

    本文提出了一种基于社区检测和流形学习的矩阵完成模型，通过约束矩阵在图上的平滑性来隐含地强制行和列之间的相似性，得到了比标准模型更好的矩阵恢复效果。

    Aug, 2014

  • 文本相似度矩阵的次线性时间近似

    本篇研究文章探讨通过推荐算法，计算相似矩阵的问题，介绍了基于 Nyström 方法的一种新的推荐算法，此算法可以以亚线性时间的复杂度对任何相似矩阵进行求解，在 NLP 的不同应用场景中展示出高精确度的表现。

    Dec, 2021

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

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

    Aug, 2023