Ollivier Ricci curvature for general graph Laplacians: Heat equation, Laplacian comparison, non-explosion and diameter bounds
Ollivier Ricci curvature for general graph Laplacians: Heat equation, Laplacian comparison, non-explosion and diameter bounds
复制标题
DOI：
10.1016/j.aim.2019.106759
复制
发表时间：
2017-12
影响因子：
1.7
通讯作者：
Florentin Münch;Radoslaw K. Wojciechowski
中科院分区：
文献类型：
--
作者：
Florentin Münch;Radoslaw K. Wojciechowski
有限集上的离散时间随机游走自然地通过一对一对应关系转换为离散拉普拉斯算子。通常，奥利维尔曲率是通过随机游走来研究的。我们首先将奥利维尔曲率的定义扩展到一般加权图，然后使用图拉普拉斯给出奥利维尔曲率的极其简单的表示。使用拉普拉斯算子作为连续时间马尔可夫链的生成器，我们将奥利维尔曲率与与连续时间随机游走密切相关的热方程联系起来。特别是，我们证明了奥利维尔曲率的下界相当于热方程解的一定的利普希茨衰减。这是 Renesse 和 Sturm 著名的 Ricci 曲率下界表征的离散模拟。我们通过拉普拉斯算子对奥利维曲率的表示使我们能够推导出拉普拉斯比较原理，通过该原理我们证明了非爆炸和改进的直径界限。
Discrete time random walks on a finite set naturally translate via a one-to-one correspondence to discrete Laplace operators. Typically, Ollivier curvature has been investigated via random walks. We first extend the definition of Ollivier curvature to general weighted graphs and then give a strikingly simple representation of Ollivier curvature using the graph Laplacian. Using the Laplacian as a generator of a continuous time Markov chain, we connect Ollivier curvature with the heat equation which is strongly related to continuous time random walks. In particular, we prove that a lower bound on the Ollivier curvature is equivalent to a certain Lipschitz decay of solutions to the heat equation. This is a discrete analogue to a celebrated Ricci curvature lower bound characterization by Renesse and Sturm. Our representation of Ollivier curvature via the Laplacian allows us to deduce a Laplacian comparison principle by which we prove non-explosion and improved diameter bounds.