# Disentangling homophily, community structure and triadic closure in networks

Tiago P. Peixoto<EMAIL_ADDRESS>Department of Network and Data Science,
Central European University, 1100 Vienna, Austria  Department of Mathematical
Sciences, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom

###### Abstract

Network homophily, the tendency of similar nodes to be connected, and
transitivity, the tendency of two nodes being connected if they share a common
neighbor, are conflated properties in network analysis, since one mechanism
can drive the other. Here we present a generative model and corresponding
inference procedure that is capable of distinguishing between both mechanisms.
Our approach is based on a variation of the stochastic block model (SBM) with
the addition of triadic closure edges, and its inference can identify the most
plausible mechanism responsible for the existence of every edge in the
network, in addition to the underlying community structure itself. We show how
the method can evade the detection of spurious communities caused solely by
the formation of triangles in the network, and how it can improve the
performance of link prediction when compared to the pure version of the SBM
without triadic closure.

##  I Introduction

One of the most typical properties of social networks is the presence of
_homophily_ McPherson and Smith-Lovin (1987); Shrum  _et al._ (1988); Moody
(2001a); McPherson  _et al._ (2001), i.e. the increased tendency of an edge to
exist between two nodes if they share the same underlying characteristic, such
as race, gender, class and a variety of other social parameters. More broadly,
when the underlying similarity parameter is not specified _a priori_ , the
same homophily pattern is known as _community structure_ Fortunato (2010).
Another pervasive pattern encountered in the same kinds of network is
_transitivity_ Rapoport (1953); Holland and Leinhardt (1971, 1975), i.e. the
increased probability of observing an edge between two nodes if they have a
neighbor in common. Although these patterns are indicative of two distinct
mechanisms of network formation, namely choice or constraint homophily
Kossinets and Watts (2009) and triadic closure Granovetter (1973),
respectively, they are generically conflated in non-longitudinal data. This is
because both processes can result in the same kinds of observation: 1. the
preferred connection between nodes of the same kind can induce the presence of
triangles involving similar nodes, and 2. the tendency of triangles to be
formed can induce the formation of groups of nodes with a higher density of
connections between them, when compared to the rest of the network Foster  _et
al._ (2011, 2010). This conflation means we cannot reliably interpret the
underlying mechanisms of network formation merely from the abundance of
triangles or observed community structure in network data.

In this work we present a solution to this problem, consisting in a principled
method to disentangle homophily and community structure from triadic closure
in network data. This is achieved by formulating a generative model that
includes community structure in a first instance, and an iterated process of
triadic closure in a second. Based on this model, we develop a Bayesian
inference algorithm that is capable of identifying which edges are more likely
to be due to community structure or triadic closure, in addition to the
underlying community structure itself.

Several authors have demonstrated that triadic closure can induce community
structure and homophily in networks. Foster et al Foster  _et al._ (2011,
2010) have shown that maximum entropy network ensembles conditioned on
prescribed abundances of triangles tend to possess high modularity. A more
recent analysis of this kind of ensemble by López et al Lopez and Coolen
(2020) showed that it is marked by a spontaneous size-dependent formation of
“triangle clusters.” Bianconi et al Bianconi  _et al._ (2014) have
investigated a network growth model, where nodes are progressively added to
the network, and connected in such a way as to increase the amount of
triangles, and shown that it is capable of producing networks with emergent
community structure. The effect of triangle formation on apparent community
structure has been further studied by Wharrie et al Wharrie  _et al._ (2019),
who showed that those patterns can even mislead methods specifically designed
to avoid the detection of spurious communities in random networks. More
recently, Asikainen et al Asikainen  _et al._ (2020) have shown that iterated
triadic closure can exacerbate homophily present in the original network, via
a simple macroscopic model.

The approach presented in this work differs from the aforementioned ones
primarily in that it runs in the reverse direction: instead of only defining a
conceptual network model that demonstrates the interlink between triadic
closure and homophily given prescribed parameters, the proposed method
operates on empirical network data, and reconstructs the underlying generative
process, decomposing it into distinct community structure and triadic closure
components. As we show, this reconstruction yields a detailed interpretation
of the underlying mechanisms of network formation, allowing us to identify
macro-scale structures that emerge spontaneously from micro-scale higher-order
interactions Battiston  _et al._ (2020); Benson  _et al._ (2018), and in this
way we can separate them from inherently macro-scale structures.

Our method is based on the nonparametric Bayesian inference of a modified
version of the stochastic block model (SBM) Holland  _et al._ (1983); Peixoto
(2019) with the addition of triadic closure edges, and therefore leverages the
statistical evidence available in the data, without overfitting. Importantly,
our method is capable of determining when the observed structure can be
attributed to an actual preference of connection between nodes, as described
by the SBM, rather than an iterated triadic closure process occurring on top
of a substrate network. As a result, we can distinguish between “true” and
_apparent_ community structure caused by increased transitivity. As we also
demonstrate, this decomposition yields an edge prediction method that tends to
perform better in many instances than the SBM used in isolation.

Our manuscript is organized as follows. In Sec. II we describe our model, and
its inference procedure. In Sec. III we demonstrate how it can be used
disambiguate triadic closure from community structure in artificially
generated networks. In Sec. IV we perform an analysis of empirical networks,
in view of our method. In Sec. V we show how our model can improve edge
prediction. We end in Sec. VI with a conclusion.

##  II Stochastic block model with triadic closure (SBM/TC)

Generative process
---
Seminal edges | Triadic closure | Observed network
|  |
Statistical inference
Observed network | Posterior distribution | Marginal probabilities
|  |  |
|

Figure 1: Schematic representation of the generative process considered (top)
and the associated inference procedure (bottom). The generative process
consists in the placement of seminal edges according to a SBM, and the
addition of triadic closure edges conditioned on the seminal edges (shown in
red). The inference procedure runs in the reverse direction, and given an
observed graph, it produces a posterior distribution of possible divisions of
seminal and triadic closure edges, with which edge marginal probabilities on
the edge identities can be obtained.

Community structure and triadic closure are generally interpreted as different
processes of network formation. With the objective of allowing their
identification _a posteriori_ from network data, our approach consists in
defining a generative network model that encodes both processes explicitly.
More specifically, our generative model consists of two steps, with the first
one being the generation of a substrate network containing “seminal” edges,
placed according to an arbitrary mixing pattern between nodes, and an
additional layer containing triadic closure edges, potentially connecting two
nodes if they share a common neighbor in the substrate network (see Fig. 1).
The final network is obtained by “erasing” the identity of the edges. i.e.
whether they are seminal or due to closure of a triangle. Conversely, the
inference procedure consists in moving in the opposite direction, i.e. given a
simple graph, with no annotations on the edges, we consider the posterior
distribution of all possible divisions into seminal and triadic closure edges,
weighted according to their plausibility.

We will denote the seminal edges with an adjacency matrix $\bm{A}$, and for
its generation we will use the degree-corrected stochastic block model (DC-
SBM) Karrer and Newman (2011), conditioned on a partition $\bm{b}$ of the
nodes into $B$ groups, where $b_{i}\in[1,B]$ is the group membership of node
$i$, which has a marginal distribution given by Peixoto (2017)

$P(\bm{A}|\bm{b})=\frac{\prod_{r<s}e_{rs}!\prod_{r}e_{rr}!!\prod_{i}k_{i}!}{\prod_{i<j}A_{ij}!\prod_{i}A_{ii}!!\prod_{r}e_{r}!}\times\prod_{r}\frac{\prod_{k}\eta_{k}^{r}!}{n_{r}!q(e_{r},n_{r})}\times\\\
{\frac{B(B+1)}{2}+E-1\choose E}^{-1},$ (1)

where $e_{rs}=\sum_{ij}A_{ij}\delta_{b_{i},r}\delta_{b_{j},s}$ is the number
of edges between groups $r$ and $s$ (or twice that for $r=s$),
$e_{r}=\sum_{s}e_{rs}$, $k_{i}=\sum_{j}A_{ij}$ is the degree of node $i$,
$n_{r}=\sum_{i}\delta_{b_{i},r}$ is the number of nodes in group $r$,
$\eta^{r}_{k}=\sum_{i}\delta_{b_{i},r}\delta_{k_{i},k}$ is the number of nodes
in group $r$ with degree $k$, $E=\sum_{ij}A_{ij}/2$ is the total number of
edges, and $q(m,n)$ is the number of restricted partitions of integer $m$ into
at most $n$ parts. We refer to Ref. Peixoto (2017) for a detailed derivation
of this marginal likelihood, including also the extension for hierarchical
partitions that is straighforward to incorporate, as well as latent
multigraphs Peixoto (2020a) (see appendix A), both of which we have used in
our analysis. This model is capable of generating networks with arbitrary
degree distributions and mixing patterns between groups of nodes, including
homophily Peixoto (2019).

The triadic closure edges are represented by an additional set of $N$ “ego”
graphs $\bm{g}$, attributed to each node $u$ of $\bm{A}$, where $\bm{g}(u)$ is
the ego graph of node $u$. The ego graph $\bm{g}(u)$ is allowed only to
contain nodes that are neighbors of $u$ in $\bm{A}$ (excluding $u$ itself),
and edges that do not exist in $\bm{A}$, so that any existing edge in
$\bm{g}(u)$ amounts to a triadic closure in $\bm{A}$. The adjacency of
$\bm{g}(u)$ is given by

$g_{ij}(u)=\begin{cases}1,&\text{ if }(i,j)\in\bm{g}(u),\\\ 0,&\text{
otherwise.}\end{cases}$ (2)

Let us denote the existence of a open triad $(i,u,j)$ in $\bm{A}$ with

$m_{ij}(u)=A_{ui}A_{uj}(1-A_{ij}),$ (3)

such that $m_{ij}(u)=1$ if the open triad exists, or $0$ otherwise, and we
adopt the convention $\bm{A}_{uu}=0$ throughout. Therefore, an edge $(i,j)$
can exist in $\bm{g}(u)$ only if $m_{ij}(u)=1$. Based on this, the ego
networks are generated independently with probability,

$P(\bm{g}(u)|\bm{A},p_{u})=\prod_{i<j}\left[p_{u}m_{ij}(u)\right]^{g_{ij}(u)}\left[1-p_{u}m_{ij}(u)\right]^{1-g_{ij}(u)}.$
(4)

where $p_{u}\in[0,1]$ is a probability associated with node $u$ that controls
the degree to which its neighbors in $\bm{A}$ end up connected in $\bm{g}(u)$.
This process may result in the same edge $(i,j)$ existing in different graphs
$\bm{g}(u)$, if $i$ and $j$ share more than one common neighbor in $\bm{A}$.
We therefore consider the resulting simple graph $\bm{G}(\bm{A},\bm{g})$,
constructed by ignoring any multiplicities introduced by the various ego
graphs, i.e. with adjacency given by

$G_{ij}(\bm{A},\bm{g})=\begin{cases}1,&\text{ if
}A_{ij}+\sum_{u}g_{ij}(u)>0,\\\ 0,&\text{ otherwise.}\end{cases}$ (5)

The joint probability of the above process is then given by

$P(\bm{G},\bm{g},\bm{A}|\bm{p},\bm{b})=\bm{1}_{\\{\bm{G}=\bm{G}(\bm{A},\bm{g})\\}}P(\bm{A}|\bm{b})\prod_{u}P(\bm{g}(u)|\bm{A},p_{u}),$
(6)

where $\bm{1}_{\\{x\\}}$ is the indicator function. Unfortunately, the
marginal probability of the final graph

$P(\bm{G})=\sum_{\bm{g},\bm{A},\bm{b}}\int
P(\bm{G},\bm{g},\bm{A}|\bm{p},\bm{b})P(\bm{p})P(\bm{b})\,\mathrm{d}\bm{p},$
(7)

with $P(\bm{p})$ and $P(\bm{b})$ being prior probabilities, does not lend
itself to a tractable computation. Luckily, however, this will not be needed
for our inference procedure. Instead, we are interested in the posterior
distribution

$P(\bm{g},\bm{A},\bm{b}|\bm{G})=\frac{P(\bm{G},\bm{g},\bm{A}|\bm{b})P(\bm{b})}{P(\bm{G})},$
(8)

