Degree-preserving graph dynamics -- a versatile process to construct random networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914631134478336 |
|---|---|
| author | Erdős, Péter L. Kharel, Shubha R. Mezei, Tamás R. Toroczkai, Zoltán |
| author_facet | Erdős, Péter L. Kharel, Shubha R. Mezei, Tamás R. Toroczkai, Zoltán |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_11994 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Degree-preserving graph dynamics -- a versatile process to construct random networks Erdős, Péter L. Kharel, Shubha R. Mezei, Tamás R. Toroczkai, Zoltán Combinatorics Discrete Mathematics Physics and Society 05C07, 05C80, 05C82, 91D30, 68R10, 68W40, 68Q15, 03D15 G.2.2; G.2.3; F.1.3 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. |
| title | Degree-preserving graph dynamics -- a versatile process to construct random networks |
| topic | Combinatorics Discrete Mathematics Physics and Society 05C07, 05C80, 05C82, 91D30, 68R10, 68W40, 68Q15, 03D15 G.2.2; G.2.3; F.1.3 |
| url | https://arxiv.org/abs/2111.11994 |