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

DOI10.1093/COMNET/CNAD046arXiv2111.11994MaRDI QIDQ6505259FDOQ6505259

Shubha R. Kharel, Péter L. Erdős, Tamás Róbert Mezei, Z. Toroczkai

Abstract: Real-world networks evolve over time via additions or removals 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 well-studied real-world networks can be constructed from small seed graphs. 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, as expected, NP-complete. It is an important open problem to uncover whether there is a structural reason behind the DPG-constructibility of real-world networks.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex degrees (05C07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

This page was built for publication: Degree-preserving graph dynamics -- a versatile process to construct random networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505259)