which describes the probability of a decomposition of an observed simple graph
$\bm{G}$ into its seminal graph $\bm{A}$, the underlying community structure
$\bm{b}$, and the triadic closures represented by the ego graphs $\bm{g}$.
(Although the marginal distribution $P(\bm{G})$ appears in the denominator of
the above equation, we will see in later on that it is just a normalization
constant that does not in fact need to be computed.) The marginal likelihood

$P(\bm{G},\bm{g},\bm{A}|\bm{b})=P(\bm{G}|\bm{A},\bm{g})P(\bm{g}|\bm{A})P(\bm{A}|\bm{b})$
(9)

can be computed easily via

$\displaystyle P(\bm{g}|\bm{A})$
$\displaystyle=\prod_{u}\int_{0}^{1}P(\bm{g}(u)|\bm{A},p)P(p)\,\mathrm{d}p$
$\displaystyle=\prod_{u}\left[{\sum_{i<j}m_{ij}(u)\choose\sum_{i<j}g_{ij}(u)}^{-1}\frac{1}{1+\sum_{i<j}m_{ij}(u)}\right],$
(10)

where we have used a uniform prior $P(p)=1$, and with the remaining likelihood
term being only the indicator function,
$P(\bm{G}|\bm{A},\bm{g})=\bm{1}_{\\{\bm{G}=\bm{G}(\bm{A},\bm{g})\\}}$.
Although this choice of priors makes the calculation very simple, it implies
that we expect the observed graphs to always have a large fraction of triadic
closures. In Appendix B we describe a slight modification of this model that
makes it more versatile with respect to the abundance of triadic closures, at
the expense of yielding somewhat longer expressions for the likelihood. We
note that we made use of the modifications specified there in our ensuing
analysis, as they can only improve the use of the model.

###  II.1 Iterated triadic closures

Figure 2: Example network illustrating how iterated triadic closures are
implemented in the model. The initial network (black edges) receives the first
generation of triadic closures (red edges). The second generation (green
edges) can only close triads involving at least one edge of the first
generation (red). The third generation (blue edges) in turn can only close
triads involving at least one edge belonging to the second generation (green).

Triadic closures increase the number of edges in the network, and in this way
can introduce opportunities for new triadic closures, involving both older and
newer edges. This leads naturally to a dynamical model, where generations of
triadic closures are progressively introduced to the network. We can
incorporate this in our model via “layers” of ego graphs $\bm{g}^{(l)}$
representing edges introduced in generation $l\in[1,\dots,L]$. For our
formulation, it will be useful to define the cumulative network at generation
$l$, defined recursively by

$A^{(l)}_{ij}=\begin{cases}1,&\text{ if
}A_{ij}^{(l-1)}+\sum_{u}g_{ij}^{(l)}(u)>0,\\\ 0,&\text{
otherwise,}\end{cases}$ (11)

with boundary conditions $\bm{A}^{(0)}=\bm{A}$, and $\bm{g}^{(0)}(u)$ being
empty graphs for all $u$, and we will denote the final generation as
$\bm{A}^{(L)}=\bm{G}$. The formation of new triadic closure layers is done
according to the probability

$P(\bm{g}^{(l)}(u)|\bm{A}^{(l-1)},\bm{g}^{(l-1)},p_{u}^{(l)})=\\\
\prod_{i<j}\left[p_{u}^{(l)}m_{ij}^{(l)}(u)\right]^{g_{ij}^{(l)}(u)}\left[1-p_{u}^{(l)}m_{ij}^{(l)}(u)\right]^{1-g_{ij}^{(l)}(u)}.$
(12)

where an open triad $(i,u,j)$ at generation $l$ is denoted by

$m_{ij}^{(l)}(u)=w_{ij}^{(l)}(u)\left(1-A_{ij}^{(l-1)}\right),$ (13)

so that $m_{ij}(u)\in\\{0,1\\}$, where

$w_{ij}^{(l)}(u)=\\\ \begin{cases}1,&\text{ if
}A_{ui}^{(l-1)}\sum_{v}g^{(l-1)}_{uj}(v)+A_{uj}^{(l-1)}\sum_{v}g^{(l-1)}_{ui}(v)>0,\\\
0,&\text{ otherwise.}\end{cases}$ (14)

determines whether or not the open triad $(i,u,j)$ at generation $l$ has at
least one of the edges $(u,i)$ or $(u,j)$ formed exactly at the preceding
generation $l-1$. This restriction means that triadic closures at generation
$l$ can only close new triads that have been introduced at generation $l-1$,
not previously. The reason for this is a matter of identifiability: an edge at
generation $l$ that closes an open triad that has been formed at generation
$l^{\prime}<l$ could also have been generated in any of the intermediate
generations $[l^{\prime},l-1]$, thus introducing a inevitable ambiguity in the
inference. The above restriction removes the ambiguity, and forces the new
generations to form triadic closures which could not have existed in the
preceding generations (see Fig. 2). Note that this restriction does not alter
the generality of the model, since the same final networks can still be formed
despite this restriction, simply by choosing appropriate values for
$\\{p_{u}^{(l)}\\}$.

With the above, the joint likelihood of all generations is given by

$P(\\{\bm{g}^{(l)}\\},\bm{A}|\bm{b},\bm{p})=\\\
P(\bm{A}|\bm{b})\prod_{l=1}^{L}\prod_{u}P(\bm{g}^{(l)}(u)|\bm{A}^{(l-1)},\bm{g}^{(l-1)},p_{u}^{(l)}).$
(15)

Following the same calculation as before, we obtain the individual marginal
likelihood at each generation $l$ as

$P(\\{\bm{g}^{(l)}\\},\bm{A}|\bm{b})=P(\bm{A}|\bm{b})\prod_{l=1}^{L}P(\bm{g}^{(l)}|\bm{A}^{(l-1)},\bm{g}^{(l-1)}).$
(16)

with the individual terms in the product being entirely analogous to Eq. 10,

$P(\bm{g}^{(l)}|\bm{A}^{(l-1)},\bm{g}^{(l-1)})=\\\
\prod_{u}\left[{\sum_{i<j}m_{ij}^{(l)}(u)\choose\sum_{i<j}g_{ij}^{(l)}(u)}^{-1}\frac{1}{1+\sum_{i<j}m_{ij}^{(l)}(u)}\right].$
(17)

Finally, the posterior distribution for the reconstruction becomes

$P(\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{G})=\frac{P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A}|\bm{b})P(\bm{b})}{P(\bm{G})}.$
(18)

Note that for $L=1$ we recover the previous model. Having to specify $L$
beforehand is not a strict necessity, since the inference will only occupy new
generations if this yields a more parsimonious description of the network.
111If we wanted to tread $L$ as an unknown, we should introduce a prior for
$L$, $P(L)$, and include that in the posterior as well. However, with the
parametrization in Appendix B, generations which are unpopulated with edges
have no contribution to the marginal likelihood. Therefore we can simply set
$L$ to be a sufficiently large value, for example $L={N\choose 2}$, since for
later generations it is impossible to add new edges.

###  II.2 Inference algorithm

|  |
---|---|---
(a) Random seminal edges |  (b) Triadic closure edges and spurious communities found with SBM ($\Sigma_{\text{SBM}}=801.7$ nats) |  (c) Inference of the SBM/TC model ($\Sigma_{\text{SBM/TC}}=590.6$ nats)
Figure 3: (a) Example artificial network generated as a fully random random
graph with a geometric degree distribution, $N=100$ nodes and $E=94$ edges,
and (b) a process of triadic closure based on network (a) with parameter
$p_{u}=0.8$ for every node, with closure edges shown in red. It is also shown
the partition found by fitting the SBM to the resulting network, and the
description length obtained. (c) The result of inferring the SBM/TC model,
which uncovers a single partition — no community structure — and the closure
edges shown in red (the thickness of the edges correspond to the marginal
probabilities $\pi_{ij}$ and $1-\pi_{ij}$ for the seminal and closure edges,
respectively). It is also shown the description length of the SBM/TC fit.

The posterior distribution of Eq. 18 can be written exactly, up to a
normalization constant. However, this fact alone does not allow us to directly
sample from this distribution, which can only be done in very special cases.
Instead, we rely here on Markov chain Monte Carlo (MCMC), implemented as
follows. We begin with an arbitrary choice of $\\{\bm{g}^{(l)}\\}$, $\bm{A}$
and $\bm{b}$ that is compatible with our observed graph $\bm{G}$. We then
consider modifications of these quantities, and accept or reject them
according to the Metropolis-Hastings criterion Metropolis  _et al._ (1953);
Hastings (1970). More specifically, we consider moves of the kind
$P(\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime}|\\{{\bm{g}}^{(l)}\\},\bm{A})$,
and accept them according to the probability

$\min\left(1,\frac{P(\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime},\bm{b}|\bm{G})P(\\{{\bm{g}}^{(l)}\\},\bm{A}|\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime})}{P(\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{G})P(\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime}|\\{{\bm{g}}^{(l)}\\},\bm{A})}\right)\\\
$ (19)

which, as we mentioned before, does not require the computation of the
intractable marginal probability $P(\bm{G})$. We also consider moves that
change the community structure, according to a proposal
$P(\bm{b}^{\prime}|\bm{b})$ and accept with probability

$\min\left(1,\frac{P(\bm{A}|\bm{b}^{\prime})P(\bm{b}^{\prime})P(\bm{b}|\bm{b}^{\prime})}{P(\bm{A}|\bm{b})P(\bm{b})P(\bm{b}^{\prime}|\bm{b})}\right).$
(20)

For the latter we use the merge-split moves described in Ref. Peixoto (2020b).
Iterating the moves described above eventually produces samples from the
target posterior distribution. In Appendix C we specify the details of the
particular move proposals we use.

Given samples from the posterior distribution, we can use them to summarize it
in a variety of ways. A useful quantity is the marginal probability $\pi_{ij}$
of an edge $(i,j)$ being seminal, which is given by

$\pi_{ij}=\sum_{\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}}A_{ij}P(\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{G}).$
(21)

Conversely, the reciprocal quantity,

$1-\pi_{ij},$ (22)

corresponds to the probability that edge $(i,j)$ is due to triadic closure,
occurring in any generation or ego graph. Therefore, the quantity $\bm{\pi}$
gives us a concise summary of posterior decomposition of a network, and we
will use it throughout our analysis. (It easy to devise and compute other
summaries, such as the marginal probability of an edge belonging to a given
triadic generation, or a particular ego graph, but we will not have use for
those in our analysis.)

##  III Distinguishing community structure from triadic closure

Here we illustrate how triadic closure can be mistaken as community structure,
and how our inference method is capable of uncovering it. We begin by
considering an artificial example, where we first sample a fully random
network with a geometric degree distribution, $N=100$ nodes and $E=94$ edges,
as shown in Fig. 3a. This network does not possess any community structure,
since the probability of observing an edge is just proportional to the product
of the degrees of the endpoint nodes — indeed if we fit a DC-SBM to it, we
uncover, correctly, only a single group. Conditioned on this network, Fig. 3b
shows sampled triadic closure edges, according to the model described
previously, where each node has the same probability $p_{u}=0.8$ of having
neighbours connected in their ego graphs. In the same figure we show the
result of fitting the DC-SBM on the network obtained by ignoring the edge
types. That approach finds five assortative communities, corresponding to
regions of higher densities of edges induced by the random introduction of
transitive edges. One should not, however, interpret the presence of these
regions as a special affinity between the respective groups of nodes, since
they are a result of a random process that has no relation to that particular
division of the network — indeed, if we run the whole process again from the
beginning, the nodes will most likely end up clustered in completely different
“communities.” If we now perform the inference of our SBM with triadic closure
(SBM/TC), we obtain the result shown in Fig. 3c. Not only are we capable of
distinguishing the seminal from the triadic closure edges (AUC ROC = $0.92$),
but we also correctly identify the presence of a single group of nodes, which
is in full accordance with the completely random nature in which the network
has been generated. In other words, with the SBM/TC we are not misled by the
density heterogeneity introduced by triadic closures into thinking that the
network possesses real community structure, and we realize instead that they
can be better explained by a different process.

In the artificial example considered above, the result obtained with the
SBM/TC model is more appealing, since it more closely matches the known
generative process that was used. However, in more realistic situations, we
will need to decide if it provides a better description of the data without
such privileged information. In view of this, we can make our model selection
argument more formal in the following way. Suppose we are considering a
partition $\bm{b}^{(1)}$ found with inferring the SBM on a given network, as
well as another partition $\bm{b}^{(2)}$ and ego graphs $\\{\bm{g}^{(l)}\\}$
found with the SBM/TC model. We can decide which one provides a better
description of a network via the posterior odds ratio,

