Dynamics of Random Graphs with Bounded Degrees
E. Ben-Naim and P. L. Krapivsky
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\geq 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.
source,
ps,
pdf