关于图上的离散Ricci曲率意义的思考

灵魂拷问

• 曲率是什么？正曲率、零曲率、负曲率各自代表什么意义(几何、物理)？能给我们什么启发？
• 高维空间中的曲率如何定义？
• 黎曼流形中的Ricci曲率与流形的性质有什么关联？
• 图和流形有什么联系？
• 为什么要将流形上的曲率迁移到图/网络上？
• 有多少种离散化的Ricci曲率？不同的离散化含义相同吗？离散化的策略会不会存在什么问题？
• Olliver Ricci曲率的定义是有意义的吗？
• 图上的Ricci曲率与图的性质有什么关联？
• Ricci曲率与网络演化有关联吗？

高维连续空间下的曲率

Ricci曲率

黎曼几何中度量流形在局部偏离于欧式空间的程度。

离散Ricci曲率

Ollivier-Ricci曲率

Ollivier-Ricci曲率是基于最优传输理论定义的。最优传输的问题最早由G.Monge提出，该问题可以形象地表述为：求解将某地点的一堆沙子搬运到另一地点并使沙堆具备特定形状所需要的最小工作量（可以是总搬运距离或者是时间开销等）对应的搬运方案。若将上例中的沙堆视作概率分布，将搬运沙堆的过程视作概率分布间的变换，则最优传输方案所对应的“最小工作量”相当于概率分布间的距离，最优传输问题可以形式化地表示为：给定源概率分布空间X和目标概率分布空间Y，从X中位置x传输单位质量到分布Y中位置y的成本为，求解一个概率分布变换$T:X\rightarrow Y$,使得概率分布通过传输变换到另一个概率分布的成本最小。

Forman-Ricci曲率

基于CW复形定义。

参考资料

相关讨论

关于曲率的解释

• 如何简明地解释曲率（curvature）？
• What’s the difference between positive curvature and negative curvature in Physics?

相关教材

黎曼几何

• Riemannian Geometry and Geometric Analysis

最优传输

• Computational Optimal Transport
• Optimal transport, old and new
• Optimal transport for applied mathematicians
• Sinkhorn distances: Lightspeed computation of optimal transport
• ……

Sinkhorn distances: Lightspeed computation of optimal transport

相关论文

Ricci曲率

曲率定义、数学性质分析、几何意义

• Over-squashing, Bottlenecks, and Graph Ricci curvature
• Ollivier’s Ricci Curvature, Local Clustering and Curvature-Dimension Inequalities on Graphs
• Comparative analysis of two discretizations of Ricci curvature for complex networks
• Ricci curvature, graphs and eigenvalues
• Ricci curvature of Markov chains on metric spaces
• Bochner’s Method for Cell Complexes and Combinatorial Ricci Curvature
• CONDENSED RICCI CURVATURE OF COMPLETE AND STRONGLY REGULAR GRAPHS
• Volume and diameter of a graph and Ollivier’s Ricci curvature
• OLLIVIER–RICCI CURVATURE AND THE SPECTRUM OF THE NORMALIZED GRAPH LAPLACE OPERATOR
• OLLIVIER-RICCI CURVATURE AND THE SPECTRUM OF THENORMALIZED GRAPH LAPLACE OPERATOR
• DISCRETE OLLIVIER-RICCI CURVATURE

曲率与网络分析

基于曲率“度量”丰富模式识别、数据挖掘的算法

• Discrete curvatures and network analysis
• Characterizing complex networks with Forman-Ricci curvature and associated geometric flows
• Forman curvature for complex networks
• [Forman curvature for directed networks]((PDF) Forman curvature for directed networks)
• Exact and asymptotic results on coarse Ricci curvature of graphs
• ……

Ollivier Ricci曲率应用案例

• Applying Ollivier-Ricci curvature to indicate the mismatch of travel demand and supply in urban transit network

• Using discrete Ricci curvatures to infer COVID-19 epidemic network fragility and systemic risk

• Interference constrained network control based on curvature

• Wireless network capacity versus Ollivier-Ricci curvature under Heat-Diffusion (HD) protocol | IEEE Conference Publication | IEEE Xplore

  通过曲率识别无线网络中的拥塞现象

• Ricci curvature of the internet topology

  分析因特网中的Ollivier-Ricci曲率分布特性及其与经典指标表的联系

• Network alignment by discrete Ollivier-Ricci flow

  通过里奇流进行图匹配

• Community Detection on Networks with Ricci Flow

  通过Ricci流进行社区分割

• ……

Forman Ricci曲率应用案例

• image processing

复杂网络

边指标

• Measuring tie strength
• Romantic partnerships and the dispersion of social ties: a network analysis of relationship status on Facebook

工具包

• Tutorial: GraphRicciCurvature
• SageMath