论文标题
使用相对熵分析合同随机网络向泊松分布的度分布的收敛性分析
Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
论文作者
论文摘要
我们提出了通过通用节点删除方案进行收缩过程的随机网络的结构演变的分析结果，即随机删除，优先删除和传播缺失。专注于配置模型网络，这些网络表现出给定的分布$ p_0（k）$且无相关性，我们使用严格的论点表明，在收缩时，这些网络的度分布会趋向于泊松分布。为此，我们使用相对熵$ s_t = s [p_t（k）||对于相应的poisson分布$π（k | \ langle k \ rangle_t $），π（k | \ langle k \ rangle_t）在时间$ t $上的度分分布$ p_t（k）$的π（k | \ langle k \ rangle_t）] $，具有相同的平均值$ \ langle k \ rangle k \ rangle_t $ a $ p_ $ p_ p_ p_ p_ p_ p_ p_ p_ p_ p_ p_ p_ p_ p_ p_相对熵适合作为距离度量，因为它满足任何度分布的$ s_t \ ge 0 $ $ p_t（k）$，而平等仅适用于$ p_t（k）=π（k | \ langle k \ rangle_t）$。我们在网络收缩期间为时间衍生$ ds_t/dt $得出一个方程，并表明相对熵在收缩过程中单调降至零。因此，我们得出的结论是，合同配置模型网络的程度分布会收敛于泊松分布。由于合同网络保持不相关，这意味着它们的结构会收敛到ERD {\ h o} s-rényi（er）图结构，从而证实了使用主方程和计算机模拟直接集成获得的早期结果[I. I. Tishby，O。Biham和E. Katzav，{\ it phys。 Rev. E} {\ bf 100}，032314（2019）]。我们演示了具有退化度分布（随机常规图），指数分布和幂律度分布（无标度网络）的配置模型网络的收敛性。
We present analytical results for the structural evolution of random networks undergoing contraction processes via generic node deletion scenarios, namely, random deletion, preferential deletion and propagating deletion. Focusing on configuration model networks, which exhibit a given degree distribution $P_0(k)$ and no correlations, we show using a rigorous argument that upon contraction the degree distributions of these networks converge towards a Poisson distribution. To this end, we use the relative entropy $S_t=S[P_t(k) || π(k|\langle K \rangle_t)]$ of the degree distribution $P_t(k)$ of the contracting network at time $t$ with respect to the corresponding Poisson distribution $π(k|\langle K \rangle_t)$ with the same mean degree $\langle K \rangle_t$ as a distance measure between $P_t(k)$ and Poisson. The relative entropy is suitable as a distance measure since it satisfies $S_t \ge 0$ for any degree distribution $P_t(k)$, while equality is obtained only for $P_t(k) = π(k|\langle K \rangle_t)$. We derive an equation for the time derivative $dS_t/dt$ during network contraction and show that the relative entropy decreases monotonically to zero during the contraction process. We thus conclude that the degree distributions of contracting configuration model networks converge towards a Poisson distribution. Since the contracting networks remain uncorrelated, this means that their structures converge towards an Erd{\H o}s-Rényi (ER) graph structure, substantiating earlier results obtained using direct integration of the master equation and computer simulations [I. Tishby, O. Biham and E. Katzav, {\it Phys. Rev. E} {\bf 100}, 032314 (2019)]. We demonstrate the convergence for configuration model networks with degenerate degree distributions (random regular graphs), exponential degree distributions and power-law degree distributions (scale-free networks).