$\displaystyle\Lambda$
$\displaystyle=\frac{P(\bm{b}^{(2)},\\{\bm{g}^{(l)}\\},\mathcal{H}_{\text{SBM/TC}}|\bm{G})}{P(\bm{b}^{(1)},\mathcal{H}_{\text{SBM}}|\bm{G})}$
(23)
$\displaystyle=\frac{P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}^{(2)})}{P(\bm{G},\bm{b}^{(1)})}\times\frac{P(\mathcal{H}_{\text{SBM/TC}})}{P(\mathcal{H}_{\text{SBM}})},$
(24)

where $P(\mathcal{H}_{\text{SBM/TC}})$ and $P(\mathcal{H}_{\text{SBM}})$ are
the prior probabilities for either model. In case these are the same, we have

$\Lambda=\mathrm{e}^{-(\Sigma_{\text{SBM/TC}}-\Sigma_{\text{SBM}})},$ (25)

where $\Sigma_{\text{SBM/TC}}$ and $\Sigma_{\text{SBM}}$ are the description
lengths of both hypotheses, given by

$\displaystyle\Sigma_{\text{SBM/TC}}$ $\displaystyle=-\ln
P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}^{(2)}),$ (26)
$\displaystyle\Sigma_{\text{SBM}}$ $\displaystyle=-\ln
P(\bm{G},\bm{b}^{(1)}).$ (27)

The description length Grünwald (2007) measures the amount of information
necessary to encode both the data and the model parameters, and hence accounts
both for the quality of fit and the model complexity. The above means that the
model that is most likely _a posteriori_ is the one that _most compresses_ the
data under its parametrization, and thus the criterion amounts to an
implementation of Occam’s razor, since it points to the best balance between
model complexity and fitness.

Before we employ the above criterion to select between both models considered,
it is important to emphasize that the pure SBM is “nested” inside the SBM/TC,
since the former amounts to the special case of the latter when there are zero
triadic closure edges. In particular, if we use the more general
parametrization described in Appendix B, in the situation with zero triadic
edges, i.e. all $\\{\bm{g}^{(l)}\\}$ are empty graphs $\bm{g}_{\text{empty}}$
and $\bm{A}=\bm{G}$, we have

$P(\bm{G},\\{\bm{g}^{(l)}=\bm{g}_{\text{empty}}\\},\bm{A}=\bm{G},\bm{b})\geq\frac{P(\bm{G},\bm{b})}{N+1}.$
(28)

Therefore, in general, we must have

$\underset{\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}}{\max}\;\ln
P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A},\bm{b})\geq\\\ \underset{\bm{b}}{\max}\;\ln
P(\bm{G},\bm{b})+\ln(N+1).$ (29)

Since the last logarithm term becomes negligible for large networks, typically
the use of the SBM/TC can only reduce the description length of the data.
Therefore, in situations where there is no evidence for triadic closure, both
models should yield approximately the same description length value.

In Fig. 3 we show the description lengths for both models for the particular
example discussed previously, where we can see that the SBM/TC provides a
substantially better compression of the data, therefore yielding a more
parsimonious and hence more probable account of the how the data was generated
— which happens also to be the true one in this controlled setting.

Inference using SBM
---
\begin{overpic}[width=108.405pt]{pp-overlap-modelsbm-N10000-B10-ak5.pdf} \put(0.0,0.0){(a)} \end{overpic} | \begin{overpic}[width=108.405pt]{pp-Be-modelsbm-N10000-B10-ak5.pdf} \put(0.0,0.0){(b)} \end{overpic}
Inference using SBM/TC
\begin{overpic}[width=108.405pt]{pp-overlap-modeltriadic_sbm-N10000-B10-ak5.pdf} \put(0.0,0.0){(c)} \end{overpic} | \begin{overpic}[width=108.405pt]{pp-Be-modeltriadic_sbm-N10000-B10-ak5.pdf} \put(0.0,0.0){(d)} \end{overpic}
Figure 4: Recovery of community structure for artificial networks generated
from the PP model with added triadic closure, as described in the text, for
networks with $N=10^{4}$ nodes, average degree ${\left<k\right>}=5$, $B=10$
planted groups, and uniform triadic closure probability $p_{u}=p$ shown in the
legend. Figures (a) and (b) correspond to inferences done using the SBM, and
(c) and (d) with the SBM/TC model. All results where averaged over 10 network
realizations. The vertical dashed line marks the detectability transition
value $c^{*}_{+}$, described in the text.

We proceed with a more systematic analysis of how triadic closure can
interfere in community detection with artificial networks generated by the
SBM, more specifically the special case known as the planted partition model
(PP), where the $B$ groups have equal size, and the number of edges between
groups is given by

$e_{rs}=2E\left[\frac{c}{B}\delta_{rs}+\frac{1-c}{B(B-1)}(1-\delta_{rs})\right],$
(30)

where $c\in[0,1]$ determines the affinity between the (dis)assortative groups.
For this model, we know that there are critical values

$c^{*}_{\pm}=\frac{1}{B}\pm\frac{B-1}{B\sqrt{k}},$ (31)

such that if $c\in[c^{*}_{-},c^{*}_{+}]$ then no algorithm can infer a
partition that is correlated to the true one from a single network
realization, as it becomes infinitely large $N\to\infty$ Decelle  _et al._
(2011). Starting from a network generated with the PP model, we include
triadic closure edges via the global probability $p_{u}=p$ for every node in
the network. Based on the resulting network, we attempt to recover the
original communities, using the SBM and the SBM/TC model. A result of this
analysis is shown in Fig. 4, where we compute the maximum overlap Peixoto
(2020c) $q\in[0,1]$ between the inferred $\hat{\bm{b}}$ and true partition
$\bm{b}$, defined as

$q=\underset{\mu}{\max}\;\frac{1}{N}\sum_{i}\delta_{\mu(\hat{b}_{i}),b_{i}},$
(32)

where $\mu(r)$ is a bijection between the group labels in $\hat{\bm{b}}$ and
$\bm{b}$, as well as the effective number of inferred groups
$B_{e}=\mathrm{e}^{S}$, where $S$ is the group label entropy

$S=-\sum_{r}\frac{n_{r}}{N}\ln\frac{n_{r}}{N}.$ (33)

As can be seen in Fig. 4a, the presence of triadic closure edges can have a
severe negative effect on the recovery of the original partitions when using
the SBM. In Fig. 4b we see that the number of groups uncovered can be orders
of magnitude larger than the original partition, specially when the latter is
not even detectable. This shows that the apparent communities that arise out
of the formation of triangles substantially overshadow the underlying true
community structure. The situation changes considerably when we use the SBM/TC
instead, as shown Fig. 4c. In this case, the presence of triadic closure has
no noticeable effect on the detectability of the true community structure, and
we obtain a recovery performance indistinguishable from the SBM in the case
with no additional edges. As seen in Fig. 4c the same is true for the number
of groups inferred. These results seem to point to a robust capacity of the
SBM/TC model to reliably distinguish between actual community structure, and
the density fluctuations with result from triadic closures.

##  IV Empirical networks

|
---|---
(a) SBM, $\Sigma_{\text{SBM}}=1145.6$ nats |  (b) SBM/TC, $\Sigma_{\text{SBM/TC}}=935.1$ nats
Figure 5: Network of cooperation between students Fire  _et al._ (2012). (a) Fit of the SBM, yielding $B=9$ communities. (b) Fit of the SBM/TC, uncovering a single community, and triadic closure edges shown in red. The thickness of the edges correspond to the marginal probabilities $\pi_{ij}$ and $1-\pi_{ij}$ for the seminal and closure edges, respectively. \begin{overpic}[width=143.09538pt]{add_health_comm26-marginal-sbm-modesbm.pdf} \put(95.0,55.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$\bm{\swarrow}$} \end{overpic} |  \begin{overpic}[width=143.09538pt]{add_health_comm26-marginal-triadic_sbm-modesbm.pdf} \put(0.0,0.0){\includegraphics[width=143.09538pt]{add_health_comm26-marginal-triadic_sbm-modesbm-grade-lines.pdf}} \end{overpic} |
---|---|---
|  Seminal edges |  Triadic closure edges
(a) SBM ($\Sigma_{\text{SBM}}=8757.0$ nats) | (b) SBM/TC ($\Sigma_{\text{SBM/TC}}=8456.3$ nats)
Figure 6: Network of friendships between high school students — Adolescent health (comm26) Moody (2001b). (a) Fit of the SBM, yielding $B=26$ communities. (b) Fit of the SBM/TC, uncovering $B=9$ communities, with seminal (black) and triadic closure (red) edges shown separately in the left and right figures. The thickness of the edges correspond to the marginal probabilities $\pi_{ij}$ and $1-\pi_{ij}$ for the seminal and closure edges, respectively. The red dashed lines delineate the known divisions into grades, as numbered. |
---|---
(a) SBM, $\Sigma_{\text{SBM}}=3816.3$ nats | (b) SBM/TC, $\Sigma_{\text{SBM/TC}}=3009.9$ nats
Figure 7: Network of collaborations between network scientists Newman (2006). (a) Fit of the SBM, yielding $B=27$ communities. (b) Fit of the SBM/TC, uncovering only $B=3$ groups, and triadic closure edges shown in red. The thickness of the edges correspond to the marginal probabilities $\pi_{ij}$ and $1-\pi_{ij}$ for the seminal and closure edges, respectively. |
---|---
(a) Cooperation between students |  (b) Adolescent health (comm26)
|
(c) Scientific collaborations in Network Science |  (d) NCAA college football 2000
Figure 8: Posterior predictive distributions of the clustering coefficient, as
described in the text, for the SBM and SBM/TC as indicated in the legend, for
different datasets. The vertical line shows the empirical value $C(\bm{G})$.
Figure 9: Network of games between American college football teams (NCAA
college football 2000) Girvan and Newman (2002). The node colors show the fit
of the SBM and SBM/TC, both yielding the same $B=11$ communities. The SBM
yields a description length of $\Sigma_{\text{SBM}}=1761.1$ nats and the
SBM/TC, $\Sigma_{\text{SBM/TC}}=1767.6$ nats. Figure 10: Values of the z-score
for the posterior predictive distributions of the clustering coefficient, as
described in the text, for the SBM and SBM/TC as indicated in the legend, for
different datasets. The solid horizontal lines mark the values $-2$ and $2$.
Figure 11: Values of the clustering coefficient (Eq. 34) computed for the
original network, $C(\bm{G})$, and for the inferred seminal network,
$C_{S}(\bm{G})$, averaged over the posterior distribution according to Eq. 37,
as shown in the legend, for different datasets.  Figure 12: Values of
effective number of inferred groups, as given by Eq. 33, for the SBM and
SBM/TC as indicated in the legend, for different datasets.

We investigate the use our method with a variety of empirical networks. We
begin with a network of cooperation among students while doing their homework
for a course at Ben-Gurion University Fire  _et al._ (2012). In Fig. 5a we
show the network and a fit of the DC-SBM, which finds 9 assortative
communities. Based on this result — and knowing that the partitions found by
inferring the SBM as we do here point to statistically significant results
that cannot be attributed to mere random fluctuations Peixoto (2019) — we
would be tempted to posit that these divisions are uncovering latent social
parameters that could explain the observed cooperation between these groups of
of students. However, if we employ instead the SBM/TC, we obtain the result
shown in Fig. 5b, which uncovers instead only a single group, and an abundance
of triadic closure edges. This is not unlike the artificial example considered
in Fig. 3, and points to a very different interpretation, namely there is no
measurable _a priori_ predisposition for students to work with each other in
groups, and the resulting network stems instead from students choosing to work
together if they already share a mutual partner. Indeed if we inspect the
description lengths obtained with each model, we immediately recognize the
SBM/TC as the most plausible explanation, and therefore we deem the community
structure found by the SBM as an unlikely one by comparison.

