Simple evolving random graphs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912018424922112 |
|---|---|
| author | Krapivsky, P. L. |
| author_facet | Krapivsky, P. L. |
| contents | We study the evolution of graphs densifying by adding edges: Two vertices are chosen randomly, and an edge is (i) established if each vertex belongs to a tree; (ii) established with probability $p$ if only one vertex belongs to a tree; (iii) an attempt fails if both vertices belong to unicyclic components. Emerging simple random graphs contain only trees and unicycles. In the thermodynamic limit of an infinite number of vertices, the fraction of vertices in unicycles undergoes a phase transition resembling a percolation transition in classical random graphs. In classical random graphs, a complex giant component born at the transition eventually engulfs all finite components and densifies forever. The evolution of simple random graphs freezes when trees disappear. We quantify simple random graphs in the supercritical phase and the properties of the frozen state. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_02952 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Simple evolving random graphs Krapivsky, P. L. Probability Disordered Systems and Neural Networks Statistical Mechanics Physics and Society We study the evolution of graphs densifying by adding edges: Two vertices are chosen randomly, and an edge is (i) established if each vertex belongs to a tree; (ii) established with probability $p$ if only one vertex belongs to a tree; (iii) an attempt fails if both vertices belong to unicyclic components. Emerging simple random graphs contain only trees and unicycles. In the thermodynamic limit of an infinite number of vertices, the fraction of vertices in unicycles undergoes a phase transition resembling a percolation transition in classical random graphs. In classical random graphs, a complex giant component born at the transition eventually engulfs all finite components and densifies forever. The evolution of simple random graphs freezes when trees disappear. We quantify simple random graphs in the supercritical phase and the properties of the frozen state. |
| title | Simple evolving random graphs |
| topic | Probability Disordered Systems and Neural Networks Statistical Mechanics Physics and Society |
| url | https://arxiv.org/abs/2312.02952 |