- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Network compression with configuration models and the minimum description length

Laurent Hébert-Dufresne1,2, Jean-Gabriel Young1,2,3,4, Alexander Daniels1, Alec Kirkley5,6,7, and Antoine Allard4,8,1

PDF

Phys. Rev. E 110, 034305 – Published 6 September, 2024

DOI: https://doi.org/10.1103/PhysRevE.110.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.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (45)

  1. P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences] 5, 17 (1960).
  2. M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64, 026118 (2001).
  3. B. K. Fosdick, D. B. Larremore, J. Nishimura, and J. Ugander, Configuring random graph models with fixed degree sequences, SIAM Rev. 60, 315 (2018).
  4. A. Vázquez and Y. Moreno, Resilience to damage of graphs with degree correlations, Phys. Rev. E 67, 015101(R) (2003).
  5. L. Hébert-Dufresne, J. A. Grochow, and A. Allard, Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition, Sci. Rep. 6, 31708 (2016).
  6. A. Allard and L. Hébert-Dufresne, Percolation and the effective structure of complex networks, Phys. Rev. X 9, 011023 (2019).
  7. P. D. Grünwald, The Minimum Description Length Principle (MIT Press, Cambridge, UK, 2007).
  8. D. J. C. MacKay, Information Theory, Inference and Learning Algorithms, 1st ed. (Cambridge University Press, Cambridge, UK, 2003).
  9. T. P. Peixoto, Parsimonious module inference in large networks, Phys. Rev. Lett. 110, 148701 (2013).
  10. T. P. Peixoto, Bayesian stochastic blockmodeling, in Advances in Network Clustering and Blockmodeling, edited by P. Doreian, V. Batagelj, and A. Ferligoj (Wiley, New York, 2019), pp. 289–332.
  11. D. Hric, T. P. Peixoto, and S. Fortunato, Network structure, metadata, and the prediction of missing nodes and annotations, Phys. Rev. X 6, 031038 (2016).
  12. A. Kirkley, Spatial regionalization based on optimal information compression, Commun. Phys. 5, 249 (2022).
  13. A. Kirkley, Identifying hubs in directed networks, Phys. Rev. E 109, 034310 (2024).
  14. T. P. Peixoto and M. Rosvall, Modelling sequences and temporal networks with dynamic community structures, Nat. Commun. 8, 582 (2017).
  15. A. Kirkley, A. Rojas, M. Rosvall, and J.-G. Young, Compressing network populations with modal networks reveal structural diversity, Commun. Phys. 6, 148 (2023).
  16. A. Kirkley, Inference of dynamic hypergraph representations in temporal interaction data, Phys. Rev. E 109, 054306 (2024).
  17. D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature (London) 393, 440 (1998).
  18. A. Allard, L. Hébert-Dufresne, J.-G. Young, and L. J. Dubé, General and exact approach to percolation on random graphs Phys. Rev. E 92, 062807 (2015).
  19. M. E. J. Newman, Assortative mixing in networks Phys. Rev. Lett. 89, 208701 (2002).
  20. M. Noy, Graph enumeration, in Handbook of Enumerative Combinatorics (Chapman and Hall/CRC, Boca Raton, FL, 2015), pp. 403–442.
  21. C. R. Lucatero, Combinatorial enumeration of graphs, in Probability, Combinatorics and Control, edited by A. Kostogryzov and V. Korolev (IntechOpen London, UK, 2019), pp. 1–24.
  22. B. D. McKay and N. C. Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, Eur. J. Combin. 11, 565 (1990).
  23. B. D. McKay and N. C. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2) Combinatorica 11, 369 (1991).
  24. A. Liebenau and N. Wormald, Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, J. European Mathematical Soc. 26, 1 (2024).
  25. T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. (John Wiley & Sons, New York, 2006).
  26. T. P. Peixoto, Nonparametric Bayesian inference of the microcanonical stochastic block model, Phys. Rev. E 95, 012317 (2017).
  27. M. Jerdee, A. Kirkley, and M. Newman, Improved estimates for the number of non-negative integer matrices with given row and column sums, Proc. R. Soc. A 480, 20230470 (2024).
  28. J. Moody, Peer influence groups: identifying dense clusters in large networks, Soc. Netw. 23, 261 (2001).
  29. M. E. J. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA 98, 404 (2001).
  30. P. M. Gleiser and L. Danon, Community Structure in Jazz, Adv. Complex Syst. 06, 565 (2003).
  31. M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74, 036104 (2006).
  32. J. Kunegis, A. Lommatzsch, and C. Bauckhage, The Slashdot zoo: mining a social network with negative edges, in Proceedings of the 18th International Conference on the World Wide Web (WWW'09) (ACM, New York, 2009), p. 741.
  33. M. De Domenico, V. Nicosia, A. Arenas, and V. Latora, Structural reducibility of multilayer networks, Nat. Commun. 6, 6864 (2015).
  34. M. Á. Serrano, M. Boguñá, and F. Sagués, Uncovering the hidden geometry behind metabolic networks, Mol. BioSyst. 8, 843 (2012).
  35. J. Hadfield, C. Megill, S. M. Bell, J. Huddleston, B. Potter, C. Callender, P. Sagulenko, T. Bedford, and R. A. Neher, Nextstrain: real-time tracking of pathogen evolution, Bioinformatics 34, 4121 (2018).
  36. G. Palla, I. Derényi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature (London) 435, 814 (2005).
  37. C. Robertson, Flowers and Insects; Lists of Visitors of Four Hundred and Fifty-three Flowers (The Science Press Printing Co., Lancaster PA, USA, 1928).
  38. S.-Y. Takemura, A. Bharioke, Z. Lu, A. Nern, S. Vitaladevuni, P. K. Rivlin, W. T. Katz, D. J. Olbris, S. M. Plaza, P. Winston, T. Zhao, J. A. Horne, R. D. Fetter, S. Takemura, K. Blazek, L.-A. Chang, O. Ogundeyi, M. A. Saunders, V. Shapiro, C. Sigmund et al., A visual motion detection circuit suggested by Drosophila connectomics, Nature (London) 500, 175 (2013).
  39. M. Kaiser and C. C. Hilgetag, Spatial growth of real-world networks, Phys. Rev. E 69, 036103 (2004).
  40. J. Kunegis, KONECT: the Koblenz network collection, in Proceedings of the 22nd International Conference on World Wide Web (Rio de Janeiro Brazil ACM, 2013), pp. 1343–1350.
  41. R. Matei, A. Iamnitchi, and P. Foster, Mapping the Gnutella network, IEEE Internet Comput. 6, 50 (2002).
  42. B. Karrer, M. E. J. Newman, and L. Zdeborová, Percolation on sparse networks, Phys. Rev. Lett. 113, 208702 (2014).
  43. M. Boguñá, R. Pastor-Satorras, A. Díaz-Guilera, and A. Arenas, Models of social networks based on social distance attachment, Phys. Rev. E 70, 056122 (2004).
  44. R. Pastor-Satorras and A. Vespignani, Epidemic spreading in scale-free networks, Phys. Rev. Lett. 86, 3200 (2001).
  45. L. Hébert-Dufresne, G. St-Onge, J. Meluso, J. Bagrow, and A. Allard, Hierarchical team structure and multidimensional localization (or siloing) on networks, J. Phys. Complex. 4, 035002 (2023).

Outline

Information

Phys. Rev. E 110, 034305– Published 6 September, 2024
  • Received 29 May 2024
  • Accepted 16 August 2024
Article part of CHORUS
Crossmark - Check for updates button

©2024 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation