DOKK Library

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

Authors Anna Levina Tanguy Fardet

License CC-BY-4.0

                                PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

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

                                                    Tanguy Fardet      and Anna Levina
                                           University of Tübingen, Tübingen 72076, Germany
                               and Max Planck Institute for Biological Cybernetics, Tübingen 72076, Germany

                                 (Received 8 June 2021; accepted 18 October 2021; published 17 November 2021)

                 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 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 proposed continuous definition provide complementary results and significantly outperform
              other definitions in multiple relevant conditions. We demonstrate, using synthetic and real-world networks, that
              when the network is inferred, noisy, or very heterogeneous, it is essential to use the fully weighted clustering

              DOI: 10.1103/PhysRevResearch.3.043124

                      I. INTRODUCTION                                    stressed in multiple studies [1–4]. This is notably the case
                                                                         for the middleman motif, which is a marker of feedforward
    The clustering coefficient (CC) was originally introduced
                                                                         loops in transcriptional networks and of information trans-
for binary undirected networks to quantify strong connect-
                                                                         fer redundancy, e.g., in neuroscience. More generally, such
edness within a local neighborhood. It was defined as the
                                                                         motifs will influence the evolution of dynamical processes
fraction of all possible triangles that were realized, i.e., the
                                                                         on the networks, for instance, synchronization patterns, and
ratio between all triangles in which node i participates (n,i )
                                                                         have been shown to characterize families of networks such as
and the total number of triangles that could theoretically be
                                                                         transcription or language networks [2]. Finally, clustering is
made given its degree di , which is the number of triplets (nT,i ):
                                                                         used in other measurements to access the small-world propen-
                             n,i       n,i                             sity of networks [5], and the choice of a specific definition
                   Cibin =        =             .               (1)
                             nT,i   di (di − 1)                          can therefore influence whether the network of interest will
                                                                         register as small world or not.
From a neighbor-centric perspective, it can be seen perhaps                  In many applications, network topology and weights are
more intuitively as the probability that two neighbors of a              measured only up to a certain precision [6,7]. For example, in
node are connected. However, as network science expanded,                neuroscience, the functional connectivity networks are mea-
more and more graphs were encountered, where directedness                sured using the indirect inference of connections from the
and edge weights play a central role. Generalizations of the             recorded activity [8,9]. Accepting the inevitability of noise in
clustering coefficient were therefore introduced to account              a network brings forward new requirements on the network
for asymmetry in the connections between pairs of nodes or               measures, namely, that they are stable to the noise and do
heterogeneity in their strength.                                         not change dramatically if the weights are perturbed or weak
   The importance of clustering, including its directed vari-            connections are randomly omitted.
ants, to understand complex dynamics on networks has been                    There is no agreement among researchers as to which
                                                                         weighted extension of the clustering coefficient definition is
                                                                         most appropriate. The three predominantly used methods at
                                                                         the moment [10–12] differ in many properties of their def-
Published by the American Physical Society under the terms of the        initions. Part of the reason for the absence of a single best
Creative Commons Attribution 4.0 International license. Further          weighted clustering lies in a different interpretation of weights
distribution of this work must maintain attribution to the author(s)     in various data sets. Consequently, a different weighted exten-
and the published article’s title, journal citation, and DOI. Open       sion might be most appropriate for various data and specific
access publication funded by the Max Planck Society.                     scientific questions. However, to understand which method to

2643-1564/2021/3(4)/043124(16)                              043124-1                             Published by the American Physical Society
TANGUY FARDET AND ANNA LEVINA                                                       PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

use when and why, we need to understand their differences             factor [the global max(w)] as long as the normalization con-
precisely.                                                            dition is fulfilled since only the normalization matters. We
   The difficulty of extending graph measures to weighted             omitted the last two conditions of Saramäki et al.’s paper
networks is not specific to the clustering coefficient but can        (invariance to weight permutation and ignorance of weights
occur whenever ratios of degrees or path length are involved.         not participating in any triangle). Although they might be of
We will therefore also discuss a second clustering-related            interest for some specific applications, we do not consider
measure, called the closure coefficient and introduced as the         them to be generally desired properties for a clustering co-
fraction of all open walks of length 2 starting from node i that      efficient. Indeed, the clustering coefficient is a node-centric
are part of a triangle [13]. This will also enable us to discuss      measure, so there is no reason to expect invariance when the
the complementarity of closure and clustering as the former           weights of a node’s edges change. As for edge ignorance, in
provides an important complement to analyze the tendency of           the original classifying paper [14] this property is introduced
nodes to form 3- and 4-cliques.                                       as a particular feature of the Onnela et al. [11] definition, with-
   We introduce here a distinction between fully weighted             out reasons why it may be a desired condition. We also did
and hybrid definitions and discuss why, for several classes           not require that all weights in a triangle should be accounted
of networks, fully weighted and directed definitions should           for because this condition is necessarily met if the continuity
be preferred to other clustering definitions that are currently       condition is fulfilled.
used for network analysis. We also propose a definition that              Continuity can be expressed mathematically as follows: for
obeys additional conditions, including continuity of the results      a graph G(V, E ), if a weighted edge (u, v, w) with u, v ∈ V
with respect to infinitesimal changes in edge weights, which          and weight w ∈ R is added to this graph to form a new graph
has significant consequences for the resilience to noise in in-       G (V, E  ), with E  = E + {(u, v, w)}, then the clustering mea-
ferred networks. We demonstrate why fully weighted methods            sure is continuous if and only if ∀i ∈ V , Ci(G ) −−−→     +
                                                                                                                                    Ci(G) .
are essential for measured and inferred networks, which are                                                                  w→0
                                                                      This condition in crucial to ensure a reasonable behavior of
pervasive in biological fields such as neuroscience, and for
                                                                      the clustering coefficient in inferred networks.
networks dealing with flows of information, money, or goods
                                                                          Though some definitions of previously proposed weighted
that display a very broad weight distribution.
                                                                      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
  II. INTERPRETATION AND PURPOSE OF WEIGHTED                          later propose a definition that fulfills all aforementioned con-
                   CLUSTERING                                         ditions. An extensive comparison of the properties fulfilled by
    A. Desired properties of weighted clustering coefficients         different clustering definitions can be found in Appendix B.
    Weighted measures are crucial for many network types
where the binary connectivity is either uninformative (fully
connected network) or displays similar or lower heterogeneity                     B. State of the art for weighted clustering
compared with the weighted structure. In this paper, we focus              First we introduce and classify the existing weighted clus-
on two classes of real-world networks: inferred or measured           tering coefficient definition. For all clustering definitions in
networks where there can be a large number of spurious                the main text, we use the following notation: A is an adja-
(false positive) edges with small weights; and networks asso-         cency matrix, and W = {wi j } is the normalized weight matrix,
ciated with flows of information or goods, which often display        obtained from the original weight matrix W̃ = {w̃i j } by wi j =
broad weight distributions. This is notably the case for many         w̃i j / maxi, j (w̃i j ).
networks in neuroscience, and more generally in informa-                   Hybrid definitions were the first extensions of the binary
tion, transportation, or other social and economic networks.          clustering coefficient definitions. They combine properties
Weights are essential to understand the dynamical processes           associated with a weighted connectivity matrix (i.e., the in-
that occur in these networks, requiring measures that go be-          tensity of the triangle) with properties that could be already
yond the binary structure.                                            obtained from an adjacency matrix (i.e., node degrees). These
    There could be multiple requirements for weighted clus-           definitions move from an integer counting the number of trian-
tering coefficients [14] depending on the particular question         gles (n ) to a sum of real numbers (computed as a function of
of interest and on the network properties. The main require-          edge weights) that we call “intensities” of triangles (I ). The
ments that we considered necessary for a weighted clustering          choice of a particular function for the intensity of the triangles
coefficient are (i) normalization (Ci ∈ [0, 1]), (ii) consistency     determines the properties of the clustering coefficient.
with the binary definition (for binary networks, it should                 Two popular hybrid weighted clusterings were given by
give back the classical result), (iii) linearity (scaling by α all    Barrat et al. [10] and Onnela et al. [11], which we will refer
edges involving node i and all edges in triangles including           to as the Barrat and Onnela definitions, respectively.
node i scales Ci by α), and (iv) continuity (weak influence of             For a node i in a graph, the Barrat definition [10] quantifies
the addition or deletion of edges having very small weights,          the fraction of the node’s strength that is invested in triangles
meaning that an edge with infinitesimally small weight should         (see Appendix C 1 for more details):
be equivalent to the absence of that edge).
    Compared with a previously proposed list of conditions
given by Saramäki et al. [14], we added a continuity condition                                  (WA2 )ii           w
                                                                                       CiB =                = Cibin i ,                (2)
but did not include a requirement of a specific normalization                                  2si (di − 1)        wi

WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS …                                            PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

