remarkRemark hypothesisHypothesis claimClaim An efficient set-theoretic
algorithm for high-order F.R.C.D. Barros de Souza et al.

# An efficient set-theoretic algorithm for high-order Forman-Ricci
curvature††thanks:  This manuscript is for review purposes only This research
is supported by the Basque Government through the BERC 2022-2025 program and
by the Ministry of Science and Innovation: BCAM Severo Ochoa accreditation
CEX2021-001142-S / MICIN / AEI / 10.13039/501100011033.

Danillo Barros de Souza Basque Center for Applied Mathematics (Corresponding
author: , , http://www.bcamath.org/en/people/dbarros<EMAIL_ADDRESS><EMAIL_ADDRESS>Jonatas T. S. da Cunha Universidade Federal de Pernambuco,
Recife, Brazil Rodrigo A. Moreira Basque Center for Applied Mathematics,
Bilbao, Spain<EMAIL_ADDRESS>Fernando A. N. Santos Dutch Institute
for Emergent Phenomena (DIEP), Institute for Advanced Studies, University of
Amsterdam, Oude Turfmarkt 147, 1012 GC, Amsterdam, The Netherlands, and
Korteweg de Vries Institute for Mathematics, University of Amsterdam, Science
Park 105-107, 1098 XG Amsterdam, the Netherlands<EMAIL_ADDRESS>Serafim Rodrigues Basque Center for Applied Mathematics, Bilbao, Spain ()
<EMAIL_ADDRESS>
###### Abstract

Differential geometric approaches are ubiquitous in several fields of
mathematics, physics and engineering, and their discretizations enable the
development of network-based mathematical and computational frameworks, which
are essential for large-scale data science. The Forman-Ricci curvature (FRC) -
a statistical measure based on Riemannian geometry and designed for networks -
is known for its high capacity for extracting geometric information from
complex networks. However, extracting information from dense networks is still
challenging due to the combinatorial explosion of high-order network
structures. Motivated by this challenge we sought a set-theoretic
representation theory for high-order network cells and FRC, as well as their
associated concepts and properties, which together provide an alternative and
efficient formulation for computing high-order FRC in complex networks. We
provide a pseudo-code, a software implementation coined FastForman, as well as
a benchmark comparison with alternative implementations. Crucially, our
representation theory reveals previous computational bottlenecks and also
accelerates the computation of FRC. As a consequence, our findings open new
research possibilities in complex systems where higher-order geometric
computations are required.

###### keywords:

Forman-Ricci curvature, discrete geometry, set theory, optimization, complex
systems, higher-order networks, data science.

05C85, 52C99, 90C35, 62R40, 68T09.

##  1 Introduction

Network analysis has emerged as a hot topic over the last decade [1, 24, 5,
23], and has enabled the theoretical and computational advances across several
fields, for instance, in neuroscience [39, 16, 38, 2, 11, 31, 35, 20, 36, 19].
Topological Data Analysis (TDA) and Geometrical Data Analysis (GDA) emerged as
alternative approaches for analyzing network-based data [40, 47, 27, 6]. Among
many ways of extracting geometric information from complex networks, discrete
Ricci curvatures are one of the most powerful approaches[32, 18, 25].
Originally inspired by Bochner’s formula for Ricci tensors in compact
manifolds [3], the discrete version of the Forman-Ricci curvature (FRC) was
first introduced by the work of [18], where the authors provide a formula for
FRC of a simplicial complex from the discrete Bochner and Laplacian operators.
Its application is a wide range. For instance, it has been applied in cancer
diagnostics [33], detecting anomalies on brain networks [7], detection of
dynamic changes on data sets [43], detection of stock market fragility [34]
and to infer pandemic states [10]. Despite the informational power of these
techniques, the time and memory complexity of computing higher-order
dimensional information from complex networks is prohibitively expensive,
which prevents researchers from using existing algorithms for higher-order
complex networks. For example, the time for computing all cliques in a graph
has exponential-time complexity [12, 17, 29] and, when feasible, might require
an efficient algorithm for this task. As another example, the Betti number
computation [4], due to the matrix construction of boundary operators is an
NP-hard problem [14]. Indeed, Betti number computation increases with the
number of cliques and, consequently, requires memory-efficient algorithms.
Among the geometric approaches, the discrete Ricci curvature for low-
dimensional structures is the most feasible. However, its computation only
considers the interaction between nodes and edges, ignoring relevant
structural information that might be contained in higher-order structures. In
addition, the lack of efficient algorithms for computing generalized geometric
structures limits the use of high-order Forman-Ricci curvature (FRC) for
complex networks. Conveniently, one way to develop efficient and optimal
algorithms is via set-theoretic approaches [15, 22, 46, 28]. To this end, we
developed a set-theoretic representation theory for higher-order network
structures based on node neighbourhoods to give an alternative (and optimal)
definition for FRC in terms of the classic node neighbourhood of a graph. This
leads us to a representation theory that reveals previous computational
bottlenecks and enables us to develop an efficient algorithm that markedly
accelerates the computation of FRC in higher-order networks. Lastly, we
implemented our algorithm - FastForman (see in [9]) - and benchmarked with
other implementations, namely GenerlisedFormanRicci [45] and HodgeLaplacians
[41]. Impressively, our implementation boosted time processing and drastically
reduced memory consumption during the process of computing FRC for low and
high-dimensional network structures. These results reinforce our beliefs in
the power of set-theoretic approaches to improve the efficiency of algorithm
implementations and their importance to motivate the work of scientists on
applying high-order geometric approaches to big data sets.

##  2 Network and higher-order network fundamentals

An undirected simple graph (or network) $G=(V,E)$ is defined by a finite set
of nodes $V$ and a set of edges $E=\\{(x,y)\,|\,x,y\in V,x\neq y\\}$. 1
depicts the definition of a simple graph.

Let $x,y\in V$. We say that $y$ is a neighbour of $x$ if the edge $(x,y)\in
E$. The _neighbourhood_ of the node $x$ is defined by

(1) $\pi_{x}=\\{y\in V\,|\,x\sim y\\},$

where $x\sim y$ denotes that $x$ is connected to $y$ via an edge in $E$. A
simple example is shown in 2. We will define the Graph neighbourhood as the
sequence of node neighbourhoods of a graph $G$. Formally,

(2) $\text{Neigh(G)}=(\pi_{x}\,|\,x\in V)$

An easy and efficient implementation for finding node neighbourhood is
provided in Algorithm 1.

Algorithm 1 Compute Graph Neighborhood: Neigh(G)

Input: $G=(V,E)$

$\pi_{x}=\emptyset,\forall x\in V$

for $e=(x,y)\in E$ do

$\pi_{x}:=\pi_{x}\cup\\{y\\}$

$\pi_{y}:=\pi_{y}\cup\\{x\\}$

end for

return $\pi_{x}$ for all $x\in V$

A subgraph $G^{{}^{\prime}}=(V^{{}^{\prime}},E^{{}^{\prime}})$ of $G$ (denoted
by $G^{{}^{\prime}}\subseteq G$) is a graph such that
$V^{{}^{\prime}}\subseteq V$ and $E^{\prime}=\\{(x,y)\,|\,x,y\in
V^{\prime},x\neq y\\}$, which clearly satisfies $E^{{}^{\prime}}\subseteq E$.
A complete subgraph in $G$ is a subgraph in which all nodes are pairwise
connected by an edge. They are also denoted $cliques$ or $cells$ of a graph,
which are concepts associated with higher-order networks since they represent
indivisible objects in their own right.

Let $d\in\mathbb{N}\bigcup\\{0\\}$ then the complete subgraphs in $G$ with
$d+1$ nodes are called (d+1)-vertex cliques or d-cells in the graph. In the
present sequel, we only deal with complete subgraphs and, for convenience, we
will refer to them simply as subgraphs. We will denote $C_{d}$ as the set of
all $d$-cells in G. Given a $d$-cell, $\alpha\in C_{d},$ we can also
explicitly define $\alpha=[x_{0},\ldots,x_{d}]$ such that $x_{i}\in V$ (with
$i=0,\ldots,d$) and $\alpha$ is a complete subgraph of $G$, i.e., there exists
$e\in E$ such that $e=(x_{i},x_{j}),$ for all $x_{i},x_{j}\in\alpha$,
$x_{i}\neq x_{j}$. Under this formulation, a $d$-cell
$\alpha=[x_{0},\dots,x_{d}]$ can also be seen as the complete subgraph
$G_{\alpha}=(V_{\alpha},E_{\alpha})$ such that
$V_{\alpha}=\\{x_{0},\ldots,x_{d}\\}$ and
$E_{\alpha}=\\{(x_{i},x_{j})\,|\,x_{i},x_{j}\in V_{\alpha},i\neq j\\}.$ Herein
we define a simplicial complex [13] as the union of all sets of complete
subgraphs in $G$, i.e., $C=\bigcup\limits_{d}C_{d}.$ We refer the reader to
Fig. 1 and accompanying 3 for a graphic exposition of the concepts of
simplicial complex and d-cells.

Figure 1: Example of a simplicial complex and its $d$-cells for
$d\in\\{0,1,2,3\\}$. In this example, we have $12$ nodes ($0$-cells), $13$
edges ($1$-cells), $5$ triangles ($2$-cells) and $1$ tetrahedron ($3$-cells).

Analogous to definition (1), we define the node neighborhood of a $d$-cell
$\alpha$ (or the neighbouring of nodes of a $d$-cell) as follows:

(3) $\pi_{\alpha}=\bigcap_{x\in\alpha}\pi_{x}.$

An application of this formulation can be accessed in 4. Note that for $d=1$
in equation (3) we reach back to the classical formula of the neighbourhood of
a node described by equation (1).

######  Remark 2.1.

Note that the definition in (3) implies that if $x\in\pi_{\alpha}$ then
$x\notin\alpha,$ since we are dealing with simple graphs.

Finally, we can characterize the set of nodes of $\alpha$ in terms of its node
neighbourhood as

(4)
$V_{\alpha}=\\{x_{0},\ldots,x_{d}\\}=\Bigg{\\{}x\in\alpha\,|\,x\in\bigcap_{\begin{subarray}{c}y\in\alpha\\\
y\neq x\end{subarray}}\pi_{y}\Bigg{\\}}.$

This formulation enables us to identify $\alpha\sim V_{\alpha}$, which is
$[x_{0},\ldots,x_{d}]\sim\\{x_{0},\ldots,x_{d}\\}$. As a consequence, it
enables us to deal with complete subgraphs as their representation in terms of
nodes and all the set operations can be applied in a natural manner. This will
be crucial for defining the concepts of parallelism and transversality of
cells in the following section.

##  3 High-order Forman-Ricci curvature

Let $G=(V,E)$ a graph and $d\in\mathbb{N}\bigcup\\{0\\}$. Let $\gamma\in
C_{d-1}$ and $\alpha\in C_{d}$. We denote by $\partial(\alpha)$ the set of all
complete subgraphs with $d$ nodes contained in $\alpha$, i.e., all
$(d-1)$-cells contained in $\alpha$. Formally, $\partial(\alpha)=\\{\gamma\in
C_{d-1},\,\gamma\subset\alpha\\}$, for $d>0$ and $\partial(\alpha)=\emptyset$
for $d=0$. In analogy with our set-theoretic approach we alternatively define
$\partial(\alpha)=\\{\\{x_{0},\ldots,\hat{x_{i}},\ldots,x_{d}\\},x_{i}\in\alpha\\}=\\{\gamma\subset\alpha\,,\,|\gamma|=d\\}$,
where $\hat{x_{i}}$ denotes the removal of element $x_{i}$. Note that
$\partial(\alpha)$ has exactly $\binom{d+1}{d}=d+1$ elements. In 5 the concept
of cell boundary is elucidated. We denote that $\gamma$ is contained in the
boundary of $\alpha$ by $\gamma<\alpha$ (noteworthy, in terms of set
properties, it also implies that $\gamma\subset\alpha$). Analogously, we
denote that $\alpha$ contains $\gamma$ in its boundary by $\alpha>\gamma$
(that is, in set theory formulation, $\alpha\supset\gamma$). We say that
$\alpha_{1},\alpha_{2}\in C_{d}$ are neighbours if at least one of the
following cell neighborhood conditions is reached:

  1. 1.

There exists a ($d-1$)-cell $\gamma$ such that $\gamma<\alpha_{1},\alpha_{2}$;

  2. 2.

There exists a ($d+1$)-cell $\beta$ such that $\alpha_{1},\alpha_{2}<\beta$.

We say that $\alpha_{1}$ and $\alpha_{2}$ are parallel neighbours if
conditions $1.$ is reached, but not $2.$ and we denote the parallelism by
$\alpha_{1}//\alpha_{2}$. In case of both conditions, $1.$ and $2.$ are
satisfied, $\alpha_{1}$ and $\alpha_{2}$ are said transverse neighbours. 6
elucidates the concept of cell neighbourhood. Let $\alpha\in C_{d}.$ We denote
the set of all neighbours of a cell $\alpha$ by $N^{d}_{\alpha}$. The sets of
parallel and transverse neighbours of $\alpha$ will be denoted by
$P^{d}_{\alpha}$ and $T^{d}_{\alpha}$, respectively. We will also denote by
$H^{d}_{\alpha}$ as the set of all $(d+1)$-cells that have $\alpha$ in its
boundary, i.e, all $\beta\in C_{d+1}$, such that $\beta>\alpha$. From
conditions $1.$ and $2.$, it is clear that these sets are disjoint, and we can
also write

(5) $\displaystyle N^{d}_{\alpha}=P^{d}_{\alpha}\sqcup T^{d}_{\alpha},$

for all $d\geq 1$ and all $\alpha\in C_{d}.$

######  Remark 3.1.

We emphasize that the concepts of node neighbourhood of a cell and cell
neighbourhood are strongly related, however, they describe completely
different objects. While the node neighbourhood of a cell describes the set of
nodes that has a common intersection with all nodes of the cell in question
(as defined in (1) and (3)), the cell neighbourhood are all cells in the
simplicial complex that reach at least one of the cell neighbourhood
conditions. A comparison between 2 and 4 can elucidate the explanation of this
difference. The link between the two concepts occurs from the fact that the
neighbours of a cell $\alpha$ can be described in terms of the node
neighbourhood of the sub-cells in its boundary, which will be clarified along
the construction of our set-theoretic definitions.

The $d$-th Forman-Ricci curvature (FRC) is then given as follows [44, 37]:

(6) $\displaystyle\mathrm{F}_{d}(\alpha)=$ $\displaystyle\left|\\{\beta\in
C_{d+1},\,\,\beta>\alpha\\}\right|$ $\displaystyle+\left|\\{\gamma\in
C_{d-1},\,\,\gamma<\alpha\\}\right|$
$\displaystyle-\left|\\{\alpha^{\prime}\in
C_{d},\,\,\alpha^{\prime}//\alpha\\}\right|,$

where $|.|$ is the number of elements in the set (i.e. cardinality).
Alternatively, it can be formulated as follows:

(7)
$\displaystyle\mathrm{F}_{d}(\alpha)=\left|H^{d}_{\alpha}\right|+(d+1)-\left|P^{d}_{\alpha}\right|.$

Note, for example, when $d=1$, we have recovered the classic FRC of an edge
$e\in E=C_{1}$ as

(8) $\displaystyle\mathrm{F}(e)=\left|\\{t\in
C_{2},\,\,t>e\\}\right|\,+2\,-\left|\\{e^{\prime}\in
E,\,\,e^{\prime}//e\\}\right|,$

where $t$ denotes a triangle ($2$-cell). The $d$-th FRC of a non-empty $C_{d}$
complex is given by the average of the Forman-Ricci curvatures by cell, i.e.,

(9) $\displaystyle\mathrm{F}_{d}(C)=\dfrac{1}{|C_{d}|}\sum_{\alpha\in
C_{d}}\mathrm{F}_{d}(\alpha).$

The computation of FRC for dimensions $d=1$ and $d=2$ can be clarified in 8.

##  4 Results

Subsequently, we propose our set-theoretic representation theory for high-
order network cells and FRC and develop the associated efficient algorithm
computing high-order FRC in complex networks.

###  4.1 Set-theoretic representation of Forman-Ricci curvature

First, note that we can formulate the set of $d$-cells as

(10) $\displaystyle
C_{d}=\Big{\\{}\alpha:=\\{x_{0},\ldots,x_{d}\\},\,\,x_{i}\in\pi_{\alpha\setminus\\{x_{i}\\}},\,\forall
i\Big{\\}}.$

The details are shown in Theorem B.1. The set of neighbours of $\alpha$ can be
redefined in terms of the node neighbourhood as follows (see Theorem B.9):

(11) $\displaystyle
N^{d}_{\alpha}=\bigsqcup_{\gamma\in\partial(\alpha)}\,\bigcup_{x\in\pi_{\gamma}\setminus(\alpha\setminus\gamma)\neq\emptyset}\\{\gamma\cup\\{x\\}\\},$

where the $\bigsqcup$ operation represents the disjoint union of sets. The
Theorem B.7 also characterizes the neighbours of a $d$-cell by finding cells
that reach the cell neighbouring condition 1., which means that it is
sufficient for two $d$-cells to have a common boundary to be neighbours. The
transverse neighbours of $\alpha$ can also be characterized (see Theorem
B.11), which lead as to the formula

(12) $\displaystyle
T^{d}_{\alpha}=\bigsqcup_{\gamma\in\partial(\alpha)}\,\bigcup_{x\in\pi_{\gamma}\cap\pi_{\alpha\setminus\gamma}\neq\emptyset}\\{\gamma\cup\\{x\\}\\}.$

######  Remark 4.1.

Indeed, we have that
$\pi_{\alpha}=\pi_{\gamma}\cap\pi_{\alpha\setminus\gamma,\,\forall\gamma\in\partial(\alpha)}$.
However, we emphasize the right-hand side of this expansion in equations (11)
and (12) in order to visualize (or intuitively conceptualise) the construction
of those sets by cell boundary.

Moreover, we can express the number of cells of dimension $d+1$ containing
$\alpha$ (see proof in Theorem B.13) as

(13) $\displaystyle
H^{d}_{\alpha}=\bigcup_{x\in\pi_{\alpha}\neq\emptyset}\\{\alpha\cup\\{x\\}\\}.$

It follows from equations (5), (11) and (12) that

(14) $\displaystyle
P^{d}_{\alpha}=\bigsqcup_{\gamma\in\partial(\alpha)}\bigcup_{\begin{subarray}{c}\Pi^{\gamma}_{\alpha}\neq\emptyset\\\
x\in\Pi^{\gamma}_{\alpha}\end{subarray}}\\{\gamma\cup\\{x\\}\\},$

where

(15)
$\displaystyle\Pi^{\gamma}_{\alpha}=\pi_{\gamma}\setminus(\pi_{\alpha}\cup(\alpha\setminus\gamma)).$

The details are shown in Theorem B.17. Combining equations (7), (13) and (14),
and considering $\alpha=\\{x_{0},\ldots,x_{d}\\}$ we finally have that

(16)
$\displaystyle\mathrm{F}_{d}(\alpha)=\left|\bigcap\limits^{d}_{i=0}\pi_{x_{i}}\right|\,+(d+1)\,-\left|\bigsqcup_{i=0}^{d}\bigcap\limits^{d}_{\begin{subarray}{c}j=0\\\
j\neq
i\end{subarray}}\pi_{x_{j}}\setminus{(\pi_{x_{i}}}\cup\\{x_{i}\\})\right|.$

Equation (16) provides a direct computation of FRC from the parallel cells.
However, an alternative equation can be derived by computing FRC directly from
the cell neighbourhood This is obtained by combining (5) and (7), and using
the fact that (Theorem B.15)

(17) $\left|T^{d}_{\alpha}\right|=(d+1)\left|H^{d}_{\alpha}\right|,$

which results explicitly in

(18)
$\displaystyle\mathrm{F}_{d}(\alpha)=(d+2)\left|\pi_{\alpha}\right|+(d+1)-\left|N^{d}_{\alpha}\right|.$

The expansion of the term $\left|N^{d}_{\alpha}\right|$ leads to

(19)
$\left|N^{d}_{\alpha}\right|=\sum_{i=0}^{d}\left|\bigcap_{\begin{subarray}{c}j=0\\\
j\neq
i\end{subarray}}^{d}\pi_{x_{j}}-\\{x_{i}\\}\right|=\sum_{i=0}^{d}\left|\bigcap_{\begin{subarray}{c}j=0\\\
j\neq i\end{subarray}}^{d}\pi_{x_{j}}\right|-(d+1),$

which when applied to (18) and further simplification, finally leads us to our
principle equation

(20)
$\displaystyle\mathrm{F}_{d}(\alpha)=(d+2)\left|\bigcap_{i=0}^{d}{}\pi_{x_{i}}\right|+2\cdot(d+1)-\sum_{i=0}^{d}\left|\bigcap_{\begin{subarray}{c}j=0\\\
j\neq i\end{subarray}}^{d}\pi_{x_{j}}\right|.$

The details for reaching the formula in (20) is shown in Theorem B.19.
Equation (20) not only establishes a new formulation for FRC but also
crucially enables us to propose a novel algorithm to efficiently compute FRC
in terms of the local node neighbourhoods of the cells into consideration.
Indeed, we propose Algorithm 2 that should be parameterized by the graph
$G=(V,E),$ the list of cells ($C$), and the maximum cell dimension
($d_{\max}$), and it computes FRC up to dimension $d\leq d_{\max}$. We
subsequently address the practical implementation of equation (20). Assume
$\alpha\in C_{d}$; then (20) computes the higher-order cells containing
$\alpha$ by counting the nodes that are in the intersection of neighbouring
nodes of $\alpha$ (i.e., $|\pi_{\alpha}|$), which are the nodes of the
$(d+1)$-cells that contain $\alpha$ in their boundary. Moreover, the
neighbouring cells of $\alpha$ are counted by the $d$-cells that have common
boundaries with $\alpha$. By counting the number of neighbouring nodes that
have these common boundaries (except the nodes in $\alpha$ itself, in order to
avoid duplicates) we count all the neighbours of $\alpha$. In the simplest
case, for $d=1$, to compute the FRC of an edge $\alpha=(x,y)$ (i.e.
$F_{1}(\alpha)$), we determine the number of triangles (i.e. $2$-cells)
containing the edge $\alpha$. This is achieved by computing the number of
elements resulting from the intersection of the nodes that are neighbours of
$x$ and $y$. Specifically, the number of neighbours of $\alpha$ is the result
of counting the number of elements in the neighbourhood of $x$ and
respectively, the neighbourhood of $y$, except the nodes $y$ and $x$
themselves. Analogously, for $d=2$, to compute FRC of a triangle
$\alpha=\\{x,y,z\\}$ (i.e. $F_{2}(\alpha)$), the number of elements at the
intersection between the neighbourhood of $x$, $y$ and $z$ provides the number
of tetrahedrons (i.e. $3$-cells) containing $\alpha$. In other words, suppose
we have the following intersection:
$\pi_{x}\cap\pi_{y}\cap\pi_{z}=\\{w_{1},...,w_{k}\\}$. Then this intersection
provides the set of nodes that together with the nodes of the triangle
$\\{x,y,z\\}$ are the tetrahedrons that contain $\alpha$, that is,
$\\{\\{w_{1},x,y,z\\},\\{w_{2},x,y,z\\},...,\\{w_{k},x,y,z\\}\\}=\\{\alpha\cup\\{w_{1}\\},\ldots,\alpha\cup\\{w_{k}\\}\\}$.
Noteworthy, the number of neighbours of $\alpha$ are computed by counting the
nodes that have $\\{x,y\\}$, $\\{x,z\\}$ and $\\{y,z\\}$ as common boundary
and are not in $\alpha$. To facilitate intuition about these computations, we
provide a graphical representation of the resulting computations for the case
of $2$-cells in Fig. 2.

Figure 2: Example of how the algorithm detects cell neighbours from node
neighbourhood for $2$-cells (triangles). The $2$-cell $\alpha$ is enhanced in
orange, whilst its boundary is drawn in red. According to the algorithm, the
number of $3$-cells containing $\alpha$ in its boundary ($|H^{d}_{\alpha}|$)
coincides with the number of common neighbours of the nodes in $\alpha$
($|\pi_{\alpha}|$). Also, the number of neighbours per boundary is counted by
the size of intersections of node neighbourhoods in the boundary. In this
example,
$\mathrm{F}_{2}(\alpha)=4\cdot|\\{6\\}|+3-(|\\{3,6\\}|+|\\{6\\}|+|\\{6\\}|)=3.$
The same output is reached by using (6): $\mathrm{F}_{2}(\alpha)=1+3-1=3.$
Algorithm 2 Compute Forman-Ricci Curvature: FastForman

Input: $C,d_{\max}\geq 1$

$\mathcal{F}_{d}=\emptyset,\forall d\leq d_{\max}$

Compute Neigh(G) from Algorithm 1;

for $c\in C$ do

$d:=|c|-1$

Compute $\mathrm{F}_{d}(c)$ according to (20)

Update $\mathcal{F}_{d}:=\mathcal{F}_{d}\cup\\{\mathrm{F}_{d}(c)\\}$

end for

return $\mathcal{F}=\bigcup\limits_{d}\\{\mathcal{F}_{d}\\}$

Note that Algorithm 2 is versatile in the sense that it can compute FRC for an
arbitrary subset of cells, not only for the full simplicial complex (provided
the correct graph $G$ associated with this simplicial complex, i.e., the graph
that generates the provided nodes). Indeed, it can compute FRC cell by cell,
and in doing so it only accesses local information at the time at which that
cell is being called (i.e. node neighbourhood for each node in the cell).
Since it iterates through the set of cells (as parameterized by some cliques’
algorithm) and because it does not store a full simplicial complex, then it
results in an algorithm with efficient time and memory footprint. Indeed, the
key to this computational efficiency is that it is solely based on local
computation thus it significantly facilitates memory management and processing
time. The main limiting factor of our algorithm is dependent on the specific
cliques’ algorithm used, which is in general NP-complete and is unavoidable to
any algorithm with this purpose. One way to reduce the time complexity is by
limiting the search space for cliques, such as, by setting an upper bound for
the highest dimension of cells ($d_{\max}$), and also using efficient
algorithms for clique’s computing.

###  4.2 Ricci-curvature Computation and Benchmark of Novel Algorithm

To validate our set-theoretic representation of FRC, we developed a Python
language version [42] of our pseudo-code (Algorithm 2), which we named
FastForman. Furthermore, we run benchmark tests and compared FastForman’s
execution time and memory usage with the leading software in the literature,
namely Python packages HodgeLaplacians [41] and GeneralisedFormanRicci [45].
The benchmark tests were performed on a Dell laptop model XPS 15-7590, Intel
Core i7-9750H CPU 2.60GHz, 32Gb RAM, running Linux Ubuntu operating system
version 20.04.4 LTS (Focal Fossa). To carry out the tests, with the help of
NetworkX package [21], we generated $20$ copies of $3$-dimensional point cloud
data from random geometric networks [30] with the parameters $n=50$ nodes and
radius $r\in\\{0.1,0.2,\ldots,1.0\\}$ (to access this data we refer the reader
to the link [9]). To undertake an unbiased benchmark test, it is first worth
noting that the Python package, GeneralisedFormanRicci, is limited to
computing the FRC for edges and triangles. Therefore, we divided the benchmark
tests into two separate groups. The first group aimed at comparing
GeneralisedFormanRicci, HodgeLaplacians and FastForman for $d_{max}=2$. The
second group focused on comparing HodgeLaplacians versus FastForman for
$d_{max}=5$. To compare the time complexity between all involved software
packages, we considered the total execution time from the generation of cells
(cliques) to the end computation of FRC. For a fair comparison, we employed
the same software package, Gudhi [26], to list the cells of the aforementioned
generated networks. Due to the separate benchmark groups, we first depict in
Fig. 3 the average number of cells for $d_{\max}\in\\{2,5\\}$ contained within
the aforementioned generated networks. In Figs. 4 and 5 we benchmark the
average of the total processing time and average memory peak usage for
computing the FRC over the generated random networks. We also compare the
results with the time and memory consumption of listing the set of cells via
the Gudhi package (grey curves in the figures). We subsequently discuss the
merits and limitations of each software package for computing FRC.

GeneralisedFormanRicci: Due to computational limitations with memory
management, we could not compute FRC for radius values higher than $r=0.7$ via
GeneralisedFormanRicci. Despite GeneralisedFormanRicci being limited to lower
dimensional computations, the time consumption was the highest, exceeding the
Hodgelaplacians and FastForman implementations. Moreover, it displays a high
variance of time and memory consumption particularly for dense networks, which
might be associated with its limitations in computing FRC up-to 2-dimensional
cells (compare Figs. 3 and 4). The limitation to point cloud data sets is also
a drawback of the algorithm since it restricts one from selecting a subset of
cells over which one may compute FRC.

Hodgelaplacians: The time processing is comparable with the performance
results of FastForman for low-dimensional cells and low connectivity values.
However, the computational efficiency decreases for high-order cells and
larger radii and thus its performance falls behind in comparison to
FastForman. Furthermore, the time and memory processing variance increase
significantly with respect to the network complexity (ie., size, number of
higher-order cells and density). This fact might be explained by the
computation of FRC via Bochner’s discrete formula, which uses Hodge Laplacian
and Bochner Laplacian matrix operators [5, 44, 8]. This demands memory for
storing the matrices and time to both generate the matrices and compute FRC.
It is worth emphasising that the Hodge Laplacian matrix for the highest cell
dimension is simply the $d_{\max}$-th boundary operator, which in
computational terms, induces a miscalculation on FRC for this dimension. Thus,
for the correct computation for all cells, the entire simplicial complex
should be provided, which impacts directly on the computational complexity.
One way to improve efficiency and avoid miscalculation would be to include
information of $(d_{\max}+1)$-cells so the correct computation up to
$d_{\max}$ can be computed correctly. A detailed report of this special case
is included in the link [9], where we provide an example of the
miscalculation.

FastForman: Our implementation supersedes existing FRC software packages
benchmarked in our tests. The key to this performance is that our set-
theoretic formulation leads us to an algorithm that only requires the use of
local node neighbourhood information for computing the FRC by cell, which, as
a consequence, reduces the complexity of computing FRC. Noteworthy, there is
no requirement for specifically computing and storing neighbouring cells,
hence this explains its low memory usage and fast computation. Moreover,
FastForman is versatile in the sense that it does not make mandatory the
inclusion of the global information of an entire simplicial complex. In other
words, the FRC computation is flexible, in a way that it can be computed for
subsets of cells within a given simplicial complex. The limiting factors are
two folds: Firstly, the complexity of the algorithm is dependent upon how
cells are computed, which is generically an NP-problem and herein in we
employed the Gudhi algorithm. Secondly, the algorithm’s complexity is
associated with node neighbourhood computation, as given by Algorithm 1, which
has a time complexity of $\mathcal{O}(|E|)$ since it iterates over edges.
Indeed, FastForman’s processing time increases in accordance with the time
required for finding cells; see Figs. 4 and 3.

To conclude, we provide a brief benchmark summary in Table 1, where we compare
FastForman, Hodgelaplacians and GeneralisedFormanRicci. The table summarises
the versatility of the algorithms in choosing the set of cells, the ability in
computing FRC for higher-order dimensional cells, as well as processing time
and memory usage.

Table 1: Algorithm comparison summary Algorithm | Flexible | High-order | Time processing | Memory Peak
---|---|---|---|---
GeneralisedFormanRicci | No | $d_{\max}=2$ | Very high | Very high
HodgeLaplacians | No | Yes | High | High
FastForman | Yes | Yes | Fair | Low
Figure 3: Average number of cliques for the set of $50$ point cloud data, and
$d_{\max}\in\\{2,5\\}.$ Figure 4: Benchmark for computing Forman-Ricci
curvature by using HodgeLaplacians (blue), FastForman (red) and
GeneralisedFormanRicci (green), in comparison with the cells computation by
using the Gudhi algorithm, for $n=50$ and $d_{\max}\in\\{2,5\\}$. Figure 5:
Benchmark for computing Forman-Ricci curvature by using HodgeLaplacians
(blue), FastForman (red) and GeneralisedFormanRicci (green), in comparison
with the cells computation by using the Gudhi algorithm, for $n=50$ and
$d_{\max}\in\\{2,5\\}$. Here, we display the result in a log scale to clarify
the analysis.

##  5 Conclusion

We proposed a novel set theoretical formulation for high-order Forman-Ricci
curvature (FRC) and this led us to the implementation of a new algorithm,
which we coined FastForman. Central to our set-theoretic representation theory
for high-order network cells and FRC computation is the fact we managed to
redefine parallelism and transversality of neighbouring cells. This enabled us
to formulate FRC computation in terms of the neighbours of nodes in a network.
As a consequence, we managed to computationally tame some of the combinatorial
complexities intrinsic to high-order networks. We validated FastForman via
benchmark tests on random higher-order geometric graphs and compared them with
leading softwares, namely, Hodgelaplacians and GeneralisedFormanRicci. To
ensure a fair comparison, we implemented FastForman with Python language since
Hodgelaplacians and GeneralisedFormanRicci are also implemented in Phyton. We
also took into consideration the intrinsic limitations of Hodgelaplacians and
GeneralisedFormanRicci, such as the maximum number of cell dimensions
tolerated by these algorithms. Our benchmark tests established that FastForman
is more efficient in time and memory complexity. In conclusion, despite the
constraints of cell search NP algorithms and the combinatorial explosion of
high-order network structures, our findings facilitate the computation of
higher-order geometric invariants in complex networks. We envisage that
FastForman will open novel research avenues in big data science, particularly
through a geometrical point of view.

##  Appendix A Examples

In this section, we provide examples of our work.

######  Example 1 (Undirected Simple Graph).

In Fig. 1, we have a undirected simple graph, $G=(V,E)$, such that
$V=\\{1,\ldots,12\\}$ and

$\displaystyle E=$
$\displaystyle\\{(1,3),(2,3),(2,4),(3,4),(3,5),(3,6),(3,7),(5,6),(5,7),(6,7),(7,9),(8,9),(10,11)\\}$

######  Example 2 (Neighborhood of a node).

In Fig. 1, we have the neighbors of each node in $V$ as described below:

$\displaystyle\pi_{1}=\\{3\\},$ $\displaystyle\pi_{2}=\\{3,4\\},$
$\displaystyle\pi_{3}=\\{1,2,4,5,6,7\\},$ $\displaystyle\pi_{4}=\\{2,3\\},$
$\displaystyle\pi_{5}=\\{3,6,7\\},$ $\displaystyle\pi_{6}=\\{3,5,7\\},$
$\displaystyle\pi_{7}=\\{3,5,6,9\\},$ $\displaystyle\pi_{8}=\\{9\\},$
$\displaystyle\pi_{9}=\\{7,8\\},$ $\displaystyle\pi_{10}=\\{11\\},$
$\displaystyle\pi_{11}=\\{10\\},$ $\displaystyle\pi_{12}=\emptyset.$

######  Example 3 ($d$-cells and Simplicial Complex).

In Fig. 1, the $d$-cells (or the complete subgraphs with $d+1$ nodes), for
$d\in\\{0,1,2,3\\}$ are

$\displaystyle C_{0}=V,$ $\displaystyle C1=E,$ $\displaystyle
C_{2}=\\{\\{2,3,4\\},\\{3,5,6\\},\\{3,6,7\\},\\{3,5,7\\},\\{5,6,7\\},$
$\displaystyle C_{3}=\\{\\{3,5,6,7\\}\\}.$

The simplicial complex is $C=\bigcup_{i=0}^{3}C_{i}.$

######  Example 4 (Node neighbourhood of a cell).

In Fig. 1, $\pi_{\\{12\\}}=\emptyset=\pi_{\\{2,3,4\\}}$ and
$\pi_{3}=\\{1,2,4,5,6\\}.$ Also, $\pi_{\\{3,5,6\\}}=\\{7\\}.$

######  Example 5 (Boundary of a cell).

The boundary of $0$-cells is always an empty set. In Fig. 1, the boundary of
the $1$-cell $\\{7,9\\}$ is

$\partial(\\{7,9\\})=\\{\\{7\\},\\{9\\}\\}.$

The boundary of the $2$-cell $\\{2,3,4\\}$ is

$\partial(\\{2,3,4\\})=\\{\\{2,3\\},\\{2,4\\},\\{3,4\\}\\},$

and the boundary of the $3$-cell $\\{3,5,6,7\\}$ is

$\partial(\\{3,5,6,7\\})=\\{\\{3,5,6\\},\\{3,5,7\\},\\{3,6,7\\},\\{5,6,7\\}\\}.$

######  Example 6 (Cell neighborhood).

In Fig. 1, the $0$-cell $\\{12\\}$ has no neighbours, as well as the $1$-cell
$\\{10,11\\}$, the $2$-cell $\\{2,3,4\\}$ and the $3$-cell $\\{3,5,6,7\\}.$
The $2$-cell $\\{3,4\\}$ has $6$ neighbours, in which $2$ are transverse
($\\{2,3\\},\\{2,4\\}$) and $4$ are parallel ($\\{1,3\\},\\{3,5\\},\\{3,6\\}$
and {3,7}). The $2$-cell $\\{3,5,7\\}$ has $3$ neighbours,
$\\{3,6,7\\},\\{3,5,6\\}$ and $\\{5,6,7\\}$, in which all of them are
transverse.

Figure 6: Neighborhood condition depicted, for $d\in\\{1,2,3\\}$. For all
dimensions, the neighbouring cells $\alpha$ and $\alpha^{\prime}$ are drawn in
blue and yellow, respectively, whilst the common boundary
($\alpha\cap\alpha^{\prime}$) is represented in green. The presence (or
absence) of the red dashed edge in the simplicial complex defines whether
$\alpha$ and $\alpha^{\prime}$ are transverse or parallel. In all cases, the
intersection $\gamma:=\alpha\cap\alpha^{\prime}$ is a $(d-1)$-cell such that
$\gamma<\alpha,\alpha^{\prime}$, which guarantees that for $\alpha$ and
$\alpha^{\prime}$ to be neighbours, it is sufficient to reach the cell
neighbourhood condition $1.$ is reached. This result is a consequence of
Theorem B.7.

######  Example 7 (Cell Neighborhood condition).

In Fig. 6, we have the characterization of neighborhood of $d$-cells, $\alpha$
(blue) and $\alpha^{\prime}$ (yellow), for $d\in\\{1,2,3\\}.$ Suppose that the
red-dashed edge belongs to the graph. For $d=1$, we have that
$\alpha=\\{2,3\\}$ and $\alpha^{\prime}=\\{2,4\\}$ are transverse neighbors,
once that the $2$-cell $\beta=\\{2,3,4\\}$ is such that
$\beta>\alpha,\alpha^{\prime}$. Analogously, for $d=2$, the $2$-cells
$\alpha=\\{1,2,4\\}$ and $\alpha^{\prime}=\\{2,3,4\\}$ are transverse once
that $\beta=\\{1,2,3,4\\}$ is a $3$-cell such that
$\beta>\alpha,\alpha^{\prime}$. Also, for $d=3$, $\alpha=\\{1,2,3,4\\}$,
$\alpha^{\prime}=\\{2,3,4,5\\}$ are transverse once that
$\beta=\\{1,2,3,4,5\\}$ is a $4$-cell such that
$\beta>\alpha,\alpha^{\prime}$. Regardless of the existence of the red-dashed
edge in the graph, we have that, for $d\in\\{1,2,3\\}$, there is a
$(d-1)$-cell, $\gamma:=\alpha\cap\alpha^{\prime}$ such that
$\gamma<\alpha,\alpha^{\prime}$. This fact can be justified by the result of
Theorem B.3, which guarantees that is sufficient to have a common boundary
between two $d$-cells so they can be neighbours. The dashed-red edge’s absence
(or presence) guarantees they are parallel (transverse) neighbours.

######  Example 8 (Forman-Ricci curvature).

In Fig. 1, $F_{1}(\\{3,4\\})=1+2-4=-1,$ $F_{2}(\\{3,5,7\\})=1+3-0=4.$

##  Appendix B Demonstrations

Here we are considering $\pi_{\alpha}$ and $\pi_{x}$ as defined in Section 2.

######  Theorem B.1.

Let $C_{d}$ be the set of all $d$-cells of a simplicial complex, as defined in
Section 2. Then,

(21) $\displaystyle
C_{d}=\Big{\\{}\alpha:=\\{x_{0},\ldots,x_{d}\\},\,\,x_{i}\in\pi_{\alpha\setminus\\{x_{i}\\}},\,\forall
i\Big{\\}}.$

######  Proof B.2.

First inclusion will be proven by contradiction. Let $\alpha\in C_{d}$.
Suppose that $\alpha$ is not contained in the right-hand side of the equation
above, i.e., there exists $x\in\alpha$ such that
$x\notin\pi_{\alpha\setminus\\{x\\}}.$ It means that exists $y\in\alpha$ such
that $y\neq x$ and $x\notin\pi_{y}$, which implies that $\alpha$ does not
belong to $C_{d}$.

Also, let $\alpha$ as on the right-hand side in (21), from the definition of
the set on the right-hand side, in $G$ every pair of vertices in $\alpha$ is
connected. Also $|\alpha|=d+1$. Define $V_{\alpha}=\alpha$ and
$E_{\alpha}=\\{(x_{i},x_{j})\hskip 2.84526pt|\hskip 2.84526ptx_{i},x_{j}\in
V_{\alpha},x_{i}\neq x_{j}\\}$ such that $G_{\alpha}=(V_{\alpha},E_{\alpha})$.
It is clear that $G_{\alpha}$ is a complete subgraph with $d+1$ nodes and we
can identify $V_{\alpha}\sim G_{\alpha}$. It follows that $\alpha\in C_{d}$.

######  Theorem B.3.

Let $\alpha,\alpha^{\prime}\in C_{d}$, $\alpha\neq\alpha^{\prime}$. They are
neighbours if and only if $\alpha\cap\alpha^{\prime}$ is the $(d-1)$-cell that
is common to the boundaries of $\alpha$ and $\alpha^{\prime}$.

######  Proof B.4.

The forward implication is proven as follows: Suppose condition 1. of the cell
neighbourhood is satisfied. There exists $\gamma\in C_{d-1}$ such that
$\gamma<\alpha,\alpha^{\prime}$. In particular,
$\gamma\subset\alpha,\alpha^{\prime}$ and $|\gamma|=d$. It is sufficient to
prove that $\gamma=\alpha\cap\alpha^{\prime}$. The inclusion
$\gamma\subseteq\alpha\cap\alpha^{\prime}$ is obvious. Suppose, by absurdity,
that there exists $x\in\alpha\cap\alpha^{\prime}$ such that $x\notin\gamma$.
Once the first inclusion is valid, it follows that
$\gamma\cup\\{x\\}\subset(\alpha\cap\alpha^{\prime})\cup\\{x\\}=\alpha\cap\alpha^{\prime}$,
which lead us to $|\gamma\cup\\{x\\}|\leq d$.

Now, suppose that condition 2. is reached. There exists $\beta\in C_{d+1}$
such that $\beta>\alpha,\alpha^{\prime}$. In particular,
$\beta\supset\alpha\cap\alpha^{\prime}:=\gamma.$ First, we need to prove that
$|\gamma|$=d. Note that we can write $\beta=\alpha\cup\\{x\\},$ for some
$x\notin\alpha.$ Analogously, we can write $\beta=\alpha^{\prime}\cup\\{y\\},$
for some $y\notin\alpha^{\prime},$ with $x\neq y.$ By intersecting this
equalities we have
$\beta=(\alpha\cup\\{x\\})\cap(\alpha^{\prime}\cup\\{y\\})=[\alpha\cap(\alpha^{\prime}\cup\\{y\\})]\cup[\\{x\\}\cap(\alpha^{\prime}\cup\\{y\\})]=[\gamma\cup(\alpha\cap\\{y\\})]\cup[(\\{x\\}\cap\alpha^{\prime})\cup(\\{x\\}\cap\\{y\\})]=\gamma\cup\\{x,y\\}.$
Thus, $|\gamma|=|\beta|-2=d.$ Suppose that $\gamma\notin C_{d-1}.$ Then, there
exists $y\in\gamma$ such that
$y\notin\bigcap_{\begin{subarray}{c}x\in\gamma\\\ x\neq
y\end{subarray}}\pi_{x}$. However, $\gamma\subset\alpha$, and it would imply
that $\alpha\notin C_{d}.$ The opposite implication of the theorem is obvious.

######  Theorem B.5.

Let $\alpha,\alpha^{\prime}\in C_{d}.$ Then, $\alpha$ and $\alpha^{\prime}$
are neighbours if and only if $\left|\alpha\cap\alpha^{\prime}\right|=d.$

######  Proof B.6.

It follows as a corollary from Theorem B.3. This neighbourhood condition can
be better elucidated in 7.

######  Theorem B.7.

Let $\alpha,\alpha^{\prime}\in C_{d}.$ Then, the neighborhood condition $2.$
implies the condition $1.$, i.e., $\alpha$ and $\alpha^{\prime}$ are
neighbours if and only if the condition $1.$ of cell neighbourhood is reach.

######  Proof B.8.

It follows as a corollary from Theorem B.3.

######  Theorem B.9.

Let $\alpha\in C_{d}$, and $N^{d}_{\alpha}$ as defined originally in Section
3. Then,

(22) $\displaystyle
N^{d}_{\alpha}=\bigsqcup_{\gamma\in\partial(\alpha)}\,\bigcup_{x\in\pi_{\gamma}\setminus(\alpha\setminus\gamma)\neq\emptyset}\\{\gamma\cup\\{x\\}\\}.$

######  Proof B.10.

Let $\alpha^{\prime}\in N_{\alpha}^{d}$. From Theorem B.3, there exists
$\gamma\in C_{d-1}$ such that $\gamma=\alpha\cap\alpha^{\prime}$ and in
particular, $|\gamma|=d.$ Once that $|\alpha|=|\alpha^{\prime}|=d+1$ and
$\gamma\subset\alpha,\alpha^{\prime}$, there exists $x\in V\setminus\alpha$
such that we can write $\alpha^{\prime}=\gamma\cup\\{x\\}.$ Analogously, there
exists $y\in V\setminus\alpha^{\prime}$ such that we can write
$\alpha=\gamma\cup\\{y\\}.$ It is clear that
$\pi_{\gamma}\setminus(\alpha\setminus\gamma)=\pi_{\gamma}\setminus\\{y\\}$.
Suppose this set is not empty. We need to prove that
$x\in\pi_{\gamma}\setminus(\alpha\setminus\gamma).$ By absurdity, suppose that
$x$ is not in this set. By using set complementary property, we have that
$x\in(\pi_{\gamma})^{\mathsf{c}}\cup(\alpha\setminus\gamma).$ If
$x\in\alpha\setminus\gamma,$ then $\alpha=\alpha^{\prime}.$ If
$x\in\pi_{\gamma}^{\mathsf{c}},$ then there exists $z\in\gamma$ such that
$x\notin\pi_{\gamma},$ which implies that $\alpha^{\prime}$ is not a $d$-cell.

The opposite inclusion is proven as follows: Let $\alpha^{\prime}$ be such
that $\alpha^{\prime}=\gamma\cup\\{x\\},$ for some
$x\in\pi_{\gamma}\setminus(\alpha\setminus\gamma),$ and some
$\gamma\in\partial(\alpha).$ Note that
$|\alpha\cap\alpha^{\prime}|=|\alpha\cap(\gamma\cup\\{x\\})|=|(\alpha\cap\gamma)\cup(\alpha\cap\\{x\\})|=|\gamma|=d.$
The result follows from applying Theorem B.3 once proven that
$\alpha^{\prime}\in C_{d}.$ Indeed,
$|\alpha^{\prime}|=|\gamma\cup\\{x\\}|=d+1.$ Suppose by absurdity that
$\alpha^{\prime}\notin C_{d}.$ Than, by using the the result of Theorem B.1,
there exists $z\in\alpha^{\prime}$ such that
$z\notin\pi_{\alpha^{\prime}\setminus\\{z\\}}.$ In case of $z=x$, we have that
it contradicts that $x\in\pi_{\gamma}\setminus\\{y\\}$. Also, if $z\neq x,$ we
would have that $z\in\gamma$ and it contradicts that $\alpha\in C_{d}.$

######  Theorem B.11.

Let $\alpha\in C_{d}$ and $T^{d}_{\alpha}$ as described in Section 3. Then,

(23) $\displaystyle
T^{d}_{\alpha}=\bigsqcup_{\gamma\in\partial(\alpha)}\,\bigcup_{x\in\pi_{\gamma}\cap\pi_{\alpha\setminus\gamma}\neq\emptyset}\\{\gamma\cup\\{x\\}\\}.$

######  Proof B.12.

The direct inclusion is proven as follows: Let $\alpha^{\prime}\in
T_{\alpha}^{d}.$ From (5), we have in particular that $\alpha^{\prime}\in
N^{d}_{\alpha},$ which means by Theorem B.3 that
$\gamma:=\alpha\cap\alpha^{\prime}\in C_{d-1}$ and we can characterize
$\alpha^{\prime}=\gamma\cup\\{x\\},$ for some $x\notin\gamma$ and also
$x\notin\alpha.$ We need to show that
$x\in\pi_{\gamma}\cap\pi_{(\alpha\setminus\gamma)}=\pi_{\alpha}.$ If
$x\notin\pi_{\alpha},$ exists $y\in\alpha$ such that $x\notin\pi_{y}$. Using
that $\alpha$ and $\alpha^{\prime}$ are transverse neighbours, we have that
exists $\beta\in C_{d+1}$ such that $\beta>\alpha,\alpha^{\prime},$ which
means that $x,y\in\beta,$ which contradicts the fact that $\beta$ is a
$(d+1)$-cell.

The opposite inclusion is proven as follows: Let
$\alpha^{\prime}=\gamma\cup\\{x\\},$ for some $\gamma\in\partial(\alpha)$ and
$x\in\pi_{\alpha}.$ We can write $\alpha=\gamma\cup\\{y\\},$ where
$y\notin\gamma,\,y\neq x.$ Define $\beta:=\gamma\cup\\{x,y\\}.$ It is obvious
that $\left|\beta\right|=d+2.$ We need to show that
$\beta>\alpha,\alpha^{\prime}.$ Once that
$\beta\supset\alpha,\alpha^{\prime},$ it is enough to show that $\beta\in
C_{d+1}.$ Note that, by the definition of $\alpha^{\prime}$ and $\alpha$,
$\forall z\in\gamma$ we have $z\in\pi_{\alpha}=\pi_{\beta\setminus\\{y\\}}$,
$z\in\pi_{\alpha^{\prime}}=\pi_{\beta\setminus\\{x\\}}$, $x\in\pi_{\gamma}$
and $y\in\pi_{\gamma}$. In addition, since we took $x\in\pi_{\alpha}$, we have
$x\in\pi_{y}$, therefore $\forall z\in\gamma\cup\\{x,y\\}=:\beta$, we have
that $z\in\pi_{\gamma\cup\\{x,y\\}\setminus\\{z\\}}$
$=\pi_{\beta\setminus\\{z\\}}$.

######  Theorem B.13.

Let $H^{d}_{\alpha}$ as defined in Section 3. Then,

(24) $\displaystyle
H^{d}_{\alpha}=\bigcup_{x\in\pi_{\alpha}\neq\emptyset}\\{\alpha\cup\\{x\\}\\}.$

######  Proof B.14.

Let $\beta\in H^{d}_{\alpha}.$ In particular, $\beta\supset\alpha$ implies
that exists $x\notin\alpha$ such that we can write $\beta=\alpha\cup\\{x\\}.$
It is clear that $x\in\pi_{\alpha},$ otherwise $\beta$ would not be a
$(d+1)$-cell. Let $\beta$ in be a set of the form $\beta=\alpha\cup\\{x\\},$
for some $x\in\pi_{\alpha}.$ It is enough to show that $\beta\in C_{d+1}$,
which is immediate, once that $\left|\beta\right|=d+2.$

######  Theorem B.15.

Let $\alpha\in C_{d}$. Then,

(25) $\left|T^{d}_{\alpha}\right|=(d+1)\left|H^{d}_{\alpha}\right|.$

######  Proof B.16.

Note that $\pi_{\alpha}=\pi_{\gamma}\cap\pi_{\alpha\setminus\gamma}$, for all
$\gamma\in\partial(\alpha).$ Thus, by taking the cardinality of
$T^{d}_{\alpha}$ and $H^{d}_{\alpha}$ using the equalities in Theorem B.11 and
Theorem B.13, we have

(26)
$\displaystyle\left|T^{d}_{\alpha}\right|=\sum_{\gamma\in\partial(\alpha)}\left|\pi_{\alpha}\right|=(d+1)\left|\pi_{\alpha}\right|=(d+1)\left|H^{d}_{\alpha}\right|.$

######  Theorem B.17.

Let $P^{d}_{\alpha}$ as defined in Section 3. Then,

(27) $\displaystyle
P^{d}_{\alpha}=\bigsqcup_{\gamma\in\partial(\alpha)}\bigcup_{\begin{subarray}{c}\Pi^{\gamma}_{\alpha}\neq\emptyset\\\
x\in\Pi^{\gamma}_{\alpha}\end{subarray}}\\{\gamma\cup\\{x\\}\\},$

where

(28)
$\displaystyle\Pi^{\gamma}_{\alpha}=\pi_{\gamma}\setminus(\pi_{\alpha}\cup(\alpha\setminus\gamma)).$

######  Proof B.18.

Let $\alpha^{\prime}\in C_{d}$ such that condition $1.$ but not $2.$ is
reached. From Theorem B.3, we have that
$\gamma=\alpha\cap\alpha^{\prime}\in\partial(\alpha).$ Also, we can write
$\alpha^{\prime}=\gamma\cup\\{x\\}$ for some $x\notin\gamma$, $x\notin\alpha$
and $x\in\pi_{\gamma}$. Suppose $x\notin\Pi^{\gamma}_{\alpha}.$ Thus, using
complement set property, we reach that
$x\in\pi_{\alpha}\cup(\alpha\setminus\gamma)\cup(\pi_{\gamma})^{c}$. By the
definition of $\alpha^{\prime}$, $x\notin\alpha\setminus\gamma$. Clearly, $x$
cannot be in $\pi_{\alpha},$ otherwise we would have $\beta=\alpha\cup\\{x\\}$
a $(d+1)$-cell such that $\alpha,\alpha^{\prime}<\beta$ and the second
condition would be satisfied. However, if $x\notin\pi_{\gamma}$ we have that
$\alpha^{\prime}\notin C_{d}.$

Now, suppose that $\alpha^{\prime}=\gamma\cup\\{x\\},$ some
$\gamma\in\partial(\alpha)$ and $x\in\Pi^{\gamma}_{\alpha}.$ It is obvious
that $\gamma<\alpha,\alpha^{\prime}.$ By absurdity, suppose that condition
$2.$ is reached. Then there is $\beta\in C_{d+1}$ such that
$\beta>\alpha,\alpha^{\prime},$ in particular, $\beta\supset\alpha.$ However,
$x\in\beta$ and $x\notin\pi_{\alpha}\cup(\alpha\setminus\gamma),$ which
contradicts that $\beta$ is a $(d+1)$-cell.

######  Theorem B.19.

Let $\alpha=\\{x_{0},\ldots,x_{d}\\}\in C_{d}.$ The Forman-Ricci curvature
defined in equation (6) can be re-written in terms of the node neighbourhood
(1) as

(29) $\displaystyle
F_{d}(\alpha)=(d+2)\left|\bigcap_{i=0}^{d}{}\pi_{x_{i}}\right|+2\cdot(d+1)-\sum_{i=0}^{d}\left|\bigcap_{\begin{subarray}{c}j=0\\\
j\neq i\end{subarray}}^{d}\pi_{x_{j}}\right|.$

######  Proof B.20.

Using the result of Theorem B.15 and equation (5) applied to equation (7), we
have that

(30) $\displaystyle
F(\alpha)=(d+2)\left|H^{d}_{\alpha}\right|+(d+1)-\left|N^{d}_{\alpha}\right|.$

By Theorem B.9, we can have the neighbours by boundary (when they exist) in
the form $\alpha^{\prime}_{i}=\gamma_{i}\cap\\{y_{i}\\},$ for some
$y_{i}\in\pi_{\gamma_{i}}\setminus(\alpha\setminus\gamma_{i})$, for all
$\gamma_{i}\in\partial(\alpha),i=1,\ldots,d.$ Once that
$|\alpha\setminus\gamma_{i}|=1,\forall i=1,\ldots,d,$ we can define
$\\{x_{i}\\}:=\alpha\setminus\gamma_{i},$ and, for all
$\gamma_{i}\in\partial(\alpha),$ we have

(31)
$\displaystyle\left|N^{d}_{\alpha}\right|=\sum_{i=0}^{d}\left|\pi_{\gamma_{i}}\setminus\\{x_{i}\\}\right|=\sum_{i=0}^{d}\left|\bigcap_{\begin{subarray}{c}j=0\\\
j\neq i\end{subarray}}\pi_{x_{j}}-\\{x_{i}\\}\right|$
$\displaystyle=\sum_{i=0}^{d}\left|\bigcap_{\begin{subarray}{c}j=0\\\ j\neq
i\end{subarray}}\pi_{x_{j}}\right|-(d+1).$

Also,

(32)
$\displaystyle\left|H^{d}_{\alpha}\right|=\left|\pi_{\alpha}\right|=\left|\bigcap_{i=0}^{d}\pi_{x_{i}}\right|.$

The result follows from applying these formulas to the equation (30).

## Acknowledgments

This research is supported by the Basque Government through the BERC 2022-2025
program and by the Ministry of Science and Innovation: BCAM Severo Ochoa
accreditation CEX2021-001142-S / MICIN / AEI / 10.13039/501100011033.
Moreover, the authors acknowledge the financial support received from the IKUR
Strategy under the collaboration agreement between Ikerbasque Foundation and
BCAM on behalf of the Department of Education of the Basque Government. SR
further acknowledges the RTI2018-093860-B-C21 funded by (AEI/FEDER, UE) and
acronym “MathNEURO”.

## References

  * [1] A.-L. Barabási et al., Network science, Cambridge university press, 2016.
  * [2] D. S. Bassett and O. Sporns, Network neuroscience, Nature Neuroscience, 20 (2017), pp. 353–364, https://doi.org/10.1038/nn.4502, http://www.nature.com/articles/nn.4502.
  * [3] S. Bochner, Vector fields and ricci curvature, (1946).
  * [4] S. Bochner, Curvature and betti numbers. ii, Annals of Mathematics, (1949), pp. 77–93.
  * [5] K. Börner, S. Sanyal, A. Vespignani, et al., Network science, Annu. rev. inf. sci. technol., 41 (2007), pp. 537–607.
  * [6] P. Bubenik, Statistical topological data analysis using persistence landscapes, The Journal of Machine Learning Research, 16 (2015), pp. 77–102.
  * [7] T. Chatterjee, R. Albert, S. Thapliyal, N. Azarhooshang, and B. DasGupta, Detecting network anomalies using forman–ricci curvature and a case study for human brain networks, Scientific reports, 11 (2021), p. 8121.
  * [8] S. Dakurah, D. V. Anand, Z. Chen, and M. K. Chung, Modelling cycles in brain networks with the hodge laplacian, in International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer, 2022, pp. 326–335.
  * [9] D. B. de Souza, Forman-ricci curvature benchmark report, 2023, https://https://www.kaggle.com/datasets/danillosouza2020/forman-ricci-curvature-benchmark-report.
  * [10] D. B. de Souza, J. T. S. da Cunha, E. F. dos Santos, J. B. Correia, H. P. da Silva, J. L. de Lima Filho, J. Albuquerque, and F. A. N. Santos, Using discrete ricci curvatures to infer COVID-19 epidemic network fragility and systemic risk, Journal of Statistical Mechanics: Theory and Experiment, 2021 (2021), p. 053501, https://doi.org/10.1088/1742-5468/abed4e, https://doi.org/10.1088/1742-5468/abed4e.
  * [11] J. Derks, J. C. Reijneveld, and L. Douw, Neural network alterations underlie cognitive deficits in brain tumor patients, Current Opinion in Oncology, 26 (2014), pp. 627–633, https://doi.org/10.1097/CCO.0000000000000126, http://www.ncbi.nlm.nih.gov/pubmed/25188475http://content.wkhealth.com/linkback/openurl?sid=WKPTLP:landingpage&an=00001622-201411000-00015.
  * [12] P. D. Dieu et al., Average polynomial time complexity of some np-complete problems, Theoretical computer science, 46 (1986), pp. 219–237.
  * [13] H. Edelsbrunner and J. L. Harer, Computational topology: an introduction, American Mathematical Society, 2022.
  * [14] H. Edelsbrunner and S. Parsa, On the computational complexity of betti numbers: reductions from matrix rank, in Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SIAM, 2014, pp. 152–160.
  * [15] H. B. Enderton, Elements of set theory, Academic press, 1977.
  * [16] J. Fan, J. Meng, Y. Ashkenazy, S. Havlin, and H. J. Schellnhuber, Network analysis reveals strongly localized impacts of El Niño., Proceedings of the National Academy of Sciences of the United States of America, 114 (2017), pp. 7543–7548, https://doi.org/10.1073/pnas.1701214114, http://www.ncbi.nlm.nih.gov/pubmed/28674008http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=PMC5530664.
  * [17] M. R. Fellows, F. A. Rosamond, U. Rotics, and S. Szeider, Clique-width is np-complete, SIAM Journal on Discrete Mathematics, 23 (2009), pp. 909–939.
  * [18] R. Forman, Bochner’s method for cell complexes and combinatorial ricci curvature, Discrete and Computational Geometry, 29 (2003), pp. 323–374.
  * [19] T. Fülöp, M. Desroches, A. A. Cohen, F. A. N. Santos, and S. Rodrigues, Why we should use topological data analysis in ageing: Towards defining the “topological shape of ageing”, Mechanisms of Ageing and Development, 192 (2020), p. 111390.
  * [20] A. Guidolin, M. Desroches, J. D. Victor, K. P. Purpura, and S. Rodrigues, Geometry of spiking patterns in early visual cortex: a topological data analytic approach, Journal of the Royal Society Interface, 19 (2022), p. 20220677.
  * [21] A. Hagberg and D. Conway, Networkx: Network analysis with python, URL: https://networkx.github.io, (2020).
  * [22] T. J. Jech, T. Jech, T. J. Jech, G. B. Mathematician, T. J. Jech, and G.-B. Mathématicien, Set theory, vol. 14, Springer, 2003.
  * [23] D. Krioukov, M. Kitsak, R. S. Sinkovits, D. Rideout, D. Meyer, and M. Boguñá, Network Cosmology, Scientific Reports, 2 (2012), p. 793, https://doi.org/10.1038/srep00793, http://www.nature.com/articles/srep00793.
  * [24] T. G. Lewis, Network science, New Jersey: Wiley and Sons, 10 (2009), p. 9780470400791.
  * [25] Y. Lin, L. Lu, and S.-T. Yau, Ricci curvature of graphs, Tohoku Mathematical Journal, 63 (2011), pp. 605–627, https://doi.org/10.2748/tmj/1325886283, http://projecteuclid.org/euclid.tmj/1325886283.
  * [26] C. Maria, J.-D. Boissonnat, M. Glisse, and M. Yvinec, The gudhi library: Simplicial complexes and persistent homology, in International congress on mathematical software, Springer, 2014, pp. 167–174.
  * [27] V. Pascucci, X. Tricoche, H. Hagen, and J. Tierny, Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications, Springer Science & Business Media, 2010.
  * [28] Z. Pawlak, Rough set theory and its applications, Journal of Telecommunications and information technology, (2002), pp. 7–10.
  * [29] R. Peeters, The maximum edge biclique problem is np-complete, Discrete Applied Mathematics, 131 (2003), pp. 651–654.
  * [30] M. Penrose, Random geometric graphs, vol. 5, OUP Oxford, 2003.
  * [31] M. Saggar, O. Sporns, J. Gonzalez-Castillo, P. A. Bandettini, G. Carlsson, G. Glover, and A. L. Reiss, Towards a new approach to reveal dynamical organization of the brain using topological data analysis, Nature communications, 9 (2018), pp. 1–14.
  * [32] 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), pp. 1–16.
  * [33] R. Sandhu, T. Georgiou, E. Reznik, L. Zhu, I. Kolesov, Y. Senbabaoglu, and A. Tannenbaum, Graph curvature for differentiating cancer networks, Scientific reports, 5 (2015), p. 12323.
  * [34] 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.
  * [35] F. A. Santos, E. P. Raposo, M. D. Coutinho-Filho, M. Copelli, C. J. Stam, and L. Douw, Topological phase transitions in functional brain networks, bioRxiv, (2018), p. 469478.
  * [36] F. A. Santos, P. K. Tewarie, P. Baudot, A. Luchicchi, D. A. Barros de Souza, G. Girier, A. P. Milan, T. Broeders, E. G. Centeno, R. Cofre, et al., Emergence of high-order functional hubs in the human brain, bioRxiv, (2023), pp. 2023–02.
  * [37] E. Saucan and M. Weber, Forman’s ricci curvature-from networks to hypernetworks, in International conference on complex networks and their applications, Springer, 2018, pp. 706–717.
  * [38] M. M. Schoonheim, K. A. Meijer, and J. J. G. Geurts, Network Collapse and Cognitive Impairment in Multiple Sclerosis, Frontiers in Neurology, 6 (2015), p. 82, https://doi.org/10.3389/fneur.2015.00082, http://journal.frontiersin.org/article/10.3389/fneur.2015.00082/abstract.
  * [39] C. J. Stam, Modern network science of neurological disorders, Nature Reviews Neuroscience, 15 (2014), pp. 683–695, https://doi.org/10.1038/nrn3801, http://www.ncbi.nlm.nih.gov/pubmed/25186238http://www.nature.com/doifinder/10.1038/nrn3801.
  * [40] D. Taylor, F. Klimm, H. A. Harrington, M. Kramár, K. Mischaikow, M. A. Porter, and P. J. Mucha, Topological data analysis of contagion maps for examining spreading processes on networks, Nature Communications, 6 (2015), p. 7723, https://doi.org/10.1038/ncomms8723, http://www.nature.com/articles/ncomms8723.
  * [41] M. Tsitsvero, Hodgelaplacians, 2019, https://github.com/tsitsvero/hodgelaplacians.
  * [42] G. Van Rossum and F. L. Drake Jr, Python reference manual, Centrum voor Wiskunde en Informatica Amsterdam, 1995.
  * [43] M. Weber, J. Jost, and E. Saucan, Forman-ricci flow for change detection in large dynamic data sets, Axioms, 5 (2016), p. 26.
  * [44] 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.
  * [45] J. Wee, Generalisedformanricci, 2020, https://github.com/ExpectozJJ/GeneralisedFormanRicci.
  * [46] H.-J. Zimmermann, Applications of fuzzy set theory to mathematical programming, Information sciences, 36 (1985), pp. 29–58.
  * [47] A. Zomorodian, Topological data analysis, Advances in applied and computational topology, 70 (2012), pp. 1–39.