remarkRemark hypothesisHypothesis claimClaim Augmented Forman-Ricci curvature
and community detectionL. Fesser, S. Serrano, K. Devriendt, M. Weber, and R.
Lambiotte

$\mathsection$$\mathsection$footnotetext: Joint first authors.

# Augmentations of Forman’s Ricci Curvature and their Applications in
Community Detection

Lukas Fesser§ Harvard University, Cambridge, MA. Sergio Serrano de Haro
Iváñez§ University of Oxford, Oxford, UK. Karel Devriendt Max Planck Institute
for Mathematics in the Sciences, Leipzig, Germany. Melanie
Weber11footnotemark: 1 Renaud Lambiotte22footnotemark: 2

###### Abstract

The notion of curvature on graphs has recently gained traction in the networks
community, with the Ollivier-Ricci curvature (ORC) in particular being used
for several tasks in network analysis, such as community detection. In this
work, we choose a different approach and study augmentations of the
discretization of the Ricci curvature proposed by Forman (AFRC). We
empirically and theoretically investigate its relation to the ORC and the un-
augmented Forman-Ricci curvature. In particular, we provide evidence that the
AFRC frequently gives sufficient insight into the structure of a network to be
used for community detection, and therefore provides a computationally cheaper
alternative to previous ORC-based methods. Our novel AFRC-based community
detection algorithm is competitive with an ORC-based approach. The codebase
for fast and efficient computations of AFRC and the experiments in this
article will be made publicly available upon publication.

###### keywords:

Discrete Curvature, Network Analysis, Community Detection

05C82, 05C10, 53C21, 68R10, 05C75

##  1 Introduction

Curvature is a key notion in differential geometry, and Ricci curvature is one
of several ways of formalizing it. Intuitively, Ricci curvature measures the
deformation of a small ball as we push it along a geodesic (the shortest path
between two points), and quantifies how much a shape locally differs from
standard, flat Euclidean space. As Ricci curvature encapsulates essential
information in differential geometry and related fields (e.g. it is a term of
Einstein’s field equations in general relativity), there have been multiple
attempts to profitably extend its definition to other domains.

The structural insight gained via discrete Ricci curvature has proven valuable
for applications in Network Science and Machine Learning. Discrete Ricci
curvature relates to many classical network characteristics and network
analysis tasks [37] and, as a result, has been applied for the analysis of
network data in many domains, including biological networks [31, 39], chemical
networks [16] and financial transaction networks [25], among others. In
Machine Learning, discrete curvature has been utilized to characterize and
mitigate the oversquashing effect in Graph Neural Networks [34] and to
identify embedding spaces in Representation Learning [36].

The two curvature versions studied in this paper are respectively due to
Ollivier [20, 21] and Forman [11]. Ollivier-Ricci curvature (ORC) is a direct
discretization of the original definition, substituting spheres and geodesics
by, respectively, node neighborhoods and shortest edge-paths. The construction
of Forman-Ricci curvature (FRC) takes a different approach: it follows from
Bochner’s method [3, 4, 5], which in the differential case is used to write
the Laplacian as the sum of a Laplacian-like term and a term that depends on
the Ricci curvature. Forman’s work consists in discretizing both the Laplacian
and Bochner’s method, which produces a term that, by analogy, can be
interpreted as a discrete Ricci curvature. Thus, ORC and FRC are two measures
with solid geometric foundations yet presenting significant differences, which
makes them two potential ways of gaining a better understanding of the
geometry of networks.

Here, we focus on geometric approaches to community detection, which have been
previously considered using ORC [13, 19, 28, 33]. Community structure, i.e.
the mesoscale organization of a network into groups of nodes with similar
connections, is widely observed in real-world networks and its detection is a
classical problem in the study of networks and graphs [1, 23]. Community
detection using ORC relies on the observation that positively curved edges
tend to be well connected, and hence naturally lie inside communities.
Negatively curved edges, on the other hand, can be interpreted as bridges
between communities. ORC-based community detection algorithms have been found
to perform well on both synthetic and real-world networks. These methods are,
however, computationally expensive as the definition of ORC involves the
computation of network flows of shortest paths via the Wasserstein distance,
which has cubic complexity and is often approximated via the (quadratic)
Sinkhorn algorithm [6].

One advantage of FRC over ORC is its significantly smaller computational
complexity: in its simplest form, the FRC of an edge only depends on the
degrees of its end points. This is often too simple of a measure in practice,
and there have been several proposals to enrich the simple FRC by taking into
account the cycles that contain an edge [24, 27, 38] 111This operation is
reminiscent of measures for the density around an edge, which have been used
in Network Science, e.g. to test the strength of weak ties [22].. In this
article, we consider the augmented Forman-Ricci curvature (AFRC) introduced in
[27] and study how different augmentations affect the balance between
expressivity and computational complexity in the context of community
detection. Based on this evaluation, we identify classes of graphs in which
AFRC-based community detection can be recommended compared with ORC-based
detection.

The main contributions in this article are

  * •

We make a detailed empirical and theoretical investigation of the
augmentations of Forman-Ricci curvature.

  * •

We discuss the relation of augmented Forman-Ricci curvature to Ollivier-Ricci
curvature and un-augmented Forman-Ricci curvature.

  * •

We provide evidence that AFRC distinguishes communities in a manner comparable
to ORC for many model and real-world networks.

  * •

We introduce a novel AFRC-based community detection algorithm, with comparable
performance to existing ORC-based methods while being computationally cheaper.

  * •

We develop the first codebase for fast and efficient computations with
augmentations of the Forman-Ricci curvature.

The rest of this paper is structured as follows: Section 2 formally introduces
ORC, FRC, its augmentations, and possible approximations. Section 3 studies
how the different curvatures are related in real-world and artificial
networks. Section 4 studies the curvature gap – a quantitative indicator for
how well a curvature can distinguish between edges within and between
communities – for the ORC, FRC, and AFRC. Section 5 introduces our AFRC-based
community detection algorithm and demonstrates its performance on several
model and real-world networks. Section 6 concludes the article with a summary
of the main findings.

##  2 Curvature definitions

Ricci curvature is a central tool in differential geometry that characterizes
the local geometric properties of geodesic spaces by relating the local rate
of volume growth to geodesic dispersion. Several discretizations of Ricci
curvature have been proposed, including notions by Forman [11], Ollivier [20,
21], Erbar and Maas [10], Bakry and Émery [2], and Devriendt and Lambiotte
[8]. In this paper, we focus on edge-level Ollivier and Forman curvature. For
the latter, we analyze _augmented_ Forman curvature, which explicitly encodes
the impact of cycles that contain the respective edge. Variants of augmented
Forman curvature have been previously studied in [15, 24, 38], among others.

###  2.1 Ollivier-Ricci curvature

