Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation

曲率作为一种强有力的描述不变量，在图论中的理论和实践中得到了验证。我们采用了Ollivier提出的广义Ricci曲率的定义，后来Lin和Yau将其应用于图论中，称为Ollivier-Ricci曲率（ORC）。ORC使用Wasserstein距离来测量曲率，从而将几何概念与概率论和最优输运相结合。Jost和Liu先前通过展示Wasserstein距离的上界来讨论ORC的下界。我们将这些界的适用范围扩展到具有整数度量的离散空间，特别是超图。与Coupette、Dalleiger和Rieck在超图中关于ORC的先前工作面临的计算挑战相比，我们的方法引入了一种简化的方法，具有线性计算复杂度，特别适用于分析大规模网络。通过广泛的模拟和应用于合成和真实数据集，我们展示了我们的方法在评估ORC方面的显着改进。

论文旨在扩展Ollivier-Ricci曲率的适用范围，以便在超图等离散空间中进行评估。同时，解决了之前研究所面临的计算复杂度问题。

论文采用线性计算复杂度的简化方法，将Ollivier-Ricci曲率扩展到离散空间，特别是超图中。这种方法可以用于大规模网络的分析。

论文的方法在合成和真实数据集上进行了广泛的模拟和应用，并证明了在评估Ollivier-Ricci曲率方面的显着改进。同时，论文的方法具有开源代码和可重复性。

之前的研究中，Coupette, Dalleiger和Rieck尝试在超图中评估ORC，但面临计算复杂度的挑战。Jost和Liu讨论了ORC的下限，但没有扩展到离散空间。