Simple evolving random graphs
arXiv:2312.02952 · doi:10.1103/PhysRevE.109.064304
Abstract
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 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.
13 pages, 6 figures; v2: various small improvements and added references
References in corpus (8)
- Kinetic Theory of Random Graphs: from Paths to Cycles
- Phase Transition with Non-Thermodynamic States in Reversible Polymerization
- Finite Size Fluctuations in Interacting Particle Systems
- Unicyclic Components in Random Graphs
- Non-extensive super-cluster states in aggregation with fragmentation
- Condensates in Driven Aggregation Processes
- Finite Size Effects in Addition and Chipping Processes
- Supercluster states and phase transitions in aggregation-fragmentation processes