Ollivier introduced a notion of discrete Ricci curvature for metric spaces in
[20]; this setting includes graphs with the shortest-path metric between
vertices. Aside from a metric, Ollivier’s curvature also requires a choice of
probability distributions $\mu_{v}$ – one for each vertex $v$ in the case of a
graph – which can be thought of as open balls around points in the space. A
common choice for graphs is the uniform distribution over the neighbors
$\text{neigh}(v)$ of a vertex [28, 33]

$\displaystyle\mu_{v}(w):=\left\\{\begin{array}[]{cl}\frac{1}{\deg(v)}&\text{if
}w\in\text{neigh}(v)\\\\[5.0pt] 0&\text{else}\end{array}\right.,$

where $\deg(v)=|\text{neigh}(v)|$ is the number of neighbors of $v$. With this
data, the _Ollivier-Ricci curvature_ (ORC) $\mathcal{O}(e)$ of an edge
$e=(v_{1},v_{2})$ is defined as

$\mathcal{O}(e):=1-\frac{W_{1}(\mu_{v_{1}},\mu_{v_{2}})}{d(v_{1},v_{2})},$

where $d$ is the shortest-path distance between vertices and $W_{1}$ denotes
the Wasserstein distance (also called earth mover’s distance in discrete
settings) between measures on a metric space; see [20, 21] for details.

Geometrically, the ORC compares the distance between the end points of an edge
to the distance between balls at the end points of the edge. If $v_{1}$ and
$v_{2}$ share many neighbors or have many edges between their neighborhoods,
the distance between $\mu_{v_{1}}$ and $\mu_{v_{2}}$ will be small and so
$\mathcal{O}(e)\approx 1$. On the other hand, if the neighborhoods of $v_{1}$
and $v_{2}$ are poorly connected, the distance between $\mu_{v_{1}}$ and
$\mu_{v_{2}}$ will be large and $\mathcal{O}(e)$ will be small and potentially
negative. In the context of community structure in a network (see Section 4),
this explains why we expect larger ORC within a community than between
communities: the neighborhoods of two vertices at the end of an edge are
better connected within than between communities.

###  2.2 Forman-Ricci curvature and augmentations

Forman developed a notion of discrete Ricci curvature for weighted CW
complexes in [11] in the context of algebraic topology. A CW complex is a type
of topological space that includes undirected graphs as a one-dimensional
case. A direct translation of Forman’s definition to unweighted graphs without
multi-edges, as derived in [29], gives the Forman-Ricci curvature (FRC)
$\mathcal{F}(e)$ of an edge $e=(v_{1},v_{2})$

(1) $\displaystyle\mathcal{F}(e):=4-\deg(v_{1})-\deg(v_{2}).$

While this definition is well-supported by Forman’s work and easy to
calculate, it is too simple a measure for many practical and theoretical
purposes. For instance, $\mathcal{F}(e)$ does not depend on the number of
triangles in which $e$ is contained, which is an important local geometric
property of graphs [14].

To overcome the limitations of the simple formula for FRC, definition (1) can
be extended to take into account more of the graph structure around a given
edge. The idea is to start from the graph and add solid 2D faces in the spaces
enclosed by cycles; see Figure 1 for an illustration. This “augmented graph”
is still a CW complex – the new faces are two-dimensional cells with one-
dimensional boundaries given by the cycles – and one can apply Forman’s
original definition to get a discrete curvature for edges that also depends on
the cycles that contain an edge. The following formula for the _augmented
Forman-Ricci curvature_ (AFRC)
$\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}}(e)$ of an edge $e$ was derived in [27] based on Forman’s
definition [11, Thm. 2.2]:

(2) $\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}}(e)=2+\Gamma_{ee}-\sum_{e^{\prime}\sim
e}\left|\Gamma_{ee^{\prime}}+\Gamma_{e^{\prime}e}-1\right|-\sum_{e^{\prime}\not\sim
e}|\Gamma_{ee^{\prime}}-\Gamma_{e^{\prime}e}|,$

where $e\sim e^{\prime}$ (resp. $e\not\sim e^{\prime}$) denotes two distinct
edges that share (resp. do not share) a vertex, and where $\Gamma$ is a matrix
(defined in (3) below) of size equal to the number of edges and whose entries
count the cycles that contain $e$ and $e^{\prime}$. The counting goes as
follows: a cycle is a sequence of vertices $\gamma=v_{1}v_{2}\dots v_{\ell}$
such that all cyclically consecutive vertices are connected by an edge in the
graph. Now fix an arbitrary order on the vertices of the graph. Two edges
$e,e^{\prime}$ are called _aligned_ in $\gamma$ if the cycle traverses both
edges from smallest to largest vertex (with respect to the order) or both from
largest to smallest vertex. The entries of $\Gamma$ are then defined as

(3) $\displaystyle\Gamma_{ee^{\prime}}$ $\displaystyle:=\begin{cases}\text{\\#
cycles in which $e$ and $e^{\prime}$ are aligned}\quad\text{(if
$e<e^{\prime}$)}\\\ \text{\\# cycles in which $e$ and $e^{\prime}$ are not
aligned}\quad\text{(if $e>e^{\prime}$)}\end{cases}$ $\displaystyle\Gamma_{ee}$
$\displaystyle:=\text{\\# cycles that contain $e$}.$

Here, the order $e<e^{\prime}$ on edges follows from the order on the
vertices222If we think of an edge as a two-letter word with letters in the
(ordered) alphabet of vertices, the induced order on the edges is simply the
familiar alphabetical order on the words. See Appendix B for an example., and
we note that the value of
$\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}}(e)$ is independent of the choice of vertex order. Figure 1
illustrates (non-)alignment of edges in a cycle and the resulting distinction
between $\Gamma_{ee^{\prime}}$ and $\Gamma_{e^{\prime}e}$. This distinction is
necessary when translating Forman’s definition, since it relies on oriented 2D
faces. We note that when calculating
$\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}}$ for all edges, the count matrix $\Gamma$ only needs to be
constructed once, by iterating over all cycles in the graph. Appendix B
contains a detailed example with the above definitions.

Figure 1: (a) Example of Forman-Ricci curvature. The edge $e=(1,2)$ has FRC
equal to $\mathcal{F}(e)=4-\deg(1)-\deg(2)=-5$. (b) Example of augmented
Forman-Ricci curvature. The edge $e$ is contained in the cycles
$\gamma_{1}=1234$ and $\gamma_{2}=125$ and the AFRC of $e$ is equal to
$\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}}(e)=2+2-3-1=0$. This augmentation arises from including
faces corresponding to $\gamma_{1}$ and $\gamma_{2}$ and then applying
Forman’s formula to the resulting 2D complex. This example is worked out in
detail in Appendix B. (c) Let the vertices be ordered as $1<2<3<4$ and thus
$e=(1,2)<(3,4)=e^{\prime}$. The edges $e,e^{\prime}$ are contained in cycles
$\gamma_{3}=1234$ and $\gamma_{4}=1243$. In $\gamma_{3}$ both edges are
traversed from the small to large vertex ($1\rightarrow 2$ and $3\rightarrow
4$), so they are aligned and $\Gamma_{ee^{\prime}}=1$. In $\gamma_{2}$ edge
$e$ is traversed from small to large ($1\rightarrow 2$) while edge
$e^{\prime}$ is traversed from large to small ($4\rightarrow 3$), so the edges
are not aligned in $\gamma_{4}$ and $\Gamma_{e^{\prime}e}=1$.

