# Network analysis of a complex disease: the gut microbiota in the
inflammatory bowel disease case

Mirko Hu  University of Parma, Department of Medicine and Surgery, Parma,
43121, Italy  Guido Caldarelli  Ca’ Foscari University of Venice, Department
of Molecular Science and Nanosystems, Venice, 30123, Italy
<EMAIL_ADDRESS>Tommaso Gili  IMT School for Advanced Studies
Lucca, Networks unit, Lucca, 55100, Italy

###### Abstract

Inflammatory bowel diseases (IBD) are complex diseases in which the gut
microbiota is attacked by the immune system of genetically predisposed
subjects when they are exposed to yet unclear environmental factors. The
complexity of this class of diseases makes them suitable to be represented and
studied with network science. In the project, the metagenomic data of the gut
microbiota of control, Crohn’s disease, and ulcerative colitis subjects were
divided in three ranges (prevalent, common, uncommon). Then, correlation
networks and co-expression networks were used to represent this data. The
former networks involved the calculation of the Pearson’s correlation and the
use of the percolation threshold to binarize the adjacency matrix, whereas the
latter involved the construction of the bipartite networks and the monopartite
projection after binarization of the biadjacency matrix. Then, centrality
measures and community detection were used on the so-built networks. The main
results obtained were about the modules of Bacteroides, which were connected
in control subjects’ correlation network, Faecalibacterium prausnitzii, where
co-enzyme A became central in IBD correlation networks and Escherichia coli,
which module has different position in the different diagnoses networks.

## Introduction

Microbes are ubiquitous. From radioactive waste to the human gastrointestinal
tract, they can be found nearly everywhere. In and on the human body, they
have evolved to co-exist with their host and it is estimated that the amount
of microbes hosted by the human body is of the same order of magnitude as the
number of human cells [1]. In particular, the $10^{14}$ commensal microbes
living in the intestinal tract form the human gut microbiota, which has
evolved to live in symbiosis with its host [2]. It is widely accepted that
this symbiosis begins from birth and the microbial communities stabilize with
age until the formation of an adult microbiota [3]. Its genetic content
(called the microbiome) characterizes each individual, rising also concerns
about identity and privacy issues, specifically when the study and the
manipulation of the microbiota are considered [4]. Since the 1840s, when the
concept of gut microbiota first appeared, the topic has been studied for two
centuries [5], and, at the moment, it is known that the gut microbiota has a
fundamental role in shaping the gut barriers [6], training the host immune
system and regulating the metabolism [7]. When the compositional and metabolic
equilibrium of the commensal microbes living in the gut is disrupted,
different types of diseases arise such as metabolic disorders or central
nervous system disorders [8]. Historically, traditional medicine attempted to
re-establish this equilibrium through remedies intervening on the digestive
system, like fasting, diets, assumption of spring waters or laxatives. A quite
recent procedure introduced to tackle the C. difficile infection is the faecal
microbiota transplantation (FMT) [9] which consists in repopulating the
intestinal tract of an ill subject with the microbiota of a healthy donor.

Inflammatory bowel diseases (IBDs), which comprise Crohn’s disease (CD) and
ulcerative colitis (UC), are an important class of diseases that arises from
dysbiosis and are being treated with FMT. Typical symptoms of this class of
diseases are chronic diarrhoea, abdominal pain, rectal bleeding, weight loss
and fatigue [10]. Although CD and UC are both characterized by the
inflammation of the intestinal tract, there are several differences between
the two diagnoses that span from the environmental factors that cause them,
e.g. smoking or diet, to the clinical and endoscopic findings in the two
diagnoses [11]. Overall, IBDs are becoming widespread in modern society
because of the change in lifestyle, socioeconomic developments and
environmental causes [12]. Until now, it is known that IBD is an exaggerated
immune response to the gut microbiota of genetically predisposed subjects
under the influence of the external environment. This complex interplay
between genetics, the microbiota, the immune system and the environment makes
it particularly hard to understand this class of diseases. [13] offered a
complete historical review of the IBD until the 1980s, by quoting Hippocrates
who described diarrhoea as a symptom of an infectious (or non-infectious)
disease to a description of hypothetical pathogenesis of IBD, which the
microbiota was not considered, though. A more recent projection predicted the
evolution of the disease between 2015 and 2025 and updated the possible
origins of IBD including the action of antibiotics on the gut microbiota in
Western society [14]. [15] summarized the findings of the origins of the IBD,
mentioning the complexity of the disease. Another historical review focuses on
the genetics of the IBD [16] identified NOD2 as the first CD susceptible gene
and then described the evolution of the IBD genetics with the coming of the
modern genome-wide association study. One of the first most comprehensive work
describing the interaction of all the aforementioned factors can be found in
[17]. Whereas, the systems biology approach to the study of IBD was presented
by [18], which proposed the creation of an IBD interactome, a complex system
connecting all the potential agents interacting among them that derived from
the combination of different omics [19].

Our work starts from here and attempts to provide tools and methods from
network science useful to build and to study the IBD interactome with a
systems biology approach by commencing from the metagenomic data of the gut
microbiome. This approach is typical of network medicine, a novel discipline
that mixes network science with systems biology to tackle the challenges
offered by the progress of personalized medicine [20], which opposes to the
current effective yet drastic procedures like the aforementioned FMT. Network
science is the discipline used to analyse complex systems and could be suited
to understand a complex disease like IBD in which a complex system like the
gut microbiota plays a fundamental role. Complexity in the intestinal
microbial communities arises at different scales; from the macroscopic point
of view, we have the ecological interactions [21, 22] that describe the
relationships among the species in the gut microbiota; among these, we have
three main different types of interactions [23]; positive interactions
(cooperation, commensalism, cross-feeding), negative interactions
(competition, ammensalism), and asymmetric interactions (exploitation,
predation, parasitism). Going towards a more microscopic scale, we can find
the gene networks, often represented by gene co-expression networks [24] and
metabolic networks built by connecting the substances, known as metabolites,
reacting in the same metabolic processes [25]. When the interaction between
bacterial proteins is considered, we are dealing with metaproteomics, which is
a novel tool in the analysis of IBD; nonetheless, the data used is still
scarce [26].

The application of network science for the study of the complexity of the gut
microbiome is recent and one of the first research was in the case of C.
difficile infection [27]. The microbiome in this work was represented as a
boolean network derived from binarized temporal data of the abundance of
specific bacteria species in the gut. Although the study was able to capture
the dynamics of the bacterial species, e.g. negative, positive or neutral
interaction, it did not take into account the genetic expression of the
microbiome (metagenome), which could explain better the complex interplay
between the bacterial species. Our study, by contrast, gives a static
screenshot of the microbial interactions through metagenomics. A more recent
study [28] analysed the co-abundance network built with SparCC [29], the need
of this tool is due to the necessity of sparsifying the network that would
have too many correlated nodes because of normalization and a $p$-value
threshold too high [30]. Based on a topological property of the biological
networks, the work by [24] portraits a weighted gene co-expression network
analysis by building a network from metagenomic data and removing the weaker
edges based on the assumption that the final network would be scale-free. In
our work, we used thresholding methods that rely on the network topology such
as the percolation threshold or the $p$-value for the projected edges,
similarly to the later research. These methods should overcome the
aforementioned problems.

## Results

In the next paragraphs, the pathways are called with their node numbers for
the sake of brevity and clarity, it is possible to consult the table mapping
these correspondences in the Supplementary Material.

### Bacteroides and Faecalibacterium prausnitzii

In the prevalent pathways, the number of edges in the NI correlation network
was $3356$ ($\text{th}_{\text{NI}}=0.453$), in CD correlation network was
$2905$ ($\text{th}_{\text{CD}}=0.357$), and in UC correlation network was
$3160$ ($\text{th}_{\text{UC}}=0.364$). The results showed that NI metagenome
was more connected for prevalent pathways and the percolation threshold was
higher compared to the percolation thresholds in CD and UC correlation
networks, translating into more strongly correlated nodes in the NI
correlation network. From the community detection algorithm, we obtained that
the lowest modularity ($0.538$) can be found in NI correlation network,
meaning that it was not possible to completely separate some of the modules
and there would be interconnections between them, CD and UC correlation
networks resulted in a modularity of $0.583$ and $0.622$, respectively.

As we can see in Figure LABEL:res1, the pathways in the NI correlation network
were divided into three large modules, one module was isolated, by contrast,
the other two modules were communicating strictly through several nodes. The
isolated module was composed of Bacteroides vulgatus and Bacteroides uniformis
pathways, this meant that in control subjects the two species co-variated and
were interdependent through specific pathways (on the frontiers of the species
modules, it was possible to find nodes $794$, $658$, $292$, $477$ on the B.
uniformis side and nodes $261$, $855$, $1027$, $1068$ on the B. vulgatus
side). The light purple module, on the other hand, contained Faecalibacterium
prausnitzii, whereas the remaining large module contained the B. ovatus
pathways, E. rectale pathways, and the unclassified species pathways. The
nodes with the highest betweenness centrality among the unclassified pathways
in the two connected modules were connected through:

  1. 1.

node $821$ (PWY-6527: stachyose degradation);

  2. 2.

node $177$ (GLYCOGENSYNTH-PWY: glycogen biosynthesis I (from ADP-D-Glucose));

  3. 3.

node $1225$ (PWY66-422: D-galactose degradation V (Leloir pathway));

  4. 4.

node $751$ (PWY-6317: galactose degradation I (Leloir pathway)).

Whereas, the nodes with the highest betweenness centrality among the F.
prausnitzii pathway module that was connected to the unclassified pathway
module were:

  1. 1.

node $466$ (PWY-5659: GDP-mannose biosynthesis);

  2. 2.

node $724$ (PWY-6277: superpathway of 5-aminoimidazole ribonucleotide
biosynthesis);

  3. 3.

node $579$ (PWY-6121: 5-aminoimidazole ribonucleotide biosynthesis I);

  4. 4.

node $610$ (PWY-6122: 5-aminoimidazole ribonucleotide biosynthesis II).

To notice that pathway of node $466$ correlated with only $4$ E. rectale
pathways.

In the CD correlation network, there were fewer connections and the network
was divided into $6$ modules. Each module corresponded to the species groups
of pathways. The smallest module was composed of E. rectale pathways. The
largest (light purple) module comprising F. prausnitzii was connected to the
unclassified (green) module by means of node $105$ similarly to the UC
correlation network. Moreover, an additional bridge connecting node was node
$1261$, which was linked to nodes $821$ and $204$, to mention two high
betweenness centrality nodes among the unclassified pathways. High betweenness
centrality nodes $137$ and $462$ connected unclassified species module with B.
ovatus module, node $632$, in turn, was connected to node $988$ linking B.
ovatus module to the B. uniformis module. Finally, similarly to the NI
correlation network, B. vulgatus and B. uniformis were connected though (nodes
$370$, $1042$, and $1074$ on the former side and nodes $1205$ and $5$ on the
latter side).

The pathways in the UC correlation network were divided into $5$ modules. The
smallest module (coral red) was composed of E. rectale pathways scattered
around the network. The dark green nodes mixed to the turquoise nodes were B.
ovatus pathways mixed with B. uniformis pathways, respectively. The green
module comprised of unclassified species pathways, whereas, the light purple
module comprised of F. prausnitzii pathways. The green and the light purple
module were strictly connected similarly to the NI correlation network, the
pathways connecting them were the node $105$, which was linked to several
nodes of both modules and node $579$, which was linked to nodes $1093$ and
$1284$. Even E. rectale behaved as a bridge between the two aforementioned
large modules through a few connections. Furthermore, there was one node of F.
prausnitzii module that was deeply correlated with all the B. vulgatus
pathways: node $133$. Finally, two nodes with high betweenness centrality were
node $901$ in the light purple module and node $873$ in the mixed dark green
and turquoise module. Differently from the NI correlation network, B.
uniformis did not correlate B. vulgatus, whereas it correlated with B. ovatus.

