# On the Relation between Graph Ricci Curvature and Community Structure

Theodora Bourni, Vasileios Maroulas, Sathyanarayanan Rengaswami

(Date: June 2024)

###### Abstract.

The connection between curvature and topology is a very well-studied theme in
the subject of differential geometry. By suitably defining curvature on
networks, the study of this theme has been extended into the domain of network
analysis as well. In particular, this has led to curvature-based community
detection algorithms. In this paper, we reveal the relation between community
structure of a network and the curvature of its edges. In particular, we give
apriori bounds on the curvature of intercommunity edges of a graph.

###### Key words and phrases:

discrete curvature, Ollivier Ricci curvature, graph curvature, optimal
transport, community structure, community detection

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 A Zero-Curvature Example
  4. 4 Proof of Main Theorem
  5. 5 Empirical Results
  6. 6 Conclusion

##  1\. Introduction

The connection between curvature and topology is a fundamental question in
Riemannian geometry. Notable examples include the Gauss-Bonnet theorem, which
relates the curvature of a surface to its Euler characteristic, and Myer’s
theorem, which bounds the diameter of a manifold in terms of its curvature
(see [14] for more details). Remarkably, successful definitions of curvature
have been extended to graphs (Forman [7], Ollivier [19], Lin [15], Devriendt
[4]), generalizing the curvature notions on Riemannian manifolds and
establishing analogous connections between curvature and topology.

A crucial topological question in the study of complex networks is their
community structure (See [8], [9] for a survey on community detection). This
involves clustering nodes such that many edges connect nodes within the same
cluster, while few edges connect nodes between different clusters. These
clusters, referred to as communities, are defined based on the application at
hand. This task is significant across various fields including computer
science [11, 13], biology [21, 23, 5], chemistry[20], logistics [12, 18] ,
where graphs are commonly used to model real-world systems. Consequently,
numerous methods based on diverse theories are available, such as partitioning
algorithms and spectral methods ([8] contains a survey of commonly used
algorithms.)

A recent approach to community detection draws inspiration from the geometric
notion of curvature. In this paper, we employ the Ollivier-Ricci curvature
(ORC), originally defined by Ollivier [19] using optimal transport theory. The
essential idea is to compare the distance $d(x,y)$ between two vertices $x$
and $y$ to the distance between the neighbors of $x$ and $y$ (defined in terms
of optimal transport). If the latter distance is smaller, the edge is
positively curved; if greater, it is negatively curved. Negatively curved
edges act as “bottlenecks,” indicating that to move from the neighbors of $x$
to those of $y$, one must pass through the edge $xy$. This concept is applied
to rewire graph neural networks in [26].

Studies such as [17] and [22] have observed that edges with positive ORC
typically exist between nodes within the same community, whereas edges with
negative ORC often connect nodes from different communities. This observation
has been turned into a computational algorithm for community detection. [22]
achieves this by sequentially deleting negatively curved edges, while [17]
employs “Ricci flow with surgery” to elongate or contract edges based on their
curvature, then removes the longest edges. These curvature-based methods have
been shown to perform competitively against other industry-standard
techniques.

A variant of ORC known as the _dynamical ORC_ has been used in [10] to reveal
community structures at varying scales of resolution. _Mixed membership_ ,
where a node is allowed to belong to multiple communities has been studied in
[24] and [25] (Note that these papers use flow-based approaches similar to
[17].) Other curvature notions that are not based on optimal transport have
also been used to attack the problem of community detection. One of the
popular definitions is that of Forman [7]. Though not equivalent to Ollivier’s
notion,it has the advantage of being computationally efficient, and its flow
version has been used in community detection in [27]. The shortcomings of
Forman’s definition have been partially mitigated by modifying its definition
(while retaining computational efficiency): one such is the Augmented Forman-
Ricci Curvature, which has also been shown to be effective for community
detection in [6].

From a theoretical point of view, ORC has been linked to other deep properties
of graphs. Besides the work of Ollivier himself, one of the earliest
theoretical analyses of ORC [15], which proves several geometrical and
spectral properties of the ORC. Its relation to the heat flow on graphs has
been studied in [16]. The spectrum of the Laplacian is also intimately
connected to ORC, and this is shown in [1]. Analyses regarding geometric
properties of ORC such as flatness, rigidity have been studied in [2], [3]. In
spite of the great theoretical interest in ORC and its relation to other
properties of graphs, and a great practical interest in its application to
community detection, there has not been a substantial amount of literature in
the theoretical relation between ORC and community structure.