In definition (2) we may choose to only take a subset of all cycles into
account; in particular, we will consider the following class of curvatures:

$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{n}}(e):=\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}}(e)\text{\leavevmode\nobreak\ taking into
account all cycles of length at most $n$.}$

Restricting AFRC to cycles up to a certain length is supported by the idea
that Ricci curvature should be a local property. This is also satisfied by
other notions of discrete curvature such as ORC and Bakry-Émery curvature,
which only depend on cycles of length $n\leq 5$. In this article we mainly
work with $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{n}}$ with $n\in\\{3,4\\}$, which are the first
augmentations of FRC that give a non-trivial improvement over FRC in a number
of applications while still being computationally efficient; in addition to
being more expensive, we have found
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{5}}$ to be less effective in community detection – see
Appendix Figures 7 and 8. We believe the poorer performance is due to the
higher number of 5-cycles that contain between-community edges, which blurs
the curvature difference between inter- and intra-community edges.

For certain choices of cycles, definition (2) for the AFRC reduces to known
extensions of FRC. For instance, the curvature
$\mathcal{F}(e)+3\cdot\\#\\{\text{3-cycles $\ni
e$}\\}=\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}(e)$ was proposed in [24] as a more expressive variant
of Forman’s curvature in graphs and networks. In [32, 38], it was observed
that in graphs where any two cycles share at most one edge – these graphs are
called quasi-convex in [11] and independent short-cycle graphs in [32] –,
Forman’s curvature simplifies to $\mathcal{F}(e)+\sum_{n\geq
3}(6-n)\cdot\text{\\#$\\{\text{$n$-cycles}\ni e\\}$}$. This expression can
provide a simple estimate for edges whose neighborhoods are expected to be
“almost quasi-convex”, but in general it differs from AFRC. In [15], Jost and
Münch studied different choices of weighted cycles when augmenting a graph.

Finally, we note that equation (2) can be written explicitly as an
augmentation of FRC as follows:

(4) $\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern
0.5mu}\mathcal{F}}(e)=\mathcal{F}(e)-\Gamma_{ee}+2\cdot\sum_{e^{\prime}\sim
e}\min\\{(\Gamma_{ee^{\prime}}+\Gamma_{e^{\prime}e}),1\\}-\sum_{e^{\prime}\not\sim
e}|\Gamma_{ee^{\prime}}-\Gamma_{e^{\prime}e}|.$

Here the second term again counts the number of cycles that contain $e$, the
third term counts the number of edges $e^{\prime}\sim e$ that share a cycle
with $e$ and the fourth term again counts the aligned and unaligned cycles
through $e$ and $e^{\prime}\not\sim e$.

Equation (4) reveals how the addition of cycles affects the value of AFRC
compared to FRC. Including cycles of length $3$, we find that
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}(e)=\mathcal{F}(e)+3\cdot\\#\\{\text{$3$-cycles $\ni
e$}\\}$ and thus that AFRC is higher for edges whose end points share many
neighbors. In networks with community structure, we thus expect
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ to be large within communities and small (possibly
negative) between communities, similar to ORC. Including cycles of length $4$
and above, however, we expect a different behavior. Now the positive term in
(4) due to the neighbors of $e$ is limited by the degrees of the end points of
$e$, while the negative terms ($\Gamma_{ee}$ and the sum over non-neighbors)
can become increasingly negative as more cycles are included. As a result, we
can expect edges within communities to have _lower_
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{n\geq 4}}$ values compared to edges between, opposite to
what is observed for ORC and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$. In later experiments on networks with
community structure, we confirm this analysis. Finally, we note that un-
augmented FRC does not distinguish edges within and between communities when
different communities have the same typical degrees.

##  3 Correlations between curvatures

Since ORC and AFRC are discretizations of the same smooth concept, their
comparison is a natural and important question.

On the theoretical side, [32] found evidence that ORC and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{5}}$ are equivalent in quasi-convex graphs and [15] found
that the maximal Forman curvature over all weighted augmentations of a graph
is equal to ORC. In general, the relation between different notions of
discrete curvature remains an important open question.

On the experimental side, Samal et al [24] extensively studied the correlation
between ORC and both FRC and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ in model and real-world networks. In
their results, ORC tended to greatly correlate with both Forman-Ricci
curvature versions, and it generally correlated higher with the augmentation.
We extend this study here by including correlations of these curvatures with
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$. Tables 1 and 2 show the Pearson correlation
coefficient between the different curvature measures in, respectively, model
and real-world networks.

Model networks: We study four different network models: the Erdős-Rényi (ER)
graph, which is a completely homogeneous model and should not exhibit a clear
community structure; a bipartite version (BG), which does not contain any
3-cycles and thus
$\mathcal{F}(e)=\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}(e)$ for all edges; and the stochastic block model
(SBM) and hierarchical bipartite graph (HBG), which do have well-defined
communities. Details on these network models can be found in Appendix A.

Table 1 shows that the FRC vs $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ correlations exhibit the expected behavior for model
networks: the fewer edges – and thus cycles – present in a network, the more
similar the curvatures are (as they are equal in a network with no cycles). In
particular, note the correlation of 1 between FRC and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ for the bipartite networks – as expected from
networks with no 3-cycles. The only outlier of this behavior is the HBG, as
the correlation FRC vs $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ seems to increase with the number of
edges.

Regarding ORC vs the different versions of AFRC, all exhibit a similar
behavior on the ER and BG graphs, being quite correlated in sparser networks
and losing this correlation as the connection probability $p$ increases –
although in general ORC appears best correlated to
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$. This same behavior can be observed in the
correlation of ORC and FRC for the SBM, but the ORC vs the two studied
augmentations of Forman-Ricci curvature are notably distinct. We observe how
the correlation ORC vs $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ increases positively with the community
sizes, whereas ORC vs $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ grows negatively with it. This behavior
agrees with our discussion at the end of Section 2, and is illustrated later
in Figure 3. Finally, the ORC vs
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ for the HBG initially shows a similar behavior, but
we see that they become uncorrelated as $q$ grows (and $p$ is held fixed). We
will further explore this last effect in Section 4, where we show that ORC
does not appear to detect communities in HBGs with noisy structure.