In Figure 2, we have projected the bipartite network onto the nodes of the
bacterial pathways and we validate the projection through a null model
($\alpha=0.05$ and $fwer=none$). Again, we divided the pathways according to
their presence along with the samples. We considered the case of 75% of the
presence across the samples for NI subjects. We found $1715$ edges for $153$
nodes and the community detection resulted in $6$ large communities; namely,
the unclassified species community, the F. prausnitzii community, the E.
rectale community, the B. uniformis community, the B. ovatus community and B.
vulgatus community. All the communities identified were isolated, the node
$105$ was connected to the unclassified module through the nodes $842$, $362$,
and $1284$. Also, nodes $419$ and $277$ were separated from the rest of the
unclassified module. Considering F. prausnitzii module, nodes $1195$, $740$,
and $466$ were disconnected from the rest of the module.

In the CD case, there were $153$ nodes and $1615$ edges, the community
detection algorithm identified $6$ different modules, one for each bacterial
species identified in the previous cases. All the communities were isolated
without nodes connecting them. Differently from the NI case, node $105$ does
not result connected to the rest of the unclassified module. Similarly to the
NI case, also node $419$ was not isolated, whereas node $277$ was well
connected to the rest of the unclassified module. When F. prausnitzii was
considered, we obtained that node $1195$ was connected to nodes $748$ and
$1222$, that both were well connected to the F. prausnitzii pathways. Also,
node $740$ differently from the NI projected network is connected to two nodes
of the bacterium module, namely $610$ and $724$, which were both pathways
involving 5-aminoimidazole ribonucleotide. On the other hand, node $466$ was
connected to node $538$ and to nodes, $748$ and $1222$, where the former was
involved in the biosynthesis of urate and the latter were involved in the
degradation of galactose.

In the UC case, we could find $153$ nodes and $669$ edges. Differently from
the previous cases, the community detection algorithm could not isolate
modules corresponding to the $6$ species of the prevalent pathway group. The
F. prausnitzii module was split into two modules held together by the nodes
$158$ and $517$. Similarly to the CD projected network, node $105$ was
isolated from the rest of the unclassified module, whereas node $419$ was
connected to the rest of the module by means of nodes $62$, $204$, $428$, and
$67$. Differently from the NI projected network and similarly to the CD
projected network, in the UC projected network, the node $277$ was well
connected to the rest of the unclassified module. When the F. prausnitzii
module was considered, nodes $1195$, $740$ and $466$ were isolated from the
rest of the module in the same fashion as the NI case. Furthermore, the UC
projected network by displaying fewer connections had more isolated pathways
compared to the NI and the CD case. For instance, nodes $128$ and $1097$
detached from the B. ovatus module, node $1008$ detached from the E. rectale
module, and several more fragments of the module.

Figure 1: Correlation networks of prevalent metagenomic pathways in (a) NI
subjects, (b) CD subjects, (c) UC subjects. In Figure (a), nodes in the
frontier between B. vulgatus and B. uniformis and in the frontier between F.
prauznitzii and unclassified module are highlighted. In Figure (b) and Figure
(c), nodes with high betweenness centrality like node 105 are higlighted. The
legend remarks the species of each node/pathway. Figure 2: Projected network
representation of prevalent metagenomic pathways in (a) NI subjects, (b) CD
subjects, (c) UC subjects. Networks are obtained through a bipartite
projection and the exclusion of an edge between two nodes is made through a
comparison with a null model. The nodes highlighted describes the pathway with
highest betweenness centrality. The legend remarks the species of each
node/pathway.

### Escherichia coli

