# Weighted directed clustering: interpretations and requirements for
heterogeneous, inferred, and measured networks

Tanguy Fardet1,2 Anna Levina1,2 1University of Tübingen, Tübingen, Germany
2Max Planck Institute for Biological Cybernetics, Tübingen, Germany

###### Abstract

Weights and directionality of the edges carry a large part of the information
we can extract from a complex network. However, many network measures were
formulated initially for undirected binary networks. The necessity to
incorporate information about the weights led to the conception of the
multiple extensions, particularly for definitions of the local clustering
coefficient discussed here. We uncover that not all of these extensions are
fully-weighted; some depend on the degree and thus change a lot when an
infinitely small weight edge is exchanged for the absence of an edge, a
feature that is not always desirable. We call these methods “hybrid” and argue
that, in many situations, one should prefer fully-weighted definitions. After
listing the necessary requirements for a method to analyze many various
weighted networks properly, we propose a fully-weighted continuous clustering
coefficient that satisfies all the previously proposed criteria while also
being continuous with respect to vanishing weights. We demonstrate that the
behavior and meaning of the Zhang–Horvath clustering and our new continuous
definition provide complementary results and significantly outperform other
definitions in multiple relevant conditions. Using synthetic and real-world
examples, we show that when the network is inferred, noisy, or very
heterogeneous, it is essential to use the fully-weighted clustering
definitions.

###### Contents

  1. I Introduction
  2. II Interpretation and purpose of weighted clustering
    1. II.1 Desired properties of weighted clustering coefficients
    2. II.2 State of the art for weighted clustering
    3. II.3 A continuous definition for weighted clustering and closure
    4. II.4 Directed weighted clustering
  3. III The advantages of fully-weighted definitions
    1. III.1 Sensitivity to weight-encoded topological features
    2. III.2 Continuity and resilience to noise
  4. IV Application to real world networks
    1. IV.1 Mouse mesoscale connectome
    2. IV.2 Decentralized social media: the Fediverse
    3. IV.3 Using local clustering to infer dynamical properties
  5. V Discussion
  6. A Limitations of other fully-weighted definitions
    1. A.1 Holme et al. (2007)
    2. A.2 Miyajima and Sakuragawa (2014)
  7. B Comparison of clustering properties
  8. C Derivation of the evolution of hybrid clustering coefficients
    1. C.1 Barrat
    2. C.2 Onnela
    3. C.3 Directed versions of the clustering coefficients
  9. D Closure
    1. D.1 Undirected weighted closure
    2. D.2 Directed weighted closure
  10. E Network generation algorithms
    1. E.1 Core-periphery network
    2. E.2 Watts–Strogatz
  11. F Real-world networks
    1. F.1 Mouse mesoscale connectome
    2. F.2 Fediverse mesoscale network
    3. F.3 Closure in the shuffled networks
    4. F.4 Networks with a high number of single-node triangles

##  I Introduction

The clustering coefficient (CC) was originally introduced for binary
undirected networks to quantify strong connectedness within a local
neighborhood. It was defined as the fraction of all possible triangles that
were realized i.e. the ratio between all triangles to which node $i$
participates ($n_{\Delta,i}$) and the total number of triangles that could
theoretically be made given its degree $d_{i}$, which is the number of
triplets ($n_{T,i}$):

$C_{i}^{\text{bin}}=\frac{n_{\Delta,i}}{n_{T,i}}=\frac{n_{\Delta,i}}{d_{i}(d_{i}-1)}$
(1)

From a neighbor-centric perspective, it can be seen perhaps more intuitively
as the probability that two neighbors of a node are connected. However, as
network science expanded, more and more graphs were encountered, where
directedness and edge weights play a central role. Generalizations of the
clustering coefficient were therefore introduced to account for asymmetry in
the connections between pairs of nodes or heterogeneity in their strength.

The importance of clustering, including its directed variants, to understand
complex dynamics on networks has been stressed in multiple studies [1, 2, 3,
4]. This is notably the case for the middleman motif which is a marker of
feedforward loops in transcriptional networks, and of information transfer
redundancy e.g. in neuroscience. More generally, such motifs will influence
the evolution of dynamical processes on the networks, for instance
synchronization patterns, and have been shown to characterize families of
networks such as transcription or language networks [2]. Finally, clustering
is used in other measurements to access the small-world propensity of networks
[5] and the choice of a specific definition can therefore influence whether
the network of interest will register as small-world or not.

In many applications network topology and weights are measured only up to
certain precision [6, 7]. For example, in neuroscience, the functional
connectivity networks measured using the indirect inference of connections
from the recorded activity [8, 9]. Accepting the inevitability of noise in a
network brings forward new requirements on the network measures, namely that
they are stable to the noise and do not change dramatically if the weights are
perturbed or weak connections are randomly omitted.

There is no agreement among the researchers which weighted extension of the
clustering coefficient definition is most appropriate. The three predominantly
used methods at the moment [10, 11, 12] differ in many properties of their
definitions. Part of the reason for the absence of a single best weighted
clustering lies in a different interpretation of weights in various datasets.
Consequently, a different weighted extension might be most appropriate for
various data and specific scientific questions. However, to understand which
method to use when and why we need to understand their differences precisely.

The difficulty of extending graph measures to weighted networks is not
specific to the clustering coefficient but can occur whenever ratios of
degrees or path-length are involved. We will therefore also discuss a second
clustering-related measure, called the closure coefficient and introduced as
the fraction of all open walks of length 2 starting from node $i$ that are
part of a triangle [13]. This will also enable us to discuss the
complementarity of closure and clustering as the former provides an important
complement to analyze the tendency of nodes to form 3 and 4-cliques.

We introduce here a distinction between fully-weighted and hybrid definitions
and discuss why, for several classes of networks, fully-weighted and directed
definitions should be preferred to other clustering definitions that are
currently used for network analysis. We also propose a new definition that
obeys additional conditions, including continuity of the results with respect
to infinitesimal changes in edge weights, which has significant consequences
for the resilience to noise in inferred networks. We demonstrate why fully-
weighted methods are essential for measured and inferred networks, that are
pervasive in biological fields such as neuroscience, and for networks dealing
with flows of information, money, or goods that display a very broad weight
distribution.

##  II Interpretation and purpose of weighted clustering

###  II.1 Desired properties of weighted clustering coefficients

Weighted measures are crucial for many network types where the binary
connectivity is either uninformative (fully connected network) or displays
similar or lower heterogeneity compared to the weighted structure. In this
study, we focus on two classes of real-world networks: inferred or measured
networks where there can be a large number of spurious (false positive) edges
with small weights; and networks associated with flows of information or
goods, which often display broad weight distributions. This is notably the
case for many networks in neuroscience, and more generally in information,
transportation, or other social and economic networks. Weights are essential
to understand the dynamical processes that occur in these networks, requiring
measures that go beyond the binary structure.

There could be multiple requirements for weighted clustering coefficients [14]
depending on the particular question of interest and on the network
properties. The main requirements that we considered necessary for a weighted
clustering coefficient are:

  * •

_normalization_ ($C_{i}\in[0,1]$),

  * •

_consistency_ with the binary definition (for binary networks, it should give
back the classical result),

  * •

_linearity_ (scaling by $\alpha$ all edges involving node $i$ and all edges in
triangles including node $i$ scales $C_{i}$ by $\alpha$),

  * •

_continuity_ (weak influence of the addition or deletion of edges having very
small weights, meaning that an edge with infinitesimally small weight should
be equivalent to the absence of that edge).

Compared to a previously proposed list of conditions [14], we added a
_continuity_ condition but did not include a requirement of a specific
normalization factor (the global $\max(w)$) as long as the _normalization_
condition is fulfilled since only the normalization matters. We omitted the
last two conditions of Saramäki’s paper (invariance under weight permutation
and ignorance of weights not participating in any triangle). Although they
might be of interest for some specific applications, we do not consider them
to be generally desired properties for a clustering coefficient. We also did
not require that all weights in a triangle should be accounted for because
this condition is necessarily met if the _continuity_ condition is fulfilled.

_Continuity_ can be expressed mathematically as follow: for a graph $G(V,E)$,
if a weighted edge $(u,v,w)$ with $u,v\in V$ and weight $w\in\mathbb{R}$ is
added to this graph to form a new graph $G^{\prime}(V,E^{\prime})$, with
$E^{\prime}=E+\\{(u,v,w)\\}$, then the clustering measure is continuous if and
only if $\forall i\in V$, $C_{i}^{(G^{\prime})}\xrightarrow[w\rightarrow
0^{+}]{}C_{i}^{(G)}$. This condition in crucial to ensure a reasonable
behavior of the clustering coefficient in inferred networks.

Though some definitions of previously proposed weighted clustering coefficient
definitions obey most of the required properties, none of them completely
fulfill the _continuity_ condition — despite previous claims [15]. This is why
we will later propose a new definition that fulfills all aforementioned
conditions. An extensive comparison of the properties fulfilled by different
clustering definitions can be found in Appendix B.

###  II.2 State of the art for weighted clustering

First we introduce and classify the existing weighted clustering coefficient
definition. For all clustering definitions in the main text, we use the
following notation: $A$ is an adjacency matrix, $W=\\{w_{ij}\\}$ is the
normalized weight matrix, obtained from the original weight matrix
$\tilde{W}=\\{\tilde{w}_{ij}\\}$ by
$w_{ij}=\tilde{w}_{ij}/\max_{i,j}\left(\tilde{w}_{ij}\right)$.

Hybrid definitions were the first extensions of the binary clustering
coefficients definitions. They combine properties associated with weighted
connectivity matrix (i.e. intensity of the triangle) with properties that
could be already obtained from adjacency matrix (i.e. node degrees). These
definitions move from an integer counting the number of triangles
($n_{\Delta}$) to a sum of real numbers (computed as a function of edge
weights) that we call “intensities” of triangles ($I_{\Delta}$). The choice of
a particular function for the intensity of the triangles determines the
properties of the clustering coefficient.

Two popular hybrid weighted clustering were given by the teams of Barrat [10]
and Onnela [11].

For a node $i$ in a graph, the definition from [10] quantifies the fraction of
the node’s strength that is invested in triangles (see Appendix C.1 for more
details):

$C^{B}_{i}=\frac{\left(WA^{2}\right)_{ii}}{2s_{i}(d_{i}-1)}=C^{\text{bin}}_{i}\frac{\overline{w^{\Delta}_{i}}}{\overline{w_{i}}}$
(2)