Network | OR, FR | OR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ | OR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ | FR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ | FR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$
---|---|---|---|---|---
ER($1000$, $0.003$) | 0.84 | 0.87 | 0.87 | 0.99 | 0.98
ER($1000$, $0.007$) | 0.42 | 0.48 | 0.59 | 0.98 | 0.94
ER($1000$, $0.01$) | -0.01 | 0.12 | 0.30 | 0.98 | 0.89
SBM($10$, $5$, $0.7$, $0.05$) | 0.27 | 0.79 | 0.76 | 0.64 | 0.59
SBM($10$, $10$, $0.7$, $0.05$) | 0.07 | 0.83 | -0.66 | 0.49 | 0.31
SBM($10$, $15$, $0.7$, $0.05$) | 0.08 | 0.90 | -0.84 | 0.28 | 0.19
SBM($10$, $20$, $0.7$, $0.05$) | -0.03 | 0.90 | -0.91 | 0.33 | 0.19
BG($50$, $0.03$) | 0.74 | 0.74 | 0.84 | 1.0 | 0.91
BG($50$, $0.07$) | 0.01 | 0.01 | 0.58 | 1.0 | 0.69
BG($50$, $0.1$) | 0.29 | 0.29 | 0.27 | 1.0 | 0.79
HBG($50$, $0.5$, $0.05$) | -0.01 | -0.01 | -0.72 | 1.0 | 0.55
HBG($50$, $0.5$, $0.1$) | -0.11 | -0.11 | -0.25 | 1.0 | 0.61
HBG($50$, $0.5$, $0.15$) | -0.01 | -0.01 | 0.00 | 1.0 | 0.74
Table 1: Comparison of Ollivier-Ricci curvature (OR) with Forman-Ricci curvature (FR) and augmentations of the Forman-Ricci curvature ($\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$) of edges in artificial networks. In this table, we list the Pearson correlation between the edge curvatures. Network | OR, FR | OR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ | OR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ | FR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ | FR, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$
---|---|---|---|---|---
Dolphin | 0.08 | 0.75 | -0.15 | 0.25 | 0.77
Power Grid | 0.48 | 0.72 | 0.61 | 0.82 | 0.89
Word Adjacency | -0.04 | 0.18 | -0.24 | 0.89 | 0.89
Southern Women | 0.47 | 0.47 | -0.01 | 1.0 | 0.71
Corporate Interlocks | 0.48 | 0.48 | -0.05 | 1.0 | 0.64
Karate Club | 0.56 | 0.81 | 0.58 | 0.62 | 0.84
College Football | -0.09 | 0.94 | -0.76 | -0.07 | 0.37
School 1 | -0.01 | 0.84 | -0.26 | 0.38 | 0.94
School 2 | 0.02 | 0.81 | -0.27 | 0.36 | 0.92
Table 2: Comparison of Ollivier-Ricci curvature (OR) with Forman-Ricci
curvature (FR) and augmentations of the Forman-Ricci curvature
($\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$) of edges in real-world networks. In
this table, we list the Pearson correlation between the edge curvatures.

Real-world networks: We study a variety of networks, including two bipartite
(Southern Women and Corporate Interlocks) and four with community structure
metadata (second half of Table 2). All networks have between 10 and 250 nodes,
except for the US Power Grid, which has around 5000. Detailed descriptions of
the networks can be found in Appendix A.

As seen in Table 2, all networks without a baseline community structure
(except for the Power Grid) exhibit similar curvature behaviors. The main
observation is that ORC and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ are slightly negatively correlated, an
effect we only observe in the models with an underlying community structure.
On the other hand, the Power Grid network behaves akin to the ER, with all
curvatures moderately correlated. We believe this is related to the network
being substantially sparser (average degree $\sim 1.3$) and with few 3- and
4-cycles (651 and 979, respectively), which causes all curvatures to behave
similarly.

Regarding the networks with ground-truth community structure, all but the
Karate Club show a positive (resp. negative) correlation between ORC and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ (resp.
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$), as expected. We attribute the different behavior of
the Karate Club to the fact that its ground-truth community structure is
slightly blurred in the context of network analysis, which is reflected by the
relatively low ratio $\hat{p}/\hat{q}\approx 6.57$, where $\hat{p}$ and
$\hat{q}$ are estimates of the probabilities of edges forming within or
between communities, respectively. By comparison, this ratio is about $19.51$
in the College Football network. We obtain these estimates by dividing the
number of edges within (between) communities by the number of possible edges.
For the Karate Club and School networks, we note that
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ is much more highly correlated to FRC than ORC, while
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ exhibits the converse behavior. This could be an
indicator that in these cases the simpler augmentation
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ is better for community detection, as ORC is
expectedly effective in detecting community structure whereas FRC is not.

To give a summary of our correlation results, we have experimentally verified
the discussion of Section 2. In particular, we have shown how the amount of
edges and cycles of a network have different effects on the various versions
of Forman-Ricci curvature, and we have also provided evidence for the expected
behaviors of the different curvatures in networks with an underlying community
structure. The high correlation between ORC and different versions of AFRC are
a first indication that the latter have a potential use in community
detection; our results also suggest that the effectiveness of the different
augmentations may depend on the characteristics of the network.

##  4 Curvature gaps

In this section we compare the performance of the studied curvatures in
community detection – both for model and real-world networks with an
underlying community structure.

The essential observation for ORC-based community detection, as discussed in
Section 2 and used for instance in [28], is that the ORC of edges within a
community tends to be higher than the ORC of edges between communities. As a
consequence, the histogram of curvature values in a network with community
structure tends to be bimodal with two separate peaks or clusters. Figure 2
shows this effect for $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ in two graphs with a clear community
structure. Figure 3 furthermore shows that the clusters in the histogram
become more pronounced as the community structure becomes stronger. One way to
quantify the separation between the two clusters is the curvature gap,
introduced in [13]. Given a partition of a network into communities, let
$\kappa_{\text{within}}$ denote the average curvature of all edges contained
in a single community, $\kappa_{\text{between}}$ the average curvature of
edges between communities, and $\sigma_{\text{within}},\
\sigma_{\text{between}}$ the standard deviation of the respective curvatures.
The curvature gap of this partition of the network is defined as

$\Delta\kappa:=\frac{1}{\sigma}\left|\kappa_{\text{within}}-\kappa_{\text{between}}\right|$

where
$\sigma=\sqrt{\frac{1}{2}\left(\sigma_{\text{within}}^{2}+\sigma_{\text{between}}^{2}\right)}$.
Intuitively, the resulting number can be interpreted as ‘the number of
standard deviations between the mean curvatures’. Since the curvature gap
reflects how well the curvature distinguishes edges within and between
communities, we will use it as a proxy for how well any given curvature
detects the community structure. Tables 3 and 4 show the curvature gap
obtained from each curvature measure in model and real-world networks,
respectively. Importantly, these curvature gaps also depend on how clear the
community structure is in a graph (i.e. the ratio $p/q$ mentioned before, or
the size vs the number of the communities); this dependency is illustrated in
Figure 3 and Appendix Figures 7-10.

(a)

(b)

(c)

(d)

Figure 2: Distributions of the Augmented Forman-Ricci Curvature
($\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$) across edges in stochastic block models with weak
((a), SBM(2, 40, $0.5$, $0.2$)) and strong ((b), SBM(2, 40, $0.7$, $0.1$))
community structure. The curvature gap captures the (normalized) distance
between the means of the edges between (orange) and within (blue) communities.
(c) and (d) shows the corresponding networks with edges colored according to
curvature.

