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 (15)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very 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
• Community detection algorithms: a comparative analysis
• 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
• Multiresolution community detection for megascale networks by information-based replica correlations
• Ensemble Clustering for Graphs

Cited by in corpus (9)

• Community detection in node-attributed social networks: a survey
• Exploring the solution landscape enables more reliable network community detection
• Revealing consensus and dissensus between network partitions
• LSEC: Large-scale spectral ensemble clustering
• Robustness of community structure under edge addition
• Identifying robust features of community structure in complex networks
• Community Detection in Networks: A Rough Sets and Consensus Clustering Approach
• Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
• Community membership consistency applied to corporate board interlock networks