Quantifying the compressibility of complex networks
Abstract
Real-world networks are complex, comprising vast webs of interconnected elements performing a diverse array of social and biological functions. Common among many networks, however, is the pressure to be efficiently compressed—either in the brain or in the genetic code. But just as files on a computer can be compressed to differing degrees, what makes one network more compressible than another? To answer this question, we adapt tools from information theory to quantify the compressibility of a network. Studying real-world and model networks, we find that hierarchical organization—with tight clustering and heterogeneous degrees—increases compressibility, enabling compressed representations across scales. Generally, our framework provides an information-theoretic method for investigating the interplay between network structure and compression.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 04, 2021
- Source ID
- 10.1073/pnas.2023473118
Entities
People
- Christopher W. Lynn
- Danielle Bassett
Organizations
- Army Research Office
- City University of New York
- James S. McDonnell Foundation
- National Institute of Mental Health
- National Science Foundation
- Princeton University
- United States Army Research Laboratory
- University of Pennsylvania