We move now to another social network, but this time of friendships between
high school students Moody (2001b). We show the results of our analysis in
Fig. 6. Using the SBM we find $B=26$ groups, shown in Fig. 6a, which at first
seems like a reasonable explanation for this network. But instead, with the
SBM/TC we find only $B=9$ groups and a substantial amount of triadic closure
edges, as seen in Fig. 6b. Differently from the previous example, the SBM/TC
still finds enough evidence for a substantial amount of community structure,
although with fewer groups than the pure SBM. The groups found with the SBM/TC
have a strong correlation with the student grades, as shown in Fig. 6b, except
for the 11th and 12th grades, which seem to intermingle more, and for which
the model finds evidence of more detailed internal social structures. This
indicates that most of the subdivisions of the grades found by the pure SBM
are in fact better explained by triadic closure edges, and the _a priori_
friendship preference within these grades are far more homogeneous than the
SBM fit would lead us to conclude. One particularly striking feature of this
analysis is that it imputes some seemingly clear communities entirely to
triadic closure. A good example is the group highlighted with an arrow in Fig.
6a, formed by students in the 8th grade. According to the SBM/TC, this group
has arisen due to the formation of triangles between an initially poorly
connected subset of students, formed by all friends of a single student,
rather than an initial affinity between them. The SBM/TC explanation is again
more plausible, due to its smaller description length.

We move now to an additional example, this time of collaborations between
researchers in network science Newman (2006), shown in Fig. 7. For this
network, the SBM finds $B=27$ communities. The interpretation here is the same
as previous analyses of the same network, namely that these communities are
groups that tend to work together, with the occasional collaboration across
groups. On the other hand, when we employ the SBM/TC, the difference this time
is quite striking. Most of the community structure found with the pure SBM
vanishes and is replaced by a substrate network with a substantial “core-
periphery” mixing pattern formed of two main groups, where the “core” (blue
nodes) is composed of perceived initiators of the collaborations with the
“periphery” (yellow nodes), which end up being connected in the final network
simply by virtue of the all-to-all nature of multi-way collaborations,
captured here by triadic closure edges. The core-periphery pattern is not
perfect, as we observe seminal edges between nodes of every type, but most
commonly these exist between core and periphery nodes, and the core nodes
themselves, who therefore seem to have a predisposition to wider
collaborations. The difference between the description lengths of both models
is substantial, indicating that the SBM/TC interpretation is indeed far more
plausible.

Lastly, we consider the network of American football games between colleges
during the fall of 2000 Girvan and Newman (2002), shown in Fig. 9. For this
network we observe an interesting result, namely the SBM and SBM/TC yield the
exact same inference, which means that SBM/TC gives a very low probability of
triadic closure edges. Although we might expect this to occur for a network
that has very few or no triangles, and therefore substantial evidence against
triadic closure, this is not the case for the particular network in question,
which has in fact an abundance of triangles, in addition to clear assortative
communities. The reason for this is that, in this particular case, the SBM is
fully capable of accounting for the triangles observed, which therefore can be
characterized being a “side-effect” of the homophily between nodes of the same
group, instead of an excess that needs additional explanation. We will revisit
this particular case in the following, from a different angle.

One natural criticism of the SBM as a useful hypothesis for real networks,
however stylized as it clearly is, is that it assumes conditional independence
for the placement of every edge. One consequence of this is that the
probability of observing a spontaneous triadic closure edge will scale with
$O(B/N)$, for a network with $N$ nodes and $B$ groups, assuming the group
affinities are uniform for all groups. Therefore if $B\ll N$, we should not
expect any abundance of triangles, which is at odds with what we observe in
many empirical data. One problem with this logic is that we do not know _a
priori_ the precise relationship between $B$ and $N$ for finite empirical
networks, and therefore we cannot rule out the SBM hypothesis based simply on
an observed abundance of triangles. Auspiciously, with the SBM/TC at hand, we
are the perfect position to evaluate the SBM in that regard, and understand
how many of the observed triangles can be attributed to an incidental link
placement due to community structure, or if they are instead better explained
by explicit triadic closure edges. A common way of quantifying the amount of
triangles in a network $\bm{G}$ is via its clustering coefficient
$C(\bm{G})\in[0,1]$, which determines the fraction of triads in the network
which are closed in a triangle, and is given by

$C(\bm{G})=\frac{\sum_{ijk}G_{ij}G_{jk}G_{ki}}{k_{i}(k_{i}-1)}.$ (34)

A meaningful way to evaluate whether a given model $P(\bm{G}|\bm{\theta})$
with parameters $\bm{\theta}$ can capture what is seen in the data is to
compute the posterior predictive distribution,

$P(C|\bm{G})=\sum_{\bm{G}^{\prime}}\delta(C-C(\bm{G}^{\prime}))\sum_{\bm{\theta}}P(\bm{G}^{\prime}|\bm{\theta})P(\bm{\theta}|\bm{G}).$
(35)

This involves sampling parameters $\bm{\theta}$ from the posterior
$P(\bm{\theta}|\bm{G})$, generating new networks $\bm{G}^{\prime}$ from the
model $P(\bm{G}^{\prime}|\bm{\theta})$, and obtaining the resulting population
of $C(\bm{G}^{\prime})$ values, which can then be compared to the observed
value $C(\bm{G})$, and in this way we can determine if the model used is
capable of capturing this aspect of the data. In Fig. 8 we show the results of
this comparison for the SBM and SBM/TC (in Appendix D we give more details
about how $\bm{\theta}$ should be chosen in each case) using three datasets.
For three of the four networks we observe what one might expect: although the
SBM is capable of accounting for a substantial amount of triangles (far more
than one would expect by naively assuming $B\ll N$), it falls short of
explaining what is actually seen in the data. The SBM/TC, on the other hand,
accounts for a realm of possibilities that comfortably includes what is
observed in the data, with a sufficiently high probability. For the remaining
network in Fig. 8c, NCAA college football 2000, as before, we observe a
different picture. Namely, both models produce predictive posterior
distributions that are essentially identical, and fully compatible with what
is seen in the data. Therefore we can say with a fair amount of confidence
that the fairly high clustering coefficient observed for this network can in
principle be attributed to community structure alone, rather than triadic
closure, contradicting the intuition obtained from the asymptotic case where
$B\ll N$, which is not applicable to this network.

We extend the previous analysis to a larger set of empirical networks, as
shown in Fig. 10, by summarizing the compatibility of the posterior predictive
distribution via the z-score,

$z=\frac{C(\bm{G})-{\left<C\right>}}{\sigma_{C}},$ (36)

where ${\left<C\right>}$ and $\sigma_{C}$ are the mean and standard deviation
of the posterior predictive distribution. As we can see, there are a number of
networks for which the z-score values lie in the plausible interval $[-2,2]$
for both models, but there is a much larger fraction of the data for which the
values for the SBM point to a decisive incompatibility, whereas the SBM/TC
yields credible values more systematically.

We can further exploit the decomposition that the SBM/TC provides by
quantifying precisely, for any given network, how much of the observed
clustering can be attributed to triadic closure directly, or to community
structure indirectly. We can do so by computing the mean clustering
coefficient of the substrate seminal network from the posterior distribution,

$C_{S}(\bm{G})=\sum_{\bm{A},\bm{g},\bm{b}}C(\bm{A})P(\bm{A},\bm{g},\bm{b}|\bm{G}).$
(37)

We can then compare this value with the coefficient for the observed network
$C(\bm{G})$, as we show in Fig. 11. We identify a variety of scenarios,
including situations where the seminal network (and hence the community
structure) accounts for the majority of the observed clustering, but most
commonly we observe that a substantial fraction can be attributed to more
direct triadic closure. Nevertheless, in many cases the values of
$C_{S}(\bm{G})$ do not drop to negligible values, showing that the presence of
triangles cannot be wholly attributed to either mechanism in these cases.
Indeed, this variability seems to indicate that mere presence of a high or low
density of triangles, as captured by the clustering coefficient, cannot be
used by itself to evaluate whether triadic closure or community structure is
the leading underlying mechanism of network formation.

Another aspect of the suitability of triadic closure as a more plausible
network model is that it tends to come together with a less pronounced
inferred community structure, since part of the density heterogeneity found is
attributed to the former mechanism, rather than the latter. In Fig. 12 we
characterize this difference by the effective number of groups found with both
models. We see that the discrepancy between them is once again quite varied,
where in some cases it can be quite small, indicating that triadic closure
plays a minor role, while in other cases it can be quite extreme, indicating
the dominant role that triadic role has in the respective networks.

Overall, what we seem to extract from these empirical networks is that, in the
majority of cases (though not all), the observed structure seems to be better
explained by a heterogeneous combination of underlying mixing patterns with a
further distortion by an additional tendency of forming triangles. The precise
balance between these two components vary considerably in general, and needs
to be assessed for each individual network.

##  V Edge prediction

Student cooperation
---
Scientific collaborations in Network Science
Adolescent health (comm26)
NCAA college football 2000
Figure 13: Distributions of Precision and Recall values, according to the SBM
and SBM/TC model, for four empirical networks, and a fraction $f=0.05$ of
omitted edges and corresponding number of omitted non-edges. The results were
obtained for $200$ different realizations of missing edges and non-edges.

As with every kind of empirical assessment, network data is subject to
measurement errors or omissions. A common use of network models is to predict
such erroneous and missing information from what is more precisely known
Clauset  _et al._ (2008); Guimerà and Sales-Pardo (2009). The SBM has been
successfully used as such a model Guimerà and Sales-Pardo (2009); Peixoto
(2018), since the latent group assignments and the affinities between them can
be learned from partial network information, which in turn can be used to
infer what has been distorted or left unobserved. Another common approach to
edge prediction consists of attributing a higher probability to a potential
edge if it happens to form a triangle Adamic and Adar (2003). As we have been
discussing in this work, these two properties — group affinity and triadic
closure — point to related but distinct processes of edge formation, and
approaches of edge prediction that rely exclusively on either one will be
maximally efficient only if it happens to be the dominant underlying
mechanism, which, as we have seen in the last section, is typically not the
case. However, with the SBM/TC model we have introduced, it should be possible
to accommodate both mechanisms at the same time, and in this way improve edge
prediction is more realistic settings. In the following, we show how this can
be done, and demonstrate it with a few examples.

The scenario we consider is the general one presented in Ref. Peixoto (2018),
where we make $n_{ij}$ measurements of node pair $(i,j)$ and record the number
of times $x_{ij}$ than an edge has been observed. Based on this data, we infer
the underlying network $\bm{G}$ according to the posterior distribution

$P(\bm{G}|\bm{n},\bm{x})=\frac{P(\bm{x}|\bm{G},\bm{n})P(\bm{G})}{P(\bm{x}|\bm{n})}.$
(38)

The measurement model corresponds to a situation where the probabilities of
observing missing and spurious edges are unknown, which amounts to marginal
probability Peixoto (2018)

$P(\bm{x}|\bm{G},\bm{n})={\mathcal{E}\choose\mathcal{T}}^{-1}\frac{1}{\mathcal{E}+1}{\mathcal{M}-\mathcal{E}\choose\mathcal{X}-\mathcal{T}}^{-1}\frac{1}{\mathcal{M}-\mathcal{E}+1}.$
(39)

where we have

$\displaystyle\mathcal{M}$ $\displaystyle=\sum_{i<j}n_{ij},$
$\displaystyle\mathcal{X}$ $\displaystyle=\sum_{i<j}x_{ij},$ (40)
$\displaystyle\mathcal{E}$ $\displaystyle=\sum_{i<j}n_{ij}G_{ij},$
$\displaystyle\mathcal{T}$ $\displaystyle=\sum_{i<j}x_{ij}G_{ij}.$ (41)

The network model comes into play via the prior $P(\bm{G})$. For the SBM/TC
model this is

$P(\bm{G})=\sum_{\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}}P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}).$
(42)

Once more, we avoid an intractable computation, by sampling instead from a
joint posterior with the model parameters, i.e.

$P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{n},\bm{x})=\frac{P(\bm{x}|\bm{G},\bm{n})P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A},\bm{b})}{P(\bm{x}|\bm{n})}$
(43)

so that the desired posterior distribution can be obtained by marginalization

$P(\bm{G}|\bm{n},\bm{x})=\sum_{\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}}P(\bm{G},\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{n},\bm{x}).$
(44)