where $s_{i}=\sum_{j\neq i}w_{ij}$ is the strength of the node,
$\overline{w_{i}}$ is the average weight of the edges involving $i$, and
$\overline{w^{\Delta}_{i}}=\sum_{j\neq
k}\frac{w_{ij}+w_{ik}}{2n_{\Delta,i}}a_{ij}a_{ik}a_{jk}$ is the average weight
of edges involving $i$ that are part of a triangle computed over all triangles
to which node $i$ participates. In terms of triangle intensity, this
definition was originally written:

$\begin{split}C^{B}_{i}&=\frac{\sum_{j\neq
k}\frac{w_{ij}+w_{ik}}{2}a_{ij}a_{ik}a_{jk}}{2s_{i}(d_{i}-1)}\\\
&=\frac{1}{d_{i}(d_{i}-1)}\sum_{j\neq
k}\frac{w_{ij}+w_{ik}}{2\overline{w_{i}}}a_{ij}a_{ik}a_{jk}\end{split}$ (3)

thus defining the intensity of triangle $\Delta_{ijk}$ as $I^{B}_{\Delta
ijk}=\frac{w_{ij}+w_{ik}}{2\overline{w_{i}}}a_{ij}a_{ik}a_{jk}$ as the
function of two of the triangle’s weights and the average weight of the edges
connected to node $i$, $\overline{w_{i}}$.

Proposed a bit later Onnela’s definition [11] scales the binary clustering by
the average intensity of the triangles (see Appendix C.2 for more details):

$C^{O}_{i}=\frac{\left(W^{\left[\frac{1}{3}\right]}\right)^{3}_{ii}}{d_{i}(d_{i}-1)}=C^{\text{bin}}_{i}\overline{I^{O}_{\Delta
ijk}}$ (4)

with the triangle intensity defined as $I^{O}_{\Delta
ijk}=\left(w_{ij}w_{ik}w_{jk}\right)^{1/3}$ and the average intensity taken
over all triangles to which $i$ participates.

For all hybrid methods the denominator relies on the node’s degree, meaning
that the addition or deletion of edges will always significantly affect the
clustering coefficient even if the edge has an infinitely small weight. Such
methods can thus lead to inaccurate results when applied to the inferred
networks, where a significant fraction of edges are false positives with small
weights. In the following we will also demonstrate that they cannot reliably
detect the most strongly clustered nodes in structured networks. Only fully-
weighted definitions can rise up to these challenges.

Fully-weighted definitions are variants of the clustering coefficient that do
not include any binary measures (anything that can be derived from the
adjacency matrix alone, e.g. degrees). In addition to substituting the number
of triangles by the sum of triangle intensities, they also move away from
counting triplets — defining the maximum number of possible triangles
$\max(n_{\Delta,i})=n_{T,i}=d_{i}(d_{i}-1)$. Instead, they introduce the
triplet intensity ($I_{T}$) such that, for a node $i$, $I_{T,i}$ is as a real-
valued function of the weights associated to $i$.

One of the first fully-weighted definition for the clustering coefficient was
provided by Zhang and Horvath [12] to analyze gene co-expression networks:

$C^{Z}_{i}=\frac{\sum_{j\neq k}w_{ij}w_{ik}w_{jk}}{\sum_{j\neq
k}w_{ij}w_{ik}}=\frac{\overline{I^{Z}_{\Delta
ijk}}}{\overline{I^{Z}_{Tijk}}}C^{\text{bin}}_{i}.$ (5)

Note, that the fact that the definition can be expressed as a function of the
binary clustering does not contradict the fully-weighted nature of the
measure, as it stems from a simple recombination of the terms.

This definition can be interpreted as the ratio of the summed intensities
$I^{Z}_{\Delta ijk}=w_{ij}w_{ik}w_{jk}$ of the triangles
$\Delta_{ijk}=(i,j,k)$ to the maximal possible summed intensities
$I^{Z(max)}_{\Delta ijk}=I^{Z}_{Tijk}=w_{ij}w_{ik}$ if all existing triplets
$T_{ijk}$ were closed by an edge of weight 1 (the maximal possible weight in
the normalized network). This way, if $i$ is involved in a single triangle,
the clustering coefficient is equal to the weight of the edge closing the
triplet centered on $i$ (see also Table 1).

Though this definition does not fulfill the _continuity_ property, we will
show that it still provides a consistent interpretation of weighted
clustering, as discussed in [16], and is well suited to tackle networks with a
large fraction of false positives.

Other fully-weighted definitions that were proposed and discussed since [17,
18, 15] do not bring significant additions compared to Zhang–Hovart’s
definition while actually losing some of its properties and its
straightforward interpretation. They are not considered further in this study
— see Appendix A for further explanations.

|  |  |  |  |  |  |  |
---|---|---|---|---|---|---|---|---
$C^{B}$ | 1 | 1 | 1 | 1 | 1/2 | 0 | 1/3 | 1/2
$C^{O}$ | 0 | 0 | 0 | 0 | 1/3 | 0 | 0 | 0
$C^{Z}$ | 0 | 1 | 0 | 1 | 1 | 0 | 1/3 | 0
$C$ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0
Table 1: Limit values for undirected weighted clustering coefficients of
vertex $i$ (full circle) for different weight configurations in graphs with
vanishing weights. Solid lines depict edges of weight $w=\max(w)=1$, dotted
lines denote edges with vanishing weight $\epsilon$. Only the new continuous
clustering (bottom row) returns the values consistent with the a continuity
condition, whereas the definitions of Barrat ($C^{B}$), Onnela ($C^{O}$), and
Zhang–Horvath ($C^{Z}$) deviate for it.

###  II.3 A continuous definition for weighted clustering and closure

For an undirected graph $G$, we define the new _continuous clustering_ of node
$i$ as:

$C_{i}=\frac{\sum_{j\neq k}I_{\Delta ijk}^{2}}{\sum_{j\neq
k}I_{Tijk}}=\frac{\sum_{j\neq
k}\left(\sqrt[3]{w_{ij}w_{jk}w_{ik}}\right)^{2}}{\sum_{j\neq
k}\sqrt{w_{ji}w_{ik}}}.$ (6)

We define the weighted intensity of triangles and triplets, respectively
$I_{\Delta ijk}=\sqrt[3]{w_{ij}w_{jk}w_{ik}}$ and
$I_{Tijk}=\sqrt{w_{ji}w_{ik}}$, using the geometric mean of the weights
involved. Thank to this, one strong weight in a triangle or triplet cannot
compensate the presence of smaller weights, contrary to what may happen if one
uses the arithmetic mean. This provides the desired property that the
intensity of triangles and triplets will go to zero if even a single edge
weight goes to zero. Note that, though the triangle intensity is defined as
the geometric mean of the three weights involved, it is the square of this
intensity that is used in the definition. The reason for this choice is
twofold: to assign higher influence to large triangles and to ensure the
linearity of the coefficient. Importantly, this definition of the triangle
intensity $I_{\Delta}$ assigns the same role to all participating edges. The
new clustering could be interpreted as the ratio of the triangle intensity
that is invested in strong triangles (given by the sum of the squared
intensities of triangles, which increases the importance of strong triangles)
to the triplet intensity, which would represent the maximum possible triangle
intensity if all weights connecting adjacent nodes were equal to one.

The new continuous definition fulfils all the conditions we put forward above,
and to he best of our knowledge it is the only one to do so. Similarly to
previous definitions, the new clustering coefficient can also be rewritten in
terms of node properties:

$C_{i}=\frac{\left(W^{\left[\frac{2}{3}\right]}\right)_{ii}^{3}}{\left(s^{\left[\frac{1}{2}\right]}_{i}\right)^{2}-s_{i}}$
(7)

where $s_{i}=\sum_{j\neq i}w_{ij}$ is the normalized strength of node $i$ and
$W^{\left[\alpha\right]}={w_{ij}^{\alpha}}$ and
$s^{\left[\alpha\right]}_{i}=\sum_{j\neq i}w_{ij}^{\alpha}$, the fractional
weight matrix and strength for any $\alpha\in\mathbb{R}$.

Same as for the previous definitions, the continuous clustering can be
interpreted as a function of intensities and the binary clustering:

$C_{i}=\frac{n_{\Delta}\overline{I^{2}_{\Delta
ijk}}}{n_{T}\overline{I_{Tijk}}}\;=\;\frac{\overline{I^{2}_{\Delta
ijk}}}{\overline{I_{Tijk}}}C^{\text{bin}}_{i}\;=\;\frac{\text{Var}(I_{\Delta
ijk})+\overline{I_{\Delta ijk}}^{2}}{\overline{I_{Tijk}}}C^{\text{bin}}_{i},$
(8)

with means $\overline{I_{\Delta ijk}}$ and $\overline{I_{Tijk}}$ and variance
taken over all the triangles or triplets the node $i$ participate in
respectively. In the limit where all triangles associated to node $i$ have
similar intensities, we can neglect the variance term, leaving
$\frac{\overline{I_{\Delta ijk}}^{2}}{\overline{I_{Tijk}}}C^{\text{bin}}_{i}$.
In this case, contrary to the Zhang–Horvath definition (Eq. 5) the absolute
value of the intensity matters, not only its ratio to the maximum possible
intensity. For a given average triangle intensity, the positive contribution
of the variance implies that nodes with more variable intensities, i.e. at
least one triangle with a high intensity, will have higher clustering
coefficients than nodes with identical triangles of average-intensity.

Finally, the global clustering can also be defined in a straightforward
fashion. For simplicity, we define $\mathcal{I}_{\Delta,i}=\sum_{j\neq
k}I_{\Delta ijk}^{2}$ and $\mathcal{I}_{T,i}=\sum_{j\neq k}I_{Tijk}$, leading
to $C_{i}=\mathcal{I}_{\Delta,i}/\mathcal{I}_{T,i}$. Using this definition,
the continuous global clustering is obtained via the formula:

$C_{g}=\frac{\sum_{i}\mathcal{I}_{\Delta,i}}{\sum_{i}\mathcal{I}_{T,i}}$ (9)