As it is possible to observe in Figure 3, the relatively uncommon pathways
were $910$ in total. There were $49203$ edges in NI correlation network
($\text{th}_{\text{NI}}=0.474$), $42617$ edges in CD correlation network
($\text{th}_{\text{CD}}=0.446$), $44523$ edges in UC correlation network
($\text{th}_{\text{UC}}=0.465$). The number of edges was comparable in the
three networks. We could observe nine modules in the NI correlation network
(modularity $0.623$, nine modules in the CD correlation network (modularity
$0.644$), and six modules in the UC correlation network (modularity $0.695$).
In every network, it was possible to identify an approximately isolated ball-
shaped module containing E. coli pathways. It was interesting to highlight the
position of B. fragilis pathways in respect of E. coli pathways in the
different diagnoses. In the NI correlation network, B. fragilis pathways were
connected to the E. coli module through V. parvula pathways, by contrast, in
the UC correlation network, B. fragilis pathways were incorporated and
surrounded by the same module containing E. coli pathways, whereas in the CD
correlation network the bacterial pathways of the two species were completely
separated. In the NI correlation network, the module containing E. coli
included also bacterial pathways of other species, notably E. siraeum and R.
gnavus pathways that behaved as bridge nodes between E. coli containing module
and the rest of the network. In the CD correlation network, this role was
assumed by R. intestinalis and V. parvula, whereas, in the UC correlation
network, we did not observe any pathways behaving as bridges nodes. An
additional important module that was also the largest was the one mainly
composed of R. torques, A. hadrus, L. bacterium 5 1 63FAA, plus other minor
species. The pathways belonging to the last two mentioned species were
strictly intertwined forming the second largest ball-shaped group of nodes.
The same ball-shaped group of nodes was present in the CD correlation network,
by contrast, in the UC correlation network, in the UC correlation network the
two species were in the same module and the nodes were not mixed in the ball
but they laid separately.

In the NI network projection, we obtained a network with $953$ nodes and
$15394$ edges. As it is possible to notice in Figure 4, there were several
modules that emerged from the network. The most evident was the E. coli module
which was one of the modules that composed the E. coli group in the uncommon
pathways. This bigger module was connected to F. plautii via $5$ nodes on the
E. coli side and via $5$ nodes on the F. plautii side. On the E. coli side:

  1. 1.

node $146$ (FUCCAT-PWY: fucose degradation);

  2. 2.

node $896$ (PWY-6737: starch degradation V);

  3. 3.

node $838$ (PWY-6609: adenine and adenosine salvage III);

  4. 4.

node $877$ (PWY-6703: preQ0 biosynthesis);

  5. 5.

node $963$ (PWY-7199: pyrimidine deoxyribonucleosides salvage).

On the F. plautii side:

  1. 1.

node $442$ (PWY-5188: tetrapyrrole biosynthesis I (from glutamate));

  2. 2.

node $611$ (PWY-6122: 5-aminoimidazole ribonucleotide biosynthesis II);

  3. 3.

node $725$ (PWY-6277: superpathway of 5-aminoimidazole ribonucleotide
biosynthesis);

  4. 4.

node $299$ (PEPTIDOGLYCANSYN-PWY: peptidoglycan biosynthesis (meso-
diaminopimelate containing));

  5. 5.

node $580$ (PWY-6121: 5-aminoimidazole ribonucleotide biosynthesis I).

Curiously there was also a C. bolteae pathway well-connected to the E. coli
main module (node $1143$). The remaining part of the E. coli group was
represented by fatty acid metabolism pathways (node $140$) or pathways
involving mannose biosynthesis, were connected to other species pathways.
Apart from these nodes scattered around the network, the species group had two
main ball-shaped modules thanks to the well-connected nature of the nodes
inside the module. Another interesting community was the module formed by the
nodes of two different species Lachnospiraceae bacterium 5 1 63FAA and A.
hadrus. The edges connecting the nodes of the two species were so dense that
the two groups formed a unique module.

In the CD network projection, there were $953$ nodes and $24298$ edges. One of
the immediately visible properties of the projected network was the isolated
module composed of E. coli pathways. Compared to the NI case, there were no
connections to the other species nodes. R. torques module was connected to A.
hadrus module, which in turn was connected to L. bacterium 5 1 63FAA module.
$5$ nodes of A. hadrus community were connected to most of the nodes of the
other two species exhibiting high betweenness centrality, they were:

  1. 1.

node $1298$ (VALSYN-PWY: L-valine biosynthesis);

  2. 2.

node $429$ (PWY-5104: L-isoleucine biosynthesis IV);

  3. 3.

node $461$ (PWY-5659: GDP-mannose biosynthesis);

  4. 4.

node $847$ (PWY-6700: queuosine biosynthesis);

  5. 5.

node $565$ (PWY-6121: 5-aminoimidazole ribonucleotide biosynthesis I).

Similarly to the NI case, node $155$ was connected only to pathways of other
species. Another difference with the NI projected network was the edges of R.
intestinalis which in this case were connected to B. instestinihominis,
whereas, in the NI case, they were connected to nodes $671$ and $41$.

The UC network projection had $953$ and only $5432$ edges. The first striking
property of this network was that there were much fewer edges compared to the
previous two cases. It was not possible to say much about the module of E.
coli. On the other hand, it was possible to observe that L. bacterium 5 1
63FAA and A. hadrus were completely separated. Furthermore, L. bacterium 5 1
63FAA module was connected to the R. hominis module through several nodes.
Related to R. torques group, we had one main module similar to the other
cases, two isolated nodes (node $1047$ as the NI case and node $569$) and two
nodes connected between them (nodes $711$ and $597$), but separated from the
rest of the pathways.

Figure 3: Correlation networks of uncommon metagenomic pathways in (a) NI
subjects, (b) CD subjects, (c) UC subjects. The nodes encircled shows the
position of B. fragilis and other species like E. coli and V. parvula. The
legend remarks the species of each node/pathway, where the grey nodes are
classified as ’other’. Figure 4: Projected network representation of uncommon
metagenomic pathways in (a) NI subjects, (b) CD subjects, (c) UC subjects.
Networks are obtained through a bipartite projection and the exclusion of an
edge between two nodes is made through a comparison with a null model. The
nodes highlighted corresponds to nodes with high betweenness centralities or
to nodes that compare to the NI projected network are isolated. The legend
remarks the species of each node/pathway.y, where the grey nodes are
classified as ’other’.

## Discussion

In the literature, the reduction of F. prausnitzii has been associated with
IBD [31], nevertheless, in our results we recognized that instead of a
decrease in the quantity of F. prausnitzii pathways expressed, there was a
change of the wiring in the metagenomic network. In particular, what changed
from the NI correlation network and the IBD correlation networks were the
bridge pathways connecting the module of unclassified pathways and the module
containing the F. prausnitzii pathways. For instance, in the NI correlation
network the bridge pathway was node $821$, whereas in the IBD networks the
bridge pathways between the two modules were node $105$. The correlation
between these bridge nodes and the nodes in the aforementioned modules meant
that both modules relied on the pathway to function correctly. On one hand,
the central substance was the tetrasaccharide stachyose which in the pathway
is degraded into UDP-alpha-D-glucose and has been recognized as potential
probiotic against enterotoxigenic E. coli [32]; on the other hand, there was
the coenzyme A, which has a fundamental role in the metabolism and, in
particular, it is important in the oxidation of fatty acids. Several studies
linked the alteration of fatty acid production to the IBDs, hence, this change
in the centrality of the pathway related to this substance could be
investigated further to explain the origins of IBDs [32]. The fact that the
modules of Bacteroides in IBD networks corresponded to its species whilst in
NI network are gathered in one module could demonstrate that in IBD the
different Bacteroides species proliferates the gut independently. This could
confirm the meta-analysis by [33], who showed that lower levels of Bacteroides
were associated with IBDs. Other pathways differentially wired between NI and
IBD networks are those involving the bacterial metabolite 5-aminoimidazole
ribonucleotide (nodes $579$, $610$, $724$), these nodes were behaving as
bridges in the NI correlation network, by contrast, in the IBD correlation
networks, they were substituted by a unique bridge node (node $105$).

In the range of uncommon bacterial species, we can observe the E. coli module;
in the literature, this bacterial species has a recognized role in the
development of IBD [34, 35]. It was possible to observe the different
interplay between E. coli, V. parvula and B. fragilis across the different
diagnoses. The increase of E. coli and B. fragilis in IBD was observed in a
previous study [36], but our results provide an additional information about
the differential wiring scheme of the aforementioned species. In particular,
it seemed that V. parvula pathways mediated the connection of E. coli with the
other module in the correlation network. In particular, in NI correlation
network, V. parvula pathways were in the same module of B. fragilis pathways
which were connected to the rest of the correlation network. In the CD
correlation network, V. parvula pathways were included in the E. coli module,
just to remark how close the two bacterial species were, but if on one hand
the relationship between E. coli and B. fragilis has been already studied, the
effect of V. parvula on E. coli has to be investigated yet in the literature.
In the UC correlation network, V. parvula formed an almost completely isolated
module far from the E. coli, this result could differentiate the connectome of
the UC microbiome from the connectome of the CD microbiome. The isolation of
the E. coli module in the UC correlation network could represent further the
peculiar features of the particular form of IBD. This isolation meant that
there are no correlations with the other pathways and the pattern of
metagenomic expression across the samples are correlated only inside the same
bacterial species. In the NI correlation network, E. siraeum and R. gnavus
pathways were the two main bridge pathways between E. coli and the rest of the
network, it could be possible to hypothesize that re-establishing a connection
between E. coli module with the aforementioned bacterial species could lead
back to a healthy gut microbiota. In the CD correlation network, R.
intestinalis pathways had the role of bridge pathways and, in fact, by using
the permutation tests between NI and CD samples, we obtained that the most
differential pathways were R. intestinalis pathways. In the literature, this
bacterial species, which has anti-inflammatory properties on the intestinal
walls, was depleted in IBD subjects; nevertheless, the complete mechanisms
underlying its protective action against IBD are still unknown [37, 38]. In
the uncommon bacterial pathways of the NI projected network, the E. coli
module was connected to the C. boltae, which, in turn, was linked to B. longum
module. B. longum is a bacterial species that can have anti-inflammatory
properties in the human gut [10]. By contrast, in the CD projected network, E.
coli was connected to the rest of the network through two Dorea longicatena
pathways, which were nodes $680$ and $81$ and were connected to node $697$. On
the other hand, in the UC projected network, two E. coli nodes were connected
to six C. comes nodes, showing the existence of an interaction between the two
species in the UC diagnosis.

## Methods

### Recruitment

The Inflammatory Bowel Disease Multi’omics Database (IBDMDB) [39] is one of
the first comprehensive studies of the gut ecosystem’s multiple molecular
properties involved in the IBD dynamics. Some of the measurements of the
microbiome offered by the study are metagenomics, metatranscriptomics and
metabolomics. The data is related to 132 subjects approached in the following
five medical centres: Cincinnati Children’s Hospital, Emory University
Hospital, Massachusetts General Hospital, Massachusetts General Hospital for
Children, and Cedars-Sinai Medical Centre. The patients recruited for the
study initially arrived at the hospitals either for routine age-related
colorectal cancer screening, presence of other gastrointestinal symptoms, or
suspected IBD. The latter could be a consequence of positive imaging, symptoms
of chronic diarrhoea or rectal bleeding. If there were no conditions for
exclusion right after enrolment, a preliminary colonoscopy was performed to
determine study strata. Based on initial analyses, the subjects that were not
diagnosed with IBD were labelled as ‘NI’ controls. This group of subjects
included the patients who arrived for routine screening and those with more
benign or non-specific symptoms [40].

### Database

The IBDMDB website contains the raw, and the final results of the processed
information, the complete pipeline for producing the final results is:

  1. 1.

Quality and error checking for completeness, producing raw files.

  2. 2.

Anadama pipeline, producing products.

In particular, if we consider the pipeline for producing the metagenomic data,
the samples for the quality control process go through the KneadData [41] and
the Anadama pipelines. The former is a tool useful to exclude the reads, which
are fragments of DNA, related to the host or related to other contaminants
from the metagenomic sequencing data, and this separation step is made
completely in silico. Whereas the latter, the Anadama pipeline, performs and
produces documents from an automated scientific workflow, where a workflow is
simply a succession of tasks, such as quantifying operational taxonomic units
(OTU). The OTUs are classifications of groups of bacteria closely related to
each other by sequence similarity. On the IBDMDB website, there are two
versions of data Version 2.0 and Version 3.0. Version 3.0 has been uploaded
with the new version of bioBakery [42]. In the thesis, we use the products
file related to the functional profiles Version 2.0. Moreover, we exploit the
HMP2 Metadata file, containing the sample IDs, the subject IDs and the
properties associated with each sample. The External ID is the unique ID of
the sample, Participant ID is the subject from where the sample has been
taken, diagnosis is either ulcerative colitis (UC), Crohn’s disease (CD) or
control group (NI), week_num points out the week number, when the sample has
been taken and data_type is the type of sample (metagenomics, 16S, etc.). we
extracted useful information to avoid importing the whole database, and we
selected only the samples from the first week (week 0). Moreover, the samples
different from metagenomic ones were excluded. Finally, we dropped the samples
from the same participant in week 0 and obtained a list of samples ID that
were present in both the metagenomic database and the HMP2 Metadata. The
metagenomic database contains as row indexes the gene descriptors;
specifically, the descriptor is composed of the pathway, genus and species
(e.g. "ARO-PWY: chorismate biosynthesis I
|g__Alistipes.s__Alistipes_finegoldii"). To generate the database, the
algorithm HUMAnN2 [43] has been used. The algorithm can be divided into three
phases; firstly, the metagenomic sample is quickly analyzed to seek known
species in the gut microbiome. The functional annotation of the identified
pangenomes (i.e. the genome of a larger group of species) of the microbiome is
concatenated to form a gene database of the sample. Secondly, using this
database, the whole sample is aligned, meaning that statistics regarding the
species and the genes are made, and unmapped reads are collected. Thirdly, the
gene abundances are calculated, and they are combined with the metabolic
network to determine the pathways in the microbial community.

Pathway | SMPL1 | SMPL2 | SMPL3
---|---|---|---
PWY1 | 0.0435726 | 0.0377424 | 0.0118981
PWY2 | 0.0170328 | 0.0144735 | 0.0134886
PWY3 | 0.0145872 | 0.0177172 | 0.0121692
PWY4 | 0.0545121 | 0.0018744 | 0.0175601
PWY5 | 0.0881223 | 0.0111788 | 0.0163441
Table 1: Representation of the database containing the gene expression data
with example values.

To reduce the number of genes present in the resulting network, we built the
correlation matrices for three different groups; namely, one group for the
pathways present in a percentage between 25% and 50% of the subjects (uncommon
pathways), another group for those in the range between 50% and 75% (common
pathways), and lastly a group for the pathways present in more than 75%
(prevalent pathways).

### Correlation Networks

Correlation networks are built from the following steps:

  1. 1.

pairwise gene similarity score (correlation);

  2. 2.

thresholding.

Normalization methods, correlation measures (Pearson or Spearman),
significance and relevance are still debated [44]. In our work, we chose
Pearson correlation similarly to [45].

To transform a correlation matrix into the correlation network, we used a
thresholding method inspired by a brain network technique that was used to cut
the least important edges and keep the significant relationships among the
nodes, hence, we calculated the absolute value of the correlations, making the
signs irrelevant. This method consists of increasing a cut-off threshold until
the network connectivity breaks apart; because of this property, this cut-off
threshold is also known as the percolation threshold. This method has been
considered one of the most effective methods to maximise the information
quantity kept by the network [46]. In our work, we started from a cut-off
threshold of $t=0$, and we used a bisection method to get to the percolation
threshold. In the bisection method, we flattened the absolute values in the
weighted adjacency matrix into a sorted array, we chose the median value and
used it as the new cut-off threshold, we calculated the connectivity of the
graph built from the adjacency matrix having this cut-off threshold, finally,
if we obtained a connected graph with the median value as a cut-off threshold,
we used as the sorted array the upper half array, on the contrary, we used the
lower half. The procedure was iterative until convergence which corresponded
to an array with zero length or with the same head and same tail.

### Co-expression Network from Bipartite Projected Networks

Bipartite networks are graphs $G=(U,V,E)$ where the nodes can be divided into
two disjoint sets, $U$ and $V$, and every edge in $E$ links an element in $U$
to an element in $V$. In our work, we designated with $U$ the set of nodes
representing the genes and with $V$ the set of nodes representing the samples.
We can find in $E$ all the edges connecting the gene $u$ to the sample $v$ if
the gene was over-expressed in the corresponding sample. We evaluated the
over-expression of a gene through the binarization of the data that led to the
construction of a biadjacency matrix $B$ of size $|U|\times|V|$ that described
the bipartite network $G=(U,V,E)$ with the entries $(0,1)$, where $B_{ij}=1$
if the gene $v_{i}$ is over-expressed in the sample $u_{j}$, and $B_{ij}=0$ if
it is not over-expressed. Biadjacency matrices are rectangular matrices where
on one side there are the nodes in $U$, and on the other side the nodes in
$V$.

#### Binarization

The binarization process is useful to highlight the edges in $E$ that are
over-expressed. By using the revealed comparative advantage (RCA) [47], We
highlighted the over-expressed genes for specific samples:

$RCA_{ij}=\frac{E_{ij}/\sum_{j^{\prime}\in
V}E_{ij^{\prime}}}{\sum_{i^{\prime}\in U}E_{i^{\prime}j}/\sum_{i^{\prime}\in
U,j^{\prime}\in V}E_{i^{\prime}j^{\prime}}}$ (1)

where $E$ is the expression of the gene $i$ in the sample $j$. When
$RCA_{ij}>1$, the quantity of gene $i$ in sample $j$ can be considered over-
expressed and the entry $b_{ij}=1$, in the other case $RCA_{ij}\leq 1$, then
$b_{ij}=0$.

#### Randomization of bipartite networks

To generate a null model useful to calculate the statistically important
properties of a real bipartite network, we randomized the bipartite networks
by using the package BiCM [48]. In particular, the package is based on the
works by [49], [50], and [51]. In the aforementioned works, the Shannon
entropy defined as

$\mathcal{S}=-\sum_{\mathbf{M}\in\mathcal{G}}P(\mathbf{M})\ln{P(\mathbf{M})}$
(2)

is maximized, where $\mathcal{G}$ is an ensemble of binary, undirected,
bipartite networks, and $\overrightarrow{C}(M)$ is a given set of constraints.
The result is:

$P\left(\mathbf{M}|\overrightarrow{\theta}\right)=\frac{e^{-H\left(\mathbf{M},\overrightarrow{\theta}\right)}}{Z\left(\overrightarrow{\theta}\right)}$
(3)

Where
$H\left(\mathbf{M},\overrightarrow{\theta}\right)=\overrightarrow{\theta}\cdot\overrightarrow{C}(M)$
is the hamiltonian and $Z\left(\overrightarrow{\theta}\right)=\sum_{M\in
G}e^{-H\left(\mathbf{M},\overrightarrow{\theta}\right)}$ is the normalization.
In the case of the bipartite extension of the configuration model (BiCM), the
hamiltonian becomes:

$H\left(\mathbf{M},\overrightarrow{\theta}\right)=\overrightarrow{\alpha}\cdot\overrightarrow{d}(\mathbf{M})+\overrightarrow{\beta}\overrightarrow{u}(\mathbf{M})$
(4)

because we have two layers of nodes and we constrained the degree sequences
$\overrightarrow{d}(\mathbf{M})$ and $\overrightarrow{u}(\mathbf{M})$.
$\overrightarrow{d}(\mathbf{M})$ is the degree sequence of the genes and
$\overrightarrow{u}(\mathbf{M})$ is the degree sequence of the samples.

#### Projection

One way to compress the information contained in a bipartite network is to
project the bipartite network onto one of the two layers (gene/pathway layer
or sample layer). We carried out the projection by connecting in the same
layer the nodes that were linked by a common node in the other layer. The
projection leads to a loss of information itself, so to avoid further loss of
information, we weighted the edges by the number of common nodes neighbouring
the nodes in the same layer [52]. The algorithm to perform the projection is:

  1. 1.

select the partition on which the projection will be done

  2. 2.

take two nodes of the selected partition, $n$ and $n^{\prime}$, and calculate
their similarity

  3. 3.

by evaluating the corresponding $p$-value compute the statistical significance
of the calculated similarity with respect to a properly-defined null model;

  4. 4.

if, and only if, the $p$-value associated with the link $n$ and $n^{\prime}$
is statistically significant, connect the selected nodes.

The similarity in the second step of the algorithm is evaluated by:

$V_{nn^{\prime}}=\sum_{c=1}^{N_{c}}m_{nc}m_{n^{\prime}c}=\sum_{c=1}^{N_{c}}V_{nn^{\prime}}^{c},$
(5)

where $V_{nn^{\prime}}^{c}\equiv m_{nc}m_{n^{\prime}c}$ and it is clear from
the definition that $V_{nn^{\prime}}^{c}=1$ if, and only if, both $n$ and
$n^{\prime}$ are common neighbours of $c$. The third step of the algorithm
passes through the calculation of the $p$-value of the Poisson–Binomial
distribution, i.e. the probability of observing a number of V-motifs greater
than, or equal to, the observed one (which will be indicated as
$V_{nn^{\prime}}^{*}$:

$p-value(V_{nn^{\prime}}^{*})=\sum_{V_{nn^{\prime}}\geq
V_{nn^{\prime}}^{*}}f_{PB}(V_{nn^{\prime}})=1-\sum_{V_{nn^{\prime}}\leq
V_{nn^{\prime}}^{*}}f_{PB}(V_{nn^{\prime}}).$ (6)

Finally, in the last step of the algorithm, in order to understand which
$p$-values were significant, a false-discovery rate or FDR has been adopted to
take into account the fact that we were testing multiple hypotheses [53].

### Betweenness centrality

There are many different centrality measures in network science; these
measures describe the importance of a node in the network. The betweenness
centrality was introduced by Freeman [54], and it considers more important the
nodes that behave as bridges in the network. It can be calculated as:

$C_{B}(i)=\sum_{s\neq t\neq i\in V}\frac{\sigma_{st}(i)}{\sigma_{st}}$ (7)

where $\sigma_{st}$ is the number of shortest paths connecting $s$ and $t$,
whilst $\sigma_{st}(i)$ is the number of shortest paths connecting $s$ and $t$
and going through $i$.

### Community detection

In the study of network science, both natural complex networks and artificial
complex networks display a modular behaviour, i.e. groups of nodes are more
densely connected within the members of the group than with the rest of the
network. This phenomenon can also be described by a function called modularity
[55], which can be used as a parameter for one of the several ways to perform
community detection in complex networks. In our work, we used Louvain method
[56] because it is suited to large complex networks. Louvain method is based
on an optimization problem that can be solved in a time $O(n\cdot log_{2}n)$
where $n$ is the number of nodes in the network [57]. The method is based on
the aforementioned modularity optimization. The modularity is defined as [58],

$Q=\frac{1}{2m}\sum_{i,j}\left[A_{ij}-\frac{k_{i}k_{j}}{2m}\right]\delta(c_{i},c_{j}).$
(8)

The algorithm is based on two phases that repeat iteratively. In the first
phase, each node is repeatedly moved individually between the communities to
maximize modularity. The first phase stops when no further individual move can
improve the modularity. In the second phase, each community formed in the
first phase is considered as a node of a weighted graph, where the weights of
the edges are given by the sum of the edges connecting the nodes in the
communities. The algorithm has a high efficiency partly because the gain
modularity $\Delta Q$, due to moving a node $i$ into a community $C$, can be
steadily calculated as:

$\Delta
Q=\left[\frac{\sum_{in}+k_{i,in}}{2m}-\left(\frac{\sum_{tot}+k_{i}}{2m}\right)^{2}\right]-\left[\frac{\sum_{in}}{2m}-\left(\frac{\sum_{tot}}{2m}\right)^{2}-\left(\frac{k_{i}}{2m}\right)^{2}\right],$
(9)

where $\sum_{in}$ is the sum of the weights of the edges inside $C$,
$\sum_{tot}$ is the sum of the weights of the edges going from the outside to
the nodes inside $C$, $k_{i}$ is the sum of the weights of the edges going to
node $i$, and $k_{i,in}$ is the sum of the weights of the edges going from $i$
to the nodes in $C$ and, finally, $m$ is the sum of the weights of all the
edges in the graph. One of the limitations of community detection based on the
modularity is the resolution limit [59]. This limitation to modularity may be
present when $l_{s}\approx\sqrt{2L}$, where $l_{s}$ is the number of internal
links in a module $S$ and $L$ is the total number of links in the network and
it can be overcome through several methods, one of the most promising is
Surprise maximization [60].

## References

  * [1] Sender, R., Fuchs, S. & Milo, R.  Revised estimates for the number of human and bacteria cells in the body.  _PLoS biology_ 14, e1002533 (2016).
  * [2] Thursby, E. & Juge, N.  Introduction to the human gut microbiota.  _Biochemical Journal_ 474, 1823–1836 (2017).
  * [3] Tanaka, M. & Nakayama, J.  Development of the gut microbiota in infancy and its impact on health in later life.  _Allergology International_ 66, 515–522 (2017).
  * [4] Ma, Y., Chen, H., Lan, C. & Ren, J.  Help, hope and hype: ethical considerations of human microbiome research and applications.  _Protein & cell_ 9, 404–415 (2018).
  * [5] Farré-Maduell, E. & Casals-Pascual, C.  The origins of gut microbiome research in Europe: From Escherich to Nissle.  _Human Microbiome Journal_ 14, 100065 (2019).
  * [6] Natividad, J. M. M. & Verdu, E. F.  Modulation of intestinal barrier by intestinal microbiota: pathological and therapeutic implications.  _Pharmacological research_ 69, 42–51 (2013).
  * [7] Sommer, F. & Bäckhed, F.  The gut microbiota—masters of host development and physiology.  _Nature reviews microbiology_ 11, 227–238 (2013).
  * [8] Belizário, J. E. & Faintuch, J.  Microbiome and gut dysbiosis.  In _Metabolic interaction in infection_ , 459–476 (Springer, 2018).
  * [9] Borody, T. J. & Khoruts, A.  Fecal microbiota transplantation and emerging applications.  _Nature reviews Gastroenterology & hepatology_ 9, 88–96 (2012).
  * [10] Singh, S. _et al._ Common symptoms and stressors among individuals with inflammatory bowel diseases.  _Clinical Gastroenterology and Hepatology_ 9, 769–775 (2011).
  * [11] Ananthakrishnan, A. N., Xavier, R. J. & Podolsky, D. K.  _Inflammatory Bowel Diseases: A Clinician’s Guide_ (John Wiley & Sons, 2017).
  * [12] Manichanh, C., Borruel, N., Casellas, F. & Guarner, F.  The gut microbiota in IBD.  _Nature reviews Gastroenterology & hepatology_ 9, 599–608 (2012).
  * [13] Kirsner, J. B.  Historical aspects of inflammatory bowel disease.  _Journal of clinical gastroenterology_ 10, 286–297 (1988).
  * [14] Kaplan, G. G.  The global burden of IBD: from 2015 to 2025.  _Nature reviews Gastroenterology & hepatology_ 12, 720–727 (2015).
  * [15] Xavier, R. J. & Podolsky, D. K.  Unravelling the pathogenesis of inflammatory bowel disease.  _Nature_ 448, 427–434 (2007).
  * [16] Lees, C. W. & Satsangi, J.  Genetics of inflammatory bowel disease: implications for disease pathogenesis and natural history.  _Expert review of gastroenterology & hepatology_ 3, 513–534 (2009).
  * [17] Zhang, Y.-Z. & Li, Y.-Y.  Inflammatory bowel disease: pathogenesis.  _World journal of gastroenterology: WJG_ 20, 91 (2014).
  * [18] Fiocchi, C. & Iliopoulos, D.  IBD Systems Biology Is Here to Stay.  _Inflammatory Bowel Diseases_ 27, 760–770 (2021).
  * [19] De Souza, H. S. P., Fiocchi, C. & Iliopoulos, D.  The IBD interactome: an integrated view of aetiology, pathogenesis and therapy.  _Nature Reviews Gastroenterology & Hepatology_ 14, 739–749 (2017).
  * [20] Barabási, A.-L., Gulbahce, N. & Loscalzo, J.  Network medicine: a network-based approach to human disease.  _Nature reviews genetics_ 12, 56 (2011).
  * [21] Faust, K. _et al._ Signatures of ecological processes in microbial community time series.  _Microbiome_ 6, 1–13 (2018).
  * [22] Bucci, V. _et al._ MDSINE: Microbial Dynamical Systems INference Engine for microbiome time-series analyses.  _Genome biology_ 17, 1–17 (2016).
  * [23] Coyte, K. Z. & Rakoff-Nahoum, S.  Understanding competition and cooperation within the mammalian gut microbiome.  _Current Biology_ 29, R538–R544 (2019).
  * [24] Vernocchi, P. _et al._ Network analysis of gut microbiome and metabolome to discover microbiota-linked biomarkers in patients affected by non-small cell lung cancer.  _International journal of molecular sciences_ 21, 8730 (2020).
  * [25] Bauer, E. & Thiele, I.  From network analysis to functional metabolic modeling of the human gut microbiota.  _MSystems_ 3, 00209–17 (2018).
  * [26] Segal, J. P. _et al._ The application of omics techniques to understand the role of the gut microbiota in inflammatory bowel disease.  _Therapeutic advances in gastroenterology_ 12, 1756284818822250 (2019).
  * [27] Stein, R. R. _et al._ Ecological Modeling from Time-Series Inference: Insight into Dynamics and Stability of Intestinal Microbiota.  _PLoS Computational Biology_ 9, e1003388, DOI: 10.1371/journal.pcbi.1003388 (2013).
  * [28] Chen, L. _et al._ Gut microbial co-abundance networks show specificity in inflammatory bowel disease and obesity.  _Nature communications_ 11, 1–12 (2020).
  * [29] Friedman, J. & Alm, E. J.  Inferring correlation networks from genomic survey data.  _PLoS Comput Biol_ (2012).
  * [30] Weiss, S. _et al._ Correlation detection strategies in microbial data sets vary widely in sensitivity and precision.  _The ISME journal_ 10, 1669–1681 (2016).
  * [31] Cao, Y., Shen, J. & Ran, Z. H.  Association between Faecalibacterium prausnitzii reduction and inflammatory bowel disease: a meta-analysis and systematic review of the literature.  _Gastroenterology research and practice_ 2014 (2014).
  * [32] Xi, M. _et al._ Effects of stachyose on intestinal microbiota and immunity in mice infected with enterotoxigenic Escherichia coli.  _Journal of Functional Foods_ 64, 103689 (2020).
  * [33] Zhou, Y. & Zhi, F.  Lower level of bacteroides in the gut microbiota is associated with inflammatory bowel disease: a meta-analysis.  _BioMed research international_ 2016 (2016).
  * [34] Rhodes, J. M.  The role of Escherichia coli in inflammatory bowel disease.  _Gut_ 56, 610–612 (2007).
  * [35] Schirmer, M., Garner, A., Vlamakis, H. & Xavier, R. J.  Microbial genes and pathways in inflammatory bowel disease.  _Nature Reviews Microbiology_ 17, 497–511 (2019).
  * [36] Keighley, M. R. _et al._ Influence of inflammatory bowel disease on intestinal microflora.  _Gut_ 19, 1099–1104 (1978).
  * [37] Zhu, C. _et al._ Roseburia intestinalis inhibits interleukin-17 excretion and promotes regulatory T cells differentiation in colitis.  _Molecular medicine reports_ 17, 7567–7574 (2018).
  * [38] Hoffmann, T. W. _et al._ Microorganisms linked to inflammatory bowel disease-associated dysbiosis differentially impact host physiology in gnotobiotic mice.  _The ISME journal_ 10, 460–477 (2016).
  * [39] IBDMDB - Home | IBDMDB.
  * [40] Lloyd-Price, J. _et al._ Multi-omics of the gut microbial ecosystem in inflammatory bowel diseases.  _Nature_ 569, 655–662, DOI: 10.1038/s41586-019-1237-9 (2019).
  * [41] KneadData – The Huttenhower Lab.
  * [42] McIver, L. J. _et al._ BioBakery: A meta’omic analysis environment.  _Bioinformatics_ 34, 1235–1237, DOI: 10.1093/bioinformatics/btx754 (2018).
  * [43] Franzosa, E. A. _et al._ Species-level functional profiling of metagenomes and metatranscriptomes.  _Nature methods_ 15, 962–968 (2018).
  * [44] Tieri, P. _et al._ Network inference and reconstruction in bioinformatics.  _Encyclopedia of Bioinformatics and Computational Biology_ (2019).
  * [45] MacMahon, M. & Garlaschelli, D.  Community detection for correlation matrices.  _arXiv preprint arXiv:1311.1924_ (2013).
  * [46] Nicolini, C., Forcellini, G., Minati, L. & Bifone, A.  Scale-resolved analysis of brain functional connectivity networks with spectral entropy.  _NeuroImage_ 211, 116603 (2020).
  * [47] Balassa, B.  Trade liberalisation and “revealed” comparative advantage 1.  _The manchester school_ 33, 99–123 (1965).
  * [48] Bruno, M.  BiCM: Python package for the computation of the Bipartite Configuration Model. (2020).
  * [49] Squartini, T. & Garlaschelli, D.  Analytical maximum-likelihood method to detect patterns in real networks.  _New Journal of Physics_ 13, 83001 (2011).
  * [50] Saracco, F., Di Clemente, R., Gabrielli, A. & Squartini, T.  Randomizing bipartite networks: The case of the World Trade Web.  _Scientific Reports_ 5, 1–18, DOI: 10.1038/srep10595 (2015).
  * [51] Saracco, F. _et al._ Inferring monopartite projections of bipartite networks: an entropy-based approach.  _New Journal of Physics_ 19, 53022 (2017).
  * [52] Neal, Z.  The backbone of bipartite projections: Inferring relationships from co-authorship, co-sponsorship, co-attendance and other co-behaviors.  _Social Networks_ 39, 84–97 (2014).
  * [53] Benjamini, Y. & Hochberg, Y.  Controlling the false discovery rate: a practical and powerful approach to multiple testing.  _Journal of the Royal statistical society: series B (Methodological)_ 57, 289–300 (1995).
  * [54] Freeman, L. C.  A set of measures of centrality based on betweenness.  _Sociometry_ 35–41 (1977).
  * [55] Newman, M. E. J.  Modularity and community structure in networks.  _Proceedings of the national academy of sciences_ 103, 8577–8582 (2006).
  * [56] Blondel, V. D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E.  Fast unfolding of communities in large networks.  _Journal of statistical mechanics: theory and experiment_ 2008, P10008 (2008).
  * [57] Lancichinetti, A. & Fortunato, S.  Community detection algorithms: a comparative analysis.  _Physical review E_ 80, 56117 (2009).
  * [58] Newman, M. E. J.  Analysis of weighted networks.  _Physical review E_ 70, 56131 (2004).
  * [59] Fortunato, S. & Barthelemy, M.  Resolution limit in community detection.  _Proceedings of the national academy of sciences_ 104, 36–41 (2007).
  * [60] Aldecoa, R. & Marín, I.  Surprise maximization reveals the community structure of complex networks.  _Scientific reports_ 3, 1–9 (2013).

## Author contributions statement

Conceptualization, G.C., T.G. and M.H.; methodology, G.C., T.G. and M.H.;
software, M.H. and T.G.; validation, M.H. and T.G.; formal analysis, M.H.;
investigation, M.H.; resources, M.H.; data curation, M.H.; writing—original
draft preparation, M.H.; writing—review and editing, T.G. and G.C.;
visualization, M.H.; supervision, M.H., T.G. and G.C.; project administration,
G.C.; funding acquisition, G.C. All authors have read and agreed to the
published version of the manuscript.

## Additional information

To include, in this order: Competing interests The authors declare no conflict
of interest.

The corresponding author is responsible for submitting a competing interests
statement on behalf of all authors of the paper. This statement must be
included in the submitted article file.


# Proof of the impossibility of probabilistic induction

Vaden Masrani

(September 12, 2019)

In what follows I restate and simplify the proof of the impossibility of
probabilistic induction given in [1, 2]. Other proofs are possible (cf. [1]).

##  1 Logical Entailment

Given two statements $x,y$ we write $x\vdash y$ if $x$ entails $y$. For
example, if

$\displaystyle x~{}=~{}\textit{``All men are mortal''}$ $\displaystyle
y~{}=~{}\textit{``Socrates is a man''}$ $\displaystyle
z~{}=~{}\textit{``Socrates is mortal''}$

we can write $(x\wedge y)\vdash z$. Entailment is a “truth broadcasting”
operation that allows the truth of the premises to flow to the conclusion.

We also have the following simple theorem.

###### Theorem 1

If $x\vdash y$ then $p(y|x)=1$.

For example if

$\displaystyle x~{}=~{}\textit{``All swans are white''}$ $\displaystyle
y~{}=~{}\textit{``All swans in Austria are white''}$

Then $x\vdash y$ and $p(y|x)=1$ reads “The probability that all swans in
Austria are white given that all swans are white is 1.”

##  2 The Problem of Induction

We describe the classical problem of induction by first describing (the non-
problem of) deduction. We have a “general law” statement $G$ which is assumed
to hold across time and space, and we have a set of observed evidence
statements $e_{1},e_{2},...,e_{N}$ that are assumed to be true in a particular
spatio-temporal region. We refer to the conjunction of the observed evidence
as $E=(e_{1}\wedge e_{2}\wedge...)$. By definition the general law $G$
logically entails each of the evidence statements

$\displaystyle G\vdash e_{i}$ $\displaystyle\forall e_{i}\in E$ (1)

For example, consider evidence statements

$\displaystyle e_{1}~{}=~{}\textit{``All observed swans in Austria in 1796 are
white''}$ $\displaystyle e_{2}~{}=~{}\textit{``All observed swans in Austria
in 1797 are white''}$ $\displaystyle...$

And consider the generalization

$\displaystyle G=\textit{``All swans are white''}$

Then $G\vdash E$ is logically valid and referred to as “deductive inference”.
However, $E\vdash G$ is logically invalid. This is the classical “problem of
induction”. It states that no amount of evidence statements $e_{i}$ can
logically justify a generalization $G$.

##  3 Probabilistic Solution to the Problem of Induction

The probabilistic solution states that while the truth of $G$ cannot be
logically established, the probability of any general law $G$ can be
established and increases with the accumulation of favorable evidence.
Therefore, while we cannot say $G$ is true, we can say $G$ is probably true.
The argument is as follows.

Let $G$ and $E$ be as above. Let $0<P(G)<1$ be our prior belief in $G$ and let
$0<P(E)<1$ be the probability of the evidence. Because $G\vdash E$ we have
$P(E|G)=1$. Therefore using Bayes rule we arrive at the following:

$\displaystyle P(G|E)=\frac{P(E|G)P(G)}{P(E)}=\frac{P(G)}{P(E)}$ And because 0
< P(E) < 1 $\displaystyle P(G|E)>P(G)$ (2)

Therefore the probability of $G$ increases with favorable evidence $E$. This
seemingly justifies a belief in probabilistic induction. In the next section
it will be shown that despite this seeming plausibility, probabilistic
induction is impossible.

##  4 Proof of the Impossibility of the Probabilistic Solution to the Problem
of Induction

Again let $E=(e_{1}\wedge e_{2}\wedge...)$ where

$\displaystyle e_{1}~{}=~{}\textit{``All observed swans in Austria in 1796 are
white''}$ $\displaystyle e_{2}~{}=~{}\textit{``All observed swans in Austria
in 1797 are white''}$ $\displaystyle...$

Now instead consider two competing generalizations of the evidence $E$

$\displaystyle G_{g}=\textit{``All swans are white''}$ $\displaystyle
G_{b}=\textit{``All swans are violet except in Austria where they are
white''}.$

$G_{g}$ is a typical “good” generalization while $G_{b}$ is a “bad”, or “anti-
inductive” generalization of the evidence. Being Bayesian, we can give the
prior probabilities of $P(G_{g})$ and $P(G_{b})$ any values between 0 and 1 we
like.

We will consider the two ratios

$\displaystyle R_{\text{prior}}=\frac{P(G_{g})}{P(G_{b})}$ $\displaystyle
R_{\text{posterior}}=\frac{P(G_{g}|E)}{P(G_{b}|E)}$

Because any generalization by definition entails the evidence, we have
$P(E|G_{g})=P(E|G_{b})=1$. Therefore we have the following theorem

###### Theorem 2

$R_{\text{posterior}}=\frac{P(E|G_{g})P(G_{g})/P(E)}{P(E|G_{b})P(G_{b})/P(E)}=R_{\text{prior}}$
(3)

This shows that inductive learning can never favor one generalization over
another. Despite raising the probability according to (2), it raises the
probability of all generalizations, even anti-inductive ones such as $G_{b}$.
Or, in Popper’s words[2]:

“Theorem (2) is shattering. It shows that the favourable evidence $E$, even
though it raises the probability according to (2), nevertheless, against first
impressions, leaves everything precisely as it was. It can never favour
$(G_{g})$ rather than $(G_{b})$. On the contrary, the order which we attached
to our hypotheses before the evidence remains. It is unshakable by any
favourable evidence. The evidence cannot influence it.”

Therefore probabilistic induction cannot favor inductive generalizations over
anti-inductive generalizations, and we conclude that probabilistic induction
is impossible.

##  5 Commentary

The proof relies on the fact that, for any generalization $G_{i}$ of the
evidence $E$, the likelihood $P(E|G_{i})=1$. This is the formal condition for
induction – to induce general laws of nature from observations. If one wished
to refute the proof, they would have to either claim:

  1. 1.

$G_{i}$ isn’t a general law, which means probabilistic induction is not
capable of inducing general laws, or

  2. 2.

$G_{i}$ is a general law but that $P(E|G_{i})~{}\neq~{}1$. Stated using our
example, this says: “the probability that all swans in Austria are white is
not 1, despite the fact that all swans are white.” In other words, the general
law $G_{i}$ is not a general law, which is a contradiction.

This shows that probability calculus is not capable of discovering (i.e.
inducing) general laws of nature from data. Given that human beings are
capable of discovering general laws of nature from data, this further shows
that the products of human cognition are not products of the probability
calculus.

## References

  * [1] Karl Popper.  The non existence of probabilistic inductive support.  1985.
  * [2] Karl Popper.  Realism and the aim of science: From the postscript to the logic of scientific discovery.  1992.


# The bridge between Desargues’ and Pappus’ theorems

Ákos G.Horváth  ELKH-BME Morphodynamics Research Group and Department of
Geometry, Institute of Mathematics, Budapest University of Technology and
Economics, Műegyetem rkp. 3., H-1111 Budapest, Hungary<EMAIL_ADDRESS>
###### Abstract.

In this paper, we investigate the configuration theorems of Desargues and
Pappus in a synthetic geometric way. We provide a bridge between the two
configurations with a third one that can be considered a specification for
both. We do not use the theory of collineations or the analytic description of
the plane over a ternary ring.

###### Key words and phrases:

Desargues’ theorem, Pappus’ theorem, plane of incidence, projective plane

###### 1991 Mathematics Subject Classification:

51A05,51A20,51A30

##  1\. Introduction

The first geometric statement about projective planes appears to be that of
Pappus, who postulated the collinearity of three points in a configuration of
points and lines. His finding, the so-called Pappus’ theorem initiated similar
geometric studies, in which the basic objects are points and lines, and
between them there is a fundamental relationship, which we call incidence. It
is not clear whether the truth value of a statement about a configuration
depends on what ”space” the configuration is in. In order to answer this
question, the basic properties of incidence must be fixed, so we need ”axioms”
that describe this relationship. The simplest such system is the axiom system
of the plane of incidence (or projective plane). When we formulate additional
true statements using the given axioms, we use the axiomatic approach of
synthetic geometry. Extending this method to ”higher dimensional” geometry
requires more basic objects, the ”planes” of the geometry, and more axioms
between the new and old basic objects. This raises a new problem, namely
whether the axiom system for the new space provides an opportunity to
formulate stronger results for the planes in the space than the set of axioms
for the plane or not. Desargues configuration and the corresponding theorem
answer this question, in a well-defined projective space Desargues’ theorem is
always true, in contrast to the case of the plane of incidence, when it would
be either true or false. Therefore, the axiomatic approach of synthetic plane
geometry and the approach through the mutual position of planes and lines of
spatial geometry give different results with respect to a specific plane. This
leads to another approach to describing projective geometry: the algebraic (or
analytic) approach to coordinate geometry. This study of projective planes is
usually based on a coordinate method over an algebraic structure. In the first
half of the twentieth century, many important questions were answered using
this method, therefore the ”modern” description of projective planes requires
knowledge of the appropriate (sometimes very strange) algebraic structures.

In this paper, we focus only on the two basic configurations of projective
geometry and give a configuration that connects them. Our method is synthetic
and does not require algebraic knowledge. Starting from the spatial
configuration of the real projective space, we arrived at the planar
configuration with the above property through successive specializations.
Since the vast literature on projective planes contains much information on
such special configurations, we also systematically review the corresponding
results.

###  1.1. History

Many works attempt to give an overview of this very special topic of geometry,
but the terminologies used in most cases differ. In our bibliography we have
listed some monographs [2, 4, 8, 10, 15, 18, 19], as well as some reviews and
research articles [3, 6, 7, 11, 17, 21, 20]. On a plane of incidence, in which
Desargues’ theorem is true, we can assign homogeneous coordinates to the
points, which are elements of a division ring (skew field). The skew field
belonging to the Desarguesian plane is a (commutative) field if and only if
Pappus’ theorem is true in the plane. Consequently, Pappus’ theorem is
necessary to define the standard tools of ”classical projective geometry”. On
the other hand, to create a well-functioning general coordinate system of the
plane, it is sufficient to use the ”Little-Desargues theorem”, which is a
weakened (or minor) version of Desargues’ theorem. A plane with the Little-
Desargues property is called a _Moufang plane_ (see [12] ). (In this case, the
coordinates form an alternative division ring.) If the Little-Desargues
property is not fulfilled in all situations, then we need a coordinate system
over a more general algebraic structure to define and examine the basic
concepts of projective geometry. (Algebraically, the coordinates form a planar
ternary ring, and the system is ”local”, related to four points in the plane
that are located at general positions.)

Skornyakov’s paper (see [16]) contains the first detailed analysis of special
(or minor) forms of Desargues and Pappus theorems. The notation of
Skornyakov’s paper covers the possible specializations of Desargues’
configuration. Smaller forms of Desargues’ theorem and Pappus’ theorem were
also investigated in some later papers, which enrich the literature with
additional results (see, for example, [14] and [1]). When Skornyakov requires
that one, two, or three vertices of one triangle fall on the lines of the
corresponding side of the other triangle, he denotes the corresponding
propositions $D_{1},D_{2}$, and $D_{3}$. (For example, our proposition $wD$ is
a proposition of type $D_{1}$ and the proof of Proposition 1 contains
configurations $D_{1}$, $D_{2}$ and $D_{3}$.) It also distinguishes two
specializations when two extra fits is present in both, but in the first
situation two sides of the first triangle contain the corresponding vertices
of the second triangle, while in the other the first fit occurs on one side of
the first triangle, while in the second it occurs on the corresponding side of
the second triangle. While the first is denoted by $D_{2}$, the second by
$D_{1}^{1}$. Finally, if the extra fit falls on a connecting line passing
through the center of the perspective, the corresponding specialization is
marked with a comma. (Our LD theorem is denoted by $D^{\prime}$ and our wLD
theorem by $D^{\prime}_{1}$ in this system.) Similarly, in the article [1] we
find five minor forms of the Pappus theorem, which are It is denoted by
$P_{i}$, where $i=1,2,3,4,5$. $P_{2}$ is the same as our LP theorem, $P_{1}$
is the dual of $P_{2}$ (the theorem we call Small-Pappus theorem), $P_{3}$ is
called the Perspective-Pappus theorem, $P_{4}$ is its dual and $P_{5}$ is a
statement about the incomplete Pappian chain of inscribed triangles. For the
sake of clarity, we list the proven aspects of these works with their original
designations.

  * •

$D^{\prime}$ is equivalent to $D_{1}$ ([16]. [14])

  * •

$D^{\prime}_{1}$, $D_{1}^{1}$, $D_{2}$ are equivalent statements ([1]).

  * •

$D^{\prime}_{2}$ is equivalent to $D_{3}$ ([1]).

  * •

$D^{\prime}$ implies $P_{1}$ and $P_{2}$ ([14]).

  * •

$D_{2}$ implies all $P_{j}$, where $j=1,2,3,4,5$. ([1])

In the rest of our article, we give the name of a specialization that refers
to the derivation of the appropriate configuration.

###  1.2. Results of the paper

We prove four statements using a purely synthetic method, three of which were
not found in the reviewed literature, and we provide a direct proof for the
fourth known statement.

######  Theorem 1.

The following statements are true for all planes of incidence.

  * •

The Little-Desargues theorem follows from the homologous-Desargues theorem.
(Proposition 1.)

  * •

The weak Little-Desargues theorem is equivalent to the strong Perspective-
Pappus theorem. (Proposition 3.)

  * •

The Little-Pappus theorem follows from the weak Little-Desargues theorem.
(Proposition 4.)

In the Euclidean model of the real projective plane, the Little-Desargues
theorem can be proved from the weak Little-Desargues theorem. (2 suggestion.)

The known implications between the special forms of Desargues’ theorem and
Pappus’ theorem are shown in the diagram below. The black arrow denotes
trivial or previously proven conclusions, the blue arrow denotes the well-
known but synthetically verified conclusions in our article, and the red arrow
those that are not found in the literature. (We do not consider the
implications that are based on ”duality” in the literature without direct
evidence. This is because our investigation also applies to planes where the
”dual” property does not exist.)

Figure 1. The table of implications.

We have only two important questions left unanswered: _Does the weak Little-
Desargues theorem follow from the little-Pappus theorem? Does the Little-
Desargues Theorem follow from the weak Little-Desargues Theorem?_ For
historical reasons, in this paper we denote many propositions by theorems, but
prove only one theorem, which is the collection of the four ”propositions” we
have proved. The placement of these statements in the article corresponds to
the logic of specialization.

##  2\. The plane of incidence and the basic configurations

Veblen and Young give the [19] synthetic structure of the incidence properties
of $n$-dimensional projective geometry. They used two undefined objects, the
point and the line, and the concepts of plane, space, and 4-space are defined
based on them. In our treatment, the above ”system of assumptions” changes to
statements that are theorems in the Veblen-Young system. We lose the
requirement of simplicity and independence, but we get a more didactic system
of axioms, which leads to faster construction of the resulting planar
geometry.

Some points are called collinear if they fall on the same line. The fitting of
points and lines can be considered a so-called _plane of incidence_ , which
satisfies the following three axioms:

######  Axiom P1.

Two points uniquely determine a line which is incident with them.

######  Axiom P2.

Two lines uniquely determine a point which is incident with them.

######  Axiom P3.

There exists four points, no three of which are collinear.

The plane of incidence is a precursor to the concept of the classical
projective plane. We can raise interesting problems in it, e.g. we can examine
statements that assert the fit of certain lines and points based on the fit of
other points and lines. Statements of this type are called _configuration
statements_. If a configuration theorem holds on the plane, then there is a
_configuration_ containing exactly the incidences that the theorem requires.
An example is Desargues’ theorem:

######  Theorem 2 (Desargues).

The lines incident with the pair of points $A,A^{\prime}$; $B,B^{\prime}$ and
$C,C^{\prime}$ are go through the same point $S$ if and only if the points
$X$, $Y$ and $Z$ incident with the pairs of lines $AB$,
$A^{\prime}B^{\prime}$; $BC$, $B^{\prime}C^{\prime}$ and $AC$,
$A^{\prime}C^{\prime}$ are incident with the same line $s$.

Figure 2. The theorem of Desargues

The question is: can we prove Desargues’ theorem on a general plane of
incidence? The answer is known, this theorem is usually not true. (A nice
counterexample is given by Moulton in [13]. For more information on non-
Desarguesian planes, I recommend Weibel’s [21] survey.)

Note that the best-known example of the plane of incidence is the real
projective plane for which this theorem holds. It is also immediately
noticeable that the opposite statement also follows from the proved direction
if we apply the statement to the pairs of points $AB$, $A^{\prime}B^{\prime}$
and $YZ$ of Figure 2 which are perspective from the point $X$. In real
projective geometry, a proof can also be obtained by using space axioms. The
figure 2 contains a complete
$\\{S,A,A^{\prime},B,B^{\prime},E,E^{\prime},X,F,G\\}$ Desargues configuration
embedded in the three-dimensional projective space, its central projection
onto the plane $SAB$ gives the plane Desargues configuration of ten points
$\\{S,A,A^{\prime},B,B^{\prime},C,C^{\prime},X,Y,Z\\}$.

Another important statement of real projective geometry is the Pappus theorem.
It is not valid on all planes of incidence, not even on all Desarguesian
planes. Hessenberg proved in [9] that in a plane of incidence Pappus’ theorem
implies Desargues’ theorem. This means that a plane satisfying Pappus’ theorem
is always Desarguesian. The Pappus configuration is the complete configuration
of the Pappus’ theorem:

######  Theorem 3 (Pappus).

Assume that $A,B,C$ are three points of a line and
$A^{\prime},B^{\prime},C^{\prime}$ are three points of an other line. Then the
points $C^{\prime\prime}=AB^{\prime}\cap A^{\prime}B$,
$B^{\prime\prime}=AC^{\prime}\cap A^{\prime}C$ and
$A^{\prime\prime}=BC^{\prime}\cap B^{\prime}C$ are collinear.

Based on the figure 3, we can easily verify that the dual form of this theorem
(which was first proved by Brianchon) is equivalent to the original statement.
We have:

Figure 3. The equivalence of the Pappus’s theorem and the theorem of Brianchon

######  Theorem 4 (Pappus-Brianchon).

Assume that $a,b,c$ are three lines through a point and
$a^{\prime},b^{\prime},c^{\prime}$ are three lines through another point. Then
the lines $c^{\prime\prime}=(a\cap b^{\prime},a^{\prime}\cap b)$,
$b^{\prime\prime}=(a\cap c^{\prime},a^{\prime}\cap c)$ and
$a^{\prime\prime}=(b\cap c^{\prime},b^{\prime}\cap c)$ are concurrent.

The complete Pappus configuration contains nine points and nine lines, with
three fits on each line and each point. In real projective geometry, there is
a nice connection with Gallucci’s theorem on the transversals of skew lines.
This connection can be seen in the figure 4 (see [5] for more details).

Figure 4. Gallucci’s theorem is equivalent to Pappus’ theorem

##  3\. Specializations of Desargues’ theorem and the corresponding
configurations

In the figure 2, we see that the planar configuration
$\\{S,A,A^{\prime},B,B^{\prime},E,E^{\prime},X,F,G\\}$ can be specialized by
the choice of the center of the projection. For example, if we choose $D$ on
the plane of the line $s^{\prime}$ and the point $S$, we get that the plane
configuration will contain a new incidence relation, namely $S\in s$.

Figure 5. Little-Desargues theorem and the weak Little-Desargues theorem

This new configuration (see the left side of the figure 5) is the
configuration of the Little-Desargues theorem. In this case, the statement is:

######  Theorem 5 (LD theorem).

The lines incident with the pair of points $A,A^{\prime}$; $B,B^{\prime}$ and
$C,C^{\prime}$ are go through the same point $S$, moreover $S,X=AB\cap
A^{\prime}B^{\prime},Y=AC\cap A^{\prime}C^{\prime}$ are also collinear then
$Z=AB\cap A^{\prime}B^{\prime}$ is incident with the line $s=XY$.

The configuration of the Little-Desargues theorem is not as symmetric as the
Desargues configuration. There are four incident lines (points) on a point (a
line), and the rest match only three lines (points). It is clear that the
Little-Desargues Theorem is a logical consequence of the Desargues Theorem,
but it is not clear whether the Little-Desargues Theorem follows from a
restriction of the Desargues Theorem in which we also require that the
perspective axis $s$ does not contain the center $S$ of the perspectivity.
This last condition is the condition of the so-called homologous-Desargues
theorem:

######  Theorem 6 (HD theorem).

The lines incident with the pair of points $A,A^{\prime}$; $B,B^{\prime}$ and
$C,C^{\prime}$ are go through the same point $S$ and $S,X=AB\cap
A^{\prime}B^{\prime},Y=AC\cap A^{\prime}C^{\prime}$ aren’t collinear then
$Z=BC\cap B^{\prime}C^{\prime}$ is incident with the line $s=XY$.

The theory of collineations gives a positive answer to the former question, as
it can be read in the book [18] (see Theorem 5.2.5). We now provide an
immediate proof of this fact.

######  Proposition 1.

The Homologue-Desargues theorem implies the Little-Desargues theorem.

###### Proof.

Consider the notation of Figure 6.

Figure 6. Homologue-Desargues theorem implies Little-Desargues theorem

We need to prove that $Y$ is incident with $s=XZ$. Consider the triangles
$AXY$ and $SB^{\prime}C^{\prime}$, the center of perspectivity is
$A^{\prime}$. (We use the notation
$AXY\overset{A^{\prime}}{\sim}SB^{\prime}C^{\prime}$ for these perspective
triangles.) Since $AX\cap SB^{\prime}=B$ and $AY\cap SC^{\prime}=C$ there are
two possibilities. If $A^{\prime}$ is not incident with the line $BC$, then we
can apply the HD theorem and obtain that the point $XY\cap
B^{\prime}C^{\prime}$ is incident with the line $BC$, that is, the line that
$X$ and $Z=BC\cap B^{\prime}C^{\prime}$ is determined incident to $Y$, as we
said.

If $A^{\prime}$ is incident to $BC$, then we cannot apply the HD theorem, but
we get a more specialized figure (see the middle image of Figure 6). Consider
the perspective triangles
$CZY\overset{C^{\prime}}{\sim}SB^{\prime}A^{\prime}$. Then $CZ\cap
SB^{\prime}=B$ and $CY\cap SA^{\prime}=A$ and again we have two options. If
$AB$ does not contain $C^{\prime}$, then the HD theorem means that the point
$ZY\cap B^{\prime}A^{\prime}$ lies on the line $AB$, so the points $X,Z$ and
$Y$ are collinear. .

In the other case, $C^{\prime}$ lies on the straight line $AB$ (see the right
image in the same figure). Let us now consider the perspective triangles
$BXZ\overset{B^{\prime}}{\sim}SA^{\prime}C^{\prime}$. Since $BX\cap
SA^{\prime}=A$ and $BZ\cap SC^{\prime}=C$ , the two possibilities are that
$B^{\prime}$ is not on $AC$ , or $B^{\prime}$ is incident on with $AC$. In the
first case, applying the HD theorem, we get that $XZ\cap A^{\prime}C^{\prime}$
lies on $AC$, and our statement is fulfilled again.

Finally, suppose that $A,C$ and $B^{\prime}$ are collinear point triples. Then
we have $A^{\prime}XY\overset{A}{\sim}SBC$, which means that $A^{\prime}X\cap
SB=B^{\prime}$, $A^{\prime}Y\cap SC=C^{\prime}$, and $XY\ capBC$ are collinear
if we can apply the HD theorem. If this is not the case, then $A,B^{\prime}$
and $C^{\prime}$ are collinear, and therefore
$AB^{\prime}=B^{\prime}C^{\prime}$. Since $B^{\prime}$ is incident with $AC$,
then $C$ lies on $AB^{\prime}=B^{\prime}C^{\prime}$, therefore
$A,B^{\prime},C,C^{\prime}$ are collinear points. Similarly, $C^{\prime}$ lies
on $AB$, so $AC^{\prime}$ also contains $B$. Thus,
$A,B^{\prime},C,C^{\prime},B$ are collinear points, therefore all points lie
on the same line, and the statement is fulfilled trivially. ∎

######  Remark 1.

The reverse of the statement is not true. A plane of incidence is called
_Moufang plane_ if it can be coordinatized over an alternative division ring.
In the Moufang plane, the Little-Desargues theorem holds, but the validity of
the Homologue-Desargues theorem depends on whether the coordinate ring is
associative or not. Since the Cayley plane over the octonion is a plane of
incidence over a non-associative alternative division ring, this is an example
of a non-Desarguesian Moufang plane. In other words, in general, the LD
theorem doesn’t implies the HD theorem.

If we choose the point $D$ on the intersection of the planes $SFG$ and
$BGA^{\prime}$ in Figure 2, the resulting planar configuration is further
specialized, as shown in the right image of Figure 5. This configuration
induced the weak Little-Desargues theorem (wLD theorem).

######  Theorem 7 (wLD theorem).

The lines incident with the pair of points $A,A^{\prime}$; $B,B^{\prime}$ and
$C,C^{\prime}$ are go through the same point $S$, moreover the points
$S,X=AB\cap A^{\prime}B^{\prime},Y=AC\cap A^{\prime}C^{\prime}$, and
$A^{\prime},B,C$ are also collinear then $Z=BC\cap B^{\prime}C^{\prime}$ is
incident with the line $s=XY$.

The configuration of the wLD theorem contains two points (two lines) with four
matching lines (points), and the other points (lines) have three incidences
with the lines (points) of the configuration.

######  Remark 2.

Note that in 2 there is only one possibility to choose the centre point $D$
for which the points $A,C$ and $B^{\prime}$ are collinear when $D=SFG\
capBGA^{\prime}\ capAFB^{\prime}$. With this choice, we get a planar
configuration similar to the image on the right of the figure 6. It is clear
that further specialization of the planar configuration is impossible with
this method, because the position of the line $AB$ and the point $C^{\prime}$
is independent of the choice of $D$.

An important observation is that the logical consequence of the wLD theorem is
its converse, i.e. the following statement is true:

######  Theorem 8 (cwLD theorem).

Assume that the points $S=AA^{\prime}\cap BB^{\prime}$,$X=AB\cap
A^{\prime}B^{\prime},Y=AC\cap A^{\prime}C^{\prime}$, $Z=BC\cap
B^{\prime}C^{\prime}$ are collinear and the points $A^{\prime},B,C$ are also
collinear then $S$ incident with the line $CC^{\prime}$.

###### Proof.

Consider the middle image in Fig. 6. Let $C^{\star}$ be the intersection of
$SC$ and $A^{\prime}C^{\prime}$ and let $Z^{\star}:=B^{\prime}C^{\star}\cap
BC$ . Then $ABC\overset{S}{\sim}A^{\prime}B^{\prime}C^{\star}$, $AC\cap
A^{\prime}C^{\star}=Y$, $AB\cap A^{\prime}B^{\prime}=X$, where $S,X,Y$ are
collinear (and so are $A^{\prime},B,C$). Applying the wLD theorem, we get that
the points $BC\cap B^{\prime}C^{\star}=R^{\star}$ $X,Z$ are collinear, which
can only happen if $R=R^{\star}$ and thus $C^{\prime}=C^{\star}$. Therefore,
the triplet $S,C,C^{\prime}$ is also collinear. ∎

We do not know whether the LD theorem follows from the wLD theorem or not, but
such a statement can be verified in a space with a metric.

######  Proposition 2.

In the Euclidean model of the real projective plane, the Little-Desargues
theorem can be proved by using only the weak Little-Desargues theorem.

Figure 7. In the real projective plane the weak Little-Desargues theorem
implies the Little-Desargues theorem

###### Proof.

Suppose that the axis of perspectivity is the line $z$ at infinity. In this
case, two triangles are axially perspective with respect to $z$ if their
corresponding sides are parallel to each other. Two triangles satisfy the
conditions of the LD theorem if they are parallel translates of each other,
and satisfy the conditions of the wLD theorem if they are translates of each
other, and one of the vertices of the first triangle falls on the side line of
the other triangle that connects the vertices corresponding to the other two
vertices of the first triangle. To prove the statement, we give a chain of
triangles $ABC=A_{0}B_{0}C_{0}\cong...\cong A_{n}B_{n}C_{n}=STR\cong
A^{\prime\prime}B^{\prime\prime}C^{\prime\prime}$ which holds the wLD
conditions such that the last triangle
$A^{\prime\prime}B^{\prime\prime}C^{\prime\prime}$ also contains the wLD
conditions for $A^{\prime}B^{\prime}C^{\prime}$. Since Archimedes’ axiom
applies to the Euclidean plane, this process can be done with a finite number
of triangles. In fact, consider a chain of translated copies of triangles
$ABC=A_{0}B_{0}C_{0}\cong...\cong A_{n}B_{n}C_{n}=STR$, where for two
consecutive triangles, one of the vertices of the second triangle fits on one
of the sides of the one before it, and one of the vertices of the last
triangle (say $A_{n}=S$) is in the closed domain consisting of the points of
the translated copies intersecting the triangle
$A^{\prime}B^{\prime}C^{\prime}$. Define the triangle
$A^{\prime\prime}B^{\prime\prime}C^{\prime\prime}$ to be the translation of
$ABC$ with the property that its one side contains the point $S$ and one of
its sides contains a vertex of the triangle $A^{\prime}B^{\prime}C^{\prime}$.
Since the parallelism is transitive, with the notations in the figure 7, we
get that $A^{\prime\prime}B^{\prime\prime}$, $A^{\prime}B^{\prime}$ ; and
$A^{\prime\prime}C^{\prime\prime}$, $A^{\prime}C^{\prime}$ are parallel pair
of segments, so $A^{\prime}A^{\prime\prime}$, $B^{\prime}B^{\prime\prime}$ and
$C^{\prime}C^{\prime\prime}$ are also parallel. Since $BC$ is parallel to
$B^{\prime\prime}C^{\prime\prime}$, we get that $BC$ is parallel to
$B^{\prime}C^{\prime}$ if and only if $B^{\prime\prime}C^{\prime\prime}$ is
parallel to $B^{\prime}C^{\prime}$. Since the configuration corresponding to
the triangles $A^{\prime}B^{\prime}C^{\prime}$ and
$A^{\prime\prime}B^{\prime\prime}C^{\prime\prime}$ is a wLD configuration,
this means that the LD theorem follows from the wLD theorem, as stated. ∎

In the figure 2, we can choose point $D$ either on the $BGA^{\prime}$ plane
(but usually not on the $SFG$ plane) or on the $AA^{\prime}G$ plane, to define
new special cases of Desargues’ theorem. The first planar configuration leads
to the _weak Desargues theorem_ (wD theorem) and the second to the _collapsing
Desargues theorem_ (cD theorem).

######  Theorem 9 (wD theorem).

The lines incident with the pair of points $A,A^{\prime}$; $B,B^{\prime}$ and
$C,C^{\prime}$ are go through the same point $S$, moreover the points
$A^{\prime},B,C$ are collinear then $X=AB\cap A^{\prime}B^{\prime},Y=AC\cap
A^{\prime}C^{\prime}$, and $Z=BC\cap B^{\prime}C^{\prime}$ are also collinear.

######  Theorem 10 (cD theorem).

The lines incident with the pair of points $A,A^{\prime}$; $B,B^{\prime}$ and
$C,C^{\prime}$ are go through the same point $S$, let be $X=AB\cap
A^{\prime}B^{\prime},Y=AC\cap A^{\prime}C^{\prime}$, and $Z=BC\cap
B^{\prime}C^{\prime}$ if moreover the points $A,A^{\prime},Z$ are collinear
then $X,Y$ and $Z$ are also collinear.

Exercise 8 in [18] on page 203 states that the theorems LD, wD, and cD are
equivalent to each other. Direct proofs of these equivalences can be
reconstructed based on Figure 8.

Figure 8. The three types of specialization are equivalent to each other.

##  4\. Specializations of Pappus’ theorem and the corresponding
configurations

Our first observation is that the configuration of the wLD theorem can also be
considered a specialized configuration of Pappus’ theorem. If we rewrite the
notation of the original left-hand configuration in the figure 9 and change
the position of the dashed line that indicates the conclusion in the theorem,
we can formulate a Pappus-type theorem whose configuration is the right-hand
image of the figure. Therefore, this configuration can be considered a
”bridge” between Desargues’ theorem and Pappus’ theorem.

Figure 9. The ”bridge configuration” between the Desargues’ theorem and
Pappus’ theorem.

######  Theorem 11 (sPP theorem).

Assume that $A,B,C$ are three points of one line and
$A^{\prime},B^{\prime},C^{\prime}$ are three points of another line, where $M$
is a common point of the two lines. Assume that the triples $S,A,A^{\prime}$
$S,B,B^{\prime}$ and $S,C,C^{\prime}$ are also collinear. Then the points $M$,
$C^{\prime\prime}=AB^{\prime}\cap A^{\prime}B$ and
$A^{\prime\prime}=BC^{\prime}\cap B^{\prime}C$ are collinear.

We call this theorem _strong perspective Pappus theorem_ (spP theorem) because
its logical consequence is the _perspective Pappus theorem_ :

######  Theorem 12 (pP theorem).

Assume that $A,B,C$ are three points of one line and
$A^{\prime},B^{\prime},C^{\prime}$ are three points of another line. Assume
that the triples $S,A,A^{\prime}$ $S,B,B^{\prime}$ and $S,C,C^{\prime}$ are
also collinear. Then the points $C^{\prime\prime}=AB^{\prime}\cap
A^{\prime}B$, $B^{\prime\prime}=AC^{\prime}\cap A^{\prime}c$ and
$A^{\prime\prime}=BC^{\prime}\cap B^{\prime}C$ are collinear.

This theorem is called ”Specialized Pappus Theorem One” by [18] (see Exercise
3 on page 212) and is true on the Desarguesian plane. Notice that in the
Moulton plane it is easy to specify the position of the points
$S,A,B,C,A^{\prime},B^{\prime},C^{\prime}$ in such a way that the assertion of
the pP theorem is fulfilled, but the points
$A^{\prime\prime},B^{\prime\prime},C^{\prime\prime}$ and $M$ are not
collinear. This shows that the sPP theorem is stronger than the PP theorem.
The following theorem proves the legitimacy of the name ”bridge
configuration”.

######  Proposition 3.

The weak Little-Desargues theorem is equivalent to the strong perspective
Pappus theorem.

Figure 10. Configuration for proofs

###### Proof.

Considering the notations in the figure 10, we see that
$C^{\prime\prime}B^{\prime}A^{\prime\prime}\overset{B}{\sim}A^{\prime}SC^{\prime}$
perspective is satisfied. Since $B^{\prime}A^{\prime\prime}\cap
SC^{\prime}=C$, $B^{\prime}C^{\prime\prime}\cap SA^{\prime}=A$, $A,B,C$ and
$A^{\prime},B^{\prime},C^{\prime}$ are collinear , we can apply the wLD
theorem and obtain that $A^{\prime}C^{\prime}\cap
A^{\prime\prime}C^{\prime\prime}$, $A$ and $C$ are also collinear. It follows
that the assertion of the spP theorem is fulfilled.

Conversely, suppose that the sPP theorem holds on the plane. Let
$A^{\prime}DC^{\prime}$ and $AB^{\prime}C$ be two given triangles with
perspective $A^{\prime}DC^{\prime}\overset{S}{\sim}AB^{\prime}C$, on which the
points $A^{\prime},B^{\prime},C^{\prime}$ is collinear, and
$R:=AB^{\prime}\cap A^{\prime}D$, $T=C^{\prime}D\cap CB^{\prime}$ and $S$ are
also collinear. Then $TSR\overset{D}{\sim}C^{\prime}B^{\prime}A^{\prime}$,
therefore the collinear triples $T,S,R$ and $C^{\prime},B^{\prime},A^{\prime}$
are in perspective position and are satisfied , that $TB^{\prime}\cap
C^{\prime}S=C$ and $B^{\prime}R\cap SA^{\prime}=A$. It follows from the sPP
theorem that the line $AC$ contains the intersection of the lines $TR$ and
$A^{\prime}C^{\prime}$, which means that the points $R,S,T$ and $AC\cap
A^{\prime}C^{\prime}=M$ is collinear. That is, the statement of the wLD
theorem is true for the examined triangles. ∎

There is another specialization of Pappus’ theorem, whose extra condition is
analogous to the condition of the LD theorem, which we call _Little-Pappus
theorem_ rather than ”Specialized Pappus theorem Two”, as [18] .

######  Theorem 13 (LP theorem).

Assume that $A,B,C$ are three points of a line and
$A^{\prime},B^{\prime},C^{\prime}$ are three points of another line whose
point of intersection is $M$. Assume that the points
$C^{\prime\prime}=AB^{\prime}\cap A^{\prime}B$,
$A^{\prime\prime}=BC^{\prime}\cap B^{\prime}C$ and $M$ are collinear. Then
$C^{\prime\prime}=AB^{\prime}\cap A^{\prime}B$,
$B^{\prime\prime}=AC^{\prime}\cap A^{\prime}c$ and
$A^{\prime\prime}=BC^{\prime}\cap B^{\prime}C$ are collinear, too.

As shown in Exercise 4 on page 212 of [18], this theorem follows from
Desargues’ theorem. Now we prove a little more:

######  Proposition 4.

The weak Little-Desargues theorem implies the Little-Pappus theorem.

###### Proof.

To prove the statement, consider the figure 10 and assume that
$A^{\prime\prime},C^{\prime\prime}$ and $M$ are collinear. Let
$S=AA^{\prime}\cap CC^{\prime}$, $R=AB^{\prime}\cap SM$, $D=B^{\prime}S\cap
A^{\prime}R$, and $T=C^{\prime}D\cap SM$. Then
$AB^{\prime}C\overset{S}{\sim}A^{\prime}DC^{\prime}$ holds, where
$AB^{\prime}\cap A^{\prime}D=R$, $A^{\prime}C^{\prime}\cap AC=M$. Now
$A^{\prime},B^{\prime},C^{\prime}$; Point triples $R,S,M$ are collinear,
therefore, according to the wLD theorem, $DC^{\prime}\cap CB^{\prime}$ lies on
the line $SM$, which means that $C,B^{\prime},T$ is collinear. Now consider
the triangles $SAC$ and $BC^{\prime\prime}A^{\prime\prime}$, with their
vertices $SA\cap BC^{\prime\prime}=A^{\prime}$, $SC\cap
BA^{\prime\prime}=C^{\prime}$ $AC\cap C^{\prime\prime}A^{\prime\prime}=M$ is
triple collinear and $AC^{\prime\prime}\cap CA^{\prime\prime}=B^{\prime}$ is
on their line. Since $B,A,C$ are also collinear, we get from the cwLD theorem
that $B^{\prime}$ is a point on the $SB$ line. This means that in the case of
$A,B,C$ and $A^{\prime},B^{\prime},C^{\prime}$ the assumption of the pP
theorem holds, which is a consequence of the spP theorem, therefore
$A^{\prime\prime},B^{\prime\prime}$ and $C^{\prime\prime}$ are also collinear.
∎

## References

  * [1] Al-Dhahir, M.W., Ghalieh, K.: On minor forms of Desargues and Pappus Geometriae Dedicata 42 (1992) 329–344.
  * [2] Baer, R.: Homogeneity of Projective Planes American J. Math. 64 (1942), 137–152.
  * [3] Burn, R.P.: Bol Quasi-Fields and Pappus’ Theorem Math. Zeitschr. 105, (1968) 351–364.
  * [4] Dembowski, P.: Finite Geometries, Springer, 1968.
  * [5] G.Horváth, Á.: Theorem of Gallucci revisited. Journal of Geometry and Graphics 23/2 (2019) 167–178.
  * [6] Grari, A.: A necessary and sufficient condition so that two planar ternary rings induce isomorphic projective planes. Arch. Math. 83 (2004) 183–192.
  * [7] Hall, M.: Projective planes Transactions of the American Mathematical Society 53 (1943), 229–277.
  * [8] Hall, M.: The Theory of Groups, 434 pp., Macmillan, 1959.
  * [9] Hessenberg, G.,(1905), Beweis des Desarguesschen Satzes aus dem Pascalschen, Mathematische Annalen 61/2 (1905), 161–172.
  * [10] Hughes, D.R., Piper, F.C.: Projective Planes, Springer, New York, 1973.
  * [11] Marchisotto, E. A.: The Theorem of Pappus: A Bridge between Algebra and Geometry The American Mathematical Monthly 109/6 (2002) 497–516.
  * [12] Moufang, R.: Alternativkörper und der Satz vom vollständigen Vierseit Abh.Math. Sem. Hamburg 9 (1933), 207–222.
  * [13] Moulton, F.R., A simple non-Desarguesian plane geometry Transactions of the American Mathematical Society 3/2, (1902) 192–195.
  * [14] Pickert, G.: Projektive Ebenen, Springer-Verlag, Berlin, Heidelberg, New York, 1976.
  * [15] Seidenberg, A.: Lectures in projective geometry, Princeton, 1962.
  * [16] Skornyakov, L.A.: Projective planes, Amer. Math. Soc. Transl. 99 1953\.
  * [17] Spencer J.C.D: On the Lenz-Barlotti classification of projective planes Quart. J. Math. 3/11 (1960), 341–357.
  * [18] Stevenson F. W.: Projective Planes, W. H. Freeman and Company, 1972.
  * [19] Veblen, O., Young, J. W., Projective geometry, I., Blaisdell Publishing Company, 1910.
  * [20] Veblen, O., Wedderburn, J.: Non-Desarguesian and non-Pascalian geometries, Trans. AMS 8 (1907), 379–388.
  * [21] Weibel, Ch., Survey of Non-Desarguesian Planes, Notices of the American Math. Soc. 54/10, (2007), 1294–1303.