Fast consensus clustering in complex networks

Abstract

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.

6 pages, 5 figures. The code of the fast consensus clustering technique introduced in the paper is freely accessible at https://github.com/adityat/fastconsensus. Final version published in Physical Review E

References in corpus (9)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• Consensus clustering in complex networks
• Robust Detection of Dynamic Community Structure in Networks