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

• {{#invoke:WikidataIB|getLink|Q3286850}} scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q3994494}} scientific article; zbMATH DE number 41266 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4040102}} scientific article; zbMATH DE number 193260 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4225410}} scientific article; zbMATH DE number 1239549 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4519896}} scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4938890}} scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q5287558}} scientific article; zbMATH DE number 236854 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q2746970}} A guide to first-passage processes
• {{#invoke:WikidataIB|getLink|Q3066842}} A kinetic view of statistical physics
• {{#invoke:WikidataIB|getLink|Q4286301}} Almost all regular graphs are hamiltonian
• {{#invoke:WikidataIB|getLink|Q5450339}} An Introduction to Nonlinear Partial Differential Equations, Second Edition
• {{#invoke:WikidataIB|getLink|Q4547718}} Community structure in social and biological networks
• {{#invoke:WikidataIB|getLink|Q3823119}} Fault Tolerance in Networks of Bounded Degree
• {{#invoke:WikidataIB|getLink|Q852892}} Gelation in coagulating systems
• {{#invoke:WikidataIB|getLink|Q5896385}} Generating random regular graphs
• {{#invoke:WikidataIB|getLink|Q4426282}} Kinetic anomalies in addition-aggregation processes
• {{#invoke:WikidataIB|getLink|Q788676}} On the critical behavior of the general epidemic process and dynamical percolation
• {{#invoke:WikidataIB|getLink|Q4246764}} Percolation
• {{#invoke:WikidataIB|getLink|Q5462482}} Percolation with multiple giant clusters
• {{#invoke:WikidataIB|getLink|Q4291211}} Random Graph Processes with Degree Restrictions
• {{#invoke:WikidataIB|getLink|Q4161142}} Random directed graph distributions and the triad census in social networks†
• {{#invoke:WikidataIB|getLink|Q4547693}} Random graph models of social networks
• {{#invoke:WikidataIB|getLink|Q5841480}} Stochastic Problems in Physics and Astronomy
• {{#invoke:WikidataIB|getLink|Q1924140}} Sudden emergence of a giant \(k\)-core in a random graph
• {{#invoke:WikidataIB|getLink|Q5288006}} The birth of the giant component
• {{#invoke:WikidataIB|getLink|Q2725029}} The scaling window of the 2-SAT transition
• {{#invoke:WikidataIB|getLink|Q4812437}} 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)