Accelerating Community Detection by Using K-core Subgraphs

Abstract

Community detection is expensive, and the cost generally depends at least linearly on the number of vertices in the graph. We propose working with a reduced graph that has many fewer nodes but nonetheless captures key community structure. The K-core of a graph is the largest subgraph within which each node has at least K connections. We propose a framework that accelerates community detection by applying an expensive algorithm (modularity optimization, the Louvain method, spectral clustering, etc.) to the K-core and then using an inexpensive heuristic (such as local modularity maximization) to infer community labels for the remaining nodes. Our experiments demonstrate that the proposed framework can reduce the running time by more than 80% while preserving the quality of the solutions. Recent theoretical investigations provide support for using the K-core as a reduced representation.

15 pages, 8 figures

References in corpus (18)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Assortative mixing in networks
• Near linear time algorithm to detect community structures in large-scale networks
• Stochastic blockmodels and community structure in networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Social Structure of Facebook Networks
• k-core organization of complex networks
• Spectral methods for network community detection and graph partitioning
• A Bayesian Approach to Network Modularity
• Clustering in complex networks. II. Percolation properties
• Empirical Comparison of Algorithms for Network Community Detection
• The k-core and branching processes

Cited by in corpus (6)

• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks by Exploiting k-core Decomposition and Motifs
• K-Core Minimization: A Game Theoretic Approach
• Sparsity Measure of a Network Graph: Gini Index
• Improving the accuracy of the k-shell method by removing redundant links-from a perspective of spreading dynamics
• On Rich Clubs of Path-Based Centralities in Networks