Figure 3: Distributions of $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ (top) and the Ollivier-Ricci Curvature
(bottom) for SBM(10, $k$, $0.7$, $0.05$) with $k\in\\{5,10,15,20\\}$ (from
left to right). As the community structure becomes more pronounced with larger
community sizes, the curvature gaps increase. Note also the “switch” in the
order of the within-community edges (blue) and the between-community edges
(orange) in the AFRC histograms.

Model networks: We study two network models with a predefined community
structure: the SBM and the HBG. The latter is particularly interesting because
its lack of triangles means that
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ no longer augments the FRC. In this case,
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ is the first non-trivial augmentation.

(a)

(b)

Figure 4: Distributions of $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ in (a) and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ in (b) for a HBG(40, 0.7, 0.05).

As discussed in Section 2, FRC should not be able to detect communities, which
is confirmed by the very poor curvature gap observed in Table 3 for both
models. Similarly as expected, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ performs poorly detecting communities
in bipartite networks. This is also illustrated in Figure 4.

On the other hand, ORC attains good curvature gaps. As noted, we observe that
the gap depends on how clear the community structure is: it decreases when we
reduce the number of inside-community edges or increase the number of between-
community edges; moreover, the gap increases with the size of the communities
of the SBM. Finally, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ (and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ for the unipartite model) performs similarly to ORC:
it shows a relevant gap in all the studied models, which also depends on the
clearness of the community structure. We observe how ORC and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ tend to perform similarly and outperform
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ in the studied SBMs (although the latter still
attains curvature gaps of a similar magnitude), whereas in the studied HBGs
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ attains relevant curvature gaps even in the cases
where ORC performs poorly.

Real-world networks: Next, we study the curvature gap in a range of real-world
network with a known community structure. We remark that all networks studied
in this section are unipartite.

As with the model networks, FRC performs poorly in all of the studied
networks, and both ORC and the augmentations of FRC offer more relevant
curvature gaps; $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ offers the best overall performance in our network
sample, and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ performs worst (see Table 4). Similarly to Section 3,
the higher the $\hat{p}/\hat{q}$ ratio of the ground-truth communities, the
bigger the curvature gap: the Football network ($\hat{p}/\hat{q}\approx
19.51$) presents a substantial curvature gap for both ORC and the FRC
augmentations, whereas for the Karate ($\hat{p}/\hat{q}\approx 6.57$) and
School networks ($\hat{p}/\hat{q}\approx 5.89$ and $\approx 6.76$, resp.) the
curvature gaps are smaller – notably,
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ offers a curvature gap comparable (and in some cases
even smaller) to that of FRC. We remark this as an example of how further
augmentations of AFRC do not always improve the effectiveness of the community
detection. We believe this could be the same effect we observed for
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{5}}$: in networks with low $\hat{p}/\hat{q}$, the inter-
and intra-community edges are contained in a number of 4-cycles similar enough
that the two curvature distributions overlap significantly.

To summarize the experimental results on the curvature gap, we have seen that
plain FRC is not able to detect community structure – which was theoretically
expected – whereas both its augmentations and ORC do. The performance of all
curvatures depends on how strongly pronounced the community structure is, but
the characteristics of each network have different effects on the various
curvature versions. In particular, we have found that ORC and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ tend to outperform
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ in unipartite networks, which suggests
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ as the better (in terms of performance/cost)
alternative for curvature based-community detection for this type of network.
On the other hand, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$ seems the most effective in the study
of bipartite networks. In the following section we further discuss the
performance in community detection of these curvature measures, both in terms
of accuracy and computational cost.

Network | OR | FR | $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ | $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$
---|---|---|---|---
SBM ($10$, $5$, $0.7$, $0.05$) | 2.14 | 0.58 | 1.93 | 1.34
SBM ($10$, $10$, $0.7$, $0.05$) | 3.30 | 0.35 | 3.54 | 1.88
SBM ($10$, $15$, $0.7$, $0.05$) | 4.10 | 0.33 | 4.02 | 3.31
SBM ($10$, $20$, $0.7$, $0.05$) | 4.92 | 0.23 | 4.61 | 4.33
SBM ($10$, $20$, $0.5$, $0.05$) | 2.66 | 0.16 | 2.16 | 2.01
SBM ($10$, $20$, $0.3$, $0.05$) | 0.97 | 0.07 | 0.79 | 0.44
SBM ($10$, $20$, $0.1$, $0.05$) | 0.06 | 0.18 | 0.17 | 0.15
HBG ($50$, $0.5$, $0.05$) | 3.83 | 0.19 | 0.19 | 4.77
HBG ($50$, $0.5$, $0.1$) | 0.40 | 0.12 | 0.12 | 3.05
HBG ($50$, $0.5$, $0.15$) | 0.03 | 0.16 | 0.16 | 1.62
HBG ($50$, $0.4$, $0.1$) | 0.62 | 0.06 | 0.06 | 1.69
HBG ($50$, $0.3$, $0.1$) | 0.83 | 0.14 | 0.14 | 0.76
HBG ($50$, $0.2$, $0.1$) | 0.27 | 0.07 | 0.07 | 0.09
Table 3: Comparison of curvature gaps attained by Ollivier-Ricci curvature (OR), Forman-Ricci curvature (FR), and augmentations of the Forman-Ricci curvature ($\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$) of edges in artificial networks with community structure. Network | OR | FR | $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ | $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$
---|---|---|---|---
Karate | 1.01 | 0.31 | 0.94 | 0.43
College Football | 2.95 | 0.34 | 2.87 | 2.91
School 1 | 1.16 | 0.74 | 1.78 | 0.57
School 2 | 1.04 | 0.85 | 1.72 | 0.65
Table 4: Comparison of curvature gaps attained by Ollivier-Ricci curvature
(OR), Forman-Ricci curvature (FR), and augmentations of the Forman-Ricci
curvature ($\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ and $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$) of edges in real-world networks.

##  5 Community-detection via sequential edge-deletion

We proceed by analogy with the Girvan-Newman method and with the ORC-based
community detection method proposed in [28], in that we incrementally delete
edges to disconnect the network. We provide pseudo-code of the algorithm in
Algorithm 1.

Our algorithm can be divided into the following steps: given a simple,
unweighted, and undirected graph $G(V,E)$, (i) calculate the AFRC for all
edges in the network, (ii) based on the AFRC distribution, choose a curvature
threshold $\Delta$, (iii) remove the most positive AFRC edge, (iv) re-compute
the edge AFRC only for those edges affected by the removal, (v) check if all
AFRCs are below $\Delta$, otherwise repeat steps (iii) and (iv) until the
condition is satisfied. It is clear that our algorithm must terminate in at
most $|E|$ steps, as there will be no more edges to delete – for a sensible
threshold such as the low-point between the modes in the AFRC histogram, it
will in fact terminate much sooner. To choose the threshold $\Delta$, we fit
two Gaussians $\mathcal{N}_{1}(\mu_{1},\sigma_{1})$, and
$\mathcal{N}_{2}(\mu_{2},\sigma_{2})$ to the curvature distribution and then
compute
$\Delta=\frac{\sigma_{2}}{\sigma_{1}+\sigma_{2}}\mu_{1}+\frac{\sigma_{1}}{\sigma_{1}+\sigma_{2}}\mu_{2}$,
based on the minimum-error decision boundary between these Gaussians [9, Ch.
2.6].