A basic question regarding this relationship is the following: it is observed
that a single edge connecting two disjoint communities will have negative
curvature, whereas a complete graph formed by all possible intercommunity
edges will have positively curved edges. (This is discussed in Section 2.)
Therefore, the critical question is: what is the maximum number of
intercommunity edges such that we can guarantee each one is negatively curved?
More broadly, when examining two particular communities in a graph, what can
we infer about the curvature of intercommunity edges? This paper aims to
address this question (and more) quantitatively, as provided by the main
theorem.

######  Theorem 1.1.

Suppose $\mathcal{G}$ is a graph comprised of several communities. Let
$C_{i},C_{j}$ be distinguished communities in $\mathcal{G}$ whose sizes are
$m$ and $n$. Let $k$ be the total number of edges that are either
intercommunity edges between $C_{i}$ and $C_{j}$, or from any other community
to $C_{i}$ or $C_{j}$.

Then, if

$k\leq\frac{-m+\sqrt{m^{2}+4(m-1)(2n-1)}}{2},$

we have $\kappa(e)\leq 0$ for every intercommunity edge $e$ between $C_{i}$
and $C_{j}$.

In particular, if $k\leq\min_{l}|C_{l}|-1$ where $C_{l}$ are the various
communities, the same conclusion holds.

We have the following when the community sizes are all the same:

######  Corollary 1.2.

Let $\mathcal{G}$ be a graph as in previous theorem. Suppose in addition that
all communities have the same size $n$. Then if $k\leq n-1$, we have
$\kappa(e)\leq 0$ for every intercommunity edge $e$ between $C_{1}$ and
$C_{2}$.

In the case where the graph only has two communities, we have the following:

######  Corollary 1.3.

Suppose $\mathcal{G}$ is a graph comprised of only two communities
$C_{1},C_{2}$ whose sizes are $m$ and $n$. Let $k$ be the total number of
intercommunity edges between $C_{1}$ and $C_{2}$.

Then, if

$k\leq\frac{-m+\sqrt{m^{2}+4(m-1)(2n-1)}}{2},$

we have $\kappa(e)\leq 0$ for every intercommunity edge $e$ between $C_{1}$
and $C_{2}$.

If $m=n$, the same conclusion holds for $k\leq n-1$.

The paper is organized as follows. In Section 2, we do a quick review of
optimal transport as it pertains to graphs, define the Ollivier-Ricci
curvature of an edge of a graph, and give some examples. In Section 3, we give
a key example that simultaneously motivates the claims in the paper and
highlights the computational techniques used to prove the main theorem. In
Section 4, we provide a proof of the main theorem and the corollaries. In
Section 5, we show that the bound prescribed in the theorem is sharp, but at
the same time we show experimental results that show that we have a lot of
latitude even if we go beyond the theoretical limit prescribed in the theorem.

##  2\. Preliminaries

###  2.1. Definitions

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a graph.

  1. (1)

A _community_ of $\mathcal{G}$ is a maximally connected subgraph of
$\mathcal{G}$.

  2. (2)

An edge whose endpoints lie in different communities is called an
_intercommmunity edge_.

  3. (3)

An edge whose endpoints both lie inside the same community is called an
_intracommunity edge_.

We remark that this is definition of community is only one of several possible
definitions, but this simplifies our mathematical analysis.

###  2.2. Optimal Transportation on Graphs

Let $\mu,\nu$ be probability measures on a graph, and let the vertices be
enumerated $1,\ldots,n$. A _transference plan_ $\pi=(\pi_{ij})$ is an $n\times
n$ matrix with nonnegative entries such that $\sum_{j}\pi_{ij}=\mu(i)$, and
$\sum_{i}\pi_{ij}=\nu(j)$. More concisely, $\pi$ is a joint probability
distribution on $\mathcal{V}\times\mathcal{V}$ whose marginals are $\mu$ and
$\nu$. We define $\Pi$ to be the set of all transference plans between $\mu$
and $\nu$.

Closeness between two probability distributions can be measured via the
_1-Wasserstein distance_ (or _earthmover’s distance_) which is defined as
follows:

(1)
$W(\mu,\nu)=W_{1}(\mu,\nu)\coloneqq\displaystyle\inf_{\pi\in\Pi}\sum_{i,j}\pi_{ij}d(i,j)$

where $d(i,j)$ is the graph distance between vertices $i,j$.

######  Proposition 2.1.

Under the metric $W$ defined above, the set of all probability measures on
$\mathcal{V}$ is a metric space.

