一类偏向删点及顶点有限制的随机图上的相变

Phase Transition in A Random Graph Process with Preferential Deletion and Limiting on Vertices

固定α_0∈[0,1)及β∈[0,1/2).该文引入如下随机图过程(G_t)t≥1:设在时刻1及2已存在图G_1=G_2,其中G_1的顶点为v_1,v_2且它们之间有2条边相连.当t≥3时,G_t定义如下:(i)G_(t-1)中任意顶点v不活跃的概率为α_0.顶点不活跃意味着其不能与t时刻新增加的顶点相连.此概率独立于自己以及其他顶点t-1之前的状态;(ii)以概率1-β增加一个新顶点v_t.在G_(t-1)中以概率dw(t-1)/∑vdv(t-1)选一顶点w,其中d_w(t-1)表w在G_(t-1)中的度.若w是活跃的则在v_t与w之间连1条边,否则在v_t上加个环;(iii)以概率β在G_(t-1)中删去一顶点u,其中u被选中的概率为(1-du(t-1)/∑vdv(t-1))/(n_(t-1)-1).此处,n_(t-1)是G_(t-1)的顶点个数.令N_k(t)表G_t中度为k的顶点个数.该文证明了G_t度分布的期望在2β/1-α_0=1附近存在一相变:当2β/1-α_0>1时,N_k(t)/t的期望是呈指数衰减的;当2β/1-α_0<1时,N_k(t)/t的期望是呈幂律衰减的.

The following random graph process Gt is introduced. Assuming that at the timestep 1 and 2 there has been a graph G1 = G2 consisting of vertices Vl, v2 and 2 edges between them. At time-step t ≥ 3, Gt is defined as follows： （i） each vertex v ∈ Gt-1 is inactive with probability a0, independently its and other vertices＇ statuses before t - 1. The inactiveness of v means it can not being connected by more edges; （ii） with probability 1 -β a new vertex vt is added along with one edge connected to it. Then a vertex wi is chosen with probability proportional to its degree. If wi is active then connect vt to wi. Otherwise, the edge of vt is connected to itself; （iii） with probability β a vertex is deleted preferentially from the network. It is proved that there is a phase transition on expected degree distribution when 2β/（1 - α0） is in the vicinity of 1. In the supercritical regime （2β/（1 - α0） 〉 1）, its expected fraction of vertices with degree k decays exponentially. While in the subcritical regime （2β/（1 - α0） 〈 1）, the expected fraction of vertices with degree k decreases asymptotically as a power law.