Simple evolving random graphs

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 $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.

arXiv comment13 pages, 6 figures; v2: various small improvements and added references

References in corpus (28)

• Are randomly grown graphs really random?
• Scaling Theory and Exactly Solved Models In the Kinetics of Irreversible Aggregation
• Degree Distributions of Growing Networks
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Anomalous percolating properties of growing networks
• The early evolution of the H-free process
• Network Transitivity and Matrix Models
• Loops of any size and Hamilton cycles in random scale-free networks
• Kinetic Theory of Random Graphs: from Paths to Cycles
• Phase transitions in a complex network
• The Asymptotics of Large Constrained Graphs
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Extremal Properties of Random Systems
• The triangle-free process and the Ramsey number $R(3,k)$
• Circuits in random graphs: from local trees to global loops
• Universal Properties of Growing Networks
• Stable Distributions in Stochastic Fragmentation
• Perturbing General Uncorrelated Networks
• Asymmetric evolving random networks
• Phase Transition with Non-Thermodynamic States in Reversible Polymerization
• Symmetry and species segregation in diffusion-limited pair annihilation
• A simple asymmetric evolving random network
• 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

Cited by in corpus (1)

• Gelation in input-driven aggregation