Note that computing $W$ amounts to solving a linear programming problem.
Therefore, by duality, we have an equivalent formulation for $W$ via a
maximization problem. To present this formulation, we first define a
$1-Lipschitz$ function to be a function $f$ such that $|f(x)-f(y)|\leq
d(x,y).$ On (combinatorial) graphs, this is equivalent to insisting that the
values of $f$ on adjacent nodes do not differ by more than $1.$

######  Proposition 2.2.

Let $\mathcal{F}$ be the set of $1$-Lipschitz functions on $G$. Then,

(2) $W(\mu,\nu)=\displaystyle\sup_{f\in\mathcal{F}}\left\\{\sum_{z\in
G}f(z)(\mu(z)-\nu(z))\right\\}$

A function $f$ that achieves this supremum is called a _Kantorovich
potential_.

###  2.3. The Ollivier-Ricci Curvature

Ollivier [19] defined Ricci curvatures on general Markov chains on metric
spaces, with random walks as the building blocks. The following is a
simplified exposition for graphs. A _random walk_ is a family of probability
distributions $\\{m_{x}\\}_{x\in\mathcal{G}}$. For any $\alpha\in[0,1]$, the
_$\alpha$ -lazy random walk_ is one where the probability measures at each
node are given by

$m_{x}(z)=m^{\alpha}_{x}(z)=\begin{cases}\alpha,\,z=x\\\
\frac{1-\alpha}{d_{x}},\,(zx)\in\mathcal{E}\\\
0,\,\text{otherwise}\end{cases}$

Finally, the $\alpha$-_Ollivier-Ricci curvature_ of an edge $e=(xy)$ is
defined as

(3) $\kappa(e)=\kappa^{\alpha}(e)\coloneqq 1-\frac{W(m_{x},m_{y})}{d(x,y)}.$

We deal with combinatorial graphs in this paper, and therefore, all edges have
length $1$. Thus the formula reduces to

(4) $\kappa(e)=1-W(m_{x},m_{y}).$

######  Example.

The intuition behind the Ollivier-Ricci curvature is captured by the following
examples:

  1. a.

An edge of the lattice $\mathbf{Z}^{n}$ has curvature $\kappa=0$. So does an
edge of the cycle $C_{n}$ for $n\geq 6.$

  2. b.

An edge of the complete graph $K_{n}$ has curvature
$\kappa=\frac{n(1-\alpha)}{n-1}>0$.

  3. c.

Imagine a ‘dumbbell’ graph comprised of two communities of size $m,n$, joined
by a single intercommunity edge. This edge has curvature
$\kappa=2(1-\alpha)\left(\frac{1}{m}+\frac{1}{n}-1\right)$, which is negative
for all $m,n\geq 3$.

######  Remark.

The claims in the above example can be proved by following the general
strategy described here.

  1. 1.

To establish an upper bound on the curvature, we need a lower bound on
$W(m_{x},m_{y})$. This uses (2) and requires prescribing an explicit potential
function.

  2. 2.

To establish a lower bound on the curvature, we need an upper bound on
$W(m_{x},m_{y})$. This uses (1) and requires prescribing an explicit
transference plan.

  3. 3.

If we can show that the curvature is bounded above and below by the same
constant $C$, then the curvature equals $C$.

We will apply this strategy to an important nontrivial example in the next
section.

##  3\. A Zero-Curvature Example

To see what motivates the claims of this paper, we start with the case that
the two communities have the same size $n\geq 3$. Consider the number of
intercommunity edges below which it is guaranteed that every intercommunity
edge is nonpositively curved. We show an explicit construction which suggests
that this number can be no more than $n-1$. (A proof of the sufficiency of
this claim is given by the main theorem of this paper. Sharpness is given by
Proposition 5.1.)

######  Theorem 3.1.

For communities of size $(n,n)$, there is a configuration of $n-1$ edges
between the communities such that each intercommunity edge has zero curvature.

###### Proof.

We give an explicit construction. Let $A,B$ be a complete graph on the
vertices $\\{a_{0},\ldots,a_{n-1}\\},\\{b_{0},\ldots,b_{n-1}\\}$ respectively.
Add inter-community edges $a_{i}b_{i},i=0,\ldots,n-2$ (See Figure 1 for an
illustration.) We claim that every edge $a_{i}b_{i}$ has zero curvature.
Indeed by symmetry, we only need to show it for one of them, say $a_{0}b_{0}$.

