Revealing consensus and dissensus between network partitions

Abstract

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 be used to perform statistical model selection between competing hypotheses.

arXiv comment28 pages, 16 figures

References in corpus (27)

• Community structure in social and biological networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Self-similar community structure in organisations
• The performance of modularity maximization in practical contexts
• Consensus clustering in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Element-centric clustering comparison unifies overlaps and hierarchy
• Efficient method for estimating the number of communities in a network
• Improved mutual information measure for classification and community detection
• Consistency of community structure in complex networks
• Exploring the solution landscape enables more reliable network community detection
• Merge-split Markov chain Monte Carlo for community detection
• Community detection in networks with unequal groups
• Fast consensus clustering in complex networks
• Latent Poisson models for networks with heterogeneous density

Cited by in corpus (9)

• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Disentangling homophily, community structure and triadic closure in networks
• Hierarchical community structure in networks
• Hierarchical core-periphery structure in networks
• Ordered community detection in directed networks
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Multi-scale Laplacian community detection in heterogeneous networks
• Detectability of hierarchical communities in networks
• Community membership consistency applied to corporate board interlock networks