where si =        j=i   wi j is the strength of the node, wi is                TABLE I. Limit values for undirected weighted clustering coeffi-
                                                                            cients of vertex i (solid circles) for different weight configurations in
the average weight of the edges involving i, and wi =
      wi j +wik                                                            graphs with vanishing weights. Solid lines depict edges of weight
   j=k 2n,i ai j aik a jk is the average weight of edges involving        w = max(w) = 1, and dotted lines denote edges with vanishing
i that are part of a triangle computed over all triangles in                weight . Only the proposed continuous clustering (bottom row)
which node i participates. In terms of triangle intensity, this             returns values consistent with the continuity condition, whereas the
definition was originally written as                                        Barrat (C B ), Onnela (C O ), and Zhang-Horvath definitions (C Z ) devi-
                             wi j +wik                                     ate for it.
                        j=k       2
                                        ai j aik a jk
             Ci =
                            2si (di − 1)
                           1          wi j + wik
                 =                                    ai j aik a jk , (3)
                    di (di − 1) j=k            2wi

thus defining the intensity of triangle i jk as Ii              B
                                                                    jk =
wi j +wik
          ai j aik a jk as the function of two of the triangle’s weights
and the average weight of the edges connected to node i, wi .
     Proposed a bit later, the Onnela definition [11] scales the             Z (max)
                                                                            Ii      = ITZi jk = wi j wik if all existing triplets Ti jk were closed
binary clustering by the average intensity of the triangles (see                jk
                                                                            by an edge of weight 1 (the maximum possible weight in the
Appendix C 2 for more details):
                                                                            normalized network). This way, if i is involved in a single
                                  1 3                                     triangle, the clustering coefficient is equal to the weight of
                                  W [ 3 ] ii
                        Ci =
                                             = Cibin Ii
                                                      O ,             (4)   the edge closing the triplet centered on i (see also Table I).
                                di (di − 1)              jk
                                                                                Though this definition does not fulfill the continuity
                                                jk = (wi j wik w jk )
                                            O                         1/3   property, we will show that it still provides a consistent in-
with the triangle intensity defined as Ii
and the average intensity taken over all triangles in which i               terpretation of weighted clustering, as discussed in Ref. [16],
participates.                                                               and is well suited to tackle networks with a large fraction of
    For all hybrid methods the denominator relies on the node’s             false positives.
degree, meaning that the addition or deletion of edges will                     Other fully weighted definitions that have been proposed
always significantly affect the clustering coefficient even if              and discussed since [15,17,18] do not bring significant ad-
the edge has an infinitely small weight. Such methods can                   ditions compared with the Zhang-Horvath definition while
thus lead to inaccurate results when applied to the inferred net-           actually losing some of its properties and its straightforward
works, where a significant fraction of edges are false positives            interpretation. They are not considered further in this paper;
with small weights. In the following we will also demonstrate               see Appendix A for further explanations.
that they cannot reliably detect the most strongly clustered
nodes in structured networks. Only fully weighted definitions                C. A continuous definition for weighted clustering and closure
can rise up to these challenges.
                                                                              For an undirected graph G, we define the proposed contin-
    Fully weighted definitions are variants of the clustering
                                                                            uous clustering of node i as
coefficient that do not include any binary measures (anything                                               
                                                                                                    2                 √               2
that can be derived from the adjacency matrix alone, e.g.,                                    j=k Ii jk      j=k ( wi j w jk wik )

degrees). In addition to substituting the number of triangles                        Ci =                 =    √                      . (6)
                                                                                              j=k IT i jk          j=k w ji wik
by the sum of triangle intensities, they also move away from
counting triplets—defining the maximum number of possible                   We define the weighted intensity of triangles and triplets,
                                                                                     √                            √
triangles max(n,i ) = nT,i = di (di − 1). Instead, they intro-             Ii jk = 3 wi j w jk wik and IT i jk = w ji wik , respectively, using
duce the triplet intensity IT such that, for a node i, IT,i is a            the geometric mean of the weights involved. Because of this,
real-valued function of the weights associated with i.                      one strong weight in a triangle or triplet cannot compensate
    One of the first fully weighted definitions for the cluster-            the presence of smaller weights, in contrast to what may
ing coefficient was provided by Zhang and Horvath [12] to                   happen if one uses the arithmetic mean. This provides the
analyze gene coexpression networks:                                         desired property that the intensity of triangles and triplets will
                                                                            go to zero if even a single edge weight goes to zero. Note
                       j=k wi j wik w jk   Ii  jk bin                     that, though the triangle intensity is defined as the geometric
              Ci = 
                                          =         Ci ,             (5)
                              w   w
                          j=k i j ik
                                            IT i jk                         mean of the three weights involved, it is the square of this
                                                                            intensity that is used in the definition. The reason for this
which we will refer to as the Zhang-Horvath definition. Note                choice is twofold: to assign higher influence to large triangles
that the fact that the definition can be expressed as a function            and to ensure the linearity of the coefficient. Importantly, this
of the binary clustering does not contradict the fully weighted             definition of the triangle intensity I assigns the same role to
nature of the measure, as it stems from a simple recombination              all participating edges. The proposed clustering could be in-
of the terms.                                                               terpreted as the ratio of the triangle intensity that is invested in
   This definition can be interpreted as the ratio of                       strong triangles (given by the sum of the squared intensities of
                                jk = wi j wik w jk of the triangles
the summed intensities Ii                                                  triangles, which increases the importance of strong triangles)
i jk = (i, j, k) to the maximum possible summed intensities                to the triplet intensity, which would represent the maximum

TANGUY FARDET AND ANNA LEVINA                                                                    PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

    TABLE II. Definitions of the continuous intensities for each partial mode pattern in directed graphs. Column 1, pattern names; column 2,
pattern 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; and column 6, continuous intensities of triplets for node i. The clustering coefficients associated with each mode m are
given by Ci(m)bin = n,i
                                for binary networks and Ci(m) = I,i /IT,i for the continuous definition.
                                                                 (m) (m)

possible triangle intensity if all weights connecting adjacent                  tained via the formula
nodes were equal to 1.                                                                                                
    The proposed continuous definition fulfills all the condi-                                                   Cg = i       .                          (9)
tions we put forward above, and to the best of our knowledge                                                            i IT,i
it is the only one to do so. Similarly to previous definitions, the
proposed clustering coefficient can also be rewritten in terms                                         D. Directed weighted clustering
of node properties:                                                                 Fagiolo [19] proposed how to generalize clustering to di-
                                      2 3                                     rected networks. He defined the different patterns or motifs
                                      W[3]                                      (shown in Table II) that can exist in these networks and
                              Ci =  1  ii ,                            (7)    adapted the Onnela definition [11] as the first weighted di-
                                     [ ] 2
                                    si 2   − si                                 rected clustering coefficient. The Barrat definition [10] was
                                                                               generalized to directed graphs in Ref. [20] following the same
where si = j=i wi j is the normalized strength of node i                       distinction into Fagiolo’s cycle, middleman, fan-in, and fan-
and W [α] = wiαj and si[α] = j=i wiαj are the fractional weight                out motifs.
matrix and strength for any α ∈ R.                                                  Similarly, the Zhang-Horvath definition [12] and the con-
   As for the previous definitions, the continuous clustering                   tinuous definition can be generalized in a straightforward
can be interpreted as a function of intensities and the binary                  manner for directed networks. For this, we only need to
clustering:                                                                     redefine the intensities of each directed triangle and triplet
                                                                                motif (as shown in Table II for the continuous definition and
               2             2                                    2
           n Ii jk        Ii jk              Var(Ii jk ) + Ii jk bin       in Table VII for the Zhang-Horvath definition). This simply
  Ci =                  =             Cibin =                        Ci , (8)   requires replacing A with W in all expressions of n,i  (m)
           nT IT i jk       IT i jk                    IT i jk
                                                                                a with w in all expressions of nT,i . As the total directed
with means Ii jk and IT i jk and variance taken over all the                   clustering is defined as the sum of all modes, we can write
triangles or triplets the node i participates in, respectively.                 it as
In the limit where all triangles associated with node i have                                          Z (tot)
                                                                                                     I,i                   (W + W T )3ii
similar intensities, we can neglect the variance term, leaving                       CiZ (tot)   =              =                                   .   (10)
                                                                                                                     j=k (wi j + w ji )(wik + wki )
                                                                                                      Z (tot)
Ii jk
       Cibin . In this case, in contrast to the Zhang-Horvath def-
 IT i jk
inition [Eq. (5)], the absolute value of the intensity matters,                    Finally, the continuous clustering can be extended for each
not only its ratio to the maximum possible intensity. For a                     directed mode (see Table II), and for the total directed cluster-
given average triangle intensity, the positive contribution of                  ing, this leads to
the variance implies that nodes with more variable intensities,                                                  2             2  3
i.e., at least one triangle with a high intensity, will have higher                           (tot)
                                                                                                     I,i     1
                                                                                                                 W [ 3 ] + W [ 3 ]T ii
                                                                                            Ci = (tot) =  1 2
                                                                                                                                       ,    (11)