Mode |  Pattern |  $\boldsymbol{n^{(m)}_{\Delta,i}}$ |  $\boldsymbol{n^{(m)}_{T,i}}$ |  $\boldsymbol{I_{\Delta,i}^{(m)}}$ |  $\boldsymbol{I_{T,i}^{(m)}}$
---|---|---|---|---|---
Cycle |  |  $A^{3}_{ii}$ |  $\begin{array}[]{c}d_{i,in}d_{i,out}-d_{i}^{\leftrightarrow}\\\ =\sum_{j\neq k}a_{ij}a_{ki}\end{array}$ |  $\left(W^{\left[\frac{2}{3}\right]}\right)^{3}_{ii}$ |  $s^{\left[\frac{1}{2}\right]}_{i,in}s^{\left[\frac{1}{2}\right]}_{i,out}-s^{\leftrightarrow}_{i}$
Middleman |  |  $\left(AA^{T}A\right)_{ii}$ |  $\begin{array}[]{c}d_{i,in}d_{i,out}-d_{i}^{\leftrightarrow}\\\ =\sum_{j\neq k}a_{ij}a_{ki}\end{array}$ |  $\left(W^{\left[\frac{2}{3}\right]}W^{\left[\frac{2}{3}\right]T}W^{\left[\frac{2}{3}\right]}\right)_{ii}$ |  $s^{\left[\frac{1}{2}\right]}_{i,in}s^{\left[\frac{1}{2}\right]}_{i,out}-s^{\leftrightarrow}_{i}$
Fan-in |  |  $\left(A^{T}A^{2}\right)_{ii}$ |  $\begin{array}[]{c}d_{i,in}(d_{i,in}-1)\\\ =\sum_{j\neq k}a_{ji}a_{ki}\end{array}$ |  $\left(W^{\left[\frac{2}{3}\right]T}\left(W^{\left[\frac{2}{3}\right]}\right)^{2}\right)_{ii}$ |  $\left(s^{\left[\frac{1}{2}\right]}_{i,in}\right)^{2}-s_{i,in}$
Fan-out |  |  $\left(A^{2}A^{T}\right)_{ii}$ |  $\begin{array}[]{c}d_{i,out}(d_{i,out}-1)\\\ =\sum_{j\neq k}a_{ij}a_{ik}\end{array}$ |  $\left(\left(W^{\left[\frac{2}{3}\right]}\right)^{2}W^{\left[\frac{2}{3}\right]T}\right)_{ii}$ |  $\left(s^{\left[\frac{1}{2}\right]}_{i,out}\right)^{2}-s_{i,out}$
Table 2: Definitions of the continuous intensities for each partial mode
pattern in directed graph. Column 1: pattern names; column 2: patterns
illustration; column 3: number of triangles for node $i$; column 4: number of
triplets for node $i$; column 5: continuous intensities of the triangles for
node $i$; column 6: continuous intensities of triplets for node $i$. The
clustering coefficients associated to each mode $m$ are given by
$C^{(m)\text{bin}}_{i}=n^{(m)}_{\Delta,i}/n^{(m)}_{T,i}$ for binary networks
and $C_{i}^{(m)}=I_{\Delta,i}^{(m)}/I_{T,i}^{(m)}$ for the continuous
definition.

###  II.4 Directed weighted clustering

Fagiolo [19] proposed how to generalize clustering to directed networks. He
defined the different patterns or motifs (shown in Table 2) that can exist in
these networks, and adapted Onnela’s definition [11] as the first weighted
directed clustering coefficient. Barrat’s definition [10] was generalized to
directed graphs in [20] following the same distinction into Fagiolo’s cycle,
middleman, fan-in, and fan-out motifs.

Similarly, the Zhang–Horvath [12] and continuous definitions can be
generalized in a straightforward manner for directed networks. For it, we only
need to redefine the intensities of each directed triangle and triplet motif
as shown in Table 2 for the continuous definition and in Table 7 for
Zhang–Horvath. This simply requires replacing $A$ by $W$ in all expressions of
$n^{(m)}_{\Delta,i}$ and $a$ by $w$ in all expressions of $n^{(m)}_{T,i}$. As
the total directed clustering is defined as the sum of all modes, we can write
it as:

$C^{Z(tot)}_{i}=\frac{I^{Z(tot)}_{\Delta,i}}{I^{Z(tot)}_{T,i}}=\frac{(W+W^{T})^{3}_{ii}}{\sum_{j\neq
k}(w_{ij}+w_{ji})(w_{ik}+w_{ki})}$ (10)

Finally, the continuous clustering can be extended for each directed mode (see
Table 2) and, for the total directed clustering, this leads to:

$C_{i}^{(tot)}=\frac{I_{\Delta,i}^{(tot)}}{I_{T,i}^{(tot)}}=\frac{\frac{1}{2}\left(W^{\left[\frac{2}{3}\right]}+W^{\left[\frac{2}{3}\right]T}\right)^{3}_{ii}}{\left(s^{\left[\frac{1}{2}\right]}_{i,tot}\right)^{2}-s_{i,tot}-2s^{\leftrightarrow}_{i}},$
(11)

with $s_{i,tot}=\sum_{j}\left(w_{ij}+w_{ji}\right)$ the total strength,
$s^{\left[\frac{1}{2}\right]}_{i,tot}=\sum_{j}\left(w_{ij}^{\frac{1}{2}}+w_{ji}^{\frac{1}{2}}\right)$
the total root strength, and
$s^{\leftrightarrow}_{i}=\sum_{j}\sqrt{w_{ij}w_{ji}}$ the reciprocal strength.

As for the undirected case, the global clustering coefficient associated to
each directed pattern can be obtained via the formula:
$C_{g}^{(m)}=\sum_{i}I_{\Delta,i}^{(m)}/\sum_{i}I_{T,i}^{(m)}$.

Figure 1:  Only continuous clustering coefficient uncovers the true structure
in the weighted core-periphery network. A network has a 11 strongly-connected
core nodes (black edges) that interact with well-clustered periphery nodes
with weaker connection strengths (light-brown edges), see Appendix E.1 for
details on the network. A. Graphical view of the network; edge width gives the
strength of the connection, node color gives its clustering coefficient. B.
Distribution of clustering coefficients for the three types of nodes over 10
realizations of such a core-periphery network. Only the continuous definition
differentiates between the central, the outer-core and the periphery nodes. In
all other methods, the clustering coefficients of the 10 “outer-core” and the
22 periphery nodes overlap: Onnela’s definition only distinguishes the central
node, while Barrat and Zhang–Horvath definitions do not hint at a core-
periphery structure.

##  III The advantages of fully-weighted definitions

In this section we discuss the sensitivity to the weight-encoded topological
features and stability to noise in network measurements of the different
clustering methods. A previous study [14] already noted the fact that previous
definitions did not fulfill the continuity condition by analyzing the behavior
of the different coefficients for nodes that participate to a single-triangle.
Table 1 illustrates some of these cases and shows that the new continuous
definition is the only one to behave as expected.

Yet, we note that the definition of Zhang and Horvath is also very resilient
to noise because, except for the corner-cases associated to single triangles,
its behavior is continuous in all other situations. Moreover, contrary to what
was asserted in [14], it provides a perfectly sensible behavior given its
interpretation of clustering as the ratio of the triangle intensity $I_{\Delta
ijk}^{Z}=w_{ij}w_{ik}w_{jk}$ to its maximum possible intensity given the
weights of node $i$: $I_{\Delta ijk}^{Z(max)}=I_{Tijk}^{Z}=w_{ij}w_{ik}$ if
$w_{jk}=1$.

Because the definitions from Barrat’s and Onnela’s [10, 11] teams are the most
well-known and (to the best of our knowledge) the only methods implemented in
popular graph libraries, we restrict our comparison to Zhang–Horvath’s and
these two definitions. A more comprehensive discussion of other definitions of
the weighted clustering coefficient can be found in Appendix A.

###  III.1 Sensitivity to weight-encoded topological features

Figure 2: Fully-weighted methods are less sensitive to spurious edges. A
“measured network” can be represented as the union of a “ground truth” (G.T.)
— here a Watts–Strogatz network in dark brown — and spurious small-weight
connections (“noise” graphs with: A random, or B scale-free connectivity, in
red). We assess the influence of the weight distribution of spurious
connections (red) by checking weights that are: C all equal and small or D
following an exponential distribution and overlapping with the real weights
(dark brown). E–G: ground-truth clustering distribution (filled dark brown)
compared to the distributions associated to the measured networks for each
method (dashed lines). Weight and noise types, from (A+C) to (B+D), are
associated to colors from brown to orange in the same order as in H. H:
correlation between the ground truth clustering and clustering in measured
networks for indicated spurious edge topology and weights. Fully-weighted
clusterings retain most of the correlation for (A+D), with $R^{2}>0.55$ and
only lose the original information for (B+D). The results were obtained for 10
realizations of the spurious edges; error bars give confidence intervals.

Here we investigate how weighted structures can be detected ore missed using
different clustering definitions. As an example we consider a weighted core-
periphery graph, Figure 1. There, core nodes are characterized by both a dense
binary connectivity and large weights, whereas periphery nodes display both
sparser connectivity (though they still have large degrees) and weaker
weights, for more details in the see Appendix E.1. We generate 10 realizations
of the network and consider distribution of clustering coefficients of
different types of nodes. Continuous definition leads to distinct clustering
of different type of nodes, making the true structure of the network clearly
visible already in the clustering distributions. Because of their hybrid
nature, Barrat’s and Onnela’s definitions cannot capture this underlying
structure as it is mostly encoded in the weights and not at all in the degrees
(core nodes are not binary hubs). Though it is purely weighted, the
Zhang–Horvath definition is also not suited to detect this type of weighted
structure because its interpretation of a node’s clustering only accounts for
the relative triangle intensity given the node’s weights.

The continuous clustering is sensitive to any topological property that is
encoded via specific weight distributions. Furthermore, contrary to the
Zhang–Horvath definition, it accounts not only for the ratio of the triangle
intensity over the triplet intensity (how strong are the triangles compared
the maximum possible value given the node’s weights) but also for the absolute
value of the intensity: a weak triangle, even if it corresponds to the highest
possible value given the node’s weights, will decrease the node’s clustering
in the continuous definition whereas it increases it with the Zhang–Horvath
method. In that sense, the continuous clustering provides a more global
evaluation of the clustering coefficient compared to Zhang–Horvath that
provides a more local information.

The definition from Barrat et al. has several limitations because it is close
to being weight-insensitive [11, 21]. It is particularly unsuitable for
assessing networks with a potentially large number of low-weight spurious
connections or very heterogeneous weight distributions. For this reason, we
will mostly leave this clustering aside in the rest of this study.

