Dynamics of random graphs with bounded degrees

DOI10.1088/1742-5468/2011/11/P11008MaRDI QIDQ3301221zbMATH OpenFDO

Authors E. Ben-Naim, P. L. Krapivsky

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.1134

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

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.

Recommendations

• Edge percolation on a random regular graph of low degree
• The phase transition in the configuration model
• Critical percolation on random regular graphs
• Random Star Processes
• Percolation on sparse random graphs with given degree sequence

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 41266 (Why is no real title available?)
• scientific article; zbMATH DE number 193260 (Why is no real title available?)
• scientific article; zbMATH DE number 1239549 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• scientific article; zbMATH DE number 236854 (Why is no real title available?)
• A guide to first-passage processes
• A kinetic view of statistical physics
• Almost all regular graphs are hamiltonian
• An Introduction to Nonlinear Partial Differential Equations, Second Edition
• Community structure in social and biological networks
• Fault Tolerance in Networks of Bounded Degree
• Gelation in coagulating systems
• Generating random regular graphs
• Kinetic anomalies in addition-aggregation processes
• On the critical behavior of the general epidemic process and dynamical percolation
• Percolation
• Percolation with multiple giant clusters
• Random Graph Processes with Degree Restrictions
• Random directed graph distributions and the triad census in social networks†
• Random graph models of social networks
• Stochastic Problems in Physics and Astronomy
• Sudden emergence of a giant \(k\)-core in a random graph
• The birth of the giant component
• The scaling window of the 2-SAT transition
• Unicyclic components in random graphs

Cited in

(4)

• On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
• Analytic results on the polymerisation random graph model
• Black holes, complex curves, and graph theory: revising a conjecture by Kasner
• Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph

This page was built for publication: Dynamics of random graphs with bounded degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301221)