Network compression with configuration models and the minimum description length

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 ten, while a Layered Configuration Model constrained by a centrality metric offers the most compact representation of the majority of sparse networks.

References in corpus (21)

• Epidemic spreading in scale-free networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Finding community structure in networks using the eigenvectors of matrices
• Random graphs with arbitrary degree distributions and their applications
• Community Structure in Jazz
• Layer aggregation and reducibility of multilayer interconnected networks
• Percolation on sparse networks
• Resilience to damage of graphs with degree correlations
• Parsimonious module inference in large networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Spatial Growth of Real-world Networks
• Modeling sequences and temporal networks with dynamic community structures
• Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
• Network structure, metadata and the prediction of missing nodes and annotations
• General and exact approach to percolation on random graphs
• Spatial regionalization based on optimal information compression
• Percolation and the effective structure of complex networks
• Compressing network populations with modal networks reveals structural diversity
• Identifying hubs in directed networks
• Improved estimates for the number of non-negative integer matrices with given row and column sums