**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 definitions. 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 043124-2 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 = B 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 2wi 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 = O = 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 ) 3 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 Z 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 = Z = Ci , (5) w w j=k i j ik Z 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 Z 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 043124-3 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 (m) /nT,i (m) 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. I,i 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) and nT IT i jk IT i jk IT i jk (m) 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 2 IT,i 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) (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 = straightforward For simplicity, we define I,i = fashion. 1 1 ↔ j=k Ii jk and IT,i = 2 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. 043124-4 WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS … PHYSICAL REVIEW RESEARCH 3, 043124 (2021) (a) (b) 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 Ii 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. 043124-5 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 043124-6 WEIGHTED DIRECTED CLUSTERING: INTERPRETATIONS … PHYSICAL REVIEW RESEARCH 3, 043124 (2021) coefficient becomes spurious that is lower than 1%. We consider a thresholding 1 procedure, where at each level of the threshold (pmax ), only O C 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 B 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 2 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 →0 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- Z 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 043124-7 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) 043124-8 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 043124-9 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. 043124-10 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 shortcomings: (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 = H , (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 = M,h . (A3) CiB = = Cibin i , (C2) j=k h[h(wi j , w jk ), maxlm (wlm )] di (di − 1) wi 043124-11 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 O jk definition is so close to the binary clustering: For networks jk + O() O n Ii n 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 wi 3. Directed versions of the clustering coefficients n,i wi +(n,i −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 O 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 = 0 = , (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 Z Ii jk 2 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 043124-12 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 O,(m) /nT,i (m) 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] B 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 1 Cycle (W [ 3 ] )3ii 1 2 (WA2 + (WA2 )T )ii 1 (s d 2 i,in i,out + si,out di,in ) − si,↔ B (W )3ii si,in si,out − si,↔ [2] [ 13 ] 1 1 Middleman (W W [ 3 ]T W [ 3 ] )ii 1 2 (WAT A + W T AAT )ii 1 (s d 2 i,in i,out + si,out di,in ) − si,↔ B (W W T W )ii si,in si,out − si,↔ [2] [ 13 ]T [ 13 ] 2 Fan in (W (W ) )ii 1 2 (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 2 (W (A + AT )AT )ii si,out (si,out − 1) (W W W T )ii (si,out )2 − si,out [2] 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 = c √ = 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 2 W[3] j=k=i wi j w jk [ 2 ] − si c Hi,CI = √ = 1 2 ii , j W ij j=k=i wk j w ji W [ 2 ,T ] − si,in j ij (D8) 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 c 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 2 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]. coefficient, Wii3 1. Core-periphery network j=k wi j w jk wki Hi,CO = 0 = , (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- 3 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 = 0 = , (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. 0 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 connections. j=k wk j w ji wki (W T W 2 )ii Hi,FI = 0 = , (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 CCbin 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 043124-13 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. 0.5. (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 = 0.03. 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%. 043124-14 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 APPENDIX F: REAL-WORLD NETWORKS 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. 043124-15 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] https://fediverse.party/. and local efficiency for weighted undirected graphs, Neural [24] https://en.wikipedia.org/wiki/Fediverse#Communication_ 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] https://dataverse.mpi-sws.org/dataset.xhtml?persistentId=doi: university life in a network perspective: Dynamics of a large 10.5072/FK2/AMYZGS. affiliation network, Phys. A (Amsterdam) 373, 821 (2007). [27] https://joinmastodon.org/. [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] https://networkrepository.com/netscience.php. (2018). [32] http://vlado.fmf.uni-lj.si/pub/networks/data/collab/geom.htm. [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] https://networkrepository.com/bio.php. 043124-16