As on arXiv
Abstract
On a connected finite graph, we propose an evolution of weights including Ollivier's Ricci flow as a special case. During the evolution process, on each edge, the speed of change of weight is exactly the difference between the Wasserstein distance related to two probability measures and certain graph distance. Here the probability measure may be chosen as an -lazy one-step random walk, an -lazy two-step random walk, or a general probability measure. Based on the ODE theory, we show that the initial value problem has a unique global solution. A discrete version of the above evolution is applied to the problem of community detection. Our algorithm is based on such a discrete evolution, where probability measures are chosen as -lazy one-step random walk and -lazy two-step random walk respectively. Note that the latter measure has not been used in previous works. Moreover, only one surgery needs to be performed after the last iteration, which makes our algorithm much simpler than earlier ones based on Lin-Lu-Yau's Ricci curvature.
Its neighbourhood
Connected papers
The 8 papers on this site closest to this one, judged by the topics they share, the words and phrases in their titles and abstracts, and their authors. They are not its citations, but a map of the work around it. Papers here go back to 2021, plus the canon.
-
A modified Ricci flow on arbitrary weighted graph
Topics Surgery, Discrete & graph Ricci, Long-time existence & convergence · Same authors Jicheng Ma, Yunyan Yang · Shared terms “community detection”, “Ollivier Ricci”, “algorithm”
-
Evolving edge weights via local entropy flow and cohesion flow on graphs
Topics Discrete & graph Ricci, Long-time existence & convergence · Same authors Jicheng Ma, Yunyan Yang · Shared terms “community detection”, “Ollivier Ricci”, “Yau Ricci”
-
Core detection via Ricci curvature flows on weighted graphs
Topics Discrete & graph Ricci · Same authors Jicheng Ma, Yunyan Yang · Shared terms “detection”, “algorithm”, “iteration”
-
Equivalence of Lin–Lu–Yau curvature and 1/2-Ollivier curvature on weighted graphs
Topics Discrete & graph Ricci, Long-time existence & convergence · Same author Yunyan Yang · Shared terms “Ollivier”, “Lin”, “Yau”
-
The existence of inversive distance circle packing on polyhedral surface
Topics Surgery, Discrete & graph Ricci
-
On the Ricci flow on Trees
Topics Discrete & graph Ricci · Shared terms “Ollivier Ricci”, “Lin”, “Yau”
-
The Ricci flow with prescribed curvature on graphs
Topics Discrete & graph Ricci, Long-time existence & convergence · Shared terms “finite graph”, “graph distance”, “Lin”
-
The Ollivier Ricci flow with prescribed curvature on infinite graphs
Topics Discrete & graph Ricci · Shared terms “Ollivier Ricci”, “Yau Ricci”, “Lin”
Read around it
Background reading
The guides for the topics of this paper: what each idea is, why it matters, and the papers to read first.
In the guidebook
- 11B.7Hamilton’s Program in 2002
What was proved, what was missing, and where Perelman came in.
- 12B.5The Canonical Neighbourhood Theorem
Every high-curvature point looks like a neck or a cap.
- 12B.7The Singular Time: Horns and Strong Necks
The limit metric at a singular time, the set Ω where curvature stays bounded, ε-horns and their ends, and strong δ-necks deep in a horn, following Perelman II §3 and Morgan–Tian chapter 11.