Dynamics of Random Graphs with Bounded Degrees

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.

10 pages, 6 figures, 2 tables

References in corpus (5)

• On the critical behavior of the Susceptible-Infected-Recovered (SIR) model on a square lattice
• Kinetic Theory of Random Graphs: from Paths to Cycles
• Percolation with Multiple Giant Clusters
• Unicyclic Components in Random Graphs
• 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