On the sum of Ricci-curvatures for weighted graphs (Q2071458): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q124887998 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 2001.01776 / rank | |||
Normal rank |
Latest revision as of 01:33, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the sum of Ricci-curvatures for weighted graphs |
scientific article |
Statements
On the sum of Ricci-curvatures for weighted graphs (English)
0 references
28 January 2022
0 references
By this notion, positive curvature implies that the neighbors of the two centers are close or overlapping, negative curvature implies that the neighbors of two centers are further apart, and zero curvature or near zero curvature implies that the neighbors are locally embeddable in a flat surface. The Ollivier Ricci curvature provides a curvature of any two nodes and it depends on an idleness parameter of the random walk. A coupling function provides a lower bound for the transportation distance. In this article provided an upper bound for the transportation distance. For applications of Ricci curvature, the weighted graph models are more useful than the unweighted graphs models, as in the realworld networks, not all relation have the same capacity. Here, generalized Lin-Lu-Yau's Ricci curvature is applied to weighted graphs and given a simple limit-free definition. The authors establish two extremal results on the sum of Ricci curvatures for weighted graph. A weighted graph \( G =(V,E,d) \) is an undirected graph \( G =(V,E) \) associated with a distance function \( d: E\to [0,\infty) \). By redefining the weights if possible, without loss of generality, they are assuming that the shortest weighted distance between \(u\) and \(v\) is exactly \(d(u,v)\) for any edge \(uv\). Considering a random walk whose transition probability from an vertex \(u\) to its neighbor \(v\) (a jump move along the edge \(uv\)) is proportional to \(wuv := F(d(u,v))/d(u,v)\) for some given function \(F(\cdot)\), the authors first generalize the Lin-Lu-Yau's Ricci curvature definition to this weighted graph and given a simple limit-free representation of \(\kappa(x,y)\) using a so called \(*\)-coupling functions. The total curvature \(K(G)\) is defined to be the sum of Ricci curvatures over all edges of \(G\). Also proved are the following theorems: if \(F(\cdot)\) is a decreasing function, then \(K(G)\geq 2|V|-2|E|\); if \(F(\cdot)\) is an increasing function, then \(K(G)\leq 2|V|-2|E|\). Both equations hold if and only if \(d\) is a constant function and the girth is at least 6. In particular, these imply a Gauss-Bonnet theorem for (unweighted) graphs with girth at least 6, where the graph Ricci curvature is defined geometrically in terms of optimal transport. This is an interesting and interdisplinary nature paper useful to geometry and discrete structures researchers.
0 references
Ricci curvature
0 references
Riemannian geometry
0 references
Laplacian
0 references
graphs
0 references
random walk
0 references
transportation distance
0 references