Abstract
In this paper, we explore the relationship between one of the most elementary and important properties of graphs, the presence and relative frequency of triangles, and a combinatorial notion of Ricci curvature. We employ a definition of generalized Ricci curvature proposed by Ollivier in a general framework of Markov processes and metric spaces and applied in graph theory by Lin–Yau. In analogy with curvature notions in Riemannian geometry, we interpret this Ricci curvature as a control on the amount of overlap between neighborhoods of two neighboring vertices. It is therefore naturally related to the presence of triangles containing those vertices, or more precisely, the local clustering coefficient, that is, the relative proportion of connected neighbors among all the neighbors of a vertex. This suggests to derive lower Ricci curvature bounds on graphs in terms of such local clustering coefficients. We also study curvature-dimension inequalities on graphs, building upon previous work of several authors.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
When one studies empirical graphs, one of the most obvious and basic properties to investigate is the presence and number of triangles, that is, connected triples of vertices. In bipartite graphs, for instance, there are no triangles, whereas in a complete graph, every triple of vertices constitutes a triangle. A basic observation then is that when two neighboring vertices are contained in a triangle, their neighborhoods of radius 1 (let us assign to every edge the length 1 for the discussion in this introduction) share the third vertex of the triangle. That is, the more triangles those two neighboring vertices are contained in, the larger the overlap of their neighborhoods. This suggests an analogy with the notion of Ricci curvature in Riemannian geometry where a lower bound on the Ricci curvature also controls the amount of overlaps of distance balls from below. This is what we are going to explore in a quantitative manner in this paper.
In fact, Ricci curvature is a fundamental concept in Riemannian geometry, see e.g. [18]. It is a quantity computed from second derivatives of the metric tensor. It controls how fast geodesics starting at the same point diverge on average. Equivalently, it controls how fast the volume of distance balls grows as a function of the radius. As already indicated, it also controls the amount of overlap of two distance balls in terms of their radii and the distance between their centers. In fact, such lower bounds follow from a lower bound on the Ricci curvature. It was then natural to look for generalizations of such phenomena on metric spaces more general than Riemannian manifolds. That is, the question to find substitutes for the lower bounds on the above mentioned second derivative combinations of the metric tensor that yield the same geometric control on a general metric space. By now, there exist several insightful definitions of synthetic Ricci curvature on general metric measure spaces, see Sturm [29, 30], Lott–Villani [22], Ohta [23], Ollivier [24] etc.
As indicated, in this paper, we want to explore the implications of such ideas in graph theory. The geometric idea is that a lower Ricci curvature bound prevents geodesics from diverging too fast and balls from growing too fast in volume. On a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. Therefore, it is natural that the Ricci curvature on a graph should be related to the relative abundance of triangles. The latter is captured by the local clustering coefficient introduced by Watts–Strogatz [33]. Thus, the intuition of Ricci curvature on a graph should play with the relative frequency of triangles a vertex shares with its neighbors. In fact, more precisely, since the local clustering coefficient averages over the neighbors of a vertex, this should really related to some notion of scalar curvature, as an average of Ricci curvatures in different directions, that is, for different neighbors of a given vertex.
Among the several definitions of generalized Ricci curvature in the literature mentioned above, the one of Ollivier works particularly well on discrete spaces like graphs. It is formulated in terms of the transportation distance between local measures:
where x,y are vertices in our graph that are neighbors (written as x∼y) and the measure \(m_{x}=\frac{1}{d_{x}}\), where d x is the degree of x, puts equal weight on all neighbors. W 1(m x ,m y ) is the transportation distance between the two measures m x and m y (defined more precisely below). When two balls strongly overlap, as is the case in Riemannian geometry when the Ricci curvature has a large lower bound, then it is easier to transport the mass of one to the other. Analogously, in the graph case, when the two vertices share many triangles, then the transportation distance should be smaller, and the curvature therefore correspondingly larger. This is the idea of Ollivier’s definition as we see it and explore in this paper. We shall obtain both upper and lower bounds for Ollivier’s Ricci curvature on graphs in Sect. 3, which are optimal on many graphs.
Let us now formulate our main result (recalled and proved below as Theorem 3).
Theorem 1
On a locally finite graph, we put for any pair of neighboring vertices x,y,
We then have
where s +:=max(s,0),s∨t:=max(s,t),s∧t:=min(s,t).
This equality is sharp for instance for a complete graph of n vertices where the left and the right hand side both equal to \(\frac{n-2}{n-1}\).
The local clustering coefficient introduced by Watts–Strogatz [33] is
which measures the extent to which neighbors of x are directly connected, i.e.,
Thus, this local clustering coefficient is an average over the ♯(x,y) for the neighbors of x. Thus, we might also introduce some kind of scalar curvature (suggested in Problem Q in Ollivier [25]) as
For illustration, let us consider the case where our graph is d-regular, that is, d z =d for all vertices z. When \(1\ge\frac{2}{d}+\frac{\sharp(x,y)}{d}\) for all y∼x, we would then get
This example nicely illustrates the relation between Ollivier’s curvature and the Watts–Strogatz clustering coefficient.
Without the triangle terms ♯(x,y) (which is the crucial term for our purposes), Theorem 1 is due to Lin–Yau [19, 21], and we take their proof as our starting point. Lin–Yau also obtain analogues of Bochner type inequalities and eigenvalue estimates as known from Riemannian geometry.
In Riemannian geometry, the Bochner formula encodes deep analytic properties of Ricci curvature. It is a key ingredient in proving many results, e.g. the spectral gap of the Laplace–Beltrami operator. A lower bound of the Ricci curvature implies a curvature-dimension inequality involving the Laplace–Beltrami operator through the Bochner formula. In an important work, Bakry and Émery [2, 3] generalize this inequality to generators of Markov semigroups, which works on measure spaces. Their inequality contains plentiful information and implies a lot of functional inequalities including spectral gap inequalities, Sobolev inequalities, and logarithmic Sobolev inequalities and many celebrated geometric theorems (see [1] and the references therein). Lin–Yau [21] study such inequalities on locally finite graphs.
In the present paper, we also want to find relations on locally finite graphs between Ollivier’s Ricci curvature and Bakry–Émery’s curvature-dimension inequalities, which represent the geometric and analytic aspects of graphs, respectively. Again, this is inspired by Riemannian geometry where one may attach a Brownian motion with a drift to a Riemannian metric [24]. We also mention that the definitions given by Sturm and Lott–Villani are also consistent with that of Bakry–Émery [22, 29, 30]. So exploring the relations on nonsmooth spaces may provide a good point of view to connect Ollivier’s definition to Sturm and Lott–Villani’s (in this respect, see also Ollivier–Villani [26]). In Sect. 4, we use the local clustering coefficient again to establish more precise curvature-dimension inequalities than those of Lin–Yau [21]. And with this in hand, we prove curvature-dimension inequalities under the condition that Ollivier’s Ricci curvature of the graph is positive.
Further analytical results following from curvature-dimension inequalities on finite graphs have been described in [19], and Lin–Lu–Yau [20] study a modified definition of Ollivier’s Ricci curvature on graphs. Recently, Paeng [27] studied upper bounds for the diameter and volume of finite simple graphs in terms of Ollivier’s Ricci curvature. For other works of synthetic Ricci curvatures on discrete spaces, see Dodziuk–Karp [14], Chung–Yau [9], Bonciocat–Sturm [7], and on cell complexes see Forman [17], Stone [28] etc.
We point out that, as in Riemannian geometry, both Ollivier’s Ricci curvature and Bakry–Émery’s curvature-dimension inequality can give lower bound estimates of the first eigenvalue λ 1 for the Laplace operator (see Ollivier [24], Bakry [1]). Therefore our results in fact relate λ 1 to the Watts–Strogatz local clustering coefficient, or the number of cycles with length 3. In [10], Diaconis and Stroock obtain several geometric bounds for eigenvalues of graphs, one of which is related to the number of odd length cycles. For more geometric quantities and methods concerning eigenvalue estimates in the study of Markov chains, see [11–13] and the references therein. We further explore the interaction between Ollivier’s Ricci curvature and eigenvalues estimates in joint work with Frank Bauer, see [6].
In this paper, G=(V,E) will denote an undirected connected simple graph without loops, where V is the set of vertices and E is the set of edges. V could be an infinite set. But we require that G is locally finite, i.e., for every x∈V, the number of edges connected to x is finite. For simplicity and in order to see more geometry, we mainly work on unweighted graphs. But we will also derive similar results on weighted graphs. In that case, we denote by w xy the weight associated to x,y∈V, where x∼y (we may simply put w xy =0 if x and y are not neighbors, to simplify the notation). The unweighted case corresponds to w xy =1 whenever x∼y. The degree of x∈V is d x =∑ y,y∼x w xy .
2 Ollivier’s Ricci Curvature and Bakry–Émery’s Calculus
In this section, we present some basic facts about Ollivier’s Ricci curvature and Bakry–Emery’s Γ 2 calculus, in particular on graphs.
2.1 Ollivier’s Ricci Curvature
Ollivier’s Ricci curvature works on a general metric space (X,d), on which we attach to each point x∈X a probability measure m x (⋅). We denote this structure by (X,d,m).
For a locally finite graph G=(V,E), we define the metric d as follows. For neighbors x,y, d(x,y)=1. For general distinct vertices x,y, d(x,y) is the length of the shortest path connecting x and y, i.e. the number of edges of the path. We attach to each vertices x∈V a probability measure
An intuitive illustration of this is a random walker that sits at x and then chooses amongst the neighbors of x with equal probability \(\frac{1}{d_{x}}\).
Definition 1
(Ollivier)
On (X,d,m), for any two distinct points x,y∈X, the (Ollivier–) Ricci curvature of (X,d,m) along (xy) is defined as
Here, W 1(m x ,m y ) is the optimal transportation distance between the two probability measures m x and m y , defined as follows (cf. Villani [31, 32], Evans [16]).
Definition 2
For two probability measures μ 1, μ 2 on a metric space (X,d), the transportation distance between them is defined as
where ∏(μ 1,μ 2) is the set of probability measures on X×X projecting to μ 1 and μ 2.
In other words, ξ satisfies
Remark 1
Intuitively, this distance measures the optimal cost to move one pile of sand to another one with the same mass. For case of a graph G=(G,d,m), the supports of m x and m y are finite discrete sets, and thus, ξ is just a matrix with terms ξ(x′,y′) representing the mass moving from x′∈support of m x to y′∈support of m y . That is, in this case,
where the infimum is taken over all matrices ξ which satisfy
We also call ξ a transfer plan. If we can find a particular transfer plan, we then get an upper bound for W 1 and therefore a lower bound for κ.
A very important property of transportation distance is the Kantorovich duality (see, e.g. Theorem 1.14 in Villani [31]). We state it here in our particular graph setting.
Proposition 1
(Kantorovich Duality)
where the supremum is taken over all functions on G that satisfy
for any x,y∈V, x≠y.
From this property, a good choice of a 1-Lipschitz function f will yield a lower bound for W 1 and therefore an upper bound for κ.
Remark 2
We list some basic first observations about this curvature concept (see Ollivier [24]):
-
κ(x,y)≤1.
-
Rewriting (2.2) gives W 1(m x ,m y )=d(x,y)(1−κ(x,y)), which is analogous to the expansion in the Riemannian case.
-
A lower bound κ(x,y)≥k for any x,y∈X implies
$$ W_1(m_x, m_y)\leq(1-k)d(x,y), $$(2.4)which can be seen as some kind of Lipschitz continuity of measures.
2.2 Bakry–Émery’s Curvature-Dimension Inequality
2.2.1 Laplace Operator
We will study the following operator which is an analogue of the Laplace–Beltrami operator in Riemannian geometry.
Definition 3
The Laplace operator on (X,d,m) is defined as follows:
For our choice of {m x (⋅)}, this is the graph Laplacian studied by many authors, see e.g. [4, 5, 8, 14, 21].
2.2.2 Bochner Formula and Curvature-Dimension Inequality
In the Riemannian case, many analytical consequences of a lower bound of the Ricci curvature are obtained through the well-known Bochner formula,
Analytically, \(|\operatorname{Hess} f|^{2}\) is difficult to define on a nonsmooth space. But using Schwarz’s inequality, we have
where m is the dimension constant. So we can use
to characterize \(\operatorname{Ric} \geq K\).
Bakry–Émery [1–3] take this inequality as the starting point and directly use the operators to define curvature bounds. Starting from an operator Δ, they define iteratively,
In fact, Γ(f,f) is an analogue of |∇f|2, and Γ 2(f,f) is an analogue of \(\frac{1}{2}\Delta|\nabla f|^{2}-\langle\nabla (\Delta f), \nabla f\rangle\) in (2.6).
Definition 4
We say an operator Δ satisfies a curvature-dimension inequality \(\operatorname{CD}(m, K) \) if for all functions f in the domain of the operator
where m∈[1,+∞] is the dimension parameter, K(x) is the curvature function.
As studied in Lin–Yau [21], applying this construction to the operator (2.5) gives
In fact generally
For the sake of convenience, we will denote
By the calculation in Lin–Yau [21] we get
and then,
3 Ollivier’s Ricci Curvature and Triangles
In this section, we mainly prove lower bounds for Ollivier’s Ricci curvauture on locally finite graphs. In particular we shall explore the implication between lower bounds of the curvature and the number of triangles including neighboring vertices; the latter is encoded in the local clustering coefficient. We remark that we only need to bound κ(x,y) from below for neighboring x,y, since by the triangle inequality of W 1, this will also be a lower bound for κ(x,y) of any pair of x,y. (See Proposition 19 in Ollivier [24].)
3.1 Unweighted Graphs
In this subsection, we only consider unweighted graphs.
In Lin–Yau [21], they prove a lower bound of Ollivier’s Ricci curvature on locally finite graphs G. Here, for later purposes, we include the case where G may have vertices of degree 1 and get the following modified result.
Theorem 2
On a locally finite graph G=(V,E), we have for any pair of neighboring vertices x,y,
Remark 3
Notice that if d x =1, then we can calculate κ(x,y)=0 exactly. So, even though in this case \(-2+\frac{2}{d_{x}}=0\), \(\kappa(x, y)\geq\frac{2}{d_{y}}\) does not hold.
For completeness, we state the proof of Theorem 2 here. It is essentially the one in Lin–Yau [21] with a small modification.
Proof of Theorem 2
Since d(x,y)=1 for x∼y, we have
Using Kantorovich duality, we get
Inserting the above estimate into (3.1) gives
□
Note that trees attain this lower bound. This coincides with the geometric intuition of curvature. Since trees have the fastest volume growth rate, it is plausible that they have the smallest curvature.
Proposition 2
We consider a tree T=(V,E). Then for any neighboring x,y, we have
Proof
In fact with Theorem 2 in hand, we only need to prove that \(1+2 (1-\frac{1}{d_{x}}-\frac{1}{d_{y}} )_{+}\) is also a lower bound of W 1. If one of x,y is a vertex of degree 1, say d x =1, it is obvious that W 1(m x ,m y )=1. So we only need to deal with the case \(1-\frac{1}{d_{x}}-\frac{1}{d_{y}}\geq0\).
We can find a 1-Lipschitz function f on a tree as follows.
Since on a tree, the path joining two vertices are unique, there is no further path between neighbors of x and y. So this can be easily extended to a 1-Lipschitz function on the whole graph. Then by Kantorovich duality, we have
This completes the proof. □
In order to make clear the geometric meaning of the term \((1-\frac{1}{d_{x}}-\frac{1}{d_{y}} )_{+}\), and also to prepare the idea used in the next theorem, we give another method to get the upper bound of W 1. That works through a particular transfer plan. If
then for m y , the mass at all z such that z∼y, z≠x is larger than that of m x at y. So we can move the mass \(\frac {1}{d_{x}}\) at y to z, z∼y, z≠x for distance 1. Symmetrically, we can move a mass of \(\frac{1}{d_{y}}\) at the vertices z which satisfy z∼x, z≠y to x for distance 1. The remaining mass of \((1-\frac{1}{d_{x}}-\frac{1}{d_{y}} )\) needs to be moved for distance 3. This gives
If
we only need to move the mass of m x for distance 1 to the support of m y . So we have in this case W 1(m x ,m y )=1. This gives the same upper bound as in (3.2).
From the view of transfer plans, the existence of triangles including neighboring vertices would save a lot of transport costs and therefore affect the curvature heavily. We denote for x∼y,
Remark 4
This quantity ♯(x,y) is related to the local clustering coefficient introduced by Watts–Strogatz [33],
which measures the extent to which neighbors of x are directly connected. In fact, we have the relation
We will explore the relation between the curvature κ(x,y) and the number of triangles ♯(x,y). A critical observation is that κ(x,y) is symmetric w.r.t. x and y. So we try to express the curvature through symmetric quantities:
Theorem 3
On a locally finite graph G=(V,E), we have for any pair of neighboring vertices x,y,
Moreover, this inequality is sharp for certain graphs.
Remark 5
If ♯(x,y)=0, then this lower bound reduces to the one in Theorem 2.
Example 1
On a complete graph \(\mathcal{K}_{n}\) (n≥2) with n vertices, ♯(x,y)=n−2 for any x,y. So Theorem 3 implies
In fact, we can easily check that the above inequality is an equality. Also notice that on those graphs, the local clustering coefficient c(x)=1 attains the largest value.
Before carrying out the proof of Theorem 3, we fix some notations. The vertices z that are adjacent to x or y, where x∼y, are divided into three classes.
-
common neighbors of x,y: z∼x and z∼y:
-
x’s own neighbors: z∼x,z≁y,z≠y;
-
y’s own neighbors: z∼y,z≁x,z≠x.
Proof of Theorem 3
We suppose w.l.o.g.,
In principle, our transfer plan moving m x to m y should be as follows.
-
1.
Move the mass of \(\frac{1}{d_{x}}\) from y to y’s own neighbors;
-
2.
Move a mass of \(\frac{1}{d_{y}}\) from x’s own neighbors to x;
-
3.
Fill gaps using the mass at x’s own neighbors. Filling the gaps at common neighbors costs 2 and the one at y’s own neighbors costs 3.
A critical point will be whether (1) and (2) can be realized or not. It is easy to see that we can realize step (1) if and only if
That is, after taking off the mass at x and common neighbors, m y still has at least a mass of \(\frac{1}{d_{x}}\). Step (2) can be realized if and only if
That is, after taking off the mass at y and common neighbors, m x still has enough mass to fill \(\frac{1}{d_{y}}\). Obviously, A≤B.
We will divide the discussion into three cases according to whether the first two steps can be realized or not.
• 0≤A≤B. This means we can adopt the above transfer plan. By definition of W 1(m x ,m y ), we get
Or in a symmetric way,
Moreover, in this case the following function f (as shown in Fig. 1) can be extended as a 1-Lipschitz function:
(that is, if there are no paths of length 1 between common neighbors and x’s own neighbors, nor paths of length 1 or 2 between x’s own neighbors and y’s own ones) we have by Kantorovich duality
That is, in this case, (3.10) should be an equality. In conclusion,
and the “=” can be attained.
Remark 6
A≥0 is equivalent to
Since ♯(x,y)∈Z, we know that d x ∧d y ≥2 and ♯(x,y)≤d x ∧d y −2. This means both x and y have at least one own neighbor.
If A<0, we get
I.e., ♯(x,y)=d x ∧d y −1. This means the vertex with smaller degree has no own neighbors.
• A<0≤B. In this case we cannot realize step (1) but step (2) can be realized. By the above remark, A<0 implies that y has no own neighbors. Our transfer plan should be step (2) at first. Since B≥0 also implies
so we can move the mass of \(\frac{1}{d_{x}}\) at y for distance 1 to common neighbors. Finally, we fill the gap at common neighbors for distance 2. In a formula,
Or in a symmetric manner,
Moreover, in case the following function f can be extended as a 1-Lipschitz one,
(that is, if there are no paths of length 1 between common neighbors and x’s own neighbors) we have by Kantorovich duality
In conclusion,
and the “=” can be attained.
Remark 7
Noting that if ♯(x,y)=d x ∧d y −1 then B≥0 is equivalent to
In this case, one of d x , d y has no own neighbors, and if the other one has sufficiently many own neighbors, B≥0 will be satisfied.
• A≤B<0. In this case, neither step (1) nor (2) is applicable. Also, y has no own neighbor, and B<0 implies that we can move all the mass at x’s own neighbors to x at first. And then we move the mass of \(\frac{1}{d_{x}}\) at y for distance 1 to fill the gaps at x and the common neighbors. In a formula,
Or in a symmetric way,
We can find a 1-Lipschitz function
Then by Kantorovich duality
In this case f can be extended to a 1-Lipschitz function on the graph, so we get finally
Luckily, we can write those three cases in a uniform formula. □
Remark 8
From extending f to a 1-Lipschitz function, we see that the paths of length 1 or 2 between neighbors of x and y have an important effect on the curvature. That is, in addition to triangles, quadrangles and pentagons are also related to Ollivier’s Ricci curvature. But polygons with more than five edges do not impact it.
Remark 9
If we see the graph G=(V,E) as a metric measure space (G,d,m), then the term ♯(x,y)/d x ∨d y is exactly m x ∧m y (G):=m x (G)−(m x −m y )+(G), i.e. the intersection measure of m x and m y . From a metric view, the vertices x 1 that satisfy x 1∼x, x 1∼y constitute the intersection of the unit metric spheres S x (1) and S y (1).
From Theorem 3, we can force the curvature κ(x,y) to be positive by increasing the number ♯(x,y).
Theorem 4
On a locally finite graph G=(V,E), for any neighboring x,y, we have
Proof
Since except for the mass at common neighbors which we need not move, the others have to be moved for a distance at least 1, we have
□
So if κ(x,y)>0, then ♯(x,y) is at least 1. Moreover, if κ(x,y)≥k>0, we have
where ⌈a⌉:=min{A∈Z|A≥a}, for a∈R.
We will denote D(x):=max y,y∼x d y . By the relation (3.7), we can get immediately
Corollary 1
The scalar curvature at x can be controlled by the local clustering coefficient at x,
Remark 10
In fact in some special cases, we can get more precise lower bounds:
3.2 Weighted Graphs
The preceding considerations readily extend to weighted graphs.
Theorem 5
On a weighted locally finite graph G=(V,E), we have
Moreover, weighted trees attain this lower bound.
Theorem 6
On a weighted locally finite graph G=(V,E), we have
The inequality is sharp for certain graphs.
Remark 11
Notice that the term replacing the number of triangles here satisfies
Proof
Similar to the proof of Theorem 3, we need to understand the following two terms:
Only the transfer plan in the case A w <0≤B w needs a more careful discussion. □
Theorem 7
On a weighted locally finite graph G=(V,E), we have for any neighboring x,y
4 Curvature-Dimension Inequalities
In this section, we establish curvature-dimension inequalities on locally finite graphs. A very interesting one is the inequality under the condition κ≥k>0. Curvature-dimension inequalities on locally finite graphs are studied in Lin–Yau [21]. We first state a detailed version of their results. Let us denote \(D_{w}(x):=\max_{y, y\sim x}\frac{d_{y}}{w_{yx}}\). Notice that on an unweighted graph, this is the D(x) we used in Sect. 3.
Theorem 8
On a weighted locally finite graph G=(V,E), the Laplace operator Δ satisfies
Remark 12
Since in this case we attach the measure (2.1), we get
We only need to choose special z=x in the second sum and then (2.8) and (2.9) imply the theorem.
4.1 Unweighted Graphs
We again restrict ourselves to unweighted graphs.
We observe that the existence of triangles causes cancelations in calculating the term \(\operatorname{Hf}(x)\). This gives
Theorem 9
On a locally finite graph G=(V,E), the Laplace operator satisfies
where
Remark 13
Notice that if there is a vertex y, y∼x, such that ♯(x,y)=0, this will reduce to (4.1).
Proof
Starting from (2.9), the main work is to compare \(\operatorname{Hf}(x)\) with
First we try to write out \(\operatorname{Hf}(x)\) as
If there is a vertex x 1 which satisfies x 1∼x, x 1∼y, we have
So the existence of a triangle which includes x and y will give another term
to the sum in \(\operatorname{Hf}(x)\). Since this effect is symmetric w.r.t. y and x 1, we can get
Inserting this into (2.9) completes the proof. □
Recalling Theorem 4 and the subsequent discussion, we get the following curvature-dimension inequalities on graphs with positive Ollivier–Ricci curvature.
Corollary 2
On a locally finite graph G=(V,E), if κ(x,y)>0, then we have
Corollary 3
On a locally finite graph G=(V,E), if κ(x,y)≥k>0, then we have
Remark 14
Observe that a rough inequality in this case is
Comparing this one with (4.1), we see that positive κ increases the curvature function here.
Remark 15
We point out that the condition κ(x,y)≥k>0 implies that the diameter of the graph is bounded by \(\frac{2}{k}\) (see Proposition 23 in Ollivier [24]). So in this case the graph is a finite one.
Let us revisit the example of a complete graph \(\mathcal{K}_{n}\) (n≥2) with n vertices. Recall in Example 1, we know
For the curvature-dimension inequality on \(\mathcal{K}_{n}\), Theorem 9 or Corollary 3 using the above κ implies
Moreover, the curvature term in the above inequality cannot be larger. To see this, we calculate, using the same trick as in (4.3),
where \(\sum_{(x_{1}, x_{2})}\) means the sum over all unordered pairs of neighbors of x. Recalling (2.9), we get
For any vertex x, we can find a particular function \(\overline{f}\),
such that the last term in (4.7) vanishes, and \(\varGamma(\overline {f},\overline{f})\neq0\). This means the curvature term in (4.6) is optimal for dimension parameter 2.
But the curvature term \(\frac{4-n}{2(n-1)}\) behaves very differently from κ. In fact as n→+∞,
To get a curvature-dimension inequality with a curvature term which behaves like κ, it seems that we should adjust the dimension parameter. In fact, we have
Proposition 3
On a complete graph \(\mathcal{K}_{n}\) (n≥2) with n vertices, the Laplace operator Δ satisfies for m∈[1,+∞],
Moreover, for every fixed dimension parameter m, the curvature term is optimal.
Proof
We have from (4.7)
Let us denote the sum of the last two terms by I. Then we have
This finishes the proof. □
An interesting point appears when we choose the dimension parameter m of \(\mathcal{K}_{n}\) as n−1. Then we have
where the curvature term is exactly \(\frac{1}{2}\kappa\). From the fact that \(\mathcal{K}_{n}\) could be considered as the boundary of a (n−1) dimensional simplex, the m we choose here seems also natural.
Remark 16
We point out another similar fact here. On a locally finite graph with maximal degree D and minimal degree larger than 1, Theorem 2 and Theorem 8 imply that
and
respectively. It is not difficult to see that for regular trees with degree larger than 1, the curvature term in (4.11) is optimal. (Just consider the extension of the function (4.8), taking values 0 on vertices which are not x and neighbors of x there.) So on regular trees, the curvature term is also exactly \(\frac{1}{2}\kappa\).
Remark 17
In Erdös–Harary–Tutte [15], they define the dimension of a graph G as the minimum number n such that G can be embedded into a n dimensional Euclidean space with every edge of G having length 1. It is interesting that by their definition, the dimension of \(\mathcal{K}_{n}\) is also n−1 and the dimension of any tree is at most 2.
From the above observations, it seems natural to expect stronger relations between the lower bound of κ and the curvature term in the curvature-dimension inequality if one chooses proper dimension parameters.
4.2 Weighted Graphs
We have similar results on weighted graphs here, with similar proofs.
Theorem 10
On a weighted locally finite graph G=(V,E), the Laplace operator satisfies
where
References
Bakry, D.: Functional inequalities for Markov semigroups. In: Dani, S.G., Graczyk, P. (eds.) Probability Measures on Groups: Recent Directions and Trends, pp. 91–147. Tata, Bombay (2006)
Bakry, D., Émery, M.: Diffusions hypercontractives. In: Azéma, J., Yor, M. (eds.) Séminaire de probabilités, XIX. Lecture Notes in Math., vol. 1123, p. 177–206. Springer, Berlin (1985)
Bakry, D., Émery, M.: Hypercontractivité de semi-groupes de diffusion. C. R. Math. Acad. Sci. 299, 775–778 (1984)
Banerjee, A., Jost, J.: On the spectrum of the normalized graph Laplacian. Linear Algebra Appl. 428, 3015–3022 (2008)
Bauer, F., Jost, J.: Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian. Commun. Anal. Geom. 21(4), 787–845 (2013). doi:10.4310/CAG.2013.v21.n4.a2
Bauer, F., Jost, J., Liu, S.: Ollivier–Ricci curvature and the spectrum of the normalized graph Laplace operator. Math. Res. Lett. 19(6), 1185–1205 (2012). doi:10.4310/MRL.2012.v19.n6.a2
Bonciocat, A.-I., Sturm, K.-T.: Mass transportation and rough curvature bounds for discrete spaces. J. Funct. Anal. 256, 2944–2966 (2009)
Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol. 92. Am. Math. Soc., Providence (1997)
Chung, F.R.K., Yau, S.T.: Logarithmic Harnack inequalities. Math. Res. Lett. 3, 793–812 (1996)
Diaconis, P., Stroock, D.: Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1, 36–61 (1991)
Diaconis, P., Saloff-Coste, L.: Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6, 695–750 (1996)
Diaconis, P.: From shuffling cards to walking around the building: an introduction to modern Markov chain theory. In: Proceedings of the International Congress of Mathematicians, Vol. I. Doc. Math., pp. 187–204 (1998)
Diaconis, P.: The Markov chain Monte Carlo revolution. Bull., New Ser., Am. Math. Soc. 46, 179–205 (2009)
Dodziuk, J., Karp, L.: Spectral and Function Theory for Combinatorial Laplacians. Contemp. Math., vol. 73. Amer. Math. Soc., Providence (1988)
Erdös, P., Harary, F., Tutte, W.T.: On the dimension of a graph. Mathematika 12, 118–122 (1965)
Evans, L.C.: Partial differential equations and Monge–Kantorovich mass transfer. In: Bott, R., Jaffe, A., Jerison, D., Lusztig, G., Yau, S.T. (eds.) Current Developments in Mathematics, pp. 65–126. International Press, Boston (1999)
Forman, R.: Bochner’s method for cell complexes and combinatorial Ricci curvature. Discrete Comput. Geom. 29, 323–374 (2003)
Jost, J.: Riemannian Geometry and Geometric Analysis, 6th edn. Springer, Berlin (2011)
Lin, Y.: Ricci curvature on graphs. John H. Barrett Memorial Lecture (2010). http://www.math.utk.edu/barrett/2010/talks/YongLinRicci.pdf
Lin, Y., Lu, L., Yau, S.T.: Ricci curvature of graphs. Tohoku Math. J. 63, 605–627 (2011)
Lin, Y., Yau, S.T.: Ricci curvature and eigenvalue estimate on locally finite graphs. Math. Res. Lett. 17, 343–356 (2010)
Lott, J., Villani, C.: Ricci curvature for metric measure spaces via optimal transport. Ann. Math. 169, 903–991 (2009)
Ohta, S.-I.: On the measure contraction property of metric measure spaces. Comment. Math. Helv. 82, 805–828 (2007)
Ollivier, Y.: Ricci curvature of Markov chains on metric spaces. J. Funct. Anal. 256, 810–864 (2009)
Ollivier, Y.: A survey of Ricci curvature for metric spaces and Markov chains. In: Kotani, M., Hino, M., Kumagai, T. (eds.) Probabilistic Approach to Geometry. Adv. Stud. Pure Math., vol. 57, pp. 343–381. Math. Soc. Japan, Tokyo (2010)
Ollivier, Y., Villani, C.: A curved Brunn–Minkowski inequality on the discrete hypercube. SIAM J. Discrete Math. 26(3), 983–996 (2012). doi:10.1137/11085966X
Paeng, S.-H.: Volume, diameter of a graph and Ollivier’s Ricci curvature. Eur. J. Comb. 33(8), 1808–1819 (2012). doi:10.1016/j.ejc.2012.03.029
Stone, D.A.: A combinatorial analogue of a theorem of Myers. Ill. J. Math. 20, 12–21 (1976). Correction: Ill. J. Math. 20, 551–554 (1976)
Sturm, K.-T.: On the geometry of metric measure spaces. I. Acta Math. 196, 65–131 (2006)
Sturm, K.-T.: On the geometry of metric measure spaces. II. Acta Math. 196, 133–177 (2006)
Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. Am. Math. Soc., Providence (2003)
Villani, C.: Optimal Transport, Old and New. Grundlehren der Mathematischen Wissenschaften, vol. 338. Springer, Berlin (2009)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)
Acknowledgements
The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement n∘267087.
We thank Persi Diaconis for pointing out Ollivier’s notion of Ricci curvature to us.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jost, J., Liu, S. Ollivier’s Ricci Curvature, Local Clustering and Curvature-Dimension Inequalities on Graphs. Discrete Comput Geom 51, 300–322 (2014). https://doi.org/10.1007/s00454-013-9558-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-013-9558-1