论文标题
通过随机节点删除通过节点添加和随机附着以及收缩在增长结合下进化的网络结构
The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
论文作者
论文摘要
我们介绍了通过生长（通过节点添加和随机附着）和收缩（通过随机节点删除）组合而发展的网络的新兴结构的分析结果。为此，我们考虑了一个网络模型，在该模型中，在每个步骤中，节点添加和随机附件步骤发生在概率$ p_ {add} $的情况下，并且随机节点删除步骤发生在概率$ p_ {del} = 1-p_ {add} $的情况下。生长和收缩过程之间的平衡是由参数$η= p_ {add} -p_ {del} $捕获的。纯网络增长的情况由$η= 1 $描述。如果$ 0 <η<1 $，节点添加的速率超过了节点删除的速率，整体过程是网络增长。在相反的情况下，如果$ -1 <η<0 $，总体过程是网络收缩的，而在$η= 0 $的特殊情况下，该网络的预期大小保持固定，则除了波动外。使用主方程，我们获得了时间相关度分布$ p_t（k）$的封闭式表达式。学位分布$ p_t（k）$包含一个术语，该术语取决于初始度分布$ p_0（k）$，随着时间的变化而衰减，渐近分布$ p_ {st}（k）$。在纯网络增长的情况下（$η= 1 $），渐近分布$ p_ {st}（k）$遵循指数分布，而$ -1 <η<1 $，它由poisson式的术语和poisson类似poisson的尾巴组成。在整体网络增长的情况下（$ 0 <η<1 $），学位分布$ p_t（k）$最终会收敛到$ p_ {st}（k）$。在整体网络收缩（$ -1 <η<0 $）的情况下，我们确定了两个不同的制度。对于$ -1/3 <η<0 $，度分布$ p_t（k）$迅速收敛于$ p_ {st}（k）$。相比之下，对于$ -1 <η<-1/3 $，$ p_t（k）$的收敛性最初非常慢，并且仅在网络消失之前就接近$ p_ {st}（k）$。
We present analytical results for the emerging structure of networks that evolve via a combination of growth (by node addition and random attachment) and contraction (by random node deletion). To this end we consider a network model in which at each time step a node addition and random attachment step takes place with probability $P_{add}$ and a random node deletion step takes place with probability $P_{del}=1-P_{add}$. The balance between the growth and contraction processes is captured by the parameter $η=P_{add}-P_{del}$. The case of pure network growth is described by $η=1$. In case that $0<η<1$ the rate of node addition exceeds the rate of node deletion and the overall process is of network growth. In the opposite case, where $-1<η<0$, the overall process is of network contraction, while in the special case of $η=0$ the expected size of the network remains fixed, apart from fluctuations. Using the master equation we obtain a closed form expression for the time dependent degree distribution $P_t(k)$. The degree distribution $P_t(k)$ includes a term that depends on the initial degree distribution $P_0(k)$, which decays as time evolves, and an asymptotic distribution $P_{st}(k)$. In the case of pure network growth ($η=1$) the asymptotic distribution $P_{st}(k)$ follows an exponential distribution, while for $-1<η<1$ it consists of a sum of Poisson-like terms and exhibits a Poisson-like tail. In the case of overall network growth ($0 < η< 1$) the degree distribution $P_t(k)$ eventually converges to $P_{st}(k)$. In the case of overall network contraction ($-1 < η< 0$) we identify two different regimes. For $-1/3 < η< 0$ the degree distribution $P_t(k)$ quickly converges towards $P_{st}(k)$. In contrast, for $-1 < η< -1/3$ the convergence of $P_t(k)$ is initially very slow and it gets closer to $P_{st}(k)$ only shortly before the network vanishes.
