  How do graph clustering techniques compare with respect to their
summarization power? How well can they summarize a million-node graph with a
few representative structures? Graph clustering or community detection
algorithms can summarize a graph in terms of coherent and tightly connected
clusters. In this paper, we compare and contrast different techniques: METIS,
Louvain, spectral clustering, SlashBurn and KCBC, our proposed k-core-based
clustering method. Unlike prior work that focuses on various measures of
cluster quality, we use vocabulary structures that often appear in real graphs
and the Minimum Description Length (MDL) principle to obtain a graph summary
per clustering method. Our main contributions are: (i) Formulation: We propose
a summarization-based evaluation of clustering methods. Our method,
VOG-OVERLAP, concisely summarizes graphs in terms of their important structures
which lead to small edge overlap, and large node/edge coverage; (ii) Algorithm:
we introduce KCBC, a graph decomposition technique, in the heart of which lies
the k-core algorithm (iii) Evaluation: We compare the summarization power of
five clustering techniques on large real graphs, and analyze their compression
performance, summary statistics and runtimes.

Information Retrieval;Social and Information Networks