Figure 1. A configuration with zero curvature on all intercommunity edges - | $a_{n-1}$ | $a_{1},\ldots,a_{n-2}$ | $a_{0}$ | $b_{0}$ | $b_{1},\ldots,b_{n-2}$ | $b_{n-1}$
---|---|---|---|---|---|---
$m_{a_{0}}$ | $\frac{1-\alpha}{n}$ | $\frac{1-\alpha}{n}$ | $\alpha$ | $\frac{1-\alpha}{n}$ | $0$ | $0$
$m_{b_{0}}$ | 0 | 0 | $\frac{1-\alpha}{n}$ | $\alpha$ | $\frac{1-\alpha}{n}$ | $\frac{1-\alpha}{n}$
$f$ | 0 | -1 | -1 | -2 | -2 | -3
Table 1. A potential function for curvature lower upper bounds

To get an upper bound on the curvature, we obtain a lower bound on
$W(m_{a_{0}},m_{b_{0}})$. We use $f$ as defined in the table 1. Applying the
equation (2), an explicit calculation shows that $W(m_{a_{0}},m_{b_{0}})\geq
1$, which implies $\kappa(a_{0}b_{0})\leq 0$.

To get a lower bound on curvature, we obtain an upper bound on
$W(m_{a_{0}},m_{b_{0}})$. We use the following transference plan:

$\pi_{a_{i}b_{i}}=\begin{cases}\alpha-\frac{1-\alpha}{n},\quad i=0\\\
\frac{1-\alpha}{n},\quad i=1,\ldots,n-1\end{cases}$

together with $\pi_{b_{0}b_{0}}=\frac{1-\alpha}{n}$ and $0$ between any other
pair of vertices not specified previously. Note that the associated distances
are

$d(a_{i},b_{i})=\begin{cases}1,\quad i=0,\ldots,n-2\\\ 3,\quad
i=n-1\end{cases}$

Applying equation (1), it follows that $W(m_{a_{0}},m_{b_{0}})\leq 1$ and
hence $\kappa(a_{0}b_{0})\geq 0$. Thus we conclude that

$\kappa(a_{0}b_{0})=0.$

∎

######  Remark.

The configuration in the previous example is not unique. Indeed, it can be
shown using the same technique that the intercommunity edges in Figure 2 have
curvature 0.

Figure 2. Another configuration with zero curvature on intercommunity edges

##  4\. Proof of Main Theorem

Figure 3. Three communities, with a potential function

Let $\mathcal{G}$ be graph, and $C_{1},C_{2}$ be two communities in
$\mathcal{G}$. Suppose $e=xy\in\mathcal{E}$, $x\in C_{1},y\in C_{2}$. We
obtain an upper bound on $\kappa(e)$ by getting a lower bound on
$W(m_{x},m_{y})$. To do so, we need a potential function. The key step is to
partition the graph into several subsets on which $f$ will be constant.

Let $C_{3}=G-C_{1}-C_{2}$, which could be a union of several communities. We
partition $C_{1}$ in five subsets $\\{x\\},A,B,C,J$, $C_{2}$ in
$\\{y\\},D,E,F,K$ and $C_{3}$ in $G,H,I,L,M$, which we define in the following
way:

  * •

$B=\\{z\in C_{1}-x:yz\in\mathcal{E}\\}$

  * •

$D=\\{w\in C_{2}-y:xw\in\mathcal{E}\\}$

  * •

$C=\\{z\in C_{1}-x-B:zw\in\mathcal{E}\,\text{ for some }w\in C_{2}\\}$

  * •

$E=\\{z\in C_{2}-y-D:zw\in\mathcal{E}\,\text{ for some }w\in C_{2}\\}$

  * •

$J=\\{z\in C_{1}-x-B-C:d(z,w)=2,\text{ for some }w\in C_{2}\\}$

  * •

$K=\\{w\in C_{w}-y-B-E:d(z,w)=2,\text{ for some }z\in C_{1}\\}$

  * •

$A=C_{1}-x-B-C-J$

  * •

$F=C_{2}-y-D-E-K$

  * •

$G=\\{v\in\mathcal{G}-C_{1}-C_{2}:\,xv,yv\in\mathcal{E}\\}$

  * •

$H=\\{v\in\mathcal{G}-C_{1}-C_{2}-G:\,xv\in\mathcal{E}\\}$

  * •

$I=\\{v\in\mathcal{G}-C_{1}-C_{2}-G:\,yv\in\mathcal{E}\\}$

  * •

$L=\\{v\in\mathcal{G}-C_{1}-C_{2}-G-H-I:\,zv\in\mathcal{E}\text{ for some
}z\in J\\}=\\{v\in\mathcal{G}-C_{1}-C_{2}:\,wv\in\mathcal{E}\text{ for some
}w\in K\\}$

  * •

