Graph compression: The effect of clusters

Emmanuel Abbe

doi:10.1109/ALLERTON.2016.7852203

Graph compression: The effect of clusters

Emmanuel Abbe

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

17 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-8
Number of pages	8
ISBN (Electronic)	9781509045495
DOIs	https://doi.org/10.1109/ALLERTON.2016.7852203
State	Published - Feb 10 2017
Event	54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 - Monticello, United States Duration: Sep 27 2016 → Sep 30 2016

Publication series

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

Other

Other	54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
Country/Territory	United States
City	Monticello
Period	9/27/16 → 9/30/16

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Computational Theory and Mathematics
Computer Networks and Communications
Hardware and Architecture
Control and Optimization

Access to Document

10.1109/ALLERTON.2016.7852203

Cite this

Abbe, E. (2017). Graph compression: The effect of clusters. In 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 (pp. 1-8). Article 7852203 (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2016.7852203

@inproceedings{9bdd6489814a4aa1a946d608b79a5698,

title = "Graph compression: The effect of clusters",

abstract = "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{\'e}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{\'e}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.",

author = "Emmanuel Abbe",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 ; Conference date: 27-09-2016 Through 30-09-2016",

year = "2017",

month = feb,

day = "10",

doi = "10.1109/ALLERTON.2016.7852203",

language = "English (US)",

series = "54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1--8",

booktitle = "54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016",

address = "United States",

}

Abbe, E 2017, Graph compression: The effect of clusters. in 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016., 7852203, 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Institute of Electrical and Electronics Engineers Inc., pp. 1-8, 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Monticello, United States, 9/27/16. https://doi.org/10.1109/ALLERTON.2016.7852203

Graph compression: The effect of clusters. / Abbe, Emmanuel.
54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016. Institute of Electrical and Electronics Engineers Inc., 2017. p. 1-8 7852203 (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Graph compression: The effect of clusters

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this