TY - GEN

T1 - Graph compression

T2 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

AU - Abbe, Emmanuel

PY - 2017/2/10

Y1 - 2017/2/10

N2 - 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 Erdos-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 Erdos-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.

AB - 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 Erdos-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 Erdos-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.

UR - http://www.scopus.com/inward/record.url?scp=85015222249&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015222249&partnerID=8YFLogxK

U2 - 10.1109/ALLERTON.2016.7852203

DO - 10.1109/ALLERTON.2016.7852203

M3 - Conference contribution

AN - SCOPUS:85015222249

T3 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

SP - 1

EP - 8

BT - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 27 September 2016 through 30 September 2016

ER -