###  III.2 Continuity and resilience to noise

Stability of a network measure to noise is of a particular importance for
networks that are obtained via experimental measurements since these are often
subject to noise and statistical biases, notably for inferred networks.
Methods abiding by the continuity condition are especially resilient to the
presence of low-weight spurious edges. Violation of continuity can have
significant and pervasive consequences for inference of network properties in
many network structures. We have already seen the simple examples in Table 1,
here we demonstrate that they are not just corner cases, but occur in larger,
real-world networks.

We illustrate the impact of spurious edges on measured clustering coefficients
using the example of Watts-Strogatz small-world networks. We consider
different topologies for the subnetwork formed by the spurious edges: either
an Erdős-Renyi random network (Figure 2 A.), associated to uncorrelated noise,
or a scale-free network (Figure 2 B.), which would correlate noise with
certain nodes in the network. Additionally, weights on the spurious edges
could be much smaller than the weight of the actual edges (Figure 2 C.) or
have an overlapping distribution (Figure 2 D.). Both fully-weighted methods
are unaffected by low-noise (conditions A+C and B+C) and are also less
influenced by the spurious edges when they weights are large enough to overlap
with the real weight distribution (conditions A+D and B+D). On other hand,
because hybrid methods explicitly depend on the nodes’ degrees, they are very
susceptible to the presence of spurious edges — Figure 2 G, H.

The difference in behavior between the methods can be easily explained by a
first-order expansion. We consider change in the clustering coefficient of a
node $i$ with degree $d_{i}$ after addition of a spurious edge $e=(i,v)$ with
weight $\epsilon\ll 1$. For Barrat’s and Onnela’s methods, the new clustering
coefficient becomes:

$\displaystyle C^{O^{\prime}}_{i}$ $\displaystyle=$
$\displaystyle\frac{I_{\Delta,i}^{C}+O\left(\epsilon^{\frac{1}{3}}\right)}{d_{i}(d_{i}+1)}=\frac{d_{i}-1}{d_{i}+1}C^{O}_{i}+O\left(\epsilon^{\frac{1}{3}}\right)\overset{\epsilon\rightarrow
0}{\nrightarrow}C^{O}_{i}$ $\displaystyle C^{B^{\prime}}_{i}$ $\displaystyle=$
$\displaystyle\frac{I_{\Delta,i}^{B}+\sum_{k}\frac{\epsilon+w_{ik}}{2}a_{vk}a_{ik}}{I_{T,i}^{B}+s_{i}+\epsilon}=\frac{d_{i}-1}{d_{i}}C^{B}_{i}+O(\epsilon)\overset{\epsilon\rightarrow
0}{\nrightarrow}C^{B}_{i}$

meaning that, for both methods, the coefficients will deviate from the
original clustering $C^{O/B}_{i}$ by a non-infinitesimal value, even when the
perturbation was infinitesimal — see Appendix C for complete derivation.

On the other hand, the continuous clustering becomes

$\begin{split}C_{i}&=\frac{I_{\Delta,i}+\sum\limits_{k\sim
i}\left(\epsilon\,w_{vk}w_{ki}\right)^{\frac{2}{3}}}{I_{T,i}+2s^{\left[\frac{1}{2}\right]}_{i}\sqrt{\epsilon}}\\\
&=C_{i}\left(1-\frac{2s^{\left[\frac{1}{2}\right]}_{i}\sqrt{\epsilon}}{I_{T,i}}+O\left(\epsilon^{\frac{2}{3}}\right)\right)\\\
&=C_{i}+O\left(\sqrt{\epsilon}\right)\xrightarrow[\epsilon\rightarrow
0^{+}]{}C_{i}\end{split}$ (12)

showing only an infinitesimal deviation to the similarly infinitesimal
perturbation.

Similarly, except for the single-triangle cases discussed in 1, the
Zhang–Horvath clustering becomes

$C^{Z^{\prime}}_{i}=\frac{I_{\Delta,i}^{Z}+O(\epsilon)}{I_{T,i}^{Z}+O(\epsilon)}=C^{Z}_{i}+O(\epsilon)\xrightarrow[\epsilon\rightarrow
0^{+}]{}C^{Z}_{i}$ (13)

It is worth noting that one _continuity_ issue, associated to nodes
participating in only one triangle, occurs for all definitions but the
continuous one. Since this situation is pervasive in networks with low degree
or binary clustering, using the continuous clustering definition can be of
particular importance in such cases — see Appendix F.4.

Figure 3:  For the mouse connectome different clustering methods give
significantly different results. A. Top view of the mouse brain, node size –
total-degree, node color – out-degree (lighter colors for higher degrees). B.
Distribution of the total clustering coefficients if only edges with the
p-value $p<p_{\mathrm{max}}$ are preserved. Smaller changes in clustering
distribution for fully-weighted definitions than for Onnela. From yellow to
black thresholding keeps respectively 9, 13, 32, and 100% of the original
network. C. The fraction of the nodes with highest total clustering (top 5, 10
and 25%) that are preserved across all subsamplings in B for Zhang (brown),
continuous (orange), and Onnela (pale yellow). D. Correlation of the three
total clustering definitions with average total node weight ($s_{i}/d_{i}$)
shows that fully-weighted definitions captures additional information beyond
degree and strength. E. Fraction of the 10% highest clustering nodes that are
common between two of the definitions (full markers on right panel include the
central region of the left panel) or among all three definitions (black
crosses, central region) as shown on the Venn diagram. F. Clustering ranks of
the areas within brain regions (telling which regions contain nodes with high
clustering coefficients) can significantly vary depending on the definition
(Zhang - brown, continuous - orange, and Onnela - pale yellow).  Figure 4:
Properties of the network of Fediverse instances. A. Chord diagram of
connections between locations. B. Spatial representations of the network
showing connections that amount for at least 1‰ of the strongest connection,
nodes placed on each country’s capital, their sizes represent the number of
instances hosted in that country. The zoom on Europe show all connections in
the European subnetwork. C. The counts of users per instance follows a heavy-
tailed distribution. D. The network displays strong structural clustering,
most nodes with non-zero in- and out-degrees displaying binary clustering
values close two one, whereas the expected value for an Erdős-Renyi network
with the same number of edges would be almost zero (dotted line). E. The
median values of the fan-out clustering for different instance sizes show that
the strong heterogeneity of the network can have a notable influence for the
Onnela method (yellow) whereas Zhang–Horvath (dark brown) and continuous
methods (orange) display much weaker correlation with the size of the
instance. F. The fan-in motifs have intensities that are several orders of
magnitude lower than fan-out and display weaker dependency on the instance
size. The binary (gray) clustering coefficient misses the difference between
fan-out and fan-in, which predominantly relies on the weights’ effect.  Figure
5:  Different structures of clustering patterns and information flow in the
mouse brain and the Fediverse. The original clustering values are compared to
graphs with the same adjacency matrix but shuffled edge weights (mouse, 10
uniformly shuffled networks; Fediverse, 200 graphs shuffled across all out-
going edges of each node to preserve out-strength normalization). The contours
show different density levels of the point clouds associated to the
original/shuffled pairs of clustering coefficients. A. The Zhang–Horvath and
continuous definitions capture the redundancy of information flow in the mouse
brain (middleman and fan-in/fan-out motifs are higher in the original graph).
However, the Onnela method does not capture this feature. B. For the
Fediverse, only fan-out and middleman motifs are significantly stronger than
in the random graphs. Patterns where the original values are significantly
greater (resp. smaller) than the randomized ones are marked by the $+$ (resp.
$-$) and the initial of the method (brown, Z for Zhang; orange, C for
continuous; yellow, O for Onnela). The original clustering is considered to be
significantly higher (resp. lower) if 75% of the points where above (resp.
below) the dotted identity line. Additional * denotes one-sided fractions
greater than 95%.

##  IV Application to real world networks

###  IV.1 Mouse mesoscale connectome

In neuroscience, the networks on different scales give a vital piece of
information to understand the brain better. Unsurprisingly, connectomics, the
mapping of the connections in the nervous system, gained significant attention
and developed dramatically over the last years. Most of the networks in
neuroscience are weighted, with all obtained connectivities are either
measured or inferred, making them a typical example for the challenges
discussed above. The mouse mesoscale connectome [22] is a fascinating example
of such networks, both because it provides information about the entire mouse
brain and because it contains an evaluation of the probability of false
positives for all connections.

Here, we investigate how the choice of the clustering coefficient definition
can alter the results. The network is very inhomogeneous, with broadly varying
degrees, Figure 3 A. The edges in the mesoscale connectome are assigned
p-values that quantify their probability to correspond to real physical
connection ($p$ denotes the probability of the connection to be a spurious
edge). They have therefore different significance levels, with only 13% of all
edges having $p$-values smaller than $0.01$, i.e. only 13% of all edges have a
probability to be spurious that is lower than 1%. We consider a thresholding
procedure, where at each level of the threshold ($p_{\mathrm{max}}$), only the
edges with smaller $p$-values are kept. This procedure can be seen as an
attempt to remove spurious edges, though no correct threshold level is known.
Compared to the hybrid method, both fully-weighted definitions are much less
sensitive to thresholding, Figure 3 B, C. Thus we see that the resilience to
noise we showed analytically and on toy networks is relevant for a real-world
network. Furthermore, the resilience is not limited to the general shape of
the distribution but indeed preserves the precise values and ranks: a larger
fraction of the nodes displaying high clustering in the full graph are still
among the highest ranking nodes in the thresholded graphs when fully-weighted
method’s are used compared to the hybrid method, Figure 3 E.

Clustering coefficient is a network measure that captures features beyond
purely local parameters, such as degree or strength. However, as we see for
the mouse connectome, the hybrid method strongly correlates with the average
weight associated with a node $i$: $s_{i}/d_{i}$. At the same time, the fully-
weighted definitions are much less correlated with it, Figure 3 D. As a
result, they can bring more independent information regarding weighted network
structure than the hybrid method. This trend is even stronger for the
Zhang–Horvath definition, which does not account for the absolute intensity of
triangles. In contrast, the continuous definition provides some intermediate
behavior as the intensity of triangles often correlates, if only in part, with
the average weight associated with the node.

Finally, though the continuous and Zhang–Horvath definition often provide
somewhat similar results, they may differ significantly, e.g. for cerebellar
cortex on Figure 3 F. Combining the results of both methods can thus be
informative, for example to single out nodes that possess only weak
connections (and will therefore register as weakly clustered for the
continuous definition) yet connect to other nodes that are strongly connected
(thus registering as strongly clustered for Zhang–Horvath).

