Degree-preserving graph dynamics: a versatile process to construct random networks

• Published in: Journal of complex networks 2023-11, Vol.11 (6)
• Main Authors: Erdős, Péter L, Kharel, Shubha R, Mezei, Tamás R, Toroczkai, Zoltan
• Format: Article
• Language: English
• Subjects: degree-preserving growth (DPG); Degree-preserving network growth; Matching Theory; MATHEMATICS AND COMPUTING; network growth models; power-law degree distribution; Prime gaps; Reimann Hypothesis; synthetic networks
• ISSN: 2051-1329; 2051-1329
• DOI: 10.1093/comnet/cnad046

Abstract Real-world networks evolve over time via the addition or removal of vertices and edges. In current network evolution models, vertex degree varies or grows arbitrarily. A recently introduced degree-preserving network growth (DPG) family of models preserves vertex degree, resulting in structures significantly different from and more diverse than previous models ([Nature Physics 2021, DOI:10.1038/s41567-021-01417-7]). Despite its degree preserving property, the DPG model is able to replicate the output of several well-known real-world network growth models. Simulations showed that many real-world networks can also be constructed from small seed graphs via the DPG process. Here, we start the development of a rigorous mathematical theory underlying the DPG family of network growth models. We prove that the degree sequence of the output of some of the well-known, real-world network growth models can be reconstructed via the DPG process, using proper parametrization. We also show that the general problem of deciding whether a simple graph can be obtained via the DPG process from a small seed (DPG feasibility) is, however, NP-complete. It is an intriguing open problem to uncover whether there is a structural reason behind the DPG-constructability of real-world networks. Keywords: network growth models; degree-preserving growth (DPG); matching theory; synthetic networks; power-law degree distribution.