Dynamics of Random Graphs with Bounded Degrees
arXiv:1110.1134 · doi:10.1088/1742-5468/2011/11/P11008
Abstract
We investigate the dynamic formation of regular random graphs. In our model, we pick a pair of nodes at random and connect them with a link if both of their degrees are smaller than d. Starting with a set of isolated nodes, we repeat this linking step until a regular random graph, where all nodes have degree d, forms. We view this process as a multivariate aggregation process, and formally solve the evolution equations using the Hamilton-Jacoby formalism. We calculate the nontrivial percolation thresholds for the emergence of the giant component when d>=3. Also, we estimate the number of steps until the giant component spans the entire system and the total number of steps until the regular random graph forms. These quantities are non self-averaging, namely, they fluctuate from realization to realization even in the thermodynamic limit.
arXiv comment10 pages, 6 figures, 2 tables
References in corpus (14)
- Community structure in social and biological networks
- The spread of epidemic disease on networks
- Scaling Theory and Exactly Solved Models In the Kinetics of Irreversible Aggregation
- Rare Events Statistics in Reaction--Diffusion Systems
- The Scaling Window of the 2-SAT Transition
- Extinction of an infectious disease: a large fluctuation in a non-equilibrium system
- On the critical behavior of the Susceptible-Infected-Recovered (SIR) model on a square lattice
- Kinetic Theory of Random Graphs: from Paths to Cycles
- Aggregation with Multiple Conservation Laws
- The path to fracture in granular flows: dynamics of contact networks
- Percolation with Multiple Giant Clusters
- Unicyclic Components in Random Graphs
- Kinetic Anomalies in Addition-Aggregation Processes
- Kinetics of Ring Formation
Cited by in corpus (8)
- Emergence of the giant weak-component in directed random graphs with arbitrary degree distributions
- Random graph approach to multifunctional molecular networks
- Dynamic Networks that Drive the Process of Irreversible Step-Growth Polymerization
- Analytical results on the polymerisation random graph model
- Native ultrametricity of sparse random ensembles
- Discrete Analog of the Burgers Equation
- Popularity-Driven Networking
- Black Holes, Complex Curves, and Graph Theory: Revising a Conjecture by Kasner