$M=\mathcal{G}-C_{1}-C_{2}-G-H-I-L$

This configuration, along with the values of the function $f$ are illustrated
in Figure 3. The number shown inside each “node” (or subset of $\mathcal{G}$
to be precise) is the value of the function $f$. Note that we have not added
all possible edges: for instance, there could be edges between $A,M$. The
important thing is that $A,J$ do not have neighbours in $C_{2}$, $F,K$ do not
have neighbours in $C_{1}$. This ensures that the function in Table 2 is
1-Lipschitz.

In Table 2 we depict the measures $m_{x},m_{y}$ together with the value of
$f$. We let $\beta\coloneqq 1-\alpha$.

- | $J$ | $A$ | $B$ | $C$ | $x$ | $y$ | $D$ | $E$ | $F$ | $K$ | $G$ | $H$ | $M$ | $I$ | $L$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$m_{x}$ | $\frac{\beta}{d_{x}}$ | $\frac{\beta}{d_{x}}$ | $\frac{\beta}{d_{x}}$ | $\frac{\beta}{d_{x}}$ | $\alpha$ | $\frac{\beta}{d_{x}}$ | $\frac{\beta}{d_{x}}$ | 0 | 0 | 0 | $\frac{\beta}{d_{x}}$ | $\frac{\beta}{d_{x}}$ | 0 | 0 | 0
$m_{y}$ | 0 | 0 | $\frac{\beta}{d_{y}}$ | 0 | $\frac{\beta}{d_{y}}$ | $\alpha$ | $\frac{\beta}{d_{y}}$ | $\frac{\beta}{d_{y}}$ | $\frac{\beta}{d_{y}}$ | $\frac{\beta}{d_{y}}$ | $\frac{\beta}{d_{y}}$ | 0 | 0 | $\frac{\beta}{d_{y}}$ | 0
$f$ | 0 | 0 | -1 | -1 | -1 | -2 | -2 | -2 | -3 | -2 | -1 | -1 | 0 | -1 | -1
Table 2. Probabilities and potential associated with curvature of edge $xy$

In the following we abuse notation by conflating $S$ with its cardinality
$|S|$ where $S$ could be any of the sets $A,\ldots,M$. Let $W=W(m_{x},m_{y})$.
Using (2) we have the following bound:

(5)
$\begin{split}W&\geq\alpha+(1-\alpha)\left[\frac{-1-C-2-2D-G}{d_{x}}+\frac{-1+B+2D+2E+2K+3F+G+I}{d_{y}}\right]\end{split}$

We also have the following constraint equations from counting nodes and edges:

(6) $\begin{split}A+B+C+J+1&=n,\\\ D+E+F+K+1&=m,\\\ n+D+G+H&=d_{x},\\\
m+B+G+I&=d_{y}.\end{split}$

Equations (5) and (6) together give

(7)
$W\geq\alpha+(1-\alpha)\left[\frac{n-1+A+J+G+H}{d_{x}}+\frac{m-1+F}{d_{y}}-1\right].$

Note that the lack of symmetry between $x$ and $y$ in the above expression is
due to the lack of symmetry in the way we defined $f$.

Let $k_{1}$ be the number of intercommunity edges between $C_{1}$ and $C_{2}$,
and $k_{2}$ be the number of edges from $C_{1}$ or $C_{2}$ to the rest of
$\mathcal{G}$. Then,

(8) $\begin{split}k_{1}&\geq 1+B+D+\max\\{C,E\\},\\\ k_{2}&\geq
2G+H+I+\max\\{J,L\\}+\max\\{K,L\\}.\end{split}$

Defining $k=k_{1}+k_{2}$, we have

(9) $k\geq 1+B+D+\max\\{C,E\\}+2G+H+I+\max\\{J,L\\}+\max\\{K,L\\}$

which, together with the constraint equations (6), yields

(10) $\begin{split}k+A&\geq n+D+2G+H+I+\max\\{K,L\\}\\\
&=d_{x}+G+I+\max\\{K,L\\}\\\ &\geq d_{x}\end{split}$

and

(11) $\begin{split}k+F&\geq m+B+2G+H+I+\max\\{J,L\\}\\\
&=d_{y}+G+I+\max\\{J,L\\}\\\ &\geq d_{y}.\end{split}$

Now we need to find an optimal $k$ such that

$\frac{n-1+A+J+G+H}{d_{x}}+\frac{m-1+F}{d_{y}}-1\geq\frac{k+A+J+G+H}{d_{x}}+\frac{k+F}{d_{y}}-1,$

