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

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.

Figure 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 pp5-s1 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.

Figure 2

Fully weighted methods are less sensitive to spurious edges. A “measured network” can be represented as the union of a “ground truth” (G.T.)—here, a Watts-Strogatz network in dark brown—and spurious small-weight connections (“noise” graphs with (a) random [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 $R^2>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 pp5. Z, C, O, and B, Zhang-Horvath, continuous, Onnela, and Barrat definitions, respectively.

Figure 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<p_{\max }$ 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 ($s_i/d_i$) 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).

Figure 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.

Figure 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%.

Figure 6

Distribution of in- and out-degrees (in orange and yellow, respectively) and weights in the mouse connectome.

Figure 7

Distribution of in- and out-degrees (in orange and yellow, respectively) and weights in the Fediverse instances.

Figure 8

Different structures of local closure in the mouse brain and Fediverse. The panels compare the local closure of directed patterns for the mouse brain (a) and Fediverse (b). The original values are compared 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%.