###  IV.2 Decentralized social media: the Fediverse

The Fediverse is a set of federated social media that can communicate via a
collection of common protocols, the most well-known being ActivityPub. This
network can be seen as a set of alternatives to corporate platforms such as
Facebook or Twitter. Social media on the Fediverse usually promote ideas of
decentralization, interoperability, free/libre and open-source software
(FLOSS), and the absence of algorithmic filters in favor of human curation and
moderation.

We analyze here a snapshot of this network that was obtained in 2018 by
Zignani et al. [23]111data available at https://dataverse.mpi-
sws.org/dataset.xhtml?persistentId=doi:10.5072/FK2/AMYZGS. Contrary to the
original publication, we chose here to look at the mesoscale level, i.e. at
connections between instances (the equivalent of a community on the Fediverse,
where at least one, but up to several thousand users can have an account).
This mesoscale view leads to a network of weighted directed interactions
between communities of strongly connected users. Indeed, users of a single
instance (the technical name for a community on the Fediverse) can see and
interact with all public messages posted by other members on that same server.
At the same time, they can only see a subset of the posts from people on other
servers (either because they follow their author or because other members of
the instance follow the author or shared this specific post).

For each instance $I_{1}$, an edge towards another instance $I_{2}$ means that
at least one user on $I_{1}$ follows at least one member of $I_{2}$. The
precise value of the weight associated to this edge gives the fraction of all
followers from the source instance that are associated to members of the
target instance. The weights are thus a proxy to characterize the fraction of
the community’s attention that is associated to content produced by another
community; this means of course that, for each node, it’s outgoing strength
$s_{o}$ is equal to one. Note that in this network, information flow occurs in
the direction _opposite_ to that of the edge, because the directed edge
denotes that the source is paying attention to what the target posts.

The network snapshot contains 3,825 nodes corresponding mostly to instances
running Mastodon, one of the most prominent microblogging platforms on the
Fediverse. These 3,825 nodes represent more than half of the entire network
and are connected via 81,371 edges. Chord diagram of connections between
locations shows that, besides the fact that the position of most instances is
unspecified (UNS), the largest hosting countries are Japan, the USA, and
France, with Japanese and French communities interacting mostly among
themselves, Figure 4 A, B. The network is both very sparse and strongly
heterogeneous, with a median degree of 5 but node degrees and sizes varying
over 3 to 5 orders of magnitude. This broad distribution has notable
implications for different clustering definitions. For the Zhang–Horvath, it
increases the likelihood of running into the corner-cases of single triangles,
increasing the average clustering compared to the other methods. For Onnela’s
definition, it strongly correlates clustering values to the degree (and thus
to the size) of the instance.

As for the mouse network, all weighted methods lead to results that differ
strongly from the binary clustering, Figure 4 (D and E). Some of the results
from the hybrid method tends to correlate strongly with some 1st order
properties of the nodes (Figure 4 E) while the fully-weighted methods bring
more independent information. The Fediverse network displays a peculiar
feature as its fan-out and fan-in clustering differ significantly despite the
usual correlation between these two patterns, as can be seen from the
comparison of Figure 4 E and F.

###  IV.3 Using local clustering to infer dynamical properties

Analysis of clustering coefficient for different structured patterns offer a
way to obtain a precise idea of the critical dynamical patterns within a
network. To determine the significance of a particular pattern we compare its
prominence in the original network with it in a null-model networks obtained
via appropriate randomization. For the mouse brain, as a randomized control,
we take the original network and only shuffle the weights, thus preserving the
weights distribution and binary structure. Comparing the actual values in the
original graphs to that of randomized graphs, we can see the importance of
looking at fully-weighted measures.

Both Zhang–Horvath and continuous definitions identify the preference of the
mouse brain network for redundant information flows, whereas the hybrid method
of Onnela does not capture this feature. Redundant information transfer in the
brain is indeed associated to situations where a signal can be transferred not
only directly from one node to another, but also indirectly via a third
(middleman) node, as can be seen in middleman, fan-in and fan-out patters (cf.
Table 2). This overexpression of redudant patterns is visible, for the fully-
weighted methods, in the high values of middleman and fan-in/fan-out motifs in
Figure 5 A.

The situation for the Fediverse is significantly more complex. Indeed, 98 % of
all edges belong to at least one triangle, some are involved in up to
thousands of triangles. A deeper understanding of the clustering requires
precisely investigation of how the weight distribution correlates with
specific patterns of triangles. For instance, though fan-in and fan-out
patterns co-occur and are thus usually correlated, the Fediverse displays an
unexpected discrepancy between the weight associated to both patterns, as seen
on Figure 5 B, which notably differentiates it from the mouse connectome (see
also Appendix F.3).

##  V Discussion

In this work, we introduced new directed weighted definitions for clustering
analysis. Using analytic derivations, generated networks models and real data,
we showed that the behavior of fully-weighted measures displayed enhanced
sensitivity, selectivity, and robustness compared to hybrid measures. To
facilitate access to these measures, all clustering methods were implemented
in Python and made compatible with the three main libraries in this language
(networkx, igraph, and graph-tool) [24].

We highlighted the importance of continuity as a crucial notion for networks
with highly heterogeneous weight distribution or numerous spurious edges with
low weights. In the previous studies, slight variations on this notion had
been introduced mathematically [15] and hinted at by the study of corner cases
[14]. However, the continuity property was inadvertently considered only in
particular classes of networks [15] (disregarding, for example, small degree
cases), erroneously marking previous methods as continuous. The other study
[14] asserted discontinuity of previous measures simply as a feature, without
discussing its implications or ways to avoid it. Our new proposal of fully
continuous clustering methods based on simple mathematical principles and
requirements is, therefore, the first to fully solve the issue of continuity.
In addition, we show in Appendix D that these principles can be extended to
other measures such as the local closure.

We discussed how each weighted definition is associated to a specific
interpretation of weighted clustering as a function of the binary clustering,
triangle, and triplet intensities (see Appendix B and Table 6 for a summary).
In turns, these interpretations are associated to specific properties for each
clustering coefficient. Combining mathematical analysis and concrete examples,
we asserted that fully-weighted measures out-perform hybrid ones to evaluate
clustering in networks with large numbers of spurious edges with small
weights. We expanded the results from previous studies comparing existing
weighted definitions [16, 14, 21, 15], extending their definition to directed
networks and providing complete mathematical justifications to previous
observations regarding linearity and continuity.

Our analyses show that either of the fully weighted definitions may be
preferred depending on the network properties. For networks with large
degrees, the Zhang–Horvath definition may be preferred if the number of low-
weight spurious edges is very high as it is least susceptible to noise. In
networks with heterogeneous weight distributions where the absolute value of
triangle strength is of interest, we showed that the continuous definition
provides more relevant results than that of Zhang and Horvath. Indeed, in
networks involving fluxes of good or matter as well as for information
processing (e.g. in brain or telecommunication networks), one may be
interested in the absolute amount that can be transferred between nodes,
making nodes with small weights of little relevance. A similar issue occurs
for networks where many nodes participate to a single triangle (see Appendix
F.4) making the Zhang–Horvath clustering non-continuous. In such networks, the
use of the Zhang–Horvath definition is likely to assign high clustering to
single-triangle nodes with low-weights, whereas the continuous definition will
not, as was shown on Figure 1.

Finally, we illustrate the usefulness of weighted clustering methods to
investigate clustering on the example of a connectome and a decentralized
social network. The fully-weighted methods were especially suitable to reveal
key differences in their weighted structural properties. Indeed, we showed
that middleman, fan-in, and fan-out patterns, characteristic of pathways
enabling redundant information transfer between nodes, were overexpressed in
the mouse brain. In the Fediverse, the methods revealed an unexpected
discrepancy between fan-in and fan-out modes, probably associated with social
interaction patterns that would mandate further investigation.

### Acknowledgments

The research was funded by a Humboldt Research Fellowship for Postdoctoral
Researchers and a Sofja Kovalevskaja Award from the Alexander von Humboldt
Foundation, endowed by the Federal Ministry of Education and Research.