In order to perform our comparison, we consider the following particular setup
for the data $(\bm{n},\bm{x})$. Given a true network $\bm{G}$ we select a
random subset $\bm{P}_{t}$ of the edges (“true positives”), and an equal-sized
random subset $\bm{N}_{t}$ of “non-edges” (“true negatives”), i.e., node pairs
$(i,j)$ for which $G_{ij}=0$, such that $|\bm{P}_{t}|=|\bm{N}_{t}|=fE$, where
$f\in[0,1]$ is a free parameter and $E$ is the total number of edges. We then
set $n_{ij}\to\infty$ for all node pairs neither in $\bm{P}_{t}$ nor in
$\bm{N}_{t}$, with $x_{ij}=n_{ij}$ if $G_{ij}=1$ and $x_{ij}=0$ otherwise —
these are parts of the network about which we are perfectly certain. For the
node pairs in $\bm{P}_{t}$ and $\bm{N}_{t}$ we set $n_{ij}=x_{ij}=0$, meaning
we lack any data about them. We then compute the posterior marginal
probability

$p_{ij}=\sum_{\bm{G}}G_{ij}P(\bm{G}|\bm{n},\bm{x}),$ (45)

and we use it to evaluate the quality of the reconstruction. We do so by
computing the Precision and Recall, defined as

Precision
$\displaystyle=\frac{\sum_{(i,j)\in\bm{P}_{t}}p_{ij}}{\sum_{(i,j)\in\bm{P}_{t}\cup\bm{N}_{t}}p_{ij}}$
(46) Recall
$\displaystyle=\frac{\sum_{(i,j)\in\bm{P}_{t}}p_{ij}}{|\bm{P}_{t}|},$ (47)

which measures the fraction of correctly predicted edges, relative to the
total number of edges predicted, or the total number of true edges,
respectively.

In Fig. 13 we show the results of the above analysis for some of the networks
studied previously, using both the SBM/TC model and the pure SBM. For most of
them, the SBM/TC model yields a superior predictive performance, sometimes
substantially. This shows that while community detection via the SBM can to
some extent detect the patterns induced by triadic closure, the more explicit
SBM/TC model does a better job at this, corroborating the model selection
arguments we have used previously. For networks of games between American
football college teams, the situation is once again different, and we observe
indistinguishable results between the SBM and SBM/TC. For this network, as the
previous analysis has established, triadic closure seems to play a
insignificant role, despite the relative abundance of triangles. As a
consequence, in this case the SBM/TC model offers no advantage in edge
prediction, but importantly, it does not degrade it either.

In a recent work, Ghasemian et al Ghasemian  _et al._ (2020) have performed a
large-scale analysis of over two hundred edge prediction methods on over five
hundred networks belonging to various domains. Although the overall conclusion
of that work was that no single method dominates on every data, the predictive
performance of the different methods were far from uniform, with the method
above based on the SBM providing the single best performance
overall.222Ghasemian et al Ghasemian  _et al._ (2020) considered only a
simplified version of the method described, where only the best-scoring
partition was used, instead of an average over the posterior distribution.
Furthermore, they have used only the version of the SBM with noninformative
priors, which is known to underfit, as opposed to the nested SBM Peixoto
(2014a, 2017) which removes this problem. Accounting for both of these issues
have been shown before to improve edge prediction systematically Vallès-Català
_et al._ (2018), and could potentially have pushed the result of the analysis
in Ref. Ghasemian  _et al._ (2020) even more in favor of the SBM approach.
Interestingly, the situations where the SBM approach yielded inferior
performance were precisely for social networks, for which some predictors
based on triadic closure performed better. Although our results above fall
short of a thorough and systematic analysis of the wide domains of network
data, since we consider only a handful of networks, they nevertheless seem to
give good indication that combining group affinity with triadic closure could
potentially eliminate this shortcoming for this particular class of network
data.

##  VI Conclusion

We have presented a generative model and corresponding inference scheme that
is capable of differentiating community structure from triadic closure in
empirical networks. We have shown that although these features are generically
conflated in traditional network analysis, our method can pick them apart,
allowing us tell us whether an observed abundance of triangles is a byproduct
of an underlying homophily between nodes, or whether they arise out of a local
property of transitivity. Likewise, we have also shown how our method can
evade the detection of spurious communities, which are not due to homophily,
but arise instead simply out of a random formation of triangles.

Our approach shows how local and global (or mesoscale) generative processes
can be combined into a single model. Since it contains a mixture of both
mechanisms, our method is able to decompose them for a given observed network
according to their inferred contributions. By employing our method on several
empirical networks, we were able to demonstrate a wide variety of scenarios,
containing everything from a large number of triangles caused predominantly by
triadic closures, by a mixture of community structure and triadic closures,
and by community structure alone. These findings seem to indicate that local
and global network properties tend to mix in nontrivial ways, and we should
refrain from automatically concluding that an observed local property (e.g.
large number of triangles) cannot have a global cause (e.g. group homophily),
and likewise an observed global property (e.g. community structure) cannot
have a purely local cause (e.g. triadic closure).

Several authors had shown before that triadic closure can induce the formation
of community structure in networks Foster  _et al._ (2011, 2010); Lopez and
Coolen (2020); Bianconi  _et al._ (2014); Wharrie  _et al._ (2019); Asikainen
_et al._ (2020). This introduces a problem of interpretation for community
detection methods that do not account for this, which, to the best of our
knowledge, happens to be the vast majority of them. This is true also for
inference methods based on the SBM, which, although it is not susceptible to
finding spurious communities formed by a fully random placement of edges
Guimerà  _et al._ (2004) (unlike non-inferential methods, which tend to
overfit Ghasemian  _et al._ (2019)), they cannot evade those arising from
triadic closure Wharrie  _et al._ (2019). Our approach provides a solution to
this interpretation problem, allowing us to reliably rule out triadic closure
when identifying communities in networks.

We have also shown how incorporating triadic closure together with community
structure can improve edge prediction, without degrading the performance in
situations where it is not present. This further demonstrates the usefulness
of approaches that model networks in multiple scales, and points to a general
way of systematically improving our understanding of network data.

## References

  * McPherson and Smith-Lovin (1987) J. Miller McPherson and Lynn Smith-Lovin, “Homophily in Voluntary Organizations: Status Distance and the Composition of Face-to-Face Groups,” American Sociological Review 52, 370–379 (1987).
  * Shrum  _et al._ (1988) Wesley Shrum, Neil H. Cheek, and Saundra MacD. Hunter, “Friendship in School: Gender and Racial Homophily,” Sociology of Education 61, 227–239 (1988).
  * Moody (2001a) James Moody, “Race, School Integration, and Friendship Segregation in America,” American Journal of Sociology 107, 679–716 (2001a).
  * McPherson  _et al._ (2001) Miller McPherson, Lynn Smith-Lovin, and James M Cook, “Birds of a Feather: Homophily in Social Networks,” Annual Review of Sociology 27, 415–444 (2001).
  * Fortunato (2010) Santo Fortunato, “Community detection in graphs,” Physics Reports 486, 75–174 (2010).
  * Rapoport (1953) Anatol Rapoport, “Spread of information through a population with socio-structural bias: I. Assumption of transitivity,” The bulletin of mathematical biophysics 15, 523–533 (1953).
  * Holland and Leinhardt (1971) Paul W. Holland and Samuel Leinhardt, “Transitivity in Structural Models of Small Groups:,” Comparative Group Studies 2, 107–124 (1971).
  * Holland and Leinhardt (1975) P. W. Holland and S. Leinhardt, “Local structure in social networks." In D. Heise (ed.), Sociological Methodology. San Francisco: Jossey-Bass,” (1975).
  * Kossinets and Watts (2009) Gueorgi Kossinets and Duncan J. Watts, “Origins of Homophily in an Evolving Social Network,” American Journal of Sociology 115, 405–450 (2009).
  * Granovetter (1973) Mark S. Granovetter, “The Strength of Weak Ties,” American Journal of Sociology 78, 1360–1380 (1973).
  * Foster  _et al._ (2011) David V. Foster, Jacob G. Foster, Peter Grassberger, and Maya Paczuski, “Clustering drives assortativity and community structure in ensembles of networks,” Physical Review E 84, 066117 (2011).
  * Foster  _et al._ (2010) David Foster, Jacob Foster, Maya Paczuski, and Peter Grassberger, “Communities, clustering phase transitions, and hysteresis: Pitfalls in constructing network ensembles,” Physical Review E 81, 046115 (2010).
  * Lopez and Coolen (2020) Fabian Aguirre Lopez and Anthony CC Coolen, “Transitions in loopy random graphs with fixed degrees and arbitrary degree distributions,” arXiv:2008.11002 [cond-mat] (2020).
  * Bianconi  _et al._ (2014) Ginestra Bianconi, Richard K. Darst, Jacopo Iacovacci, and Santo Fortunato, “Triadic closure as a basic generating mechanism of communities in complex networks,” Physical Review E 90, 042806 (2014).
  * Wharrie  _et al._ (2019) Sophie Wharrie, Lamiae Azizi, and Eduardo G. Altmann, “Micro-, meso-, macroscales: The effect of triangles on communities in networks,” Physical Review E 100, 022315 (2019).
  * Asikainen  _et al._ (2020) Aili Asikainen, Gerardo Iñiguez, Javier Ureña-Carrión, Kimmo Kaski, and Mikko Kivelä, “Cumulative effects of triadic closure and homophily in social networks,” Science Advances 6, eaax7310 (2020).
  * Battiston  _et al._ (2020) Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri, “Networks beyond pairwise interactions: Structure and dynamics,” Physics Reports Networks beyond pairwise interactions: Structure and dynamics, 874, 1–92 (2020).
  * Benson  _et al._ (2018) Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg, “Simplicial closure and higher-order link prediction,” Proceedings of the National Academy of Sciences 115, E11221–E11230 (2018).
  * Holland  _et al._ (1983) Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt, “Stochastic blockmodels: First steps,” Social Networks 5, 109–137 (1983).
  * Peixoto (2019) Tiago P. Peixoto, “Bayesian Stochastic Blockmodeling,” in  _Advances in Network Clustering and Blockmodeling_ (John Wiley & Sons, Ltd, 2019) pp. 289–332.
  * Karrer and Newman (2011) Brian Karrer and M. E. J. Newman, “Stochastic blockmodels and community structure in networks,” Physical Review E 83, 016107 (2011).
  * Peixoto (2017) Tiago P. Peixoto, “Nonparametric Bayesian inference of the microcanonical stochastic block model,” Physical Review E 95, 012317 (2017).
  * Peixoto (2020a) Tiago P. Peixoto, “Latent Poisson models for networks with heterogeneous density,” Physical Review E 102, 012309 (2020a).
  * Metropolis  _et al._ (1953) Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller, “Equation of State Calculations by Fast Computing Machines,” The Journal of Chemical Physics 21, 1087 (1953).
  * Hastings (1970) W. K. Hastings, “Monte Carlo sampling methods using Markov chains and their applications,” Biometrika 57, 97 –109 (1970).
  * Peixoto (2020b) Tiago P. Peixoto, “Merge-split Markov chain Monte Carlo for community detection,” Physical Review E 102, 012305 (2020b).
  * Grünwald (2007) Peter D. Grünwald,  _The Minimum Description Length Principle_ (The MIT Press, 2007).
  * Decelle  _et al._ (2011) Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová, “Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications,” Physical Review E 84, 066106 (2011).
  * Peixoto (2020c) Tiago P. Peixoto, “Revealing consensus and dissensus between network partitions,” arXiv:2005.13977 [physics, stat] (2020c).
  * Fire  _et al._ (2012) Michael Fire, Gilad Katz, Yuval Elovici, Bracha Shapira, and Lior Rokach, “Predicting student exam’s scores by analyzing social network data,” in  _Active Media Technology_ (Springer Berlin Heidelberg, 2012) pp. 584–595.
  * Moody (2001b) James Moody, “Peer influence groups: identifying dense clusters in large networks,” Social Networks 23, 261–283 (2001b).
  * Newman (2006) M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Physical Review E 74 (2006), 10.1103/physreve.74.036104.
  * Girvan and Newman (2002) M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences 99, 7821–7826 (2002).
  * Clauset  _et al._ (2008) Aaron Clauset, Cristopher Moore, and M. E. J. Newman, “Hierarchical structure and the prediction of missing links in networks,” Nature 453, 98–101 (2008).
  * Guimerà and Sales-Pardo (2009) Roger Guimerà and Marta Sales-Pardo, “Missing and spurious interactions and the reconstruction of complex networks,” Proceedings of the National Academy of Sciences 106, 22073 –22078 (2009).
  * Peixoto (2018) Tiago P. Peixoto, “Reconstructing Networks with Unknown and Heterogeneous Errors,” Physical Review X 8, 041011 (2018).
  * Adamic and Adar (2003) Lada A Adamic and Eytan Adar, “Friends and neighbors on the Web,” Social Networks 25, 211–230 (2003).
  * Ghasemian  _et al._ (2020) Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M. Airoldi, and Aaron Clauset, “Stacking models for nearly optimal link prediction in complex networks,” Proceedings of the National Academy of Sciences 117, 23393–23400 (2020).
  * Peixoto (2014a) Tiago P. Peixoto, “Hierarchical Block Structures and High-Resolution Model Selection in Large Networks,” Physical Review X 4, 011047 (2014a).
  * Vallès-Català  _et al._ (2018) Toni Vallès-Català, Tiago P. Peixoto, Marta Sales-Pardo, and Roger Guimerà, “Consistencies and inconsistencies between model selection and link prediction in networks,” Physical Review E 97, 062316 (2018).
  * Guimerà  _et al._ (2004) Roger Guimerà, Marta Sales-Pardo, and Luís A. Nunes Amaral, “Modularity from fluctuations in random graphs and complex networks,” Physical Review E 70, 025101 (2004).
  * Ghasemian  _et al._ (2019) Amir Ghasemian, Homa Hosseinmardi, and Aaron Clauset, “Evaluating Overfit and Underfit in Models of Network Community Structure,” IEEE Transactions on Knowledge and Data Engineering , 1–1 (2019).
  * Peixoto (2014b) Tiago P. Peixoto, “The graph-tool python library,” figshare (2014b), 10.6084/m9.figshare.1164194, available at https://graph-tool.skewed.de.
  * Peixoto (2020d) T. P. Peixoto, “The Netzschleuder network catalogue and repository.”  (2020d), accessible at https://networks.skewed.de.
  * Clauset  _et al._ (2016) Aaron Clauset, Ellen Tucker, and Matthias Sainz, “The Colorado Index of Complex Networks,”  (2016), accessible at https://icon.colorado.edu.
  * Newman (2001) M. E. J. Newman, “The structure of scientific collaboration networks,” Proceedings of the National Academy of Sciences 98, 404–409 (2001).
  * Duch and Arenas (2005) Jordi Duch and Alex Arenas, “Community detection in complex networks using extremal optimization,” Physical Review E 72 (2005), 10.1103/physreve.72.027104.
  * 198 (1986) “The structure of the nervous system of the nematode caenorhabditis elegans,” Philosophical Transactions of the Royal Society of London. B, Biological Sciences 314, 1–340 (1986).
  * Watts and Strogatz (1998) Duncan J. Watts and Steven H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature 393, 440–442 (1998).
  * Collins  _et al._ (2007) Sean R. Collins, Patrick Kemmeren, Xue-Chu Zhao, Jack F. Greenblatt, Forrest Spencer, Frank C. P. Holstege, Jonathan S. Weissman, and Nevan J. Krogan, “Toward a comprehensive atlas of the physical interactome ofSaccharomyces cerevisiae,” Molecular & Cellular Proteomics 6, 439–450 (2007).
  * Kunegis (2013) Jérôme Kunegis, “KONECT,” in  _Proceedings of the 22nd International Conference on World Wide Web - WWW '13 Companion_ (ACM Press, 2013).
  * Lusseau  _et al._ (2003) David Lusseau, Karsten Schneider, Oliver J. Boisseau, Patti Haase, Elisabeth Slooten, and Steve M. Dawson, “The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations,” Behavioral Ecology and Sociobiology 54, 396–405 (2003).
  * McAuley and Leskovec (2012) Julian McAuley and Jure Leskovec, “Discovering social circles in ego networks,”  (2012), arXiv:1210.8182v3 [cs.SI] .
  * Maier and Brockmann (2017) Benjamin F. Maier and Dirk Brockmann, “Cover time for random walks on arbitrary complex networks,”  (2017), 10.1103/PhysRevE.96.042307 .
  * Fire  _et al._ (2013a) Michael Fire, Rami Puzis, and Yuval Elovici, “Organization mining using online social networks,”  (2013a), arXiv:1303.3741v2 [cs.SI] .
  * Martinez (1991) Neo D. Martinez, “Artifacts or attributes? effects of resolution on the little rock lake food web,” Ecological Monographs 61, 367–392 (1991).
  * Beveridge and Shan (2016) Andrew Beveridge and Jie Shan, “Network of thrones,” Math Horizons 23, 18–22 (2016).
  * Fire  _et al._ (2013b) Michael Fire, Lena Tenenboim-Chekina, Rami Puzis, Ofrit Lesser, Lior Rokach, and Yuval Elovici, “Computationally efficient link prediction in a variety of social networks,” ACM Transactions on Intelligent Systems and Technology 5, 1–25 (2013b).
  * Gleiser and Danon (2003) Pablo M. Gleiser and Leon Danon, “Community Structure In Jazz,” Advances in Complex Systems 06, 565–573 (2003).
  * Zachary (1977) Wayne W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of Anthropological Research 33, 452–473 (1977).
  * Knuth (1993) Donald Ervin Knuth,  _The Stanford GraphBase: a platform for combinatorial computing_ (AcM Press New York, 1993).
  * Larremore  _et al._ (2013) Daniel B. Larremore, Aaron Clauset, and Caroline O. Buckee, “A network approach to analyzing highly recombinant malaria parasite genes,” PLoS Computational Biology 9, e1003268 (2013).
  * Coleman  _et al._ (1957) James Coleman, Elihu Katz, and Herbert Menzel, “The diffusion of an innovation among physicians,” Sociometry 20, 253 (1957).
  * Domenico  _et al._ (2014) Manlio De Domenico, Andrea Lancichinetti, Alex Arenas, and Martin Rosvall, “Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems,”  (2014), 10.1103/PhysRevX.5.011027.
  * Pasternak and Ivask (1970) Boris Pasternak and Ivor Ivask, “Four unpublished letters,” Books Abroad 44, 196 (1970).
  * Mastrandrea  _et al._ (2015) Rossana Mastrandrea, Julie Fournet, and Alain Barrat, “Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys,” PLOS ONE 10, e0136497 (2015).
  * Krebs (2002) Valdis Krebs, “Uncloaking terrorist networks,” First Monday 7 (2002), 10.5210/fm.v7i4.941.
  * Hayes (2006) Brian Hayes, “Connecting the dots,” American Scientist 94, 400 (2006).
  * Guimerà  _et al._ (2003) R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas, “Self-similar community structure in a network of human interactions,” Physical Review E 68 (2003), 10.1103/physreve.68.065103.

