Reducing Large Graphs to Small Supergraphs: A Unified Approach
Summarizing a large graph with a much smaller graph is critical for applications such as speeding up graphalgorithms and interactive visualization. In this paper, we propose ConDeNSe (Conditional Diversified Network Summarization), a Minimum Description Length-based method that summarizes a given graph with approximate ‘supergraphs’ conditioned on diverse, predefined structural patterns.
Our focus here is on the 3rd module of ConDeNSe, which selects the structural patterns that will constitute the supernodes of the generated supergraphs. The input is a set of structures, and our methods sift through them and select the ones that will be included in the supergraphs. We have developed three powerful, parallel methods: Step-P, Step-PA and k-Step.