Source-linked AI summary
Multiresolution Consensus Clustering in Networks
Lucas G. S. Jeub, Olaf Sporns, Santo Fortunato
TL;DR
Community detection often yields many partitions and networks may contain meaningful structure at multiple scales. The paper combines event sampling for multiresolution modularity with hierarchical consensus clustering using modified modularity, recovering planted hierarchy accurately in a benchmark and avoiding arbitrary consensus thresholds. The approach also has scope limits: event sampling is specific to pairwise-decomposable quality functions, while alternative samplings are more general.
Problem
Community detection must handle many candidate partitions and meaningful network structure appearing at different scales, without an obvious single partition or resolution value to select.
Method
The paper samples modularity resolutions with event sampling and applies hierarchical consensus clustering based on modified modularity to ensembles of input partitions.
Results
The method recovers hierarchical structure almost perfectly in a synthetic benchmark and identifies no communities in LFR networks with µ ≥0.8.
Takeaways & Limitations
The consensus hierarchy automatically identifies relevant network scales and can combine features from partitions obtained at different resolutions.
Takeaways & Limitations
Event sampling is specific to quality functions decomposable as sums over vertex pairs, whereas exponential and linear sampling are more general for other techniques.
Abstract
from arXiv · showhide
Networks often exhibit structure at disparate scales. We propose a method for identifying community structure at different scales based on multiresolution modularity and consensus clustering. Our contribution consists of two parts. First, we propose a strategy for sampling the entire range of possible resolutions for the multiresolution modularity quality function. Our approach is directly based on the properties of modularity and, in particular, provides a natural way of avoiding the need to increase the resolution parameter by several orders of magnitude to break a few remaining small communities, necessitating the introduction of ad-hoc limits to the resolution range with standard sampling approaches. Second, we propose a hierarchical consensus clustering procedure, based on a modified modularity, that allows one to construct a hierarchical consensus structure given a set of input partitions. While here we are interested in its application to partitions sampled using multiresolution modularity, this consensus clustering procedure can be applied to the output of any clustering algorithm. As such, we see many potential applications of the individual parts of our multiresolution consensus clustering procedure in addition to using the procedure itself to identify hierarchical structure in networks.
Introduction
The paper addresses two recurring community-detection challenges: selecting among many stochastic or multiresolution partitions and identifying structure across network scales. It combines event sampling of modularity resolutions with hierarchical consensus clustering based on a modified modularity.
- Introduction: Many community-detection methods produce multiple plausible partitions, leaving no reliable way to select a single best one.The alternatives can arise from different algorithms, stochastic runs, or resolution-parameter values.
- Introduction: Consensus clustering combines an ensemble of partitions into a representative partition that is more similar on average to the ensemble, while primarily reducing noise rather than guaranteeing a better objective-function solution.The paper emphasizes that consensus clustering provides robustness, not necessarily a higher-quality optimization result.
- Introduction: The proposed consensus procedure uses modified modularity with an ensemble-based null model to assess the statistical significance of co-classification.This design avoids identifying communities in random networks without requiring an arbitrary threshold.
- Introduction: Recursively applying the consensus procedure to detected clusters yields simpler, interpretable hierarchical structures and avoids sweeping threshold values or computationally expensive sorting.Recursion stops when a cluster has no significant sub-clusters.
- Introduction: Event sampling targets network scales more evenly than standard resolution sampling when modularity resolutions span several orders of magnitude and community sensitivity varies across the range.The strategy directly exploits the behavior of the modularity quality function.
- Introduction: The method is especially suited to multiresolution modularity because a single consensus partition may be inadequate when networks contain meaningful structure at different scales.The hierarchical consensus structure is intended to preserve information across those scales.
Results
The HC procedure generally recovers planted or multiscale community structure, but its performance depends on ensemble size, resolution sampling, and significance settings. It produces interpretable hierarchies and applies to benchmark and brain networks, while conservatively splitting communities and sometimes introducing spurious intermediate levels.
- Comparison with Lancichinetti-Fortunato consensus clustering: HC significantly outperforms the best individual-partition baseline for fixed-resolution ensembles and nearly perfectly recovers planted communities, including from low-quality modularity partitions.With Infomap inputs, HC provides a smaller improvement, especially at high mixing parameter µ.
- Comparison with Lancichinetti-Fortunato consensus clustering: For multiresolution ensembles, the best initial partition performs better than consensus partitions, but HC comes close to identifying the difficult-to-select optimal resolution.This gap is especially pronounced at large µ.
- Comparison with Lancichinetti-Fortunato consensus clustering: HC requires a sufficiently large initial ensemble, after which it can outperform LF; increasing ensemble size resolves smaller communities, while larger α raises over-fitting risk.The minimum ensemble size also increases as α decreases.
- Hierarchical benchmark performance: Event sampling recovers hierarchical benchmark structure more accurately and tolerates more noise than exponential γ-sampling, including meaningful structure at p0 = 0.6.On a hierarchical benchmark, event sampling with the local permutation model recovered the hierarchy almost perfectly and identified the second level more accurately than any individual partition.
- Hierarchical benchmark performance: HC successfully identifies hierarchical structure across benchmark scales, matching strong individual-partition performance for coarse levels and identifying when communities should not be split further.For larger 10,000-node networks, comparable results require larger initial ensembles.
- Real Networks: The method is conservative when splitting communities, so consensus hierarchies often contain spurious intermediate levels formed by merging ground-truth clusters.Results were reasonably robust to changing α from 0.05 to 0.01 in the real-network examples.
- Real Networks: On real networks, HC yields simpler descriptions than full partition ensembles and reveals nested, spatially organized, multiscale structure in human and rat brain networks.The rat analysis recovers previously identified modules while revealing additional associations and their arrangement across scales.
Discussion
The paper addresses multiple community solutions and multiscale structure with hierarchical consensus clustering and multiresolution sampling. The resulting consensus hierarchy is usually simpler than the original ensemble, while its best partition is typically comparable to the ensemble’s best partition.
- Discussion: The hierarchical consensus algorithm identifies multiscale community structure from input partitions without requiring an arbitrary co-classification threshold.The authors report competitiveness with the LF consensus procedure when its threshold is optimized using artificial ground-truth examples.
- Discussion: The consensus hierarchy typically has only a few nested levels, making network structure easier to interpret than the original partition ensemble.
- Discussion: The best partition in the consensus hierarchy is usually comparable to the best partition in the original ensemble for artificial and real-world examples with ground-truth communities.
- Discussion: The event-sampling technique is specific to quality functions decomposable as sums over vertex pairs, whereas linear and exponential sampling generalize more readily to other multiresolution methods.
Methods
The methods combine multiresolution modularity, event sampling across meaningful resolution scales, and consensus clustering based on partition-derived null models. A local permutation model supports recursive consensus clustering, while event sampling avoids wasting samples in highly fragmented resolution regimes.
- Sampling Strategies for γ: The meaningful resolution range uses an exactly computable upper bound and an iteratively estimated lower bound, with iteration stopping when sampled partitions are trivial.The upper bound is the smallest γ making Aij − γPij ≤ 0 for every pair; the lower-bound procedure updates samples below the current estimate.
- Sampling Strategies for γ: Linear and exponential sampling can waste many samples where networks are nearly fragmented into singletons, leaving little information about community structure.
- Sampling Strategies for γ: Event sampling allocates resolution samples by equally spaced values of a scale measure derived from ferromagnetic and antiferromagnetic pair contributions.The pair-contribution sets change only at discrete events, which can be identified to construct the sampling map.
- Consensus Clustering: Consensus clustering combines multiple partitions through a co-classification matrix and applies a modularity-like objective with a partition-based statistical null model.The co-classification matrix is treated as a network, while the null model estimates expected co-classification and its variability.
- Null Models for Consensus Clustering: The local permutation model fixes one node’s community assignment while randomizing the other, providing a compromise between splitting unsupported groups and preserving clusters.The authors prefer this model because the global permutation model can split individual nodes or small groups, while other tested models can be too aggressive or too conservative.
- Consensus Modularity: The consensus modularity uses statistical significance under the local permutation model, and experiments optimize it with an iterated GenLouvain algorithm.