Algorithm 1 AFRC Community Detection Algorithm

A graph $G(V,E)$ and a threshold $\Delta$

A list of tuples $(v,l)$, with vertices $v$ and labels $l$

For all $e\in E$, compute $\text{AFRC}(e)$

while there exists an edge with AFRC $>\Delta$ in $G$ do

if there is a unique edge $e_{\text{max}}$ with maximal AFRC then

remove $e_{\text{max}}$ from $G$

else

choose an edge $e_{\text{min}}$ from the edges with maximal

AFRC uniformly at random and remove it from $G$

end if

re-calculate the AFRC for all affected edges in $G$

end while

assign the same label $l$ to each vertex $v$ in a connected component of $G$

return a list of tuples $(v,l)$

In general, it is possible to use a priori knowledge of a network to choose an
appropriate augmentation of the Forman curvature to detect communities in a
computationally efficient way, but with accuracy similar to that achieved
using the ORC. For example, as proposed in Section 4, for unipartite, SBM-like
networks with relatively clear community structure (i.e. large ratio
$\hat{p}/\hat{q}$), we can use the
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ in Algorithm 1. Note that in this case, the while
loop in Algorithm 1 changes to while there exists an edge with AFRC $<\Delta$,
and we are looking for the edges with minimal AFRC. As Figure 5 shows, the
accuracy of this method is comparable to that of the ORC-based method (panel
(a)), while being orders of magnitude faster to run (panel (b)).

For networks which we suspect to be (approximately) bipartite, we can include
the 4-cycles, which makes Algorithm 1 more costly to run. However, as can be
seen in Figure 5, panels (c) and (d), this is still significantly faster than
using the ORC, while being competitive in terms of accuracy.

(a)

(b)

(c)

(d)

Figure 5: Mean accuracy (percentage of correctly identified communities) and
standard deviation (shaded areas) of ORC-based (red) and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$-based community-detection (blue) in (a), and the time
required for the algorithm to terminate (in seconds) in (b) for an SBM with
parameters $(10,k,0.7,0.05)$. (c) and (d) depict the same using the
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{4}}$ for a hierarchical bipartite graph with parameters
$(k+k,0.5,0.05)$

We conduct some additional experiments to compare the performance of Algorithm
1 for our three curvatures around the community detection threshold and refer
the reader to Appendix C (Figure 11 and Table 6) for details. We find that for
networks with few or no cycles within communities, all three curvatures yield
small curvature gaps, which makes community detection difficult or even
impossible. We quantify this using the notion of tree-SBMs, i.e. SBMs where
the communities are not Erdős-Rényi random graphs, but randomly chosen trees
with a small probability $p$ of having additional edges within communities.
For $p$ close to zero, only the ORC picks up on the emerging community
structure. As we increase $p$, and our tree-SBM becomes more similar to a
standard SBM, the augmentations of the Forman-Ricci curvature begin to also
yield increasingly large curvature gaps.

Similarly, we find that for standard SBMs where the probability $p$ of an edge
within a community is only marginally larger than the probability $q$ of an
edge between communities, the ORC yields larger curvature gaps and more
accurate community detection results than our augmentations of the Forman-
Ricci curvature. As we increase $p$, all three curvatures begin to yield
similarly good accuracies. This underlines the idea that for networks with a
particularly difficult community structure, especially in the very sparse
regime, the ORC is generally the best, and sometimes only, curvature for
community detection. In most cases, the augmentations of the Forman-Ricci
curvature give similarly good results, which together with their computational
efficiency makes them preferable to the ORC.

##  6 Conclusion

Discrete notions of curvature have recently become the subject of interest in
network science, both for theoretical investigations and in applications such
as community detection. Much of this interest has been focused on the
Ollivier-Ricci Curvature: to the best of our knowledge, all previous
curvature-based community-detection algorithms have used the ORC. While this
yields state-of-the-art results for many networks, it is also computationally
expensive and quickly becomes inapplicable for larger graphs.

In this work, we chose a different approach and provided a detailed study of
augmentations of the Ricci-curvature discretization proposed by Forman (AFRC).
We discussed the relation of these augmentations to the FRC and ORC both
empirically and theoretically – in particular, we provided evidence that in
many artificial and real-world networks, Augmented Forman-Ricci curvature can
be used to attain similar or even better community detection results than the
traditionally used Ollivier-Ricci curvature. Established Ollivier-Ricci
curvature-based algorithms for community detection are therefore not without
well-performing and computationally cheaper alternatives.

The advantages of AFRC over ORC in community detection suggest that the former
could represent important improvements in other areas where different discrete
curvature measures have already found an application – for instance network
embedding or graph learning. Moreover, the fact that AFRC and ORC behave
differently in the studied networks indicates that the former is not just a
computational improvement over the latter, but it also reflects different
geometric properties of networks. The augmentations proposed in this paper may
thus provide further insight into curvature-related problems, and create new
possibilities in contexts where other curvature measures are ineffective. For
instance, we found the augmentation based on 4-cycles to significantly
outperform ORC in community detection in bipartite networks, which opens
opportunities for the design of curvature-based methods for this kind of
networks.

##  Appendix A Studied networks

Model networks

  * •

Erdős-Rényi graph: Parameters $n\in\mathbb{N}$, $p\in[0,1]$. Network of $n$
nodes where each edge has an independent probability $p$ of being present. The
bipartite version consists on two groups of $n$ nodes, with the inter-group
edges having a probability $p$ of appearing.

  * •

Stochastic Block Model: Parameters $l,k\in\mathbb{N}$, $p,q\in[0,1]$, $q\leq
p$. Network of $l\cdot k$ nodes divided into $l$ groups (or communities) of
size $k$. Each edge between two nodes of a same community has an independent
probability $p$ of being present, and edges between communities appear with
independent probability $q$.

  * •

Tree Stochastic Block Model: Parameters $l,k\in\mathbb{N}$, $p,q\in[0,1]$.
Network created by first generating $l$ disconnected communities which are
random trees of size $k$. Then, each edge between two nodes of a same
community has an independent probability $p$ of being present, and edges
between communities appear with independent probability $q$.

  * •

Hierarchical Bipartite Graph: Parameters $n\in\mathbb{N}$, $p,q\in[0,1]$,
$q\leq p$. Bipartite network of $4n$ nodes divided into 2 communities, so that
each community has size $2n$ and contains $n$ nodes of each partition of the
network. Edges inside a community appear with independent probability $p$, and
edges between communities appear with independent probability $q$.