which reduces to

$\displaystyle\frac{n-1}{d_{x}}+\frac{m-1}{d_{y}}\geq\frac{k}{d_{x}}+\frac{k}{d_{y}}$
$\displaystyle\iff$ $\displaystyle(m-1)d_{x}+(n-1)d_{y}\geq k(d_{x}+d_{y})$
$\displaystyle\iff$ $\displaystyle(m-n)d_{x}+(n-1)(d_{x}+d_{y})\geq
k(d_{x}+d_{y})$ $\displaystyle\iff$
$\displaystyle(m-n)d_{x}\geq(k-n+1)(d_{x}+d_{y})$ $\displaystyle\iff$
$\displaystyle\frac{d_{x}}{d_{x}+d_{y}}\geq\frac{k-n+1}{m-n}$

Since $d_{x}\geq n$ and $d_{x}+d_{y}\leq n+m+k-1$, a sufficient condition for
the above to be true is

$\frac{n}{n+m+k-1}\geq\frac{k-n+1}{m-n},$

which results in the quadratic inequality

$k^{2}+mk-(m-1)(2n-1)\leq 0.$

Theorem 1.1 now follows directly from this.

_Proof of Corollary 1:_

By letting $m=n$, we get

$\displaystyle k\leq$ $\displaystyle\frac{-m+\sqrt{m^{2}+4(m-1)(2n-1)}}{2}$
$\displaystyle=$ $\displaystyle\frac{-n+\sqrt{n^{2}+4(n-1)(2n-1)}}{2}$
$\displaystyle=$ $\displaystyle\frac{-n+\sqrt{n^{2}+4(2n^{2}-3n+1)}}{2}$
$\displaystyle=$ $\displaystyle\frac{-n+\sqrt{9n^{2}-12n+4}}{2}$
$\displaystyle=$ $\displaystyle\frac{-n+3n-2}{2}$ $\displaystyle=$
$\displaystyle n-1.\qed$

_Proof of Corollary 2:_

In the proof of main theorem, we may assume that $G,H,L,I,M=\emptyset$.
Consequently, $J,K=\emptyset$ as well, and $k_{2}=0$, and the claim follows
immediately. ∎

##  5\. Empirical Results

In the previous section, we gave theoretical bounds on the number of
intercommunity edges that guarantee the negativity of curvatures. This bound
is sharp due to the following proposition:

######  Proposition 5.1.

For communities of size $(n,n)$, there is a configuration of $n$ edges between
the communities such that each intercommunity edge has positive curvature.

###### Proof.

Consider the product graph of the complete graph $K_{n}$ with the graph
consisting of only two points joined by an edge. See Figure 4 for an
illustration with $n=4$.

Figure 4. Two communities with all $n$ intercommunity edges positively curved

We can show that edge $a_{0}b_{0}$ (and hence every intercommunity edge) has
positive curvature. The distributions $m_{a_{0}},m_{b_{0}}$ are

- | $a_{0}$ | $a_{1},\ldots,a_{n}$ | $b_{0}$ | $b_{1},\ldots,b_{n}$
---|---|---|---|---
$m_{a_{0}}$ | $\alpha$ | $\frac{1-\alpha}{n}$ | $\frac{1-\alpha}{n}$ | 0
$m_{b_{0}}$ | $\frac{1-\alpha}{n}$ | $0$ | $\alpha$ | $\frac{1-\alpha}{n}$

Consider the transference plan

(12) $\pi_{a_{i}b_{i}}=\begin{cases}\alpha-\frac{1-\alpha}{n},\quad i=j=0\\\
\frac{1-\alpha}{n},\quad i=j\neq 0\\\ 0,\quad i\neq j\end{cases}$

This plan has a cost of

$\sum_{i,j}\pi_{a_{i}b_{j}}d(a_{i},b_{j})=\alpha+\frac{(n-2)(1-\alpha)}{n}=1-\frac{2(1-\alpha)}{n}$

which is an upper bound on $W(m_{a_{0}},m_{b_{0}})$, and hence

$\kappa(a_{0}b_{0})\geq\frac{2(1-\alpha)}{n}>0.$

∎

Even though it is theoretically possible for all edges to be positively curved
when we have $k=n$ intercommunity edges, the point of the remainder of this
section is to share experimental findings that indicate how unlikely such a
situation is. For the sake of simplicity, we generate two-community graphs
with randomly chosen intercommunity edges and observe the empirical proportion
of nonpositively curved edges.

