On the Degree Sequence and its Critical Phenomenon of an Evolving Random Graph Process

2008/06/28 by Xian‐Yuan Wu, Wu, Xian-Yuan, Dong, Zhao +4 · 1 citation
Mathematics · Physics and Astronomy · #05C07 #05C80 #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #History and Overview (math.HO) #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.0806.4684

openalex publication_date 2008/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we focus on the problem of the degree sequence for the following random graph process. At any time-step t, one of the following three substeps is executed: with probability α₁, a new vertex x_t and m edges incident with x_t are added; or, with probability α-α₁, m edges are added; or finally, with probability 1-\a, m random edges are deleted. Note that in any case edges are added in the manner of preferential attachment. we prove that there exists a critical point α_c satisfying: 1) if α₁α_c, then the model has exponential degree sequence; and 3) if α₁=α_c, then the model has a degree sequence lying between the above two cases.

Cited by

• Phase Transition on The Degree Sequence of a Mixed Random Graph Process

Related

• The degree-restricted random process is far from uniform
• Behavior of the Minimum Degree Throughout the d-process
• Random networks with sublinear preferential attachment: Degree evolutions
• The Degree Sequence of a Scale-Free Random Graph Process with Hard Copying
• Phase Transition on The Degree Sequence of a Mixed Random Graph Process