Dynamics of random graphs with bounded degrees

DOI10.1088/1742-5468/2011/11/P11008zbMATH Open1456.05139arXiv1110.1134MaRDI QIDQ3301221FDOQ3301221

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)