Graph compression: The effect of clusters
Emmanuel A. Abbe · 2016
This paper investigates the fundamental limits for compressing random graphs. It also discusses the compression of data on graphs. The graphs are assumed to have labelled vertices. The most basic example is the Erdös-Rényi model, which corresponds to the well-understood case of compressing i.i.d. bits. This paper investigates inhomogeneous random graphs that have clusters, or equivalently, block models. These correspond to mixtures of Erdös-Rényi models for which basic tools for i.i.d.-like sources may not apply, capturing a key feature of general network models. It is shown how the fundamental limit of lossless compression for such models takes different forms as the graph gets sparser. The paper also introduces connections between compression and clustering, how each field can impact the other, and how clustering can help for the compression of data on graphs.