Figure 5 shows the result of one such experiment. Here, we choose the
community sizes $|C_{1}|=|C_{2}|=128$. We experiment with $k=128,256,384,512$
intercommunity edges. For each $k$, we generate 100 graphs where $k$
intercommunity edges are chosen at random. In each of those random graphs, we
compute the proportion $p^{k}_{\leq 0}$ of nonpositively curved edges.
Finally, we plot $p^{k}_{\leq 0}$ versus its frequency of occurrence.

One notices in Figure 5 that for $k=128,256$, almost all edges were negatively
curved in every one of the 100 randomly generated graphs. When $k=384$, most
of the edges are negatively curved. But when $k=512$, the proportion of
negatively curved edges is small.

Figure 5. Distribution of Proportion of Nonpositively Curved Intercommunity
Edges

In fact, we find something similar for different sizes. In Figure 6, we
examine community sizes $n=16,32,64,128,256,512$. And for each $n$, we
generate graphs with number of intercommunity edges $k=n,2n,3n,4n$ and
empirically find the proportion of intercommunity edges that have nonpositive
curvature. For each choice of $(n,k)$, we generate $100$ graphs at random. We
plot the empirical proportion of nonpositive edges with error bars one
standard deviation wide (over the 100 runs.) What we find is that for $n\geq
32$, even when we have $2n$ intercommunity edges, almost all of them are
negatively curved. When $n=512$, even when $k=4n$ we have almost all edges
negatively curved.

Figure 6. Proportion of Negative Edges for different $k$ and $n$

##  6\. Conclusion

In this paper, we have examined the relation between curvature and community
structure from a theoretical point of view. In particular, we have sought to
understand how the sizes of communities and the number of intercommunity edges
affects the curvature of those intercommunity edges. More specifically, we
have given sufficient conditions for intercommunity edges to be negatively
curved. In addition, we show these requirements are sharp, in the sense that
there are counterexamples as soon as we cross the cutoff. We have achieved
this by exploiting two equivalent definitions of the Wasserstein distance
between probability distributions, which give us concrete computational tools
for proving curvature estimates.

In the experimental section of the paper, we explored how likely it is to find
positively curved edges when the number of intercommunity edges $k$ exceeds
the theoretical bound. We found that as the community sizes become large, $k$
can get much larger than the theoretical bound while most of the
intercommunity edges have negative curvature. A likely explanation for this is
in the estimate (7). Here we see that the Wasserstein distance is large when
the “unmatched” sections $A,F$ are large and the node degrees $d_{x},d_{y}$
are small. When we randomly sample intercommunity edges from the list of all
possible intercommunity edges, we are less likely to sample an edge
configuration where degrees are very large and the unmatched sections are very
small, at least when the number of intercommunity edges is very small.

We believe that this analysis raises several interesting questions. For
instance, it would be very interesting to study the curvature of
intracommunity edges and obtain criteria that ensure that they are positively
curved. In effect, this would provide a theoretical underpinning for
curvature-based community detection via edge deletion. Another interesting
direction is the analysis of curvature distribution as a function of the
number of intercommunity edges. For instance, for a fixed $k$, let $I$ be a
random sample of $k$ intercommunity edges from the list of all possible ones.
Now we can generate a graph with $I$ as the set of intercommunity edges. Let
$\kappa_{max}(I)$ be the maximum curvature among edges in $I$, which we may
regard as a random variable. What is the probability distribution of
$\kappa_{max}$? How is it affected by $k$? Another interesting question is one
that concerns “surgery”, or edge deletion. How does the deletion of a subset
of edges of a graph affect the curvature of the remaining edges? Questions of
this nature provide ideal circumstances for the synthesis of tools from
differential geometry, graph theory, statistics, and programming.

### Acknowledgements

The work of authors SR and VM was partially supported by the US Army Research
Office Grant No W911NF2110094. The work of TB was supported through grant
DMS-2105026 of the National Science Foundation.

