2011/10/31 by E. Ben-Naim, E Ben-Naim, P L Krapivsky +1 · 2 citations
Mathematics · Physics and Astronomy · #Bounded function #Complex Network Analysis Techniques #Giant component #Percolation (cognitive psychology) #Percolation threshold #Random graph #Realization (probability) #Set (abstract data type) #Stochastic process #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.dis-nn #cond-mat.stat-mech #math.PR
paper · pdf · doi:10.1088/1742-5468/2011/11/p11008
published as J. Stat. Mech. P11008 (2011) · 10 pages, 6 figures, 2 tables
openalex publication_date 2011/11/11 · arxiv created 2011/11/15 · arxiv updated 2011/11/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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–Jacobi formalism. We calculate the nontrivial percolation thresholds for the emergence of the giant component when d ≥ 3. Also, we estimate the number of steps that have occurred before the giant component spans the entire system and the total number of steps that have occurred before the regular random graph forms. These quantities are non-self-averaging, namely, they fluctuate from realization to realization even in the thermodynamic limit.