Real-world networks

Network | Nodes | Edges | Triangles | Squares | $\hat{p}/\hat{q}$
---|---|---|---|---|---
Dolphin [17] | 62 | 159 | 95 | 278 | -
Power Grid [35] | 4941 | 6594 | 651 | 979 | -
Word Adjacency [18] | 112 | 425 | 284 | 2579 | -
Southern Women [7] | 32 | 89 | 0 | 341 | -
Corporate Interlocks [26] | 244 | 358 | 0 | 245 | -
Karate Club [40] | 34 | 78 | 45 | 154 | $6.57$
College Football [12] | 115 | 613 | 810 | 3915 | $19.51$
School 1 [30] | 236 | 5899 | 48401 | 1678496 | $5.89$
School 2 [30] | 238 | 5539 | 46687 | 1560642 | $6.76$
Table 5: Summary of the studied real-world networks. The three sections
correspond respectively to networks without additional structure, bipartite
networks, and networks with community metadata.

##  Appendix B Example: computing
$\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}}(e)$ in a small graph

We revisit the example from Section 2 and calculate the FRC and AFRC of edge
$e=e_{12}=(1,2)$ in Figure 6.

Figure 6:

For the Forman-Ricci curvature (1), we only have to count the degrees of the
end points of edge $e_{12}$. These are $\deg(1)=4$ and $\deg(2)=5$ and thus we
obtain

$\mathcal{F}(e)=4-\deg(1)-\deg(2)=-5.$

For the augmented Forman-Ricci curvature, we need to compute the count matrix
$\Gamma$. Since we focus on edge $e_{12}$ it suffices to calculate the
${e_{12}}^{\text{th}}$ row and column of $\Gamma$. We fix the vertex order
$1<2<\dots<7<8$ which induces the order
$e_{12}<e_{14}<e_{15}<e_{23}<e_{25}<e_{34}$ on the edges. Since $e_{12}$ is
contained in two cycles, $\gamma_{1}=1234$ and $\gamma_{2}=125$, we have

$\Gamma_{e_{12}e_{12}}=2$

Cycle $\gamma_{1}=1234$ traverses $e_{12},e_{23},e_{34}$ from small to large,
and $e_{14}$ from large to small. Applying definition (3), we find

$\begin{cases}\Gamma_{e_{12}e_{23}}=1\text{\leavevmode\nobreak\
\leavevmode\nobreak\ (since $e_{12},e_{23}$ are aligned in $\gamma_{1}$, and
$e_{12}<e_{23}$)}\\\ \Gamma_{e_{12}e_{34}}=1\text{\leavevmode\nobreak\
\leavevmode\nobreak\ (since $e_{12},e_{34}$ are aligned $\gamma_{1}$, and
$e_{12}<e_{34}$)}\\\ \Gamma_{e_{14}e_{12}}=1\text{\leavevmode\nobreak\
\leavevmode\nobreak\ (since $e_{12},e_{14}$ are not aligned in $\gamma_{1}$,
and $e_{14}>e_{12}$)}\end{cases}$

Cycle $\gamma_{2}=125$ traverses $e_{12},e_{25}$ from small to large and
$e_{15}$ from large to small. Applying definition (3), we find

$\begin{cases}\Gamma_{e_{12}e_{25}}=1\text{\leavevmode\nobreak\
\leavevmode\nobreak\ (since $e_{12},e_{25}$ are aligned in $\gamma_{2}$, and
$e_{12}<e_{25}$)}\\\ \Gamma_{e_{15}e_{12}}=1\text{\leavevmode\nobreak\
\leavevmode\nobreak\ (since $e_{12},e_{15}$ are not aligned in $\gamma_{2}$
and $e_{15}>e_{12}$)}\end{cases}$

All other entries in the ${e_{12}}^{\text{th}}$ row and column of $\Gamma$ are
zero since they correspond to edges that do not share a cycle with $e_{12}$
(e.g. $\Gamma_{e_{12}e_{16}}=0$). Finally, the neighbors of $e_{12}$ are
$\\{e_{14},e_{15},e_{16},e_{23},e_{25},e_{28},e_{27}\\}\sim e_{12}$ and the
non-neighbors are $\\{e_{34},e_{78}\\}\not\sim e_{12}$. The AFRC is calculated
from expression (2) as

$\displaystyle\operatorname{\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}}(e_{12})$
$\displaystyle=2+\Gamma_{e_{12}e_{12}}-\sum_{e^{\prime}\sim
e_{12}}|\Gamma_{e_{12}e^{\prime}}+\Gamma_{e^{\prime}e_{12}}-1|-\sum_{e^{\prime}\not\sim
e_{12}}|\Gamma_{e_{12}e^{\prime}}-\Gamma_{e^{\prime}e_{12}}|$
$\displaystyle=2+2-\left(4\cdot|1-1|+3\cdot|0-1|\right)-(|1|+|0|)$
$\displaystyle=0.$

The code to calculate the AFRC in a graph will be made available along with
the publication of the paper. This includes a calculation of
$\mathcal{AF}(e_{12})$ in the example above using the codebase.

##  Appendix C Additional Numerical Experiments

Figure 7: Top to bottom: Distributions of
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{5}}$, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$,
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$, and ORC for SBMs($2,100,p,0.1$) for
$p\in\\{0.1,0.3,0.5,0.7\\}$ (left to right). Edges within (between)
communities in blue (orange).

Figure 8: Top to bottom: Distributions of
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{5}}$, $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern
0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$,
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$, and ORC for SBMs($2,100,0.5,q$) for
$q\in\\{0.5,0.3,0.1,0.07\\}$ (left to right). Edges within (between)
communities in blue (orange).

Figure 9: Distributions of the Augmented Forman-Ricci Curvature (top) and the
Ollivier-Ricci Curvature (bottom) for HBGs($50,p,0.1$) for
$p\in\\{0.1,0.3,0.5,0.7\\}$, from left to right.

Figure 10: Distributions of the Augmented Forman-Ricci Curvature (top) and the Ollivier-Ricci Curvature (bottom) for HBGs($50,0.3,q$) for $q\in\\{0.3,0.1,0.07,0.03\\}$, from left to right. Network | ORC | $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{3}}$ | $\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern 0.5mu}\mathcal{F}_{{4}}$
---|---|---|---
t-SBM($2,50,0,0.03$) | 0.52 | 0.46 | 0.40
t-SBM($2,50,0.1,0.03$) | 2.14 | 0.93 | 0.53
t-SBM($2,50,0.2,0.03$) | 3.98 | 1.72 | 1.41
t-SBM($2,50,0.3,0.03$) | 6.18 | 3.04 | 3.29
Table 6: Comparison of curvature gaps attained by the Ollivier-Ricci curvature
and augmentations of the Forman-Ricci curvature for tree-SBMs with increasing
probability of additional edges within communities. Figure 11: Mean accuracy
(percentage of correctly identified communities) and standard deviation
(shaded areas) of 15 ORC-based (red) and
$\mathcal{A}\mkern-3.65mu\mathchoice{}{}{\mkern 0.2mu}{\mkern
0.5mu}\mathcal{F}_{{3}}$ community-detection (blue) for an SBM with parameters
$(5,20,p,0.05)$ for $p\in\\{0.3,0.35,0.4,0.45,0.5,0.55,0.6\\}$.

