Network compression with configuration models and the minimum description length
- 6 September 2024
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 110 (3) , 034305
Abstract
Random network models, constrained to reproduce specific statistical features, are often used to represent and analyze network data and their mathematical descriptions. Chief among them, the configuration model constrains random networks by their degree distribution and is foundational to many areas of network science. However, configuration models and their variants are often selected based on intuition or mathematical and computational simplicity rather than on statistical evidence. To evaluate the quality of a network representation, we need to consider both the amount of information required to specify a random network model and the probability of recovering the original data when using the model as a generative process. To this end, we calculate the approximate size of network ensembles generated by the popular configuration model and its generalizations, including versions accounting for degree correlations and centrality layers. We then apply the minimum description length principle as a model selection criterion over the resulting nested family of configuration models. Using a dataset of over 100 networks from various domains, we find that the classic configuration model is generally preferred on networks with an average degree above 10, while a layered configuration model constrained by a centrality metric offers the most compact representation of the majority of sparse networks.Keywords
Funding Information
- National Science Foundation (DMS-1829826)
- Natural Sciences and Engineering Research Council of Canada (2019-05183)
This publication has 36 references indexed in Scilit:
- Compressing network populations with modal networks reveal structural diversityCommunications Physics, 2023
- Spatial regionalization based on optimal information compressionCommunications Physics, 2022
- Modelling sequences and temporal networks with dynamic community structuresNature Communications, 2017
- Structural reducibility of multilayer networksNature Communications, 2015
- A visual motion detection circuit suggested by Drosophila connectomicsNature, 2013
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Peer influence groups: identifying dense clusters in large networksSocial Networks, 2001
- Collective dynamics of ‘small-world’ networksNature, 1998
- Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2)Combinatorica, 1991
- Asymptotic Enumeration by Degree Sequence of Graphs of High DegreeEuropean Journal of Combinatorics, 1990