How can we succinctly describe a million-node graph with a few simple sentences? Given a large graph, how can we find its most "important" structures, so that we can summarize it and easily visualize it? How can we measure the "importance" of a set of discovered subgraphs in a large graph? Starting with the observation that real graphs often consist of stars, bipartite cores, cliques, and chains, our main idea is to find the most succinct description of a graph in these "vocabulary" terms. To this end, we first mine candidate subgraphs using one or more graph partitioning algorithms. Next, we identify the optimal summarization using the minimum description length MDL principle, picking only those subgraphs from the candidates that together yield the best lossless compression of the graph-or, equivalently, that most succinctly describe its adjacency matrix.
['Danai Koutra', 'Ui-Gum Kang', 'Jilles Vreeken', 'Christos Faloutsos']
Summarizing and understanding large graphs