Revealing Consensus and Dissensus between Network Partitions

Community detection methods attempt to divide a network into groups of nodes that share similar properties, thus revealing its large-scale structure. A major challenge when employing such methods is that they are often degenerate, typically yielding a complex landscape of competing answers. As an attempt to extract understanding from a population of alternative solutions, many methods exist to establish a consensus among them in the form of a single partition “point estimate” that summarizes the whole distribution. Here, we show that it is, in general, not possible to obtain a consistent answer from such point estimates when the underlying distribution is too heterogeneous. As an alternative, we provide a comprehensive set of methods designed to characterize and summarize complex populations of partitions in a manner that captures not only the existing consensus but also the dissensus between elements of the population. Our approach is able to model mixed populations of partitions, where multiple consensuses can coexist, representing different competing hypotheses for the network structure. We also show how our methods can be used to compare pairs of partitions, how they can be generalized to hierarchical divisions, and how they can be used to perform statistical model selection between competing hypotheses.

Popular Summary

Many network systems, such as the Internet, online social networks, and protein interactions, are so large and complex that to obtain insight into their function, researchers require a way to provide a summary of the large-scale network structure. This is the role of network-clustering algorithms. However, it is often the case that such large networks admit a large number of competing summaries, each focusing on a distinct aspect of their structure. Here, we provide a systematic methodology to fully characterize the distribution of solutions given by network-clustering algorithms.

The emergence of many competing summaries leads to an additional level of complexity that is not sufficiently tackled by state-of-the-art network-clustering algorithms, which tend to focus on a single summary or a single consensus among several. Our method is capable of revealing not only the consensus, or the extent to which the summaries agree, but also the dissensus, the extent to which they disagree. This is achieved by a clustering of the summaries themselves, yielding groups of results that point in a cohesive direction.

Our methodology allows us to extract more meaningful and accurate results from network-clustering algorithms as well as weight the distinct summaries according to their plausibility.

Figure 1

(a) Five sampled partitions from the posterior distribution of a network of political books, with the group labels represented as colors, using the Poisson DC-SBM and the MCMC algorithm of Ref. [22] (b) Marginal posterior distribution of the group memberships of the nodes highlighted in red in (a), obtained for ${10}^5$ samples from the posterior distribution. The same asymptotic distribution is obtained for every single node in the network.

Figure 2

Relabeling a partition corresponds to finding the solution of a maximum bipartite weighted matching problem, where the partition labels are the nodes of a bipartite graph with weights $w_{rs}$ on the edges. The matching is a bijection $\mu (r)$ that needs to be chosen so that the total sum ${\sum }_r{w}_{r,\mu (r)}$ is maximized. In this illustration, the edge thickness corresponds to the weight $w_{rs}$, and the edges in green correspond to the maximum matching.

Figure 3

Five sampled partitions from Fig. 1, in the top panel, with their relabeled counterparts on the bottom panel, using the algorithm described in the text, where it becomes possible to identify groups consistently according to their label (color).

Figure 4

(a) Marginal posterior group membership distribution on the nodes obtained from relabeled partitions for a network of political books, the same as in Fig. 1, obtained with the algorithm described in the text with $M={10}^5$ samples, represented as pie diagrams on the nodes. (b) Same distributions for the nodes highlighted in red in panel (a).

Figure 5

Effective number of groups $B_e(\widehat{\mathit{b}})$ for the consensus estimate $\widehat{\mathit{b}}$ obtained for $M$ random partitions of $N=100$ nodes into $B=4$ groups, according to the different error functions as indicated in the legend. The results were obtained by averaging over 50 realizations.

Figure 6

Inference of the community structure of the political books network, according to the DC-SBM and using the different estimators as shown in the legend. For the VI/MAP estimate (top panel), the three groups can be interpreted, from left to right, as “liberal,” “neutral,” and “conservative.”

Figure 7

Inference of the community structure of Zachary’s karate club network, according to the DC-SBM and using the different estimators as shown in the legend.

Figure 8

Inferred partition modes from $M={10}^5$ samples of the DC-SBM posterior distribution for the political books network. Panels (a)–(j) show the marginal distributions for each identified mode as pie diagrams on the nodes of the network, with the legend specifying the relative mode fraction $w_k$ and the uncertainty ${\sigma }_{\widehat{\mathit{b}}}$ of the maximum for each mode. The bottom-right panel shows the projection of the partition distribution in two dimensions according to the UMAP dimensionality reduction algorithm [17], where the different modes can be identified as local peaks of the distribution. The star symbol shows the location of the MOC estimate, the diamond symbol the position of the MAP/VI estimate, and the triangle the position of the RMI estimate.

Figure 9

Inferred partition modes from $M={10}^5$ samples of the latent Poisson DC-SBM posterior distribution for the political books network. The left panel shows the mode fractions $w_k$, and the right panel the four largest modes (a)–(d), with the marginal distributions shown as pie diagrams on the nodes of the network.

Figure 10

Inferred partition modes from $M={10}^5$ samples of the posterior distribution obtained with the Poisson DC-SBM (left panel) and latent Poisson DC-SBM (right panel) for the karate club network. The insets show the modes as indicated by the arrows, with the marginal distributions shown as pie diagrams on the nodes of the network.

Figure 11

Inferred partition modes from $M={10}^5$ samples of the posterior distribution obtained with the Poisson DC-SBM for the American college football network. The insets show the modes as indicated by the arrows, with the marginal distributions shown as pie diagrams on the nodes of the network.

Figure 12

Inferred partition modes from $M={10}^5$ samples of the latent Poisson DC-SBM posterior distribution for the American college football network. The left panel shows the mode fractions $w_k$, and the right panel shows the two largest modes (a) and (b), with the marginal distributions shown as pie diagrams on the nodes of the network.

Figure 13

Inferred hierarchical partition modes from $M={10}^5$ samples of the hierarchical latent Poisson DC-SBM posterior distribution for the co-occurrence network of characters in the Les Misérables novel. The left panel shows the mode fractions $w_k$, and the right panel shows the three largest modes (a)–(c), with the marginal distributions shown as pie diagrams on the nodes of the network.

Figure 14

Time required to compute $d(\mathit{x},\mathit{y})$ for $\mathit{x}$ and $\mathit{y}$ both randomly sampled with $q(\mathit{x})=q(\mathit{y})=B$ groups, as shown in the legend, as a function of $N$, averaged over 100 samples, using an Intel i9-9980HK CPU. The solid line shows an $O(N)$ slope.

Figure 15

(Top panel) Average relative description length difference $(\mathrm{\Sigma }-{\mathrm{\Sigma }}_{\mathrm{RMI}})/\max (\mathrm{\Sigma },{\mathrm{\Sigma }}_{\mathrm{RMI}})$ between maximum overlap and RMI encodings for empirical networks with $N$ nodes, averaged over pairs of partitions independently sampled from the Poisson DC-SBM posterior distribution. The point size and color indicate the size of the network. (Middle panel) Like the top panel, but with the mean normalized overlap distance computed for each network. (Bottom panel) Histogram of average relative description length differences over all empirical networks.

Figure 16

Projection of the partition distribution in two dimensions according to the UMAP dimensionality reduction algorithm [17], for the same data of Fig. 9, using (a) the variation of information and (b) the (negative) reduced mutual information as dissimilarity functions. The labels indicate a correspondence of the modes with those found in Fig. 9 according to the majority of partitions.