## References

  * [1] Frank Bauer, Jürgen Jost, and Shiping Liu.  Ollivier-ricci curvature and the spectrum of the normalized graph laplace operator, 2013.
  * [2] D. Cushing, S. Kamtue, J. Koolen, S. Liu, F. Münch, and N. Peyerimhoff.  Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature.  Adv. Math., 369:107188, 53, 2020.
  * [3] David Cushing, Supanat Kamtue, Riikka Kangaslampi, Shiping Liu, and Norbert Peyerimhoff.  Curvatures, graph products and Ricci flatness.  J. Graph Theory, 96(4):522–553, 2021.
  * [4] Karel Devriendt and Renaud Lambiotte.  Discrete curvature on graphs from the effective resistance.  Journal of Physics: Complexity, 3(2):025008, 2022.
  * [5] Ruth Dunn, Frank Dudbridge, and Christopher M Sanderson.  The use of edge-betweenness clustering to investigate biological function in protein interaction networks.  BMC bioinformatics, 6:1–14, 2005.
  * [6] Lukas Fesser, Sergio Serrano de Haro Iváñez, Karel Devriendt, Melanie Weber, and Renaud Lambiotte.  Augmentations of forman’s ricci curvature and their applications in community detection.  arXiv preprint arXiv:2306.06474, 2023.
  * [7] Forman.  Bochner’s method for cell complexes and combinatorial ricci curvature.  Discrete & Computational Geometry, 29:323–374, 2003.
  * [8] Santo Fortunato.  Community detection in graphs.  Physics reports, 486(3-5):75–174, 2010.
  * [9] Santo Fortunato and Darko Hric.  Community detection in networks: A user guide.  Physics reports, 659:1–44, 2016.
  * [10] Adam Gosztolai and Alexis Arnaudon.  Unfolding the multiscale structure of networks with dynamical ollivier-ricci curvature.  Nature Communications, 12(1):4561, 2021.
  * [11] Vic Grout and Stuart Cunningham.  A constrained version of a clustering algorithm for switch placement and interconnection in large networks.  In CAINE, pages 252–257, 2006.
  * [12] Roger Guimera, Stefano Mossa, Adrian Turtschi, and LA Nunes Amaral.  The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles.  Proceedings of the National Academy of Sciences, 102(22):7794–7799, 2005.
  * [13] Prasad Krishna, Nitin H Vaidya, Mainak Chatterjee, and Dhiraj K Pradhan.  A cluster-based approach for routing in dynamic networks.  ACM SIGCOMM computer communication review, 27(2):49–64, 1997.
  * [14] John M Lee.  Introduction to Riemannian manifolds, volume 2.  Springer, 2018.
  * [15] Yong Lin, Linyuan Lu, and Shing-Tung Yau.  Ricci curvature of graphs.  Tohoku Mathematical Journal, Second Series, 63(4):605–627, 2011.
  * [16] Florentin Münch and Radosław K Wojciechowski.  Ollivier ricci curvature for general graph laplacians: heat equation, laplacian comparison, non-explosion and diameter bounds.  Advances in Mathematics, 356:106759, 2019.
  * [17] Chien-Chun Ni, Yu-Yao Lin, Feng Luo, and Jie Gao.  Community detection on networks with ricci flow.  Scientific reports, 9(1):9984, 2019.
  * [18] Morton E O’Kelly.  A clustering approach to the planar hub location problem.  Annals of Operations Research, 40(1):339–353, 1992.
  * [19] Yann Ollivier.  Ricci curvature of markov chains on metric spaces.  Journal of Functional Analysis, 256(3):810–864, 2009.
  * [20] Owen Queen, Gavin A McCarver, Saitheeraj Thatigotla, Brendan P Abolins, Cameron L Brown, Vasileios Maroulas, and Konstantinos D Vogiatzis.  Polymer graph neural networks for multitask property learning.  npj Computational Materials, 9(1):90, 2023.
  * [21] Alexander W Rives and Timothy Galitski.  Modular organization of cellular networks.  Proceedings of the national Academy of sciences, 100(3):1128–1133, 2003.
  * [22] Jayson Sia, Edmond Jonckheere, and Paul Bogdan.  Ollivier-Ricci curvature-based method to community detection in complex networks.  Scientific reports, 9(1):9800, 2019.
  * [23] Victor Spirin and Leonid A Mirny.  Protein complexes and functional modules in molecular networks.  Proceedings of the national Academy of sciences, 100(21):12123–12128, 2003.
  * [24] Yu Tian, Zachary Lubberts, and Melanie Weber.  Curvature-based clustering on graphs.  arXiv preprint arXiv:2307.10155, 2023.
  * [25] Yu Tian, Zachary Lubberts, and Melanie Weber.  Mixed-membership community detection via line graph curvature.  In NeurIPS Workshop on Symmetry and Geometry in Neural Representations, pages 219–233. PMLR, 2023.
  * [26] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein.  Understanding over-squashing and bottlenecks on graphs via curvature.  arXiv preprint arXiv:2111.14522, 2021.
  * [27] Melanie Weber, Emil Saucan, and Jürgen Jost.  Characterizing complex networks with forman-ricci curvature and associated geometric flows.  Journal of Complex Networks, 5(4):527–550, 2017.