## References

  * Mason and Verwoerd [2007] O. Mason and M. Verwoerd, Graph theory and networks in Biology, IET Systems Biology 1, 89 (2007).
  * Ahnert and Fink [2008] S. E. Ahnert and T. M. A. Fink, Clustering signatures classify directed networks, Physical Review E 78, 036112 (2008).
  * Zhang  _et al._ [2016] X.-J. Zhang, B. Gu, X.-M. Guan, Y.-B. Zhu, and R.-L. Lv, Cascading failure in scale-free networks with tunable clustering, International Journal of Modern Physics C 27, 1650093 (2016).
  * Li  _et al._ [2018] Y.-W. Li, Z.-H. Zhang, D. Fan, Y.-R. Song, and G.-P. Jiang, Influence of Clustering on Network Robustness Against Epidemic Propagation, in  _Science of Cyber Security_, Lecture Notes in Computer Science, edited by F. Liu, S. Xu, and M. Yung (Springer International Publishing, 2018) pp. 19–33.
  * Muldoon  _et al._ [2016] S. F. Muldoon, E. W. Bridgeford, and D. S. Bassett, Small-World Propensity and Weighted Brain Networks, Scientific Reports 6, 22057 (2016).
  * Young  _et al._ [2021] J.-G. Young, G. T. Cantwell, and M. E. J. Newman, Bayesian inference of network structure from unreliable data, Journal of Complex Networks 8, 10.1093/comnet/cnaa046 (2021), cnaa046, https://academic.oup.com/comnet/article-pdf/8/6/cnaa046/36509950/cnaa046.pdf .
  * Guimerà and Sales-Pardo [2009] R. Guimerà and M. Sales-Pardo, Missing and spurious interactions and the reconstruction of complex networks, Proceedings of the National Academy of Sciences 106, 22073 (2009), https://www.pnas.org/content/106/52/22073.full.pdf .
  * Fox and Greicius [2010] M. Fox and M. Greicius, Clinical applications of resting state functional connectivity, Frontiers in Systems Neuroscience 4, 19 (2010).
  * Orlandi  _et al._ [2014] J. G. Orlandi, O. Stetter, J. Soriano, T. Geisel, and D. Battaglia, Transfer entropy reconstruction and labeling of neuronal connections from simulated calcium imaging, PloS one 9, e98842 (2014).
  * Barrat  _et al._ [2004] A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani, The architecture of complex weighted networks, Proceedings of the National Academy of Sciences 101, 3747 (2004).
  * Onnela  _et al._ [2005] J.-P. Onnela, J. Saramäki, J. Kertész, and K. Kaski, Intensity and coherence of motifs in weighted complex networks, Physical Review E 71, 065103 (2005), arXiv:cond-mat/0408629 .
  * Zhang and Horvath [2005] B. Zhang and S. Horvath, A General Framework for Weighted Gene Co-Expression Network Analysis, Statistical Applications in Genetics and Molecular Biology 4, 10/bc8bw3 (2005).
  * Yin  _et al._ [2019] H. Yin, A. R. Benson, and J. Leskovec, The Local Closure Coefficient: A New Perspective On Network Clustering, in  _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ (ACM, Melbourne VIC Australia, 2019) pp. 303–311.
  * Saramäki  _et al._ [2007] J. Saramäki, M. Kivelä, J.-P. Onnela, K. Kaski, and J. Kertész, Generalizations of the clustering coefficient to weighted complex networks, Physical Review E 75, 027105 (2007).
  * Wang  _et al._ [2016] Y. Wang, E. Ghumare, R. Vandenberghe, and P. Dupont, Comparison of Different Generalizations of Clustering Coefficient and Local Efficiency for Weighted Undirected Graphs, Neural Computation 29, 313 (2016).
  * Kalna and Higham [2006] G. Kalna and D. J. Higham, Clustering Coefficients for Weighted Networks ∗ (2006) p. 7.
  * Holme  _et al._ [2007] P. Holme, S. M. Park, B. J. Kim, and C. R. Edling, Korean university life in a network perspective: Dynamics of a large affiliation network, Physica A: Statistical Mechanics and its Applications 373, 821 (2007), arXiv:cond-mat/0411634 .
  * Miyajima and Sakuragawa [2014] K. Miyajima and T. Sakuragawa, Continuous and robust clustering coefficients for weighted and directed networks, arXiv:1412.0059 [physics] (2014), arXiv:1412.0059 [physics] .
  * Fagiolo [2007] G. Fagiolo, Clustering in complex directed networks, Physical Review E 76, 026107 (2007), arXiv:physics/0612169 .
  * Clemente and Grassi [2018] G. Clemente and R. Grassi, Directed clustering in weighted networks: A new perspective, Chaos, Solitons & Fractals 107, 26 (2018), arXiv:1706.07322 .
  * Antoniou and Tsompa [2008] I. E. Antoniou and E. T. Tsompa, Statistical Analysis of Weighted Networks, Discrete Dynamics in Nature and Society 2008, 1 (2008).
  * Oh  _et al._ [2014] S. W. Oh, J. A. Harris, L. Ng, B. Winslow, N. Cain, S. Mihalas, Q. Wang, C. Lau, L. Kuan, A. M. Henry, M. T. Mortrud, B. Ouellette, T. N. Nguyen, S. A. Sorensen, C. R. Slaughterbeck, W. Wakeman, Y. Li, D. Feng, A. Ho, E. Nicholas, K. E. Hirokawa, P. Bohn, K. M. Joines, H. Peng, M. J. Hawrylycz, J. W. Phillips, J. G. Hohmann, P. Wohnoutka, C. R. Gerfen, C. Koch, A. Bernard, C. Dang, A. R. Jones, and H. Zeng, A mesoscale connectome of the mouse brain, Nature 508, 207 (2014).
  * Zignani  _et al._ [2019] M. Zignani, C. Quadri, S. Gaito, H. Cherifi, and G. P. Rossi, The footprints of a “mastodon”: How a decentralized architecture influences online social relationships, in  _IEEE Conference on Computer Communications Workshops 2019_ (IEEE, 2019) pp. 472–477.
  * Fardet [2021] T. Fardet, NNGT 2.3.0 (2021).
  * Opsahl and Panzarasa [2009] T. Opsahl and P. Panzarasa, Clustering in weighted networks, Social Networks 31, 155 (2009).
  * Watts and Strogatz [1998] D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393, 440 (1998).
  * Yin  _et al._ [2020] H. Yin, A. R. Benson, and J. Ugander, Measuring directed triadic closure with closure coefficients, Network Science 8, 551 (2020).
  * Cho  _et al._ [2014] A. Cho, J. Shin, S. Hwang, C. Kim, H. Shim, H. Kim, H. Kim, and I. Lee, WormNet v3: A network-assisted hypothesis-generating server for Caenorhabditis elegans, Nucleic Acids Research 42, W76 (2014).

##  Appendix A Limitations of other fully-weighted definitions

See Table 3 for a complete comparison of the fully-weighted clustering
definitions.

###  A.1 Holme et al. (2007)

Most studies consider the definition of Holme et al. [17] to be:

$C_{i}^{H}=\frac{\sum_{jk}w_{ij}w_{ik}w_{jk}}{\max_{ij}(w_{ij})\sum_{jk}w_{ij}w_{jk}}$
(14)

which would make it inconsistent with the binary definition. However the
discussion in their paper states that _consistency_ was one of their
requirements, letting us think that they actually meant to define it as

$C_{i}^{H}=\frac{\sum_{j\neq
k}w_{ij}w_{ik}w_{jk}}{\max_{ij}(w_{ij})\sum_{j\neq k}w_{ij}w_{jk}}$ (15)

which would make it equal to the definition from Zhang and Horvath [12], we
will therefore not consider 14 here.

###  A.2 Miyajima and Sakuragawa (2014)

The authors define a multitude of generalized clustering coefficients based on
the use of an arbitrary function $h:\mathbb{R}^{2}\rightarrow\mathbb{R}$ such
that:

$C_{i}^{M,h}=\frac{\sum_{jk}h(h(w_{ij},w_{ik}),w_{jk})}{\sum_{j\neq
k}h(h(w_{ij},w_{jk}),\max_{lm}(w_{lm}))}$ (16)

More specifically, Wang et al. [15] argue in favor of the use of a specific
version using the harmonic mean:

$C_{i}^{M,hm}=\frac{\sum_{jk}\frac{2}{\frac{2}{\frac{1}{w_{ij}}+\frac{1}{w_{ik}}}+\frac{1}{w_{jk}}}}{\sum_{j\neq
k}\frac{2}{\frac{2}{\frac{1}{w_{ij}}+\frac{1}{w_{ik}}}+\frac{1}{\max_{lm}(w_{lm})}}}$
(17)

However, this definition suffers from three major shortcomings:

  * •

despite what is asserted by the authors, it does not fulfill the _continuity_
condition;

  * •

it is not locally linear, meaning that two nodes that have the same
neighborhood but with all weights differing by a factor $\lambda$ will not
have the ratio of their clustering coefficients equal to $\lambda$;

  * •

it introduces an undesired asymmetry in the definition of the triangle
intensity: for a given triangle $\Delta_{ijk}$, the computed intensity will be
different for each node as it depends on which one is considered as $i$.

|  |  |  |  |  |  |  |
---|---|---|---|---|---|---|---|---
$C^{Z}$ | 0 | 1 | 0 | 1 | 1 | 0 | 1/3 | 0
$C^{H}$ | 0 | 1 | 0 | 1 | 1 | 0 | 1/3 | 0
$C^{M,hm}$ | 0 | 1 | 0 | 1 | 1 | 0 | 1/3 | 0
$C$ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0
Table 3: Undirected weighted clustering coefficients of vertex $i$ (full
circle) for different weight configurations. Solid lines depict edges of
weight $w=\max(w)=1$, whereas dotted lines are associated to edges with
vanishing weight $\epsilon$. Only the new continuous clustering (bottom row)
displays the required properties, compared to the definitions of Zhang
($C^{Z}$), Holme ($C^{H}$), and Miyajima ($C^{M,hm}$).

##  Appendix B Comparison of clustering properties

Multiple properties of the main definitions for the clustering coefficient are
listed in Table 4. These properties depend on the definitions of triangle and
triplet intensity that are recapitulated in Table 5.

Property | Barrat | Onnela | Miyajima | Zhang | Continuous
---|---|---|---|---|---
Consistent with binary definition | X | X | X | X | X
Normalized ($C\in[0,1]$) | X | X | X | X | X
All weights participate to $I_{\Delta}$ |  | X | X | X | X
All weights participate equally to $I_{\Delta}$ |  | X |  | X | X
Linear against local scaling of the weights |  | X |  | X | X
Sensitive to weight permutations | X |  | X | X | X
For a triangle $\Delta=(i,j,k)$, $I_{\Delta}=I_{T}f(w_{jk})$ |  |  |  | X |
Continuous |  |  |  |  | X
Table 4: Comparison of the different properties of the different clustering coefficients. Zhang–Horvath and the continuous definitions fulfill the maximum number of desirable properties. An X means that the method possesses this property. Definition | Triangle ($I_{\Delta ijk}$) | Triplet ($I_{Tijk}$)
---|---|---
Barrat | $\displaystyle\frac{w_{ij}+w_{ik}}{2\overline{w_{i}}}a_{ij}a_{ik}a_{jk}$ | $d_{i}(d_{i}-1)$
Onnela | $\left(w_{ij}w_{ik}w_{jk}\right)^{1/3}$ | $d_{i}(d_{i}-1)$
Miyajima (hm) | $\displaystyle\frac{2}{\frac{2}{\frac{1}{w_{ij}}+\frac{1}{w_{ik}}}+\frac{1}{w_{jk}}}$ | $\displaystyle\frac{2}{\frac{1}{w_{ij}}+\frac{1}{w_{ik}}}$
Zhang | $w_{ij}w_{ik}w_{jk}$ | $w_{ij}w_{ik}$
Continuous | $\sqrt[3]{w_{ij}w_{jk}w_{ik}}$ | $\sqrt{w_{ij}w_{ik}}$
Table 5: Comparison of the formula for triangle and triplet intensity among
the different clustering definitions for undirected networks.

The different formulas for the intensities lead to different interpretations
of weighted clustering — Table 6. Barrat and Zhang only quantify ratios of
triangle and triplet strength. while Onnela and the continuous definitions are
sensitive to the absolute value of the triangle intensity. The latter provides
an intermediate between Zhang and Onnela as it reacts to both the ratio of
intensities and the absolute value of the triangle intensity.

