On a random graph evolving by degrees
type: Item
instance of: scholarly article
title: On a random graph evolving by degrees
zbMATH Open document ID: 1203.05140
published in: Advances in Mathematics
publication date: 2010-01-05T00:00:00Z
review text: Starting from an empty graph \(G(0)\) on \(V=\{1,\dots,n\}\), the graph \(G(m)\) is successively obtained from its predecessor \(G(m-1)\) for \(m=1,\dots,n\) by inserting a new edge with conditional probability proportional to the product \((a+d(i))(a+d(j))\), where \(a>0\) is a parameter and \(d(i)\) and \(d(j)\) are the current degrees of any distinct disjoint vertices \(i\) and \(j\). The limiting case with infinite parameter is the Erdős-Rényi graph process. Conditions are given for the existence with high probability of a unique giant component and its asymptotic size. A phase transition window is investigated. Conditions for connectedness with high probability are also given for a multigraph process in which loops and multiple edges are allowed.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60K35
zbMATH DE Number: 5653480
zbMATH Keywords: Random graph
zbMATH Keywords: Random multigraph
zbMATH Keywords: Preferential attachment
zbMATH Keywords: Phase transition
zbMATH Keywords: Giant component
author: Boris Pittel
MaRDI profile type: Publication
full work available at URL: j.aim.2009.08.015
OpenAlex ID: W2013294371
cites work: On a random graph with immigrating vertices: Emergence of the giant component
cites work: Q4004078
cites work: Emergence of Scaling in Random Networks
cites work: Q5820721
cites work: The asymptotic number of labeled graphs with given degree sequences
cites work: The Evolution of Random Graphs
cites work: Paths in graphs
cites work: Directed scale-free graphs
cites work: The degree sequence of a scale-free random graph process
cites work: The diameter of a scale-free random graph
cites work: Random subgraphs of finite graphs: I. The scaling window under the triangle condition
cites work: Random subgraphs of finite graphs. II: The lace expansion and the triangle condition
cites work: A general model of web graphs
cites work: Q3286850
cites work: Q4519896
cites work: The birth of the giant component
cites work: Stable husbands
cites work: Component behavior near the critical point of the random graph process
cites work: On the number of sparse connected graphs
cites work: The Structure of a Random Graph at the Point of the Phase Transition
cites work: On the structure of random plane‐oriented recursive trees and their branches
cites work: Q3684147
cites work: Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
cites work: A critical point for random graphs with a given degree sequence
cites work: The Size of the Giant Component of a Random Graph with a Given Degree Sequence
cites work: Q5616724
cites work: Critical percolation on random regular graphs
cites work: Note on the heights of random recursive trees and random m‐ary search trees
cites work: Edge percolation on a random regular graph of low degree
cites work: Random tree-type partitions as a model for acyclic polymerization: Holtsmark (3/2-stable) distribution of the supercritical gel
cites work: A Graph-Valued Markov Process as Rings-Allowed Polymerization Model: Subcritical Behavior
cites work: Q3357248
cites work: Q4236280
cites work: Renormalization group analysis of the small-world network model
cites work: Collective dynamics of ‘small-world’ networks
cites work: Q3718613
cites work: Differential equations for random processes and random graphs
cites work: The number of connected sparsely edged graphs. III. Asymptotic results
DOI: 10.1016/J.AIM.2009.08.015
Recommended article: Q3286850
Recommended article: On the Degree Sequence of an Evolving Random Graph Process and Its Critical Phenomenon
Recommended article: The Evolution of Random Graphs
Recommended article: Q3291948
Recommended article: Evolution of random graph processes with degree constraints
Recommended article: Q3317151
Recommended article: Random Walks on Randomly Evolving Graphs
Recommended article: Q4865687
Recommended article: On the degree evolution of a fixed vertex in some growing networks
Recommended article: Degree sequence of a scale-free random graph
description: scientific article; zbMATH DE number 5653480