On the Degree Sequence and its Critical Phenomenon of an Evolving Random Graph Process
On the Degree Sequence and its Critical Phenomenon of an Evolving Random Graph Process
复制标题
DOI：
--
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Xian-Yuan Wu;Zhao Dong;Ke Liu;K. Cai
中科院分区：
文献类型：
--
作者：
Xian-Yuan Wu;Zhao Dong;Ke Liu;K. Cai
本文主要研究随机图过程的度序列问题。在任何时间步$t$，执行以下三个子步骤之一：以概率$\alpha_1 $，添加新顶点$x_t$和与$x_t$关联的$m$条边;或者，以概率$\alpha-\alpha_1 $，添加$m$条边;或者最后，以概率$1-\a$，删除$m$条随机边。请注意，在任何情况下，边都是以优先连接的方式添加的。证明了存在一个临界点$\alpha_c$满足：1）如果$\alpha_1\alpha_c$，则模型具有指数度序列; 3）如果$\alpha_1 =\alpha_c$，则模型具有介于上述两种情况之间的度序列.
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 $\alpha_1$, a new vertex $x_t$ and $m$ edges incident with $x_t$ are added; or, with probability $\alpha-\alpha_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 $\alpha_c$ satisfying: 1) if $\alpha_1 \alpha_c$, then the model has exponential degree sequence; and 3) if $\alpha_1=\alpha_c$, then the model has a degree sequence lying between the above two cases.