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

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 $α_1$, a new vertex $x_t$ and $m$ edges incident with $x_t$ are added; or, with probability $α-α_1$, $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 $α_1<α_c$, then the model has power law degree sequence; 2) if $α_1>α_c$, then the model has exponential degree sequence; and 3) if $α_1=α_c$, then the model has a degree sequence lying between the above two cases.

18 pages