##  Appendix A Latent multigraph SBM

The marginal likelihood of Eq. 1 is in fact obtained for a multigraph model
Peixoto (2017), where the adjacency entries can take any natural value,
$A_{ij}\in\mathbf{N}$. Although we could in principle ignore this discrepancy,
since this kind of model generates simple graphs as a special case, this comes
at the expense of a reduced expressiveness of the model Peixoto (2020a), since
this kind of multigraph model cannot describe the placement of single edges
with high probability, or account for the emergent degree-degree correlations
that must be present in simple graphs. Instead, here we take the approach
proposed in Peixoto (2018, 2020a), and consider a _latent_ multigraph
$\bm{A}^{\prime}$, with $\bm{A}^{\prime}_{ij}\in\mathbf{N}$, which is then
converted into a simple graph $\bm{A}(\bm{A}^{\prime})$ simply by ignoring the
edge multiplicities, i.e.

$A_{ij}=\begin{cases}1&\text{ if }A_{ij}^{\prime}>0,\\\ 0&\text{
otherwise.}\end{cases}$ (48)

The latent multigraph $\bm{A}^{\prime}$ is generated according to Eq. 1, which
means the simple graph $\bm{A}$ is generated according to

$P(\bm{A}|\bm{b})=\sum_{\bm{A}^{\prime}}\bm{1}_{\\{\bm{A}(\bm{A}^{\prime})=\bm{A}\\}}P(\bm{A}^{\prime}|\bm{b}).$
(49)

Instead of working with this marginal probability directly (which is
intractable), we infer the latent edge multiplicities as well, from a joint
posterior distribution

$P(\bm{g},\bm{A}^{\prime},\bm{b}|\bm{G})=\frac{P(\bm{G},\bm{g}|\bm{A}(\bm{A}^{\prime}))P(\bm{A}^{\prime}|\bm{b})P(\bm{b})}{P(\bm{G})},$
(50)

where the simple graph $\bm{A}(\bm{A}^{\prime})$ is used for the triadic
closure likelihood $P(\bm{G},\bm{g}|\bm{A})$. In this way, the inference
procedure is the same as the one described in the main text, with the only
modification that we need to infer the integer values of $\bm{A}^{\prime}$
rather than its binary values.

##  Appendix B Expected density of transitivity

As mentioned in the main text, the choice of priors used for Eq. 10 makes the
calculation very simple, but it implies that we expect the observed graphs to
always have a large fraction of triadic closures. An outcome of this is that
the probability of observing a final graph without any triadic closure, i.e.
$\sum_{uij}g^{\prime}_{ij}(u)=0$, is given by

$\displaystyle P(\bm{g}^{\prime}|\bm{A})$
$\displaystyle=\prod_{u}\left[1+\sum_{i<j}m_{ij}(u)\right]^{-1}$ (51)
$\displaystyle=O\left(\frac{1}{[{\left<k^{2}\right>}-{\left<k\right>}]^{N}}\right),$
(52)

which is exponentially suppressed for a large number of nodes $N$. Even though
we are interested in modelling networks which do posses some amount of triadic
closure, we should be _a priori_ more agnostic about the actual amount, as to
also accommodate situations where this property is not abundant. We can
address this by noting that the likelihood of Eq. 10 can be alternatively
interpreted as the one of a fully equivalent model given by

$P(\bm{g}|\bm{A})=\prod_{u}\sum_{E_{u}}P(\bm{g}(u)|\bm{A},E_{u})P(E_{u}|\bm{A}),$
(53)

where

$P(\bm{g}(u)|\bm{A},E_{u})=\frac{\bm{1}_{\\{E_{u}=\sum_{i<j}g_{ij}(u)\\}}}{{\sum_{i<j}m_{ij}(u)\choose
E_{u}}}$ (54)

is the probability of uniformly sampling an ego graph $\bm{g}(u)$ with exactly
$E_{u}=\sum_{i<j}g_{ij}(u)$ edges, and

$P(E_{u}|\bm{A})=\frac{1}{1+\sum_{i<j}m_{ij}(u)}$ (55)

is the probability of uniformly sampling the number of edges in $\bm{g}(u)$ in
the allowed range $[0,\sum_{i<j}m_{ij}(u)]$. This interpretation allows us to
do a small modification of our model that makes it more versatile, namely we
separate the nodes into two sets, according to an auxiliary binary variable
$t_{u}\in\\{0,1\\}$, such that if $t_{u}=0$ then the corresponding ego graph
has no edges, $P(E_{u}|\bm{A},t_{u}=0)=\delta_{0,E_{u}}$, otherwise it has a
nonzero number of edges, sampled uniformly as

$P(E_{u}|\bm{A},t_{u}=1)=\frac{1-\delta_{E_{u},0}}{\sum_{i<j}m_{ij}(u)}.$ (56)

The modified marginal distribution becomes then

$\displaystyle P(\bm{g}|\bm{A})$
$\displaystyle=\sum_{\bm{t}}\left[\prod_{u}\sum_{E_{u}}P(\bm{g}(u)|\bm{A},E_{u})P(E_{u}|\bm{A},\bm{t})\right]P(\bm{t}|\bm{A})$
(57)
$\displaystyle=\left\\{\prod_{u}\left[{\sum_{i<j}m_{ij}(u)\choose\sum_{i<j}g_{ij}(u)}\sum_{i<j}m_{ij}(u)\right]^{\delta_{0,\sum_{i<j}g_{ij}(u)}-1}\right\\}{\sum_{u}\Theta\left[\sum_{i<j}m_{ij}(u)\right]\choose\sum_{u}\Theta\left[\sum_{i<j}g_{ij}(u)\right]}^{-1}\times\frac{1}{1+\sum_{u}\Theta\left[\sum_{i<j}m_{ij}(u)\right]},$
(58)

where $\Theta[x]=\\{1\text{ if }x>0,\text{ else }0\\}$ is the Heaviside step
function, and we have used the prior

