  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.
