# Fast consensus clustering in complex networks

arXiv: https://arxiv.org/abs/1902.04014 · HTML: https://mlsanity.com/paper/1902.04014/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2019.

## Built on by (most cited first, 2 of 2)

- [LSEC: Large-scale spectral ensemble clustering](https://mlsanity.com/paper/2106.09852/) (2021)
- [Community Detection in Networks: A Rough Sets and Consensus Clustering Approach](https://mlsanity.com/paper/2406.12412/) (2024)

## Abstract (arXiv)

Algorithms for community detection are usually stochastic, leading to different partitions for different choices of random seeds. Consensus clustering has proven to be an effective technique to derive more stable and accurate partitions than the ones obtained by the direct application of the algorithm. However, the procedure requires the calculation of the consensus matrix, which can be quite dense if (some of) the clusters of the input partitions are large. Consequently, the complexity can get dangerously close to quadratic, which makes the technique inapplicable on large graphs. Here we present a fast variant of consensus clustering, which calculates the consensus matrix only on the links of the original graph and on a comparable number of additional node pairs, suitably chosen. This brings the complexity down to linear, while the performance remains comparable as the full technique. Therefore, our fast consensus clustering procedure can be applied on networks with millions of nodes and links.