$P(\bm{t}|\bm{A})=\sum_{N_{t}}P(\bm{t}|\bm{A},N_{t})P(N_{t}|\bm{A}),$ (59)

with

$P(\bm{t}|\bm{A},N_{t})=\frac{\bm{1}_{\\{\sum_{u}t_{u}=N_{t}\\}}\prod_{u}\Theta\left[\sum_{i<j}m_{ij}(u)\right]^{t_{u}}}{{\sum_{u}\Theta\left[\sum_{i<j}m_{ij}(u)\right]\choose
N_{t}}},$ (60)

and

$P(N_{t}|\bm{A})=\frac{1}{1+\sum_{u}\Theta\left[\sum_{i<j}m_{ij}(u)\right]}.$
(61)

Although these equations take longer to write, they are not much more
difficult to use. As a result of this parametrization, if we consider again
the particular graph with no triadic closures, i.e.
$\sum_{uij}g_{ij}^{\prime}(u)=0$, it is generated with probability

$P(\bm{g}^{\prime}|\bm{A})=\frac{1}{1+\sum_{u}\Theta[\sum_{i<j}m_{ij}(u)]}=O\left(\frac{1}{N}\right),$
(62)

which is relatively large and no longer exponentially suppressed for large
$N$, meaning that our model can also accommodate the same kinds of networks
that are sampled from the pure SBM, without triadic closures. This does not
mean that the modified model generates _typical_ networks with substantially
smaller number of transitive edges, only that the variance with respect to
this property is larger, and the model is thus more indifferent about the
potential networks that are possible to be observed.

As mentioned in the main text, this modification makes the SBM fully nested
inside the SBM/TC, as we have

$\displaystyle P(\bm{G},\bm{g}^{\prime},\bm{A}=\bm{G}|\bm{b})$
$\displaystyle=\frac{P(\bm{G}|\bm{b})}{1+\sum_{u}\Theta\left[\sum_{i<j}m_{ij}(u)\right]}$
(63) $\displaystyle\geq\frac{P(\bm{G}|\bm{b})}{N+1},$ (64)

with $\bm{g}^{\prime}$ being empty ego graphs, and the last equality achieved
if $\sum_{i<j}m_{ij}(u)>0$ for every node $u$.

###  B.1 Iterated triadic closure

For the generalized model with iterated triadic closures, the marginal
likelihood is also analogous to Eq. 58,

$P(\bm{g}^{(l)}|\bm{A}^{(l-1)},\bm{g}^{(l-1)})=\\\
\left\\{\prod_{u}\left[{\sum_{i<j}m_{ij}^{(l)}(u)\choose\sum_{i<j}g_{ij}^{(l)}(u)}\sum_{i<j}m_{ij}^{(l)}(u)\right]^{\delta_{0,\sum_{i<j}g_{ij}^{(l)}(u)}-1}\right\\}{\sum_{u}\bm{1}_{\\{\sum_{i<j}m_{ij}^{(l)}(u)>0\\}}\choose\sum_{u}\bm{1}_{\\{\sum_{i<j}g^{(l)}_{ij}(u)>0\\}}}^{-1}\frac{1}{1+\sum_{u}\bm{1}_{\\{\sum_{i<j}m_{ij}^{(l)}(u)>0\\}}}.$
(65)

##  Appendix C MCMC moves

The MCMC algorithm described in the main text is implemented with the
following moves. The first kind is to attempt to move an edge $(i,j)$ in ego
graph $\bm{g}^{(l)}(u)$ at its current generation $l\in[0,L]$ to another ego
graph $\bm{g}^{(l^{\prime})}(v)$ for $v\neq u$ at generation $l^{\prime}\neq
l$. We do so by selecting first an edge $(i,j)$ in $\bm{G}$ as well as a
generation $l$, both uniformly at random, and an ego node $u$ that is relevant
to edge $(i,j)$ at generation $l$, also uniformly at random. The number of ego
graphs that are relevant for this edge is given by

$n_{ij}^{(l)}=\sum_{u}A^{(l-1)}_{ui}(1-A^{(l-1)}_{uj}),$ (66)

which is independent on the value of $g_{ij}^{(l^{\prime})}(u)$ for any
$l^{\prime}$. We then sample another generation $l^{\prime}\neq l$ and proceed
in the same way to sample a relevant ego node $v$. In either case, if $l=0$ is
selected, then the choice of an ego graph is not made, since we are selecting
simply an entry $(i,j)$ in $\bm{A}$ with probability one. The final
probability of selecting the move $(i,j,u,l)\to(i,j,v,l^{\prime})$, assuming
$l>0$ and $l^{\prime}>0$, is given by

$P(i,j,u,v,l,l^{\prime}|\\{\bm{g}^{(l)}\\},\bm{A})=\frac{1}{E_{G}n_{ij}^{(l)}n_{ij}^{(l^{\prime})}L(L+1)},$
(67)

where $E_{G}$ is the number of edges in $\bm{G}$. Given this selection we then
make the change $g_{ij}^{\prime(l)}(u)=g_{ij}^{(l)}-1$ and
$g_{ij}^{\prime(l^{\prime})}(u)=g_{ij}^{(l^{\prime})}+1$, and accept it with
probability

$\min\left(1,\frac{P(\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime},\bm{b}|\bm{G})P(i,j,u,v,l,l^{\prime}|\\{{\bm{g}}^{(l)}\\},\bm{A}^{\prime})}{P(\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{G})P(i,j,v,u,l^{\prime},l|\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A})}\right)\\\
=\min\left(1,\frac{P(\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime},\bm{b}|\bm{G})}{P(\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{G})}\right)$
(68)

which is independent on the actual move probabilities, since they remain the
same after and before the move. Note that invalid moves that result in
$\bm{g}^{(l)}_{ij}<0$ or $\bm{A}_{ij}<0$ are always rejected in this way.

In addition, we also make a second kind of move by selecting again an edge
$(i,j)$ in $\bm{G}$ as well as a generation $l$, both uniformly at random, and
an ego node $u$ that is relevant to edge $(i,j)$ at generation $l$, with the
same probability as before. We then make the move
${g^{\prime}}_{ij}^{(l)}=g_{ij}^{(l)}\pm 1$ with probability $1/2$, and accept
again according to

$\min\left(1,\frac{P(\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A},\bm{b}|\bm{G})}{P(\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{G})}\right).$
(69)

In case $l=0$ is selected, the move is different, due to the multigraph nature
of $\bm{A}$. We make instead the proposal $A_{ij}\to A_{ij}^{\prime}$
according to a geometric distribution with mean $A_{ij}+1$,

$P(A_{ij}^{\prime}|A_{ij})=\left(\frac{A_{ij}+1}{A_{ij}+2}\right)^{A_{ij}^{\prime}}\frac{1}{A_{ij}+2}.$
(70)

In this case, the acceptance probability changes to

$\min\left(1,\frac{P(\\{{\bm{g}}^{(l)}\\},\bm{A}^{\prime},\bm{b}|\bm{G})P(A_{ij}|A_{ij}^{\prime})}{P(\\{\bm{g}^{(l)}\\},\bm{A},\bm{b}|\bm{G})P(A_{ij}^{\prime}|A_{ij})}\right).$
(71)

Finally, we last kind of move involves a change in partition
$\bm{b}\to\bm{b}^{\prime}$ from the proposal $P(\bm{b}^{\prime}|\bm{b})$,
which is accepted with probability

$\min\left(1,\frac{P(\bm{A}|\bm{b}^{\prime})P(\bm{b}^{\prime})P(\bm{b}|\bm{b}^{\prime})}{P(\bm{A}|\bm{b})P(\bm{b})P(\bm{b}^{\prime}|\bm{b})}\right).$
(72)

For the latter we use the merge-split moves, combined with single-node moves,
described in Ref. Peixoto (2020b).

The moves above fulfill detailed balance, and when combined, they also
preserve ergodicity, since they allow every latent multigraph, decomposition
into ego graphs, and node partition to be sampled. Due to this, with
sufficiently many iterations the algorithm must eventually produce samples
from the desired posterior distribution.

###  C.1 Algorithmic complexity

We can break down the time complexity of the above algorithm as follows. At
any given time, we keep track of all relevant ego graphs for each edge $(i,j)$
in $\bm{G}$, those that have edge $(i,j)$ in them, as well as the number of
edges $E_{u}^{(l)}=\sum_{i<j}g_{ij}^{(l)}(u)$ of every ego graph. Based on
this bookkeeping, whenever an entry $g_{ij}^{(l)}(u)$ (or $A_{ij}$ if $l=0$)
is modified, to compute the log-likelihood difference we need only to evaluate
the common neighbors of $i$ and $j$ or the new or removed open and closed
triads $(i,j,v)$ or $(v,i,j)$ that affect generation $l+1$, both of which can
be computed in $O(k_{i}+k_{j})$. As a result, a whole “sweep” of the MCMC
algorithm, where each edge in $\bm{G}$ had a chance to be moved by one of the
proposals considered, has an overall complexity of $O(N{\left<k^{2}\right>})$,
since each node $i$ has $k_{i}$ edges that need to be moved at every sweep,
each of which requiring time $O(k_{i}+k_{j})$, with $j$ being the other
endpoint.

For the partition part of the algorithm, the overall complexity of a sweep,
where every node had a chance to be moved to a different group, is $O(E+N)$,
independent of the number of groups being occupied Peixoto (2020b).

Combining the two kinds of moves gives us an overall complexity of
$O(N{\left<k^{2}\right>})$ per sweep, which for sparse graphs with
${\left<k^{2}\right>}=O(1)$ amounts to $O(N)$. This means that it is possible,
at least in principle, to apply this algorithm for very large networks.

On top of the time it takes to perform sweeps of the MCMC, there is also the
mixing time of the Markov chain, which determines how long one needs to wait
before usable samples from the posterior distribution are made. It is
difficult to estimate the mixing time, as it depends heavily on the actual
network structure being considered, but we found that the algorithm gives
usable results in reasonable time even for networks with over a hundred of
thousand edges, although we did not attempt a detailed investigation of
networks which are much larger than this.

A reference implementation of this algorithm is freely made available as part
of the graph-tool library Peixoto (2014b).

##  Appendix D Predictive posterior distribution

The predictive posterior distribution considered in the main text is

$P(C|\bm{G})=\sum_{\bm{G}^{\prime}}\delta(C-C(\bm{G}^{\prime}))\sum_{\bm{\theta}}P(\bm{G}^{\prime}|\bm{\theta})P(\bm{\theta}|\bm{G}),$
(73)

where $\bm{\theta}$ are the parameters of model $P(\bm{G}|\bm{\theta})$. Here
we specify more precisely how these parameters are chosen and sampled for the
SBM/TC model. The marginal likelihood for the SBM given by Eq. 1 can be
written equivalently as Peixoto (2017)

$P(\bm{A}|\bm{b})=P(\bm{A}|\bm{k},\bm{e},\bm{b})P(\bm{k}|\bm{e},\bm{b})P(\bm{e}|\bm{b}),$
(74)

where the likelihood of the microcanonical DC-SBM is given by

$P(\bm{A}|\bm{k},\bm{e},\bm{b})=\frac{\prod_{r<s}e_{rs}!\prod_{r}e_{rr}!!\prod_{i}k_{i}!}{\prod_{i<j}A_{ij}!\prod_{i}A_{ii}!!\prod_{r}e_{r}!},$
(75)

and prior for the degrees is

$P(\bm{k}|\bm{e},\bm{b})=\prod_{r}\frac{\prod_{k}\eta_{k}^{r}!}{n_{r}!q(e_{r},n_{r})},$
(76)

and the prior for the edge counts between groups is

$P(\bm{e}|\bm{b})={\frac{B(B+1)}{2}+E-1\choose E}^{-1}.$ (77)

For the triadic closure edges we have the likelihood
$P(\bm{g}(u)|\bm{A},p_{u})$ of Eq. 4, which, given a uniform prior
$P(p_{u})=1$, gives us a a Beta posterior distribution

$P(p_{u}|\bm{g}(u),\bm{A})=\\\
\frac{p_{u}^{\sum_{i<j}g_{ij}(u)m_{ij}(u)}(1-p_{u})^{\sum_{i<j}(1-g_{ij}(u))m_{ij}(u)}}{\mathcal{B}\left(\textstyle\sum_{i<j}g_{ij}(u)m_{ij}(u),\textstyle\sum_{i<j}(1-g_{ij}(u))m_{ij}(u)\right)},$
(78)

