FastEnsemble: Scalable ensemble clustering on large networks

Many community detection algorithms are inherently stochastic, leading to variations in their output depending on input parameters and random seeds. This variability makes the results of a single run of these algorithms less reliable. Moreover, different clustering algorithms, optimization criteria (e.g., modularity and the Constant Potts model), and resolution values can result in substantially different partitions on the same network. Consensus clustering methods, such as Ensemble Clustering for Graphs (ECG) and FastConsensus, have been proposed to reduce the instability of non-deterministic algorithms and improve their accuracy by combining a set of partitions resulting from multiple runs of a clustering algorithm. In Complex Networks and their Applications 2024, we introduced FastEnsemble, a new consensus clustering method; here we present a more extensive evaluation of this method. Our results on both real-world and synthetic networks show that FastEnsemble produces more accurate clusterings than two other consensus clustering methods, ECG and FastConsensus, for many model conditions. Furthermore, FastEnsemble is fast enough to be used on networks with more than 3 million nodes, and so improves on the speed and scalability of FastConsensus. Finally, we showcase the utility of consensus clustering methods in mitigating the effect of resolution limit and clustering networks that are only partially covered by communities.Author summary: Consensus (ensemble) clustering methods, such as FastConsensus and Ensemble Clustering for Graphs (ECG), combine partitions from multiple runs of the same clustering algorithm, in order to improve stability and accuracy of the output partition. In this study, we present a new ensemble clustering method, FastEnsemble, and show that it provides improved accuracy under many conditions compared to FastConsensus and ECG. We show results using FastEnsemble with Leiden optimizing modularity or the Constant Potts model (CPM) and the Louvain algorithm. We show that FastEnsemble and other consensus clustering methods can reduce the effect of resolution limit for both modularity- and CPM-optimization. Finally, we demonstrate that consensus clustering methods can improve community detection over modularity-optimization using Leiden on networks with both clusterable and unclusterable regions.