clustering coefficients than nodes with identical triangles of                                                 [2] 2
                                                                                                     IT,i     si,tot   − si,tot − 2si↔
average intensity.
    Finally, the global clustering can also be defined in a                                                                              [ 21 ]
                                                                                with si,tot = j (wi j + w ji ) being the total strength, si,tot  =
                             For simplicity, we define I,i =
                      fashion.                                                        1         1
    j=k Ii jk and IT,i =
                                j=k IT i jk , leading to Ci = I,i /IT,i .
                                                                                     (w + w ji ) being the total root strength, and si =
                                                                                       2         2
                                                                                j √ij
Using this definition, the continuous global clustering is ob-                     j   wi j w ji being the reciprocal strength.

WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS …                                             PHYSICAL REVIEW RESEARCH 3, 043124 (2021)



    FIG. 1. Only the continuous clustering coefficient uncovers the true structure in the weighted core-periphery network. A network has 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; the edge width gives the strength of the connection,
and the node color gives its clustering coefficient. (b) Distribution of clustering coefficients for the three types of nodes over ten realizations of
such a core-periphery network. Only the continuous definition differentiates between the central, the outer-core, and the periphery nodes. In all
the other methods, the clustering coefficients of the 10 “outer-core” and 22 periphery nodes overlap: The Onnela definition only distinguishes
the central node, whereas the Barrat and Zhang-Horvath definitions do not hint at a core-periphery structure.

   As for the undirected case, the global clustering coefficient                    A. Sensitivity to weight-encoded topological features
associated with each
                 (m) directed
                           (m)pattern can be obtained via the                  Here, we investigate how weighted structures can be de-
formula Cg(m) = i I,i  / i IT,i  .                                          tected or missed using different clustering definitions. As
                                                                             an example we consider weighted core-periphery graphs in
       III. THE ADVANTAGES OF FULLY WEIGHTED                                 Fig. 1. There, core nodes are characterized by both a dense
                     DEFINITIONS                                             binary connectivity and large weights, whereas periphery
    In this section we discuss the sensitivity to the weight-                nodes display both sparser connectivity (though they still
encoded topological features and stability to noise in network               have large degrees) and weaker weights; for more details, see
measurements of the different clustering methods. A previous                 Appendix E 1. We generate ten realizations of the network
study [14] already noted the fact that previous definitions did              and consider distribution of clustering coefficients of differ-
not fulfill the continuity condition by analyzing the behavior               ent types of nodes. Continuous definition leads to distinct
of the different coefficients for nodes that participate in a                clustering of different types of nodes, making the true struc-
single triangle. Table I illustrates some of these cases and                 ture of the network clearly visible already in the clustering
shows that the proposed continuous definition is the only one                distributions. Because of their hybrid nature, the Barrat and
to behave as expected.                                                       Onnela definitions cannot capture this underlying structure
    Yet we note that the Zhang-Horvath definition is also very               as it is mostly encoded in the weights and not at all in the
resilient to noise because, except for the corner cases asso-                degrees (core nodes are not binary hubs). Though it is purely
ciated with single triangles, its behavior is continuous in all              weighted, the Zhang-Horvath definition is also not suited to
other situations. Moreover, contrary to what was asserted in                 detect this type of weighted structure because its interpretation
Ref. [14], it provides a perfectly sensible behavior given its               of a node’s clustering only accounts for the relative triangle
interpretation of clustering as the ratio of the triangle intensity          intensity given the node’s weights.
                                                                                The continuous clustering is sensitive to any topological
    jk = wi j wik w jk to its maximum possible intensity given the
                        Z (max)                                              property that is encoded via specific weight distributions.
weights of node i: Ii     jk   = ITZi jk = wi j wik if w jk = 1.            Furthermore, in contrast to the Zhang-Horvath definition, it
    Because the Barrat and Onnela definitions [10,11] are the                accounts not only for the ratio of the triangle intensity over
most well known and (to the best of our knowledge) the only                  the triplet intensity (how strong the triangles are compared
methods implemented in popular graph libraries, we restrict                  with the maximum possible value given the node’s weights)
our comparison to the Zhang-Horvath definition and these                     but also for the absolute value of the intensity: A weak tri-
two definitions. A more comprehensive discussion of other                    angle, even if it corresponds to the highest possible value
definitions of the weighted clustering coefficient can be found              given the node’s weights, will decrease the node’s clustering
in Appendix A.

TANGUY FARDET AND ANNA LEVINA                                                             PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

(a)                                (b)                                 (c)                                  (d)