Definition | Barrat | Onnela | Zhang | Continuous
---|---|---|---|---
Formula | $\displaystyle\frac{\overline{w^{\Delta}_{i}}}{\overline{w_{i}}}C^{\text{bin}}_{i}$ | $\displaystyle\overline{I^{O}_{\Delta ijk}}C^{\text{bin}}_{i}$ | $\displaystyle\frac{\overline{I^{Z}_{\Delta ijk}}}{\overline{I^{Z}_{Tijk}}}C^{\text{bin}}_{i}$ | $\displaystyle\frac{\overline{I^{2}_{\Delta ijk}}}{\overline{I_{Tijk}}}C^{\text{bin}}_{i}$
Table 6: Comparison of the interpretation of the different clustering
definitions for undirected networks.

##  Appendix C Derivation of the evolution of hybrid clustering coefficients

###  C.1 Barrat

Upon addition to a graph $G(N,E)$ of an edge $(i,v)$ of weight $\epsilon$,
giving $G^{\prime}(N,E^{\prime}=E+\\{(i,v)\\}$, one can compute the evolution
of the initial clustering coefficient $C^{B}_{i}$ to its new value
$C^{B^{\prime}}_{i}$ by rewriting the definition from [10] as in [14]:

$\begin{split}C^{B}_{i}&=\frac{1}{d_{i}(d_{i}-1)}\sum_{j\neq
k}\frac{w_{ij}+w_{ik}}{2\overline{w_{i}}}a_{ij}a_{ik}a_{jk}\\\
&=\frac{1}{d_{i}(d_{i}-1)}\sum_{j\neq
k}\frac{w_{ij}}{\overline{w_{i}}}a_{ij}a_{ik}a_{jk}\end{split}$ (18)

From this, we can deduce the following relationship between Barrat’s
definition and the binary clustering coefficient $C^{bin}_{i}$:

$C^{B}_{i}=\frac{n_{\Delta,i}\overline{w^{\Delta}_{i}}/\overline{w_{i}}}{d_{i}(d_{i}-1)}=C^{\text{bin}}_{i}\frac{\overline{w^{\Delta}_{i}}}{\overline{w_{i}}}$
(19)

with $n_{\Delta,i}$ the number of triangles to which node $i$ participates and
$\overline{w^{\Delta}_{i}}$ the average weight associated to edges connected
to $i$ and participating in a triangle.

Notice that this expression also explains why the definition from Barrat is so
close to the binary clustering: for networks where weights are either rather
homogeneous or where they are not strongly correlated to triangles,
$\overline{w^{\Delta}_{i}}$ and $\overline{w_{i}}$ become very close as the
number of triangles per node increases.

Using equation 19, the new clustering can be defined as:

$\begin{split}C^{B^{\prime}}_{i}&=C^{bin^{\prime}}_{i}\frac{\overline{w^{\Delta}_{i}}^{\prime}}{\overline{w_{i}}^{\prime}}\\\
&=\frac{n_{\Delta,i}^{\prime}}{d_{i}(d_{i}+1)}\frac{\frac{n_{\Delta,i}\overline{w^{\Delta}_{i}}+(n_{\Delta,i}^{\prime}-n_{\Delta,i})\epsilon}{n_{\Delta,i}^{\prime}}}{\frac{d_{i}\overline{w_{i}}+\epsilon}{d_{i}+1}}\\\
&=\frac{n_{\Delta,i}\overline{w^{\Delta}_{i}}}{d_{i}^{2}\overline{w_{i}}}+O(\epsilon)\\\
&=\frac{d_{i}-1}{k}C^{B}_{i}+O(\epsilon)\end{split}$ (20)

###  C.2 Onnela

As for the other definitions, the clustering from [11] can be defined as a
function of the binary clustering:

$C^{O}_{i}=\frac{n_{\Delta}\overline{I^{O}_{\Delta
ijk}}}{d_{i}(d_{i}-1)}=C^{\text{bin}}_{i}\overline{I^{O}_{\Delta ijk}}$ (21)

From this, one can define the evolution upon addition of an edge $(i,v)$ of
weight $\epsilon$ as:

$\begin{split}C^{O^{\prime}}_{i}&=C^{bin^{\prime}}_{i}\overline{I^{O}_{\Delta
ijk}}^{\prime}\\\
&=\frac{n_{\Delta}^{\prime}}{d_{i}(d_{i}+1)}\frac{n_{\Delta}\overline{I^{O}_{\Delta
ijk}}+O(\epsilon)}{n_{\Delta}^{\prime}}\\\
&=\frac{n_{\Delta}}{d_{i}(d_{i}+1)}\overline{I^{O}_{\Delta
ijk}}+O(\epsilon)\\\
&=\frac{d_{i}-1}{d_{i}+1}C^{O}_{i}+O(\epsilon)\end{split}$ (22)

###  C.3 Directed versions of the clustering coefficients

To generalize the Zhang-Horvath definition of clustering [12] for directed
graphs we use the same approach as proposed in Fagiolo [19]. These definitions
are visible in Table 7 together with the directed definitions associated to
Barrat [10] and Onnela [11], respectively defined in [20] and [19].

Mode |  $\boldsymbol{I^{O,(m)}_{\Delta,i}}$ |  $\boldsymbol{I^{B,(m)}_{\Delta,i}}$ |  $\boldsymbol{I^{B,(m)}_{T,i}}$ |  $\boldsymbol{I_{\Delta,i}^{Z,(m)}}$ |  $\boldsymbol{I_{T,i}^{Z,(m)}}$
---|---|---|---|---|---
Cycle |  $\left(W^{\left[\frac{1}{3}\right]}\right)^{3}_{ii}$ |  $\frac{1}{2}\left(WA^{2}+\left(WA^{2}\right)^{T}\right)_{ii}$ |  $\frac{1}{2}\left(s_{i,in}d_{i,out}+s_{i,out}d_{i,in}\right)-s^{B}_{i,\leftrightarrow}$ |  $\left(W\right)^{3}_{ii}$ |  $s_{i,in}s_{i,out}-s^{[2]}_{i,\leftrightarrow}$
Middleman |  $\left(W^{\left[\frac{1}{3}\right]}W^{\left[\frac{1}{3}\right]T}W^{\left[\frac{1}{3}\right]}\right)_{ii}$ |  $\frac{1}{2}\left(WA^{T}A+W^{T}AA^{T}\right)_{ii}$ |  $\frac{1}{2}\left(s_{i,in}d_{i,out}+s_{i,out}d_{i,in}\right)-s^{B}_{i,\leftrightarrow}$ |  $\left(WW^{T}W\right)_{ii}$ |  $s_{i,in}s_{i,out}-s^{[2]}_{i,\leftrightarrow}$
Fan-in |  $\left(W^{\left[\frac{1}{3}\right]T}\left(W^{\left[\frac{1}{3}\right]}\right)^{2}\right)_{ii}$ |  $\frac{1}{2}\left(W^{T}(A+A^{T})A\right)_{ii}$ |  $s_{i,in}(s_{i,in}-1)$ |  $\left(W^{T}WW\right)_{ii}$ |  $\left(s_{i,in}\right)^{2}-s^{[2]}_{i,in}$
Fan-out |  $\left(\left(W^{\left[\frac{1}{3}\right]}\right)^{2}W^{\left[\frac{1}{3}\right]T}\right)_{ii}$ |  $\frac{1}{2}\left(W(A+A^{T})A^{T}\right)_{ii}$ |  $s_{i,out}(s_{i,out}-1)$ |  $\left(WWW^{T}\right)_{ii}$ |  $\left(s_{i,out}\right)^{2}-s^{[2]}_{i,out}$
Table 7: Definitions of the Barrat, Onnela, and Zhang-Horvath intensities for
each partial mode pattern in directed graph. Column 1: pattern names; column
2: patterns illustration; column 3: Barrat triangle intensity for node $i$;
column 4: Onnela triangle intensity for node $i$; column 5: Zhang–Horvath
triangle intensity for node $i$; column 6: Zhang–Horvath triplet intensity for
node $i$. The clustering coefficients associated to each mode $m$ are given by
$C^{O,(m)}_{i}=I^{O,(m)}_{\Delta,i}/n^{(m)}_{T,i}$ for Onnela,
$C^{B,(m)}_{i}=I_{\Delta,i}^{B,(m)}/I_{T,i}^{B,(m)}$ Barrat and by
$C_{i}^{Z,(m)}=I_{\Delta,i}^{Z,(m)}/I_{T,i}^{Z,(m)}$ for Zhang–Horvath. Note
that, for Barrat, the reciprocal strength has been defined in [20] as
$s^{B}_{i,\leftrightarrow}=\sum_{i\neq j}\frac{1}{2}(w_{ij}+w_{ji})$.

##  Appendix D Closure

Closure was introduced in [13] as a complementary measure of clustering for
binary undirected networks.

###  D.1 Undirected weighted closure

From the Zhang–Horvath definition of clustering, closure can be generalized in
a fully-weighted but non-continuous way as

$H_{i}^{0}=\frac{\sum_{j\neq k}w_{ij}w_{jk}w_{ki}}{\sum_{j\neq k\neq
i}w_{ij}w_{jk}}=\frac{W^{3}_{ii}}{\sum_{j}w_{ij}(s_{j}-w_{ij})}$ (23)

again comparing the triangle intensities to their maximum possible value if
all open-walks of length two were closed into a triangle by an edge of weight
1.

Finally, it can also be defined in a continuous way as:

$H_{i}=\frac{\sum_{j\neq k}\sqrt[3]{w_{ij}w_{jk}w_{ki}}^{2}}{\sum_{j\neq k\neq
i}\sqrt{w_{ij}w_{jk}}}=\frac{\left(W^{\left[\frac{2}{3}\right]}\right)_{ii}^{3}}{\sum_{j}\left(W^{\left[\frac{1}{2}\right]}\right)_{ij}^{2}-s_{i}}$
(24)

###  D.2 Directed weighted closure

For directed networks, contrary to [27], we only consider the extension of the
undirected measure to directed walks and therefore define only four variants
of the directed closure, two for outgoing walks (cycle-out, CO, and fan-out,
FO) and two for incoming walks (cycle-in, CI, and fan-in, FI).

We define the weighted version either directly using the weights, as in the
Zhang–Horvath definition for the clustering coefficient:

$H_{i,CO}^{0}=\frac{\sum_{j\neq k}w_{ij}w_{jk}w_{ki}}{\sum_{j\neq k\neq
i}w_{ij}w_{jk}}=\frac{W^{3}_{ii}}{\sum_{j}w_{ij}(s_{j,out}-w_{ij})}$ (25)

$H_{i,CI}^{0}=\frac{\sum_{j\neq k}w_{kj}w_{ji}w_{ik}}{\sum_{j\neq k\neq
i}w_{kj}w_{ji}}=\frac{\left(W^{T}\right)^{3}_{ii}}{\sum_{j}w_{ji}(s_{j,in}-w_{ji})}$
(26)

$H_{i,FO}^{0}=\frac{\sum_{j\neq k}w_{ij}w_{jk}w_{ik}}{\sum_{j\neq k\neq
i}w_{ij}w_{jk}}=\frac{\left(W^{2}W^{T}\right)_{ii}}{\sum_{j}w_{ij}(s_{j,out}-w_{ij})}$
(27)

$H_{i,FI}^{0}=\frac{\sum_{j\neq k}w_{kj}w_{ji}w_{ki}}{\sum_{j\neq k\neq
i}w_{kj}w_{ji}}=\frac{\left(W^{T}W^{2}\right)_{ii}}{\sum_{j}w_{ji}(s_{j,in}-w_{ji})}$
(28)

Or via the continuous definition:

$H_{i,CO}^{c}=\frac{\sum_{j\neq
k}\sqrt[3]{w_{ij}w_{jk}w_{ki}}^{2}}{\sum_{j\neq k\neq
i}\sqrt{w_{ij}w_{jk}}}=\frac{\left(W^{\left[\frac{2}{3}\right]}\right)_{ii}^{3}}{\sum_{j}\left(W^{\left[\frac{1}{2}\right]}\right)_{ij}^{2}-s_{i,out}}$
(29)

$H_{i,CI}^{c}=\frac{\sum_{j\neq
k}\sqrt[3]{w_{kj}w_{ji}w_{ik}}^{2}}{\sum_{j\neq k\neq
i}\sqrt{w_{kj}w_{ji}}}=\frac{\left(W^{\left[\frac{2}{3}\right],T}\right)_{ii}^{3}}{\sum_{j}\left(W^{\left[\frac{1}{2},T\right]}\right)_{ij}^{2}-s_{i,in}}$
(30)

$H_{i,FO}^{c}=\frac{\sum_{j\neq
k}\sqrt[3]{w_{ij}w_{jk}w_{ki}}^{2}}{\sum_{j\neq k\neq
i}\sqrt{w_{ij}w_{jk}}}=\frac{\left({W^{\left[\frac{2}{3}\right]}}^{2}W^{\left[\frac{2}{3}\right],T}\right)_{ii}}{\sum_{j}\left(W^{\left[\frac{1}{2}\right]}\right)_{ij}^{2}-s_{i,out}}$
(31)

$H_{i,FI}^{c}=\frac{\sum_{j\neq
k}\sqrt[3]{w_{kj}w_{ji}w_{ki}}^{2}}{\sum_{j\neq k\neq
i}\sqrt{w_{kj}w_{ji}}}=\frac{\left(W^{\left[\frac{2}{3}\right],T}{W^{\left[\frac{2}{3}\right]}}^{2}\right)_{ii}}{\sum_{j}\left(W^{\left[\frac{1}{2},T\right]}\right)_{ij}^{2}-s_{i,in}}$
(32)

##  Appendix E Network generation algorithms

All networks were generated using the NNGT library [24].

###  E.1 Core-periphery network

The core-periphery network on Figure 1 contains:

  * •

1 central core node (CCN)

  * •

10 outer-core nodes (OCNs)

  * •

20 periphery nodes (PNs)

The nodes are connected as follow:

  * •

the 10 OCNs for a circular graph with fully reciprocal connections to their 4
nearest-neighbors,

  * •

the OCNs all connect to the CCN with reciprocal connections.

The weights associated to these connections are drawn from $U(5,10)$. The
connections with the PNs are as follow:

  * •

each OCN receive one connection from every other PN, starting with the first
or second PN depending on the OCN’s evenness,

  * •

the OCN reciprocate the connections with probability 0.5

  * •

the PNs are connected among themselves following an Erdős–Renyi scheme of
density 0.05.

Weights associated to connections involving PNs are drawn from $U(0.05,0.5)$.

###  E.2 Watts–Strogatz

The original Watts–Strogatz network [26] consists of a regular lattice basis
(characterized by a coordination number $k$) that is then modified, rewiring
each edge with a probability $p$. For directed networks, we used a
generalization of that method implemented in NNGT which is strictly equivalent
except for the fact that edges are now directed:

  1. 1.

start from a directed regular lattice with coordination number $k$ and
reciprocity $r$ (taken as 1 in this paper),

  2. 2.

rewire each edge with probability $p$.

The original lattice $L(N,k,r)$ has $\frac{1}{2}Nk(1+r)$ edges, leading to the
limit cases

  * •

$\frac{1}{2}Nk$ edges if $r=0$, like the undirected lattice,

  * •

$Nk$ edges if $r=1$, with all connections being reciprocal.

In the network used on Figure 2, we used a coordination number $k=20$ and a
rewiring probability $p=0.03$.

##  Appendix F Real-world networks

###  F.1 Mouse mesoscale connectome

The network was obtained from [22] and contains 426 nodes corresponding to
brain regions of intermediate scale connected by 65,465 edges. It is a
symmetric version of the original network that separates nodes from both
hemispheres. Each node is associated a “name” property corresponding of a
abbreviated denomination for the corresponding brain region, as well as a
suffix (left, or right) corresponding to the hemisphere. Edges are associated
three attributes: a “weight”, a “pvalue”, and a “distance” (corresponding to
the Euclidean distance from the source to the target node).

| Mean | STD | Median | Min | Max
---|---|---|---|---|---
In-degree | 153.7 | 25.6 | 152 | 104 | 223
Out-degree | 153.7 | 77.6 | 151 | 14 | 357
$CC^{bin}_{tot}$ | 0.43 | 0.02 | 0.43 | 0.38 | 0.49
Weights | 0.076 | 0.36 | 0.038 | 3.9$\cdot 10^{-16}$ | 20.4
Table 8: Some characteristic properties of the mesoscale mouse brain. Figure
6: Distribution of in/out-degrees (respectively in orange/yellow) and weights
in the mouse connectome.

###  F.2 Fediverse mesoscale network

The network was obtained from [23]222data available at https://dataverse.mpi-
sws.org/dataset.xhtml?persistentId=doi:10.5072/FK2/AMYZGS. It contains 3,825
nodes representing servers (instances) that are connected via 81,371 edges.
Each node is associated two attributes: a “name”, corresponding to the server
domain, and a “size”, $S_{i}$, corresponding to the number of users registered
on that server. Edges are associated four attributes: “num_follows”, defined a
$F_{ij}$, the number of followers from $i$ to $j$, “follow/size” defined as
$F_{ij}/S_{i}$, a “weight” given by $w_{ij}=F_{ij}/F_{i}$, the ratio between
the number of followers from $i$ to $j$ divided by the total number of
followers from $i$, and a “distance” giving the Euclidean distance between the
two servers on the latitude/longitude plane.

| Mean | STD | Median | Min | Max
---|---|---|---|---|---
In-degree | 21.3 | 82.6 | 4 | 0 | 2271
Out-degree | 21.3 | 77.8 | 5 | 0 | 2038
$CC^{bin}_{tot}$ | 0.68 | 0.37 | 0.86 | 0 | 1
Weights | 0.045 | 0.14 | 0.0029 | 6.0$\cdot 10^{-7}$ | 1
Table 9: Some characteristic properties of the Fediverse mesoscale network.
Figure 7: Distribution of in/out-degrees (respectively in orange/yellow) and
weights in the Fediverse instances.

###  F.3 Closure in the shuffled networks

The results obtained for the local closure confirm those obtained using the
clustering coefficient for the mouse brain and Fediverse networks, as show on
Figure 8. Namely, we see an overexpression of fan-in and fan-out patterns for
the mouse and a discrepancy between those two patterns for the Fediverse.

###  F.4 Networks with a high number of single-node triangles

The presence of nodes participating to a single triangle is frequently in very
sparse networks such as collaboration or gene/protein interaction networks.

Table 10 details several such networks:

NetScience

co-authorship in the network science
community333https://networkrepository.com/netscience.php

CompGeo

collaborations in computational geometry444http://vlado.fmf.uni-
lj.si/pub/networks/data/collab/geom.htm

CE-CX

a graph of gene associations inferred from co-expression pattern of two genes
(based on high-dimensional gene expression data) for C. elegans

CE-HT

gene associations inferred from high-throughput protein-protein interactions
for C. elegans

HS-HT

gene associations inferred from high-throughput protein-protein interactions
for Homo sapiens

SC-HT

gene associations inferred from high-throughput protein-protein interactions
for S. cerevisiae

Gene functional association networks [28] were downloaded from
https://networkrepository.com/bio.php.

Network | N | E | 1-T nodes (%)
---|---|---|---
NetScience | 1,589 | 2,742 | 23
CompGeo | 7,343 | 11,898 | 21
CE-CX | 15,229 | 24,5952 | 8
CE-HT | 2,617 | 2,985 | 2
HS-HT | 2,570 | 13,691 | 7
SC-HT | 2,084 | 63,027 | 5
Table 10: Number of nodes (N), edges (E), and fraction of single-triangle
(1-T) nodes in several collaboration and gene association networks. Figure 8:
Different structures of local closure in the mouse brain and Fediverse. The
panels compare the local closure of directed patterns for the mouse brain (A)
and Fediverse (B). The original values are compared to the averages over an
ensemble of graphs with the same adjacency matrix but shuffled edge weights.
For mouse: 10 uniformly shuffled networks, for Fediverse: 200 shuffling across
all out-going edges of a each node (to preserve out-strength normalization).
A. The local closure also shows an increase for patterns promoting redundancy
of information flow in the mouse brain (fan-in/fan-out motifs are higher in
the original graph). B. For the Fediverse, only fan-out is significantly
stronger than in the random graphs. Patters where the original values are
significantly greater (smaller) than the randomized ones are marked by the $+$
(resp. $-$) and initial of the method (brown, Z for Zhang; orange, C for
continuous; yellow, O for Onnela). The original closure is considered to be
significantly higher (resp. lower) if 75% of the points where above (resp.
below) the dotted identity line. Additional * denotes one-sided fractions
greater than 95%.