Graph compression: The effect of clusters

Emmanuel Abbe

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 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 languageEnglish (US)
Title of host publication54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-8
Number of pages8
ISBN (Electronic)9781509045495
DOIs
StatePublished - Feb 10 2017
Event54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 - Monticello, United States
Duration: Sep 27 2016Sep 30 2016

Publication series

Name54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

Other

Other54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
CountryUnited States
CityMonticello
Period9/27/169/30/16

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Graph compression: The effect of clusters'. Together they form a unique fingerprint.

  • 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). [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