Reducing large graphs to small supergraphs: a unified approach

摘要: Summarizing a large graph with much smaller is critical for applications like speeding up intensive algorithms and interactive visualization. In this paper, we propose CONditional Diversified Network Summarization (CondeNSe), Minimum Description Length-based method that summarizes given approximate “supergraphs” conditioned on set of diverse, predefined structural patterns. CondeNSe features unified pattern discovery module effective summary assembly methods, including powerful parallel approach, k-Step, creates high-quality summaries not biased toward specific structures. By leveraging ’s ability to efficiently handle overlapping structures, contribute novel evaluation seven existing clustering techniques by going beyond classic cluster quality measures. Extensive empirical real networks in terms compression, runtime, shows finds 30–50% more compact than baselines, 75–90% fewer structures equally good node coverage.