where $\mathcal{B}(x,y)$ is the Beta function. Based on this parametrization,
our predictive posterior distribution is obtained by setting
$\theta=(\\{\bm{p}^{(l)}\\},\bm{k},\bm{e},\bm{b})$, amounting to

$P(C|\bm{G})=\sum_{\begin{subarray}{c}\\{{\bm{g}}^{(l)}\\}\\\
\\{{\bm{g}^{\prime}}^{(l)}\\}\\\ \bm{A},\bm{A}^{\prime}\\\
\bm{k},\bm{e},\bm{b}\end{subarray}}\int\,d\\{\bm{p}^{(l)}\\}\delta\left\\{C-C\left[\bm{G}(\bm{A},\\{\bm{g}^{(l)}\\})\right]\right\\}\left[\prod_{l,u}P(\bm{g}^{(l)}(u)|p_{u}^{(l)},\bm{A})\right]P(\bm{A}|\bm{k},\bm{e},\bm{b})\times\\\
\left[\prod_{l,u}P(p_{u}^{(l)}|{{\bm{g}^{\prime}}^{(l)}(u)},\bm{A}^{\prime})\right]P(\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime},\bm{k},\bm{e},\bm{b}|\bm{G}).$
(79)

Operationally, this just means running our inference algorithm to obtain our
latent variables $\\{{\bm{g}^{\prime}}^{(l)}\\},\bm{A}^{\prime},\bm{k},\bm{e}$
and $\bm{b}$, and the triadic closure propensities $\bm{p}^{(l)}$ from its
posterior, using that to obtain a new seminal network $\bm{A}$ from the same
SBM, together with its new ego graphs $\\{\bm{g}^{(l)}\\}$, and then finally
computing the resulting clustering coefficient.

##  Appendix E Dataset descriptions

Below are descriptions of the network datasets used in this work. The
codenames in parenthesis correspond to the respective entries in the
Netzschleuder repository Peixoto (2020d) where the networks can be downloaded.
Some of the descriptions were obtained from the Colorado Index of Complex
Networks Clauset  _et al._ (2016).

#### Adolescent health (add_health) Moody (2001b):

A directed network of friendships obtained through a social survey of high
school students in 1994. The ADD HEALTH data are constructed from the in-
school questionnaire; 90,118 students representing 84 communities took this
survey in 1994-95. Some communities had only one school; others had two. Where
there are two schools in a community students from one school were allowed to
name friends in the other, the “sister school”. For this analysis, a
symmetrized version of the original directed network has been used,
considering only its largest connected component. The particular network named
comm26 has been used. This network has $N=551$ nodes and $E=2624$ edges.

#### Scientific collaborations in physics (arxiv_collab) Newman (2001):

Collaboration graphs for scientists, extracted from the Los Alamos e-Print
arXiv (physics), for 1995-1999 for three categories, and additionally for
1995-2003 and 1995-2005 for one category. For copyright reasons, the MEDLINE
(biomedical research) and NCSTRL (computer science) collaboration graphs from
this paper are not publicly available. For this analysis, only the largest
connected component of the networks were considered. The particular networks
named cond-mat-1999, hep-th-1999 have been used, with number of nodes and
edges, $(N,E)$, given by (13861, 44619), (5835, 13815), respectively.

#### Metabolic network (celegans_metabolic) Duch and Arenas (2005):

List of edges comprising the metabolic network of the nematode _C. elegans_.
This network has $N=453$ nodes and $E=4596$ edges.

#### C. elegans neurons (celegansneural) 198 (1986); Watts and Strogatz
(1998):

A network representing the neural connections of the Caenorhabditis elegans
nematode. For this analysis, a symmetrized version of the original directed
network has been used. This network has $N=297$ nodes and $E=2359$ edges.

#### Collins yeast interactome (collins_yeast) Collins  _et al._ (2007):

Network of protein-protein interactions in Saccharomyces cerevisiae (budding
yeast), measured by co-complex associations identified by high-throughput
affinity purification and mass spectrometry (AP/MS). For this analysis, only
the largest connected component of the network was considered. This network
has $N=1004$ nodes and $E=8319$ edges.

#### DNC emails (dnc) Kunegis (2013):

A network representing the exchange of emails among members of the Democratic
National Committee, in the email data leak released by WikiLeaks in 2016. For
this analysis, only the largest connected component of the network was
considered. This network has $N=849$ nodes and $E=12038$ edges.

#### Dolphin social network (dolphins) Lusseau  _et al._ (2003):

An undirected social network of frequent associations observed among 62
dolphins (Tursiops) in a community living off Doubtful Sound, New Zealand,
from 1994-2001. This network has $N=62$ nodes and $E=159$ edges.

#### Ego networks in social media (ego_social) McAuley and Leskovec (2012):

Ego networks associated with a set of accounts of three social media platforms
(Facebook, Google+, and Twitter). Datasets include node features (profile
metadata), circles, and ego networks, and were crawled from public sources in
2012. For this analysis, only the largest connected component of the network
was considered. The particular network named facebook_0 has been used. This
network has $N=324$ nodes and $E=2514$ edges.

#### Maier Facebook friends (facebook_friends) Maier and Brockmann (2017):

A small anonymized Facebook ego network, from April 2014. Nodes are Facebook
profiles, and an edge exists if the two profiles are “friends” on Facebook.
Metadata gives the social context for the relationship between ego and alter.
For this analysis, only the largest connected component of the network was
considered. This network has $N=329$ nodes and $E=1954$ edges.

#### Within-organization Facebook friendships (facebook_organizations) Fire
_et al._ (2013a):

Six networks of friendships among users on Facebook who indicated employment
at one of the target corporation. Companies range in size from small to large.
Only edges between employees at the same company are included in a given
snapshot. Node metadata gives listed job-type on the user’s page. The
particular networks named S1, S2 have been used, with number of nodes and
edges, $(N,E)$, given by (320, 2369), (165, 726), respectively.

#### Little Rock Lake food web (foodweb_little_rock) Martinez (1991):

A food web among the species found in Little Rock Lake in Wisconsin. Nodes are
taxa (like species), either autotrophs, herbivores, carnivores or decomposers.
Edges represent feeding (nutrient transfer) of one taxon on another. For this
analysis, a symmetrized version of the original directed network has been
used. This network has $N=183$ nodes and $E=2494$ edges.

#### NCAA college football 2000 (football) Girvan and Newman (2002):

A network of American football games between Division IA colleges during
regular season Fall 2000. This network has $N=115$ nodes and $E=613$ edges.

#### Game of Thrones coappearances (game_thrones) Beveridge and Shan (2016):

Network of coappearances of characters in the Game of Thrones series, by
George R. R. Martin, and in particular coappearances in the book “A Storm of
Swords.” Nodes are unique characters, and edges are weighted by the number of
times the two characters’ names appeared within 15 words of each other in the
text. This network has $N=107$ nodes and $E=352$ edges.

#### Google+ (google_plus) Fire  _et al._ (2013b):

Snapshot of connections among users of Google+, collected in 2012. Nodes are
users and a directed edge $(i,j)$ represents user $i$ added user $j$ to $i$’s
circle. For this analysis, a symmetrized version of the original directed
network has been used, considering only its largest connected component. This
network has $N=201949$ nodes and $E=1496936$ edges.

#### Jazz collaboration network (jazz_collab) Gleiser and Danon (2003):

The network of collaborations among jazz musicians, and among jazz bands,
extracted from The Red Hot Jazz Archive digital database, covering bands that
performed between 1912 and 1940. This network has $N=198$ nodes and $E=2742$
edges.

#### Zachary Karate Club (karate) Zachary (1977):

Network of friendships among members of a university karate club. Includes
metadata for faction membership after a social partition. Note: there are two
versions of this network, one with 77 edges and one with 78, due to an
ambiguous typo in the original study. (The most commonly used is the one with
78 edges.). The particular network named 78 has been used. This network has
$N=34$ nodes and $E=78$ edges.

#### Les Misérables coappearances (lesmis) Knuth (1993):

The network of scene coappearances of characters in Victor Hugo’s novel “Les
Miserables.” Edge weights denote the number of such occurrences. This network
has $N=77$ nodes and $E=254$ edges.

#### Malaria var DBLa HVR networks (malaria_genes) Larremore  _et al._ (2013):

Networks of recombinant antigen genes from the human malaria parasite _P.
falciparum_. Each of the 9 networks shares the same set of vertices but has
different edges, corresponding to the 9 highly variable regions (HVRs) in the
DBLa domain of the var protein. Nodes are var genes, and two genes are
connected if they share a substring whose length is statistically significant.
Metadata includes two types of node labels, both based on sequence structure
around HVR6. For this analysis, only the largest connected component of the
network was considered. The particular network named HVR_9 has been used. This
network has $N=297$ nodes and $E=7562$ edges.

#### Scientific collaborations in network science (netscience) Newman (2006):

A coauthorship network among scientists working on network science, from 2006.
This network is a one-mode projection from the bipartite graph of authors and
their scientific publications. For this analysis, only the largest connected
component of the network was considered. This network has $N=379$ nodes and
$E=914$ edges.

#### Physician trust network (physician_trust) Coleman  _et al._ (1957):

A network of trust relationships among physicians in four midwestern (USA)
cities in 1966. Edge direction indicates that node $i$ trusts or asks for
advice from node $j$. Each of the four components represent the network within
a given city. For this analysis, a symmetrized version of the original
directed network has been used, considering only its largest connected
component. This network has $N=117$ nodes and $E=542$ edges.

#### Multilayer physicist collaborations (physics_collab) Domenico  _et al._
(2014):

Two multiplex networks of coauthorships among the Pierre Auger Collaboration
of physicists (2010-2012) and among researchers who have posted preprints on
arXiv.org (all papers up to May 2014). Layers represent different categories
of publication, and an edge’s weight indicates the number of reports written
by the authors. These layers are one-mode projections from the underlying
author-paper bipartite network. For this analysis, only the largest connected
component of the network was considered. The particular network named
pierreAuger has been used. This network has $N=475$ nodes and $E=7090$ edges.

#### Political books network (polbooks) Pasternak and Ivask (1970):

A network of books about U.S. politics published close to the 2004 U.S.
presidential election, and sold by Amazon.com. Edges between books represent
frequent copurchasing of those books by the same buyers. The network was
compiled by V. Krebs and is unpublished. This network has $N=105$ nodes and
$E=441$ edges.

#### High school temporal contacts (sp_high_school) Mastrandrea  _et al._
(2015):

These data sets correspond to the contacts and friendship relations between
students in a high school in Marseilles, France, in December 2013, as measured
through several techniques. For this analysis, symmetrized versions of the
original directed networks have been used, considering only their largest
connected component. The particular networks named diaries, survey, facebook
have been used, with number of nodes and edges, $(N,E)$, given by (120, 502),
(128, 658), (156, 1437), respectively.

#### Student cooperation (student_cooperation) Fire  _et al._ (2012):

Network of cooperation among students in the "Computer and Network Security"
course at Ben-Gurion University, in 2012. Nodes are students, and edges denote
cooperation between students while doing their homework. The graph contains
three types of links: Time, Computer, Partners. For this analysis, only the
largest connected component of the network was considered. This network has
$N=141$ nodes and $E=297$ edges.

#### 9-11 terrorist network (terrorists_911) Krebs (2002):

Network of individuals and their known social associations, centered around
the hijackers that carried out the September 11th, 2001 terrorist attacks.
Associations extracted after-the-fact from public data. Metadata labels say
which plane a person was on, if any, on 9/11. This network has $N=62$ nodes
and $E=152$ edges.

#### Madrid train bombing terrorists (train_terrorists) Hayes (2006):

A network of associations among the terrorists involved in the 2004 Madrid
train bombing, as reconstructed from press stories after-the-fact. Edge
weights encode four levels of connection strength: friendships, ties to Al
Qaeda and Osama Bin Laden, co-participants in wars, and co-participants in
previous terrorist attacks. This network has $N=64$ nodes and $E=243$ edges.

#### Email network (uni_email) Guimerà  _et al._ (2003):

A network representing the exchange of emails among members of the Rovira i
Virgili University in Spain, in 2003. For this analysis, a symmetrized version
of the original directed network has been used. This network has $N=1133$
nodes and $E=10903$ edges.