Source-linked AI summary
Consensus clustering in complex networks
Andrea Lancichinetti, Santo Fortunato
TL;DR
Community detection methods often produce non-unique partitions because of stochastic choices and tie-breaking, complicating the identification of representative community structure. The paper combines consensus clustering with existing methods through an iterative consensus matrix, improving partition stability and accuracy and extending the framework to temporal networks. An application to physics-paper citations illustrates its use for tracking topic evolution.
Problem
Many community-detection methods produce results dependent on random seeds, initial conditions, or tie-breaking, leaving the representative community structure unclear.
Method
The method iteratively constructs a vertex cooccurrence-based consensus matrix from multiple partitions and reclusters it until a unique stable partition is reached.
Results
Consensus clustering produces more stable and more accurate partitions than direct method applications and can combine snapshots to monitor temporal community evolution.
Takeaways & Limitations
Consensus clustering turns the diversity of stochastic partitions into a usable signal for community detection and provides a framework for analyzing evolving networks.
Takeaways & Limitations
Temporal results depend on the time-window amplitude and the number of snapshots combined, which should not span much more than the network’s natural evolutionary timescale.
Abstract
from arXiv · showhide
The community structure of complex networks reveals both their organization and hidden relationships among their constituents. Most community detection methods currently available are not deterministic, and their results typically depend on the specific random seeds, initial conditions and tie-break rules adopted for their execution. Consensus clustering is used in data analysis to generate stable results out of a set of partitions delivered by stochastic methods. Here we show that consensus clustering can be combined with any existing method in a self-consistent way, enhancing considerably both the stability and the accuracy of the resulting partitions. This framework is also particularly suitable to monitor the evolution of community structure in temporal networks. An application of consensus clustering to a large citation network of physics papers demonstrates its capability to keep track of the birth, death and diversification of topics.
I. INTRODUCTION
Community detection seeks modules whose internal connectivity exceeds their external connectivity, but both the community concept and algorithmic outputs remain difficult to validate and stabilize. The paper combines multiple stochastic partitions through iterative consensus clustering to obtain stable partitions and extend the approach to temporal networks.
- Community structure identifies modules through higher within-module than between-module edge density, revealing vertex similarities, system organization, and functional roles.
- Community detection remains difficult to validate because community definitions depend on the system or problem under study.
- Random seeds, initial conditions, and tie-breaking among equal-valued edges can make clustering outputs non-unique, including for ostensibly deterministic methods.
- Consensus clustering combines multiple partitions by constructing a cooccurrence-based consensus matrix and iteratively reclustering it until a stable partition is reached.
- The framework aims to increase within-community cohesion and decrease between-community connectivity rather than find a better optimum of a method’s objective function.
- The study presents a systematic consensus-clustering framework for improving community partitions and combining snapshots to monitor temporal community evolution.
A. Accuracy
The accuracy evaluation applies consensus clustering alongside several community-detection methods on benchmark graphs with planted structure. It uses NMI across mixing levels to assess how well detected partitions recover increasingly mixed communities.
- The evaluation uses LFR benchmark graphs with planted community structure to test whether integrating consensus clustering improves clustering performance.
- The schematic shows consensus clustering making two visible communities more clique-like with heavy internal edges despite two inaccurate input partitions.
- The tested methods include fast greedy modularity optimization, simulated annealing, Louvain, label propagation, Infomap, and OSLOM.
- Consensus clustering requires methods that can operate on weighted networks, because its consensus matrix assigns weights to vertex cooccurrences.
- NMI measures agreement between each algorithm’s detected partition and the benchmark’s planted partition, with 1 indicating identical partitions and values near 0 indicating strong difference.
- Increasing the mixing parameter µ makes communities more difficult to distinguish, producing decreasing NMI curves across the tested methods.
B. Stability
Consensus clustering produces increasingly stable partitions across repeated runs on both C. elegans and the APS citation network, generally outperforming the selected best individual partitions. The consensus partitions also show higher fidelity than the input partitions.
- Evaluation setup: The APS stability analysis compares average NMI between best partitions with average NMI between consensus partitions across repeated sets of r input runs.Each figure contains curves for six clustering algorithms and averages over all pairs among 20 best or consensus partitions.
- C. elegans: Consensus partitions are more stable than best partitions for all tested methods on the C. elegans network, except for a near-tie with Clauset et al.The consensus partition’s stability increases monotonically with the number of input runs, whereas some best-partition curves become less stable around r ≃10.
- C. elegans: Consensus stability increases monotonically with the number of input runs for all six algorithms on C. elegans.The comparison averages NMI values across 20 sequences of r runs, using pairwise comparisons among the resulting partitions.
- APS citation network: Consensus stability also grows monotonically with r and remains higher than best-partition stability on the APS citation-network subset.The subset contains papers published in 1960 and papers cited by them, yielding 5 696 vertices and 8 634 edges.
- Fidelity: Consensus partitions have higher fidelity than the individual input partitions they combine, in addition to being more stable.This result is reported for the supplementary analyses in Figs. S5 and S6.
C. Dynamic communities
Consensus clustering tracks changing communities in the APS citation network by matching clusters across time windows and following their sizes. The analysis reveals expansion, contraction, emergence, diversification, and decline of scientific topics.
- Dynamic communities: Consensus clustering follows the birth, growth, fragmentation, decay, and death of scientific topics in the APS citation network.The procedure derives consensus partitions from temporal network snapshots.
- Statistical Physics: The Statistical Physics topic landscape alternates between expansion and contraction while showing long-term growth in paper counts.The selected topics span 1945–2008 in five-year time windows, and keyword popularity changes across historical phases.
- Cluster tracking: Clusters are matched across consecutive time windows using shared papers, with link width representing the number of common papers.Communities are identified by colors, and matching clusters retain the same color across consecutive times.
- Emerging topics: The analysis identifies emerging fields including Self-Organized Criticality, Spin Glasses, Complex Networks, Neural Networks, and Complex Networks.The Network-focused view specifically highlights the genesis of Neural Networks and Complex Networks.
- Quantitative evolution: Cluster-size sequences are aligned to each community’s peak year to quantify topic evolution before and after the peak.Clusters are aggregated by peak magnitude; some important Infomap topics approach 1000 papers at their peak.
III. DISCUSSION
Consensus clustering stabilizes stochastic community-detection outputs, improves accuracy, and provides a framework for tracing community evolution in dynamic networks.
- Accuracy and stability: Consensus clustering combines diverse partitions to produce more accurate results than the original methods, including methods that perform poorly alone.The improvement is reported for artificial graphs with planted community structure.
- Accuracy and stability: Consensus partitions address stochastic fluctuations without necessarily improving the objective-function optimum.The method emphasizes combining information across outputs rather than selecting a better optimum.
- Temporal networks: For dynamic networks, consensus combines partitions from overlapping snapshots to follow changing community structure.The method can track topic birth, growth, fragmentation, decay, and death in citation networks.
- Temporal networks: Time-window size and the number of combined snapshots should reflect the system’s natural evolution timescale, with robustness checked across reasonable settings.Windows spanning much broader periods than the network’s natural timescale should be avoided.
Methods
The method builds a consensus matrix from repeated or temporally overlapping partitions, filters weak coassignments, reclusters iteratively, and matches clusters across time.
- Consensus matrix: The consensus matrix D_ij records the fraction of input partitions assigning vertices i and j to the same cluster.D is an n×n weighted matrix and is generally denser than the original adjacency matrix.
- Iterative consensus: Weak consensus-matrix entries below threshold τ are discarded, while isolated noisy vertices are reconnected to their highest-weight neighbors.This maintains graph connectivity during the procedure.
- Iterative consensus: The algorithm repeatedly applies the same clustering method to D and rebuilds the consensus matrix until the resulting partition is stable.The process ends when the consensus matrix becomes block diagonal; typically one iteration is sufficient.
- Algorithm: The procedure begins with repeated applications of algorithm A, computes D, thresholds it, reclusters D repeatedly, and stops when all partitions agree.The number of input partitions and threshold are set before computation.
- Temporal consensus: For temporal networks, overlapping time windows generate snapshot partitions whose coassignment counts account only for snapshots containing both vertices.Cluster correspondences across adjacent times use a Jaccard-based best-match rule that can represent discontinuities and fragmentation.
Appendix A: Selection of the optimal number of runs and threshold τ
The benchmark analysis selects the number of runs and threshold by examining NMI across clustering methods, with optimal settings depending on the method.
- Number of runs: r ≈50 reaches an optimal consensus partition and remains stable across additional runs.The tests therefore used r between 50 and 100.
- Threshold selection: Threshold choices depend on the clustering technique: Louvain favors low τ, while other methods favor method-specific intermediate or high ranges.LPM performs best for τ in [0.3, 0.7], SA from 0.5 to 0.7, and Clauset et al. at fairly high thresholds.
- Evaluation: Figure 7 plots NMI against the number of input runs for each method and compares τ values 0, 0.5, and 0.7.The benchmark uses LFR graphs with planted partitions and method-specific mixing parameters.
- Evaluation: Figure 8 plots NMI against τ for each method at r=20 and r=50, revealing different optimal threshold ranges.The threshold is evaluated on the same LFR benchmark graphs used for Figure 7.
Appendix B: On the effectiveness of consensus clustering
A clique-based model explains consensus clustering’s effectiveness: stochastic modularity partitions vary in how neighboring cliques are grouped, while coassignment filtering can recover planted cliques.
- Model: The appendix studies a clique graph with interclique edges to explain why consensus improves modularity-based clustering.The model resembles the LFR benchmarks and focuses on modularity because its behavior is easier to analyze.
- Model: Many equivalent groupings of cliques make neighboring cliques join the same module with roughly equal probability across runs.This run-to-run diversity creates variable coassignment frequencies for neighboring cliques.
- Model: For sparse interclique connections, the probability that cliques are grouped together decreases with their distance in the clique network.The sparse case is approximated by a tree-like structure with average degree near 2.
- Validation: The approximation is especially good for high C in the examined setting h=10 and n_c=10.These parameter values are used in the following plots.
- Consensus effect: The consensus matrix can separate planted cliques when τ exceeds the relevant interclique coassignment probability, whereas modularity continues merging cliques.The appendix reports higher planted-partition NMI for consensus than for the input partitions already at τ=0.3.
Appendix C: Stability and fidelity of consensus partitions
Consensus partitions are generally more stable than the best input partitions while remaining close to the input partitions. Fidelity is assessed across threshold values and network settings, with excessive thresholds producing small clusters.
- Consensus partitions are more stable than the best partitions, avoiding the trivial stability of putting all vertices in one cluster.Their stability must therefore be evaluated together with fidelity to the input partitions.
- Figure 10 measures NMI between planted and input partitions versus planted and consensus partitions across thresholds for networks with 400 and 800 cliques.
- The consensus partition is often closer to the input partitions than the input partitions are to one another, while also being more stable.
- At excessively high thresholds, many low-weight connections are deleted, leaving the consensus partition composed of small clusters.
- Figure 11 compares average NMI among input partitions with average NMI between input and consensus partitions for the C. elegans neural network.