(e)                                (f)                                  (g)                                 (h)
                                                                                                                                        (a) (c)
                                                                                                                                        (a)   (d)
                                                                                                                                        (b) (c)
                                                                                                                                        (b)   (d)

    FIG. 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 [Erdős-
Rényi (ER)] or (b) scale-free (SF) 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 with the distributions associated with the measured networks
for each method (dashed lines). Weight and noise types, combining noise shown in (a) or (b) with weight shown in (c) or (d), which we refer
to as conditions “(a)+(c),” “(a)+(d),” “(b)+(c),” and “(b)+(d),” are associated with colors from brown to orange in the same order as in
(h). Distributions associated with the exponential noise [conditions (a)+(d) and (b)+(d)] differ most from the original distributions for the
Zhang-Horvath and continuous clusterings [(e) and (f)] and are broader for the Onnela clustering (g). (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 condition (a)+(d), with R2 > 0.55, and only lose the original information for condition (b)+(d). The results were obtained
for ten realizations of the spurious edges; error bars give confidence intervals. Network properties are detailed in Appendix E. Z, C, O, and B,
Zhang-Horvath, continuous, Onnela, and Barrat definitions, respectively.

in the continuous definition whereas it increases it with the                   We illustrate the impact of spurious edges on measured
Zhang-Horvath method. In that sense, the continuous clus-                    clustering coefficients using the example of Watts-Strogatz
tering provides a more global evaluation of the clustering                   small-world networks. We consider different topologies for
coefficient compared with the Zhang-Horvath definition that                  the subnetwork formed by the spurious edges: either an
provides more local information.                                             Erdős-Rényi random network [Fig. 2(a)], associated with un-
    The Barrat definition has several limitations because it is              correlated noise, or a scale-free network [Fig. 2(b)], which
close to being weight insensitive [11,21]. It is particularly                would correlate noise with certain nodes in the network.
unsuitable for assessing networks with a potentially large                   Additionally, weights on the spurious edges could be much
number of low-weight spurious connections or very hetero-                    smaller than the weight of the actual edges [Fig. 2(c)] or
geneous weight distributions. For this reason, we will mostly                have an overlapping distribution [Fig. 2(d)]. We refer to the
leave this clustering aside in the rest of this paper.                       combinations of these noise and weight types as conditions
                                                                             “(a)+(c),” “(a)+(d),” “(b)+(c),” and “(b)+(d).” Both fully
              B. Continuity and resilience to noise                          weighted methods are unaffected by low noise [conditions
    The stability of a network measure to noise is of particular             (a)+(c) and (b)+(c)] and are also less influenced by the spuri-
importance for networks that are obtained via experimental                   ous edges when their weights are large enough to overlap with
measurements since these are often subject to noise and sta-                 the real weight distribution [conditions (a)+(d) and (b)+(d)].
tistical biases, notably for inferred networks. Methods abiding              On the other hand, because hybrid methods explicitly depend
by the continuity condition are especially resilient to the pres-            on the nodes’ degrees, they are very susceptible to the pres-
ence of low-weight spurious edges. Violation of continuity                   ence of spurious edges [Figs. 2(g) and 2(h)].
can have significant and pervasive consequences for inference                   The difference in behavior between the methods can be
of network properties in many network structures. We have                    easily explained by a first-order expansion. We consider
already seen the simple examples in Table I; here, we demon-                 change in the clustering coefficient of a node i with degree
strate that they are not just corner cases, but occur in larger,             di after addition of a spurious edge e = (i, v) with weight
real-world networks.                                                             1. For the Barrat and Onnela methods, the new clustering


coefficient becomes                                                spurious that is lower than 1%. We consider a thresholding
                    1                                            procedure, where at each level of the threshold (pmax ), only
         I,i +O 3         di − 1 O        1  →0               the edges with smaller p values are kept. This procedure can
 Ci =                   =          Ci + O  3  CiO ,
          di (di + 1)       di + 1                                 be seen as an attempt to remove spurious edges, though no
                  +wik                                           correct threshold level is known. Compared with the hybrid
        I,i + k 2 avk aik
                                     di − 1 B         →0
 CiB =                            =         Ci + O()  CiB ,      method, both fully weighted definitions are much less sensi-
              IT,i + si + 
                B                       di                         tive to thresholding [Figs. 3(b) and 3(c)]. Thus we see that
meaning that, for both methods, the coefficients will deviate      the resilience to noise we showed analytically and on toy
                                                                   networks is relevant for a real-world network. Furthermore,
from the original clustering CiO/B by a noninfinitesimal value,
                                                                   the resilience is not limited to the general shape of the dis-
even when the perturbation was infinitesimal; see Appendix C
                                                                   tribution but indeed preserves the precise values and ranks:
for a complete derivation.
                                                                   A larger fraction of the nodes displaying high clustering in
   On the other hand, the continuous clustering becomes
                                                                   the full graph are still among the highest ranking nodes in
                                                                   the thresholded graphs when fully weighted methods are used
                    I,i + k∼i ( wvk wki ) 3
              Ci =                                                 compared with the hybrid method [Figure 3(e)].
                                     [ 1 ]√
                         IT,i + 2si 2                                 The clustering coefficient is a network measure that cap-
                               [ 1 ]√                            tures features beyond purely local parameters, such as degree
                              2si 2             2               or strength. However, as we see for the mouse connec-
                 = Ci 1 −                  +O 3
                                 IT,i                              tome, the hybrid method strongly correlates with the average
                             √                                     weight associated with a node i: si /di . At the same time,
                 = Ci + O( ) −−−→        +
                                            Ci ,           (12)    the fully weighted definitions are much less correlated with
                                                                   it [Fig. 3(d)]. As a result, they can bring more independent
showing only an infinitesimal deviation to the similarly in-       information regarding the weighted network structure than the
finitesimal perturbation.                                          hybrid method. This trend is even stronger for the Zhang-
    Similarly, except for the single-triangle cases discussed in   Horvath definition, which does not account for the absolute
Table I, the Zhang-Horvath clustering becomes                      intensity of triangles. In contrast, the continuous definition
                                                                   provides some intermediate behavior as the intensity of trian-
                I,i + O()
        CiZ =                 = CiZ + O() −−−→ CiZ .      (13)    gles often correlates, if only in part, with the average weight
                 Z + O()
                IT,i                          +
                                            →0                    associated with the node.
                                                                       Finally, though the continuous and Zhang-Horvath defini-
   It is worth noting that one continuity issue, associated with
                                                                   tions often provide somewhat similar results, they may differ
nodes participating in only one triangle, occurs for all defini-
                                                                   significantly, e.g., for the cerebellar cortex in Fig. 3(f). Com-
tions but the continuous one. Since this situation is pervasive    bining the results of both methods can thus be informative,
in networks with low degree or binary clustering, using the        for example, to single out nodes that possess only weak con-
continuous clustering definition can be of particular impor-       nections (and will therefore register as weakly clustered for
tance in such cases; see Appendix F 4.                             the continuous definition) yet connect to other nodes that are
                                                                   strongly connected (thus registering as strongly clustered for
    IV. APPLICATION TO REAL-WORLD NETWORKS                         the Zhang-Horvath definition).
                A. Mouse mesoscale connectome
                                                                            B. Decentralized social media: The Fediverse
    In neuroscience, the networks on different scales give a
vital piece of information to understand the brain better. Un-         The Fediverse [23] is a set of federated social media that
surprisingly, connectomics, the mapping of the connections in      can communicate via a collection of common protocols [24],
the nervous system, has gained significant attention and devel-    the most well known being ActivityPub. This network can be
oped dramatically over the last years. Most of the networks in     seen as a set of alternatives to corporate platforms such as
neuroscience are weighted, and the obtained connectivities are     Facebook or Twitter. Social media on the Fediverse usually
either measured or inferred, making them a typical example         promote ideas of decentralization, interoperability, free/libre
for the challenges discussed above. The mouse mesoscale            and open-source software (FLOSS), and the absence of algo-
connectome [22] is a fascinating example of such networks,         rithmic filters in favor of human curation and moderation.
both because it provides information about the entire mouse            We analyze here a snapshot of this network that was ob-
brain and because it contains an evaluation of the probability     tained in 2018 by Zignani et al. [25] (data are available [26]).
of false positives for all connections.                            In contrast to the original publication, we chose here to look
    Here, we investigate how the choice of the clustering co-      at the mesoscale level, i.e., at connections between instances
efficient definition can alter the results. The network is very    (the equivalent of a community on the Fediverse, where at
inhomogeneous, with broadly varying degrees [Fig. 3(a)]. The       least one, but up to several thousand users can have an ac-
edges in the mesoscale connectome are assigned p values            count). This mesoscale view leads to a network of weighted
that quantify their probability to correspond to a real physical   directed interactions between communities of strongly con-
connection (p denotes the probability of the connection to be      nected users. Indeed, users of a single instance (the technical
a spurious edge). They have therefore different significance       name for a community on the Fediverse) can see and interact
levels, with only 13% of all edges having p values smaller         with all public messages posted by other members on that
than 0.01, i.e., only 13% of all edges have a probability to be    same server. At the same time, they can only see a subset of

TANGUY FARDET AND ANNA LEVINA                                                               PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

    FIG. 3. For the mouse connectome, different clustering methods give significantly different results. (a) Top view of the mouse brain; node
size indicates the total degree, and node color indicates the out-degree (lighter colors for higher degrees). (b) Distribution of the total clustering
coefficients if only edges with the p value p < pmax are preserved. There are smaller changes in clustering distribution for fully weighted
definitions than for the Onnela definition. From pale yellow to dark gray, thresholding keeps 9, 13, 32, and 100%, respectively, of the original
network. (c) The fraction of the nodes with the highest total clustering (top 5, 10, and 25%) that are preserved across all subsamplings in (b) for
the Zhang-Horvath (brown), continuous (orange), and Onnela definitions (pale yellow). (d) Correlation of the three total clustering definitions
with average total node weight (si /di ) shows that fully weighted definitions capture additional information beyond degree and strength. (e)
Fraction of the 10% highest clustering nodes that are common between two of the definitions (filled markers in the right panel include the
central region of the left panel) or among all three definitions (black crosses, central region) as shown in the Venn diagram. (f) Clustering ranks
of the areas within brain regions (showing which regions contain nodes with high clustering coefficients) can significantly vary depending on
the definition (Zhang-Horvath, brown; continuous, orange; and Onnela, pale yellow).

the posts from people on other servers (either because they                  3825 nodes represent more than half of the entire network
follow their author or because other members of the instance                 and are connected via 81 371 edges. A chord diagram of
follow the author or shared this specific post).                             connections between locations shows that, besides the fact
   For each instance I1 , an edge towards another instance I2                that the position of most instances is unspecified (UNS), the
means that at least one user on I1 follows at least one member               largest hosting countries are Japan, the United States, and
of I2 . The precise value of the weight associated with this                 France, with Japanese and French communities interacting
edge gives the fraction of all followers from the source in-                 mostly among themselves [Figs. 4(a) and 4(b)]. The network
stance that are associated with members of the target instance.              is both very sparse and strongly heterogeneous, with a median
The weights are thus a proxy to characterize the fraction                    degree of 5 but node degrees and sizes varying over 3–5 orders
of the community’s attention that is associated with content                 of magnitude. This broad distribution has notable implications
produced by another community; this means of course that,                    for different clustering definitions. For the Zhang-Horvath
for each node, its outgoing strength so is equal to 1. Note                  definition, it increases the likelihood of running into the corner
that in this network, information flow occurs in the direction               cases of single triangles, increasing the average clustering
opposite to that of the edge, because the directed edge denotes              compared with the other methods. For the Onnela definition,
that the source is paying attention to what the target posts.                it strongly correlates clustering values to the degree (and thus
   The network snapshot contains 3825 nodes corresponding                    to the size) of the instance.
mostly to instances running Mastodon [27], one of the most                       As for the mouse network, all weighted methods lead to re-
prominent microblogging platforms on the Fediverse. These                    sults that differ strongly from the binary clustering [Figs. 4(d)

WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS …                                            PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

      (a)                           (b)

(c)                                 (d)                                 (e)                                 (f)

    FIG. 4. Properties of the network of Fediverse instances. (a) Chord diagram of connections between locations (DEU, Germany; FRA,
France; JPN, Japan; UNS, unspecified; USA, United States of America). (b) Spatial representation of the network showing connections that
amount to at least 1% of the strongest connection; nodes are placed on each country’s capital, and their sizes represent the number of instances
hosted in that country. The zoom on Europe shows all connections in the European subnetwork. (c) The count of users per instance follows a
heavy-tailed distribution. (d) The network displays strong structural clustering, most nodes with nonzero in- and out-degrees displaying binary
clustering values close to 1, whereas the expected value for an Erdős-Rényi 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 the 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.

and 4(e)]. Some of the results from the hybrid method tend to                 the brain is indeed associated with situations where a signal
correlate strongly with some first-order properties of the nodes              can be transferred not only directly from one node to another,
[Fig. 4(e)], whereas the fully weighted methods bring more                    but also indirectly via a third (middleman) node, as can be
independent information. The Fediverse network displays a                     seen in middleman, fan-in, and fan-out patterns (cf. Table II).
peculiar feature as its fan-out and fan-in clusterings differ                 This overexpression of redundant patterns is visible, for the
significantly despite the usual correlation between these two                 fully weighted methods, in the high values of the middleman,
patterns, as can be seen from the comparison of Figs. 4(e) and                fan-in, and fan-out motifs in Fig. 5(a).
4(f).                                                                            The situation for the Fediverse is significantly more com-
                                                                              plex. Indeed, 98% of all edges belong to at least one triangle,
                                                                              and some are involved in up to thousands of triangles. A
      C. Using local clustering to infer dynamical properties                 deeper understanding of the clustering requires precise in-
    Analysis of the clustering coefficient for different struc-               vestigation of how the weight distribution correlates with
tured patterns offers a way to obtain a precise idea of                       specific patterns of triangles. For instance, though fan-in and
the critical dynamical patterns within a network. To deter-                   fan-out patterns co-occur and are thus usually correlated, the
mine the significance of a particular pattern, we compare its                 Fediverse displays an unexpected discrepancy between the
prominence in the original network with its prominence in                     weights associated with the two patterns, as seen in Fig. 5(b),
null-model networks obtained via appropriate randomization.                   which notably differentiates it from the mouse connectome
For the mouse brain, as a randomized control, we take the                     (see also Appendix F 3).
original network and only shuffle the weights, thus preserving
the weight distribution and binary structure. Comparing the
                                                                                                     V. DISCUSSION
actual values in the original graphs with those of the random-
ized graphs, we can see the importance of looking at fully                       In this paper, we introduced directed weighted definitions
weighted measures.                                                            for clustering analysis. Using analytic derivations, generated
    Both the Zhang-Horvath and continuous definitions iden-                   network models, and real data, we showed that the behavior
tify the preference of the mouse brain network for redundant                  of fully weighted measures displayed enhanced sensitivity,
information flows, whereas the hybrid method of Onnela does                   selectivity, and robustness compared with hybrid measures.
not capture this feature. Redundant information transfer in                   To facilitate access to these measures, all clustering methods

TANGUY FARDET AND ANNA LEVINA                                                             PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

(a)                                                                        (b)

    FIG. 5. Different structures of clustering patterns and information flow in the mouse brain and the Fediverse. The original clustering values
are compared with graphs with the same adjacency matrix but shuffled edge weights (mouse, 10 uniformly shuffled networks; Fediverse, 200
graphs shuffled across all outgoing edges of each node to preserve out-strength normalization). The contours show different density levels of
the point clouds associated with the original and shuffled pairs of clustering coefficients. (a) The Zhang-Horvath and continuous definitions
capture the redundancy of information flow in the mouse brain (the middleman, fan-in, and 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 than the randomized ones are marked by a + and the
initial of the method (brown Z, Zhang-Horvath method; orange C, continuous method; yellow O, Onnela method). The original clustering is
considered to be significantly higher (lower) if 75% of the points are above (below) the dotted identity line. The addition of * denotes one-sided
fractions greater than 95%.

were implemented in PYTHON and made compatible with the                    numbers of spurious edges with small weights. We expanded
three main libraries in this language (NETWORKX, IGRAPH, and               the results from previous studies comparing existing weighted
GRAPH-TOOL) [28].                                                          definitions [14–16,21], extending their definition to directed
    The use of a specific weighted clustering coefficient should           networks and providing complete mathematical justifications
be an informed choice, based on the precise questions and ob-              for previous observations regarding linearity and continuity.
jects of study and thus on the specific properties that a relevant             Our analyses show that either of the fully weighted defini-
measure should fulfill to answer these questions. We therefore             tions may be preferred depending on the network properties.
wish to highlight the importance of continuity as a potentially            For networks with large degrees, the Zhang-Horvath defini-
crucial notion for networks with highly heterogeneous weight               tion may be preferred if the number of low-weight spurious
distribution or numerous spurious edges with low weights.                  edges is very high, as it is least susceptible to noise. In
In previous studies, slight variations on this notion had been             networks with heterogeneous weight distributions where the
introduced mathematically [15] or hinted at by the study of                absolute value of triangle strength is of interest, we showed
corner cases [14]. However, the continuity property was in-                that the continuous definition provides more relevant results
advertently considered only in particular classes of networks              than the Zhang-Horvath definition. Indeed, in networks in-
in Ref. [15] (disregarding, for example, small-degree cases),              volving fluxes of goods or matter as well as for information
erroneously marking previous methods as continuous. The                    processing (e.g., in brain or telecommunications networks),
other study (Ref. [14]) asserted discontinuity of previous mea-            one may be interested in the absolute amount that can be
sures simply as a feature, without discussing its implications             transferred between nodes, making nodes with small weights
or ways to avoid it. Our proposal of fully continuous clus-                of little relevance. A similar issue occurs for networks where
tering methods based on simple mathematical principles and                 many nodes participate in a single triangle (see Appendix F 4)
requirements fully solves the issue of continuity. In addition,            making the Zhang-Horvath clustering noncontinuous. In such
we show in Appendix D that these principles can be extended                networks, the use of the Zhang-Horvath definition is likely
to other measures such as the local closure.                               to assign high clustering to single-triangle nodes with low
    We discussed how each weighted definition is associated                weights, whereas the continuous definition will not, as was
with a specific interpretation of weighted clustering as a func-           shown in Fig. 1.
tion of the binary clustering, triangle, and triplet intensities               Finally, we illustrate the usefulness of weighted cluster-
(see Appendix B and Table VI for a summary). Corre-                        ing methods to investigate clustering in the examples of a
spondingly, these interpretations are associated with specific             connectome and a decentralized social network. The fully
properties of each clustering coefficient. In rare cases where,            weighted methods were especially suitable to reveal key dif-
by design, there are edges with small weights that should be               ferences in their weighted structural properties. Indeed, we
treated significantly differently from an absence of connec-               showed that middleman, fan-in, and fan-out patterns, charac-
tion, researchers may want to check whether the properties of              teristic of pathways enabling redundant information transfer
the Barrat or Onnela definitions fit their needs or if they should         between nodes, were overexpressed in the mouse brain. In the
come up with new, more appropriate definitions. In many                    Fediverse, the methods revealed an unexpected discrepancy
other cases, combining mathematical analysis and concrete                  between fan-in and fan-out modes, probably associated with
examples, we asserted that fully weighted measures outper-                 social interaction patterns that would mandate further investi-
form hybrid ones to evaluate clustering in networks with large             gation.

WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS …                                       PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

   TABLE III. Undirected weighted clustering coefficients of ver-        More specifically, Wang et al. [15] argue in favor of the use of
tex i (solid circles) for different weight configurations. Solid lines   a specific version using the harmonic mean (hm):
depict edges of weight w = max(w) = 1, whereas dotted lines are                                               2
associated with edges with vanishing weight . Only the proposed                                              jk        2
                                                                                                                                + w1
                                                                                                                    1      1
continuous clustering (bottom row) displays the required properties,                                               wi j + wik        jk
                                                                                        CiM,hm   =                         2
                                                                                                                                                ,   (A4)
compared with the Zhang-Horvath (C Z ), Holme et al. [17] (C H ), and                                  j=k         2
                                                                                                                            + max     1
Miyajima-Sakuragawa (hm) definitions (C M,hm ).                                                                 1      1
                                                                                                               wi j + wik           lm (wlm )

                                                                         which we will refer to as the Miyajima-Sakuragawa (hm)
                                                                         definition. However, this definition suffers from three major
                                                                            (i) Despite what is asserted by the authors, it does not fulfill
                                                                         the continuity condition.
                                                                            (ii) It is not locally linear, meaning that two nodes that have
                                                                         the same neighborhood but with all weights differing by a
                                                                         factor λ will not have the ratio of their clustering coefficients
                                                                         equal to λ.
                       ACKNOWLEDGMENTS                                      (iii) It introduces an undesired asymmetry in the definition
                                                                         of the triangle intensity: For a given triangle i jk , the com-
   This research was funded by a Humboldt Research Fellow-
                                                                         puted intensity will be different for each node as it depends
ship for Postdoctoral Researchers and a Sofja Kovalevskaja
                                                                         on which one is considered as i.
Award from the Alexander von Humboldt Foundation, en-
dowed by the Federal Ministry of Education and Research.
We thank the anonymous reviewers for their comments, which                      APPENDIX B: COMPARISON OF CLUSTERING
helped to significantly improve our manuscript. We acknowl-                                  PROPERTIES
edge the support from the BMBF through the Tübingen AI                       Multiple properties of the main definitions for the cluster-
Center (FKZ 01IS18039B).                                                 ing coefficient are listed in Table IV. These properties depend
                                                                         on the definitions of triangle and triplet intensity that are
       APPENDIX A: LIMITATIONS OF OTHER FULLY                            recapitulated in Table V.
               WEIGHTED DEFINITIONS                                          The different formulas for the intensities lead to different
                                                                         interpretations of weighted clustering (Table VI). The Barrat
  See Table III for a complete comparison of the fully                   and Zhang-Horvath definitions only quantify ratios of trian-
weighted clustering definitions.                                         gle and triplet strength, while the Onnela and continuous
                                                                         definitions are sensitive to the absolute value of the triangle
                           1. Holme et al. [17]                          intensity. The latter provides an intermediate interpretation
                                                                         between the Zhang-Horvath and Onnela definitions as it reacts
     Most studies consider the definition of Holme et al. [17] to        to both the ratio of intensities and the absolute value of the
be                                                                       triangle intensity.
                                   jkwi j wik w jk
                 CiH   =                              ,        (A1)           APPENDIX C: DERIVATION OF THE EVOLUTION
                           maxi j (wi j ) jk wi j w jk
                                                                                 OF HYBRID CLUSTERING COEFFICIENTS
which would make it inconsistent with the binary definition.                                      1. Barrat method
However, the discussion in their paper states that consistency
                                                                            Upon addition to a graph G(N, E ) of an edge (i, v) of
was one of their requirements, letting us think that they actu-
                                                                         weight , giving G (N, E  ) = E + {(i, v)}, one can compute
ally meant to define it as
                                                                         the evolution of the initial clustering coefficient CiB to its new
                                                                         value CiB by rewriting the definition from Ref. [10] as in
                              j=k wi j wik w jk
               Ci =
                                                   ,     (A2)           Ref. [14]:
                      maxi j (wi j ) j=k wi j w jk
                                                                                                 1      wi j + wik
                                                                                    CiB =                             ai j aik a jk
which would make it equal to the Zhang-Horvath definition                                  di (di − 1) j=k    2wi
[12], and we will therefore not consider Eq. (A1) here.
                                                                                                  1      wi j
                                                                                        =                       ai j aik a jk .                     (C1)
                                                                                            di (di − 1) j=k wi
                2. Miyajima and Sakuragawa [18]
   Miyajima and Sakuragawa [18] define a multitude of gen-                  From this, we can deduce the following relationship
eralized clustering coefficients based on the use of an arbitrary        between the Barrat definition and the binary clustering coeffi-
function h : R2 → R such that                                            cient Cibin :
                          jk h[h(wi j , wik ), w jk ]                                             n,i wi /wi        w
       Ci = 
                                                         .  (A3)                          CiB =                = Cibin i ,                          (C2)
                   j=k h[h(wi j , w jk ), maxlm (wlm )]                                          di (di − 1)         wi

TANGUY FARDET AND ANNA LEVINA                                                                                             PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

    TABLE IV. Comparison of the different properties of the different clustering coefficients. The Zhang-Horvath and continuous definitions
fulfill the maximum number of desirable properties. An “X” means that the method possesses this property.

Property                                                                       Barrat           Onnela        Miyajima-Sakuragawa (hm)               Zhang-Horvath          Continuous
Consistent with binary definition                                                X                 X                      X                                X                      X
Normalized (C ∈ [0, 1])                                                          X                 X                      X                                X                      X
All weights participate in I                                                                      X                      X                                X                      X
All weights participate equally in I                                                              X                                                       X                      X
Linear against local scaling of the weights                                                        X                                                       X                      X
Sensitive to weight permutations                                                 X                                        X                                X                      X
For a triangle  = (i, j, k), I = IT f (w jk )                                                                                                            X
Continuous                                                                                                                                                                        X

with n,i being the number of triangles in which node i partic-                                                 From this, one can define the evolution upon addition of an
ipates and wi being the average weight associated with edges                                                edge (i, v) of weight  as
connected to i and participating in a triangle.                                                                                                
   Notice that this expression also explains why the Barrat                                                                 CiO = Cibin Ii
definition is so close to the binary clustering: For networks
                                                                                                                                                        jk + O()
                                                                                                                                                 n Ii
where weights are either rather homogeneous or not strongly                                                                        =                       
correlated to triangles, wi and wi become very close as the                                                                         di (di + 1)         n
number of triangles per node increases.                                                                                                   n
                                                                                                                                   =             I O + O()
   Using Eq. (C2), the new clustering can be defined as                                                                              di (di + 1) i jk
                                                                                                                                     di − 1 O
                                                                                                                                  =         C + O().                                 (C5)
                                    wi                                                                                            di + 1 i
                CiB     =   Cibin
                                                                                                                     3. Directed versions of the clustering coefficients
                                                    n,i wi +(n,i −n,i )
                                                              n,i                                              To generalize the Zhang-Horvath definition of cluster-
                        =                                      di wi +
                            di (di + 1)                         di +1
                                                                                                             ing [12] for directed graphs, we use the same approach as
                                                                                                             proposed by Fagiolo [19]. These definitions are visible in
                            n,i wi                                                                         Table VII together with the directed definitions associated
                        =            + O()                                                                  with Barrat et al. [10] and Onnela et al. [11], respectively
                             di2 wi
                                                                                                             defined in Refs. [20] and [19].
                            di − 1 B
                        =         Ci + O().                                                       (C3)
                               k                                                                                                   APPENDIX D: CLOSURE
                                                                                                               Closure was introduced in Ref. [13] as a complementary
                                2. Onnela method                                                             measure of clustering for binary undirected networks.
   As for the other definitions, the clustering from Ref. [11]
can be defined as a function of the binary clustering:                                                                        1. Undirected weighted closure
                                                                                                                From the Zhang-Horvath definition of clustering, closure
                                  n Ii jk                                                                  can be generalized in a fully weighted but noncontinuous way
                   CiO      =                              =          O .
                                                               Cibin Ii                           (C4)
                                di (di − 1)                              jk                                  as
                                                                                                                            j=k wi j w jk wki           Wii3
                                                                                                                  Hi = 
                                                                                                                                                =                      , (D1)
                                                                                                                              j=k=i wi j w jk    j wi j (s j − wi j )
    TABLE V. Comparison of the formula for triangle and triplet
intensity among the different clustering definitions for undirected                                          again comparing the triangle intensities with their maximum
networks.                                                                                                    possible value if all their second neighbors are also connected
                                                                                                             to them (i.e., also first neighbors) by an edge of weight 1.
Definition                                        Triangle (Ii jk )                    Triplet (IT i jk )
                                                 wi j + wik                                                     TABLE VI. Comparison of the interpretations of the different
Barrat                                                      ai j aik a jk                 di (di − 1)
                                                     2wi                                                     clustering definitions for undirected networks.
Onnela                                            (wi j wik w jk )1/3                     di (di − 1)
                                                          2                                     2
Miyajima-Sakuragawa (hm)                                                                                     Definition    Barrat       Onnela        Zhang-Horvath         Continuous
                                                     1 + 1 + w                                  +
                                                       2          1                         1      1
                                                                          jk               wi j   w  ik
                                                    wi j   wik

Zhang-Horvath                                        wi j wik w jk                         w w                            wi bin              bin
                                                                                                                                                         Ii jk
                                                                                                                                                                             Ii jk
                                                    √                                      √ i j ik          Formula         C          O
                                                                                                                                       Ii jk Ci                    Cibin              Cibin
Continuous                                          3 w w w
                                                         i j jk ik                          wi j wik                      wi i                            ITZi jk            IT i jk

WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS …                                                      PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

    TABLE VII. Definitions of the Barrat, Onnela, and Zhang-Horvath intensities for each partial mode pattern in directed graphs. Column
1, pattern name; column 2, Onnela triangle intensity for node i; column 3, Barrat triangle intensity for node i; column 4, Barrat triplet
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 with each mode m are given by CiO,(m) = I,i
                                                                                for the Onnela method, CiB,(m) = I,i  /IT,i for the Barrat method,
                                                                                                                  B,(m) B,(m)

and Ci Z,(m)
              I,i   /I
                 Z,(m) Z,(m)
                        T,i  for  the Zhang-Horvath method. Note that, for the  Barrat method, the reciprocal strength has been defined in Ref. [20]
as si,↔  = i= j 21 (wi j + w ji ).

                                      O,(m)                     B,(m)                              B,(m)                       Z,(m)                  Z,(m)
Mode                                 I,i                      I,i                               IT,i                        I,i                   IT,i
Cycle                           (W [ 3 ] )3ii            1
                                                           (WA2 + (WA2 )T )ii      1
                                                                                     (s d
                                                                                   2 i,in i,out
                                                                                                 + si,out di,in ) − si,↔
                                                                                                                              (W )3ii          si,in si,out − si,↔

                            [ 13 ]   1         1
Middleman               (W W [ 3 ]T W [ 3 ] )ii        1
                                                         (WAT A + W T AAT )ii      1
                                                                                     (s d
                                                                                   2 i,in i,out
                                                                                                 + si,out di,in ) − si,↔
                                                                                                                           (W W T W )ii        si,in si,out − si,↔

                            [ 13 ]T     [ 13 ] 2
Fan in                   (W         (W ) )ii              1
                                                            (W T (A + AT )A)ii               si,in (si,in − 1)             (W T W W )ii         (si,in ) − si,in
                                                                                                                                                         2    [2]
                                 1          1
Fan out                  ((W [ 3 ] )2W [ 3 ]T )ii         1
                                                            (W (A + AT )AT )ii              si,out (si,out − 1)            (W W W T )ii        (si,out )2 − si,out

This is equivalent to comparing with the situation where all                       or via the continuous definition,
open paths of length 2 are closed into a triangle by an edge of                                √                                     2 3
weight 1.                                                                                        j=k
                                                                                                         3 w w w 2
                                                                                                             i j jk ki                W[3]
  Finally, it can also be defined in a continuous way as                            Hi,CO = 
                                                                                                            √               =   1 2 ii             , (D7)
                                                                                                   j=k=i      wi j w jk             [ 2 ] − si,out
                                                                                                                                 j W          ij
              √                       2 3
                 3 w w w 2
                 j=k                  W[3]                                                      √                                    2 ,T 3
     Hi = 
                    i j jk ki
                    √            =   1 2ii      .                       (D2)                     j=k
                                                                                                           3 w w w
                                                                                                                k j ji ik
            j=k=i    wi j w jk        [ 2 ] − si
                                                                                       Hi,CI =                √              =   1 2 ii               ,
                                    j W      ij                                                       j=k=i     wk j w ji           W  [ 2 ,T ] − si,in
                                                                                                                                   j             ij
                        2. Directed weighted closure
                                                                                                      √                         2 2 2 ,T 
    For directed networks, in contrast to Ref. [29], we only                                             3 w w w 2
                                                                                                      j=k   i j jk ki           W [ 3 ] W [ 3 ] ii
                                                                                     Hi,FO  =               √             =   1 2                   , (D9)
consider the extension of the undirected measure to di-                                             j=k=i     wi j w jk                [ 2 ] − si,out
                                                                                                                                 j  W
rected paths (that is, we consistently consider only second                                                                                    ij
in-neighbors via in-neighbors and second out-neighbors via                                   √                                               2 2
                                                                                                                               W [ 3 ],T W [ 3 ] ii
                                                                                                     3 w w w 2
                                                                                              j=k        k j ji ki
out-neighbors, but not the out-neighbors of the node’s in-                           c
                                                                                   Hi,FI   =           √                =   1 2                  . (D10)
neighbors or vice versa). Therefore we define only four                                         j=k=i     wk j w ji               [ 2 ,T ] − si,in
                                                                                                                              j W             ij
variants of the directed closure, two for outgoing paths [cycle
out (CO) and fan out (FO)] and two for incoming paths [cycle
                                                                                    APPENDIX E: NETWORK GENERATION ALGORITHMS
in (CI) and fan in (FI)].
    We define the weighted version either directly using the                          All networks were generated using the Neural Networks
weights, as in the Zhang-Horvath definition for the clustering                     and Graphs’ Topology (NNGT) library [28].
                                               Wii3                                                          1. Core-periphery network
                j=k wi j w jk wki
   Hi,CO = 
                                    =                           , (D3)
                                       j wi j (s j,out − wi j )
                  j=k=i wi j w jk
                                                                                       The core-periphery network in Fig. 1 contains (i) 1 cen-
                                                                                   tral core node (CCN), (ii) 10 outer-core nodes (OCNs), and
                j=k wk j w ji wik          (W T )ii                               (iii) 20 periphery nodes (PNs).
     Hi,CI = 
                                    =                         , (D4)
                                       j w ji (s j,in − w ji )
                  j=k=i wk j w ji
                                                                                       The nodes are connected as follows:
                                                                                      (i) The ten OCNs for a circular graph have fully reciprocal
                j=k wi j w jk wik        (W 2W T )ii                              connections to their four nearest neighbors.
    Hi,FO  =                       =                          , (D5)
                  j=k=i wi j w jk    j wi j (s j,out − wi j )                        (ii) The OCNs all connect to the CCN with reciprocal
                j=k wk j w ji wki       (W T W 2 )ii
     Hi,FI = 
                                    =                         ,   (D6)                The weights associated with these connections are drawn
                  j=k=i wk j w ji    j w ji (s j,in − w ji )                     from U (5, 10). The connections with the PNs are as follows:

  TABLE VIII. Some characteristic properties of the mesoscale                        TABLE IX. Some characteristic properties of the Fediverse
mouse brain. SD, standard deviation.                                               mesoscale network.

                  Mean                SD      Median          Min          Max                         Mean          SD    Median            Min              Max
In-degree         153.7               25.6      152           104          223     In-degree            21.3        82.6      4                0           2271
Out-degree        153.7               77.6      151            14          357     Out-degree           21.3        77.8      5                0           2038
   tot             0.43               0.02     0.43           0.38         0.49    CCbin
                                                                                      tot               0.68        0.37    0.86               0             1
Weight            0.076               0.36     0.038      3.9 × 10−16      20.4    Weight              0.045        0.14   0.0029         6.0 × 10−7         1

TANGUY FARDET AND ANNA LEVINA                                                             PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

   FIG. 6. Distribution of in- and out-degrees (in orange and yellow,          FIG. 7. Distribution of in- and out-degrees (in orange and yellow,
respectively) and weights in the mouse connectome.                          respectively) and weights in the Fediverse instances.

   (i) Each OCN receives one connection from every other                       The original lattice L(N, k, r) has 21 Nk(1 + r) edges, lead-
PN, starting with the first or second PN depending on the                   ing to the limit cases (i) 21 Nk edges if r = 0, like the
OCN’s evenness.                                                             undirected lattice, and (ii) Nk edges if r = 1, with all con-
   (ii) The OCN reciprocates the connections with probability               nections being reciprocal.
   (iii) The PNs are connected among themselves following                                    3. Network properties for Fig. 2
an Erdős-Rényi scheme of density 0.05.
   Weights associated with connections involving PNs are                       In the Watts-Strogatz network used in Fig. 2, we used a
drawn from U (0.05, 0.5).                                                   coordination number k = 20 and a rewiring probability p =
                                                                               The Erdős-Rényi network is generated to have an average
                    2. Watts-Strogatz network                               degree of 15, whereas the scale-free network is generated via
   The original Watts-Strogatz network [30] consists of a reg-              a degree list drawn from a power-law distribution with an
ular lattice basis (characterized by a coordination number k)               exponent of 1.2 and normalized to get an average degree of
that is then modified, rewiring each edge with a probability                15.
p. For directed networks, we used a generalization of that                     The weights of the Watts-Strogatz network are drawn from
method implemented in NNGT which is strictly equivalent                     an exponential distribution of parameter 1.5 and shifted by
except for the fact that edges are now directed:                            +0.1 so that they are all nonzero.
   (1) Start from a directed regular lattice with coordination                 The weights or the “noise” networks are either all equal
number k and reciprocity r (taken as 1 in this paper).                      to 10−4 or drawn from a second exponential distribution of
   (2) Rewire each edge with probability p.                                 parameter 0.05, shifted by +10−4 .

(a)                                                                        (b)

   FIG. 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 with the averages over an ensemble of graphs with the same
adjacency matrix but shuffled edge weights. For the mouse brain, 10 uniformly shuffled networks; for Fediverse, 200 shuffling across all
outgoing 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 and fan-out motifs are higher in the original graph). (b) For the Fediverse, only fan
out is significantly stronger than in the random graphs. Patterns where the original values are significantly greater (smaller) than the randomized
ones are marked by a + (−) and the initial of the method (brown Z, Zhang-Horvath method; orange C, continuous method; yellow O, Onnela
method). The original closure is considered to be significantly higher (lower) if 75% of the points are above (below) the dotted identity line.
The addition of * denotes one-sided fractions greater than 95%.

WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS …                                        PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

    TABLE X. Number of nodes (N) and edges (E) and fraction of          sponding to the number of users registered on that server.
single-triangle (1-T) nodes in several collaboration and gene associ-   Edges are associated with four attributes: “num follows”, de-
ation networks.                                                         fined as Fi j , the number of followers from i to j; “follow/size”,
                                                                        defined as Fi j /Si ; a “weight” given by wi j = Fi j /Fi , the ratio
Network                N                E             1-T nodes (%)     between the number of followers from i to j divided by the
NetScience           1589             2742                  23          total number of followers from i; and a “distance” giving the
CompGeo              7343            11 898                 21          Euclidean distance between the two servers on the latitude-
CE-CX               15 229          245 952                  8          longitude plane. See Table IX and Fig. 7.
CE-HT                2617             2985                   2
HS-HT                2570            13 691                  7                          3. Closure in the shuffled networks
SC-HT                2084            63 027                  5
                                                                           The results obtained for the local closure confirm those
                                                                        obtained using the clustering coefficient for the mouse brain
                                                                        and Fediverse networks, as shown in Fig. 8. Namely, we see
                                                                        an overexpression of fan-in and fan-out patterns for the mouse
                                                                        network and a discrepancy between those two patterns for the
                 1. Mouse mesoscale connectome                          Fediverse network.
    The mouse mesoscale connectome network was obtained
from Ref. [22] and contains 426 nodes corresponding to brain                  4. Networks with a high number of single-node triangles
regions of intermediate scale connected by 65 465 edges. It                 The presence of nodes participating in a single triangle
is a symmetric version of the original network that separates           is frequent in very sparse networks such as collaboration or
nodes from both hemispheres. Each node is associated with               gene-protein interaction networks.
a “name” property composed of an abbreviated denomination                   Table X details several such networks: NetScience in-
for the corresponding brain region, as well as a suffix (left or        volves coauthorship in the network science community [31],
right) corresponding to the hemisphere. Edges are associated            CompGeo involves collaborations in computational geome-
with three attributes: a “weight,” a “p value,” and a “distance”        try [32], CE-CX is a graph of gene associations inferred
(corresponding to the Euclidean distance from the source to             from the coexpression pattern of two genes (based on
the target node). See Table VIII and Fig. 6.                            high-dimensional gene expression data) for Caenorhabdi-
                                                                        tis elegans, CE-HT is for gene associations inferred from
                                                                        high-throughput protein-protein interactions for C. elegans,
                 2. Fediverse mesoscale network                         HS-HT is for gene associations inferred from high-throughput
   The Fediverse mesoscale network was obtained from Ref.               protein-protein interactions for Homo sapiens, and SC-HT is
[25] (data are available [26]). It contains 3825 nodes rep-             for gene associations inferred from high-throughput protein-
resenting servers (instances) that are connected via 81 371             protein interactions for Saccharomyces cerevisiae.
edges. Each node is associated with two attributes: a “name”,               Gene functional association networks [33] were down-
corresponding to the server domain, and a “size”, Si , corre-           loaded [34].

 [1] O. Mason and M. Verwoerd, Graph theory and networks in              [8] M. D. Fox and M. Greicius, Clinical applications of rest-
     biology, IET Syst. Biol. 1, 89 (2007).                                  ing state functional connectivity, Front. Syst. Neurosci. 4, 19
 [2] S. E. Ahnert and T. M. A. Fink, Clustering signatures classify          (2010).
     directed networks, Phys. Rev. E 78, 036112 (2008).                  [9] J. G. Orlandi, O. Stetter, J. Soriano, T. Geisel, and D. Battaglia,
 [3] X.-J. Zhang, B. Gu, X.-M. Guan, Y.-B. Zhu, and R.-L. Lv, Cas-           Transfer entropy reconstruction and labeling of neuronal con-
     cading failure in scale-free networks with tunable clustering,          nections from simulated calcium imaging, PLoS One 9, e98842
     Int. J. Mod. Phys. C 27, 1650093 (2016).                                (2014).
 [4] Y.-W. Li, Z.-H. Zhang, D. Fan, Y.-R. Song, and G.-P. Jiang,        [10] A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A.
     Influence of clustering on network robustness against epidemic          Vespignani, The architecture of complex weighted networks,
     propagation, in Science of Cyber Security, Lecture Notes in             Proc. Natl. Acad. Sci. USA 101, 3747 (2004).
     Computer Science, edited by F. Liu, S. Xu, and M. Yung             [11] J.-P. Onnela, J. Saramäki, J. Kertész, and K. Kaski, Intensity
     (Springer International, Cham, Switzerland, 2018), pp. 19–33.           and coherence of motifs in weighted complex networks, Phys.
 [5] S. F. Muldoon, E. W. Bridgeford, and D. S. Bassett, Small-              Rev. E 71, 065103(R) (2005).
     world propensity and weighted brain networks, Sci. Rep. 6,         [12] B. Zhang and S. Horvath, A general framework for weighted
     22057 (2016).                                                           gene co-expression network analysis, Stat. Appl. Genet. Mol.
 [6] J.-G. Young, G. T. Cantwell, and M. E. J. Newman, Bayesian              Biol. 4, 17 (2005).
     inference of network structure from unreliable data, J. Complex    [13] H. Yin, A. R. Benson, and J. Leskovec, The local closure coeffi-
     Networks 8, cnaa046 (2021).                                             cient: A new perspective on network clustering, in Proceedings
 [7] R. Guimerà and M. Sales-Pardo, Missing and spurious interac-            of the Twelfth ACM International Conference on Web Search
     tions and the reconstruction of complex networks, Proc. Natl.           and Data Mining (Association for Computing Machinery, Mel-
     Acad. Sci. USA 106, 22073 (2009).                                       bourne, 2019), pp. 303–311.

TANGUY FARDET AND ANNA LEVINA                                                          PHYSICAL REVIEW RESEARCH 3, 043124 (2021)

[14] J. Saramäki, M. Kivelä, J.-P. Onnela, K. Kaski, and J. Kertész,          Ouellette, T. N. Nguyen, S. A. Sorensen, C. R. Slaughterbeck,
     Generalizations of the clustering coefficient to weighted com-           W. Wakeman, Y. Li, D. Feng, A. Ho, E. Nicholas et al., A
     plex networks, Phys. Rev. E 75, 027105 (2007).                           mesoscale connectome of the mouse brain, Nature (London)
[15] Y. Wang, E. Ghumare, R. Vandenberghe, and P. Dupont, Com-                508, 207 (2014).
     parison of different generalizations of clustering coefficient    [23]
     and local efficiency for weighted undirected graphs, Neural       [24]
     Comput. 29, 313 (2016).                                                  protocols_used_in_the_fediverse.
[16] G. Kalna and D. J. Higham, Clustering coefficients for weighted   [25]   M. Zignani, C. Quadri, S. Gaito, H. Cherifi, and G. P.
     networks, in AISB’06: Adaptation in Artificial and Biological            Rossi, The footprints of a “mastodon”: How a decentralized
     Systems, edited by T. Kovacs and J. A. R. Marshall (Society              architecture influences online social relationships, in IEEE Con-
     for the Study of Artificial Intelligence and the Simulation of           ference on Computer Communications Workshops 2019 (IEEE,
     Behaviour, Bath, UK, 2006), Vol. 3, pp. 132–138.                         Piscataway, NJ, 2019), pp. 472–477.
[17] P. Holme, S. M. Park, B. J. Kim, and C. R. Edling, Korean         [26]
     university life in a network perspective: Dynamics of a large            10.5072/FK2/AMYZGS.
     affiliation network, Phys. A (Amsterdam) 373, 821 (2007).         [27]
[18] K. Miyajima and T. Sakuragawa, Continuous and robust              [28]   T. Fardet, NNGT 2.5.1, 2021, doi: 10.5281/zenodo.5571901.
     clustering coefficients for weighted and directed networks,       [29]   H. Yin, A. R. Benson, and J. Ugander, Measuring directed
     arXiv:1412.0059 [physics.soc-ph].                                        triadic closure with closure coefficients, Network Sci. 8, 551
[19] G. Fagiolo, Clustering in complex directed networks, Phys. Rev.          (2020).
     E 76, 026107 (2007).                                              [30]   D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-
[20] G. Clemente and R. Grassi, Directed clustering in weighted               world’ networks, Nature (London) 393, 440 (1998).
     networks: A new perspective, Chaos, Solitons Fractals 107, 26     [31]
     (2018).                                                           [32]
[21] I. E. Antoniou and E. T. Tsompa, Statistical analysis of          [33]   A. Cho, J. Shin, S. Hwang, C. Kim, H. Shim, H. Kim, H.
     weighted networks, Discrete Dyn. Nat. Soc. 2008, 375452                  Kim, and I. Lee, WormNet v3: A network-assisted hypothesis-
     (2008).                                                                  generating server for Caenorhabditis elegans, Nucleic Acids
[22] S. W. Oh, J. A. Harris, L. Ng, B. Winslow, N. Cain, S. Mihalas,          Res. 42, W76 (2014).
     Q. Wang, C. Lau, L. Kuan, A. M. Henry, M. T. Mortrud, B.          [34]