## References

  * [1] E. Abbe, Community detection and stochastic block models: Recent developments, Journal of Machine Learning Research, 18 (2018), pp. 1–86.
  * [2] D. Bakry, I. Gentil, and M. Ledoux, Analysis and geometry of Markov diffusion operators, Grundlehren der mathematischen Wissenschaften; 348, Springer, Cham, 2014.
  * [3] S. Bochner, Vector fields and Ricci curvature, Bulletin of the American Mathematical Society, 52 (1946), pp. 776 – 797.
  * [4] S. Bochner, Curvature and Betti numbers, Annals of Mathematics, 49 (1948), pp. 379–390.
  * [5] S. Bochner, Curvature and Betti numbers. II, Annals of Mathematics, 50 (1949), pp. 77–93.
  * [6] M. Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport, Advances in neural information processing systems, 26 (2013).
  * [7] A. Davis, B. Gardner, and M. Gardner, Deep South: a social anthropological study of caste and class, Phoenix books, P204, University of Chicago Press, 1941.
  * [8] K. Devriendt and R. Lambiotte, Discrete curvature on graphs from the effective resistance, Journal of Physics: Complexity, 3 (2022), p. 025008.
  * [9] R. Duda, P. Hart, and D. Stork, Pattern Classification, Wiley, 2012\.
  * [10] M. Erbar and J. Maas, Ricci curvature of finite Markov chains via convexity of the entropy, Archive for Rational Mechanics and Analysis, 206 (2012), pp. 997–1038.
  * [11] R. Forman, Bochner’s method for cell complexes and combinatorial Ricci curvature, Discrete and Computational Geometry, 29 (2003), pp. 323–374.
  * [12] M. Girvan and M. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America, 99 (2002), pp. 7821–6.
  * [13] A. Gosztolai and A. Arnaudon, Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature, Nature Communications, 12 (2021), p. 4561.
  * [14] J. Jost and S. Liu, Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs, Discrete & Computational Geometry, 51 (2013), pp. 300–322.
  * [15] J. Jost and F. Münch, Characterizations of Forman curvature, arXiv:2110.04554, (2021).
  * [16] W. Leal, G. Restrepo, P. F. Stadler, and J. Jost, Forman-Ricci curvature for hypergraphs, Advances in Complex Systems, 24 (2021), p. 2150003.
  * [17] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait?, Behavioral Ecology and Sociobiology, 54 (2003), pp. 396–405.
  * [18] M. Newman, Finding community structure in networks using the eigenvectors of matrices, Physical review E, 74 (2006), p. 036104.
  * [19] C. C. Ni, Y. Y. Lin, F. Luo, and J. Gao, Community detection on networks with Ricci flow, Scientific reports, 9 (2019), pp. 1–12.
  * [20] Y. Ollivier, Ricci curvature of metric spaces, C. R. Acad. Sci. Paris, 345 (2007), pp. 643–646.
  * [21] Y. Ollivier, Ricci curvature of Markov chains on metric spaces, Journal of Functional Analysis, 256 (2009), pp. 810–864.
  * [22] J.-P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.-L. Barabási, Structure and tie strengths in mobile communication networks, Proceedings of the national academy of sciences, 104 (2007), pp. 7332–7336.
  * [23] M. A. Porter, J.-P. Onnela, and P. J. Mucha, Communities in networks, Notices of the American Mathematical Society, 56 (2009), pp. 1082–1097.
  * [24] A. Samal, R. Sreejith, J. Gu, S. Liu, E. Saucan, and J. Jost, Comparative analysis of two discretizations of Ricci curvature for complex networks, Scientific reports, 8 (2018), p. 8650.
  * [25] R. S. Sandhu, T. T. Georgiou, and A. R. Tannenbaum, Ricci curvature: An economic indicator for market fragility and systemic risk, Science advances, 2 (2016), p. e1501495.
  * [26] J. Scott, M. Hughes, and J. Mackenzie, The anatomy of Scottish capital: Scottish companies and Scottish capital, 1900-1979, McGill-Queen’s University Press, 1980.
  * [27] S. Serrano de Haro Iváñez, Comparative analysis of Forman-Ricci curvature versions applied to the persistent homology of networks, arXiv:2212.01357, (2022).
  * [28] J. Sia, E. Jonckheere, and P. Bogdan, Ollivier-Ricci curvature-based method to community detection in complex networks, Scientific reports, 9 (2019), pp. 1–12.
  * [29] R. P. Sreejith, K. Mohanraj, J. Jost, E. Saucan, and A. Samal, Forman curvature for complex networks, Journal of Statistical Mechanics: Theory and Experiment, 2016 (2016), p. 063206.
  * [30] J. Stehlé, N. Voirin, A. Barrat, C. Cattuto, L. Isella, J.-F. Pinton, M. Quaggiotto, W. Van den Broeck, C. Régis, B. Lina, et al., High-resolution measurements of face-to-face contact patterns in a primary school, PloS one, 6 (2011), p. e23176.
  * [31] A. Tannenbaum, C. Sander, L. Zhu, R. Sandhu, I. Kolesov, E. Reznik, Y. Senbabaoglu, and T. Georgiou, Ricci curvature and robustness of cancer networks, arXiv:1502.04512, (2015).
  * [32] P. Tee and C. A. Trugenberger, Enhanced Forman curvature and its relation to Ollivier curvature, Europhysics Letters, 133 (2021), p. 60006.
  * [33] Y. Tian, Z. Lubberts, and M. Weber, Mixed-membership community detection via line graph curvature, in Symmetry and Geometry in Neural Representations, PMLR, 2023, pp. 219–233.
  * [34] J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein, Understanding over-squashing and bottlenecks on graphs via curvature, arXiv:2111.14522, (2021).
  * [35] D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, nature, 393 (1998), pp. 440–442.
  * [36] M. Weber, Neighborhood growth determines geometric priors for relational representation learning, in International Conference on Artificial Intelligence and Statistics, vol. 108, 2020, pp. 266–276.
  * [37] M. Weber, E. Saucan, and J. Jost, Characterizing complex networks with Forman-Ricci curvature and associated geometric flows, Journal of Complex Networks, 5 (2017), pp. 527–550.
  * [38] M. Weber, E. Saucan, and J. Jost, Coarse geometry of evolving networks, Journal of Complex Networks, 6 (2018), pp. 706–732.
  * [39] M. Weber, J. Stelzer, E. Saucan, A. Naitsat, G. Lohmann, and J. Jost, Curvature-based methods for brain network analysis, arXiv:1707.00180, (2017).
  * [40] W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research, 33 (1977), pp. 452–473.