Kinetic Theory of Random Graphs: from Paths to Cycles

Abstract

Structural properties of evolving random graphs are investigated. Treating linking as a dynamic aggregation process, rate equations for the distribution of node to node distances (paths) and of cycles are formulated and solved analytically. At the gelation point, the typical length of paths and cycles, l, scales with the component size k as l ~ k^{1/2}. Dynamic and finite-size scaling laws for the behavior at and near the gelation point are obtained. Finite-size scaling laws are verified using numerical simulations.

11 pages, 10 figures

References in corpus (15)

• Community structure in social and biological networks
• Random graphs with arbitrary degree distributions and their applications
• Scaling Theory and Exactly Solved Models In the Kinetics of Irreversible Aggregation
• Generic scale of the "scale-free" growing networks
• Subgraphs in random networks
• The Scaling Window of the 2-SAT Transition
• Statistical ensemble of scale-free random graphs
• Finiteness and Fluctuations in Growing Networks
• Vertical transmission of culture and the distribution of family names
• Number of loops of size h in growing scale-free networks
• Network Transitivity and Matrix Models
• Aggregation with Multiple Conservation Laws
• Perturbing General Uncorrelated Networks
• Leadership Statistics in Random Structures
• Unicyclic Components in Random Graphs

Cited by in corpus (33)

• Explosive Phenomena in Complex Networks
• Explosive Percolation: Novel critical and supercritical phenomena
• Local cluster aggregation models of explosive percolation
• Recent advances of percolation theory in complex networks
• Emergence of the giant weak-component in directed random graphs with arbitrary degree distributions
• Random graph approach to multifunctional molecular networks
• On the number of circuits in random graphs
• Re-inventing Willis
• Diverse types of percolation transitions
• Dynamic Networks that Drive the Process of Irreversible Step-Growth Polymerization
• Critical percolation clusters in seven dimensions and on a complete graph
• Phase Transition with Non-Thermodynamic States in Reversible Polymerization
• Kinetics of First Passage in a Cone
• Statistics of cycles in large networks
• Geometric scaling behaviors of the Fortuin-Kasteleyn Ising model in high dimensions
• Native ultrametricity of sparse random ensembles
• On scale-free and poly-scale behaviors of random hierarchical network
• Scaling Behavior of Threshold Epidemics
• Dynamics of Random Graphs with Bounded Degrees
• Unified framework for hybrid percolation transitions based on microscopic dynamics
• Kinetics of Ring Formation
• Critical phenomena of a hybrid phase transition in cluster merging dynamics
• Condensates in Driven Aggregation Processes
• Percolation effects in the Fortuin-Kasteleyn Ising model on the complete graph
• Polymerization with Freezing
• Emergence of biconnected clusters in explosive percolation
• Geometric properties of the complete-graph Ising model in the loop representation
• Recursive contact tracing in Reed-Frost epidemic models
• Simple evolving random graphs
• Gelation in input-driven aggregation
• Universality of the complete-graph Potts model with $0<q\le 2$
• Nonreciprocal random networks and their percolation properties
• Kinetics of Aggregation with Choice