Markovian iterative method for degree distributions of growing networks.
Markovian iterative method for degree distributions of growing networks.
复制标题
DOI：
10.1103/physreve.82.031105
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
D. Shi;Huijie Zhou;Liming Liu
中科院分区：
文献类型：
--
作者：
D. Shi;Huijie Zhou;Liming Liu
目前，仿真通常用于估计网络度分布P（k），并检查网络模型是否预测无标度网络，当解析公式不存在时。Shi [Phys.Rev.E71，036140（2005）]提出了另一种基于马尔可夫链的数值方法来计算时间依赖的度分布P（k，t）。虽然数值结果表明Barabási-Albert模型的P（k，t）到P（k）的快速收敛性，但关于收敛速度的关键问题尚未得到正式解决。本文提出了一种计算一类增长网络模型P（k，t）的简单马尔可夫迭代方法。我们还提供了一个上限估计的误差使用P（k，t）表示P（k）足够大的t，我们表明，与迭代方法，P（k，t）的收敛速度是根线性。
Currently, simulation is usually used to estimate network degree distribution P(k) and to examine if a network model predicts a scale-free network when an analytical formula does not exist. An alternative Markovian chain-based numerical method was proposed by Shi [Phys. Rev. E 71, 036140 (2005)] to compute time-dependent degree distribution P(k,t) . Although the numerical results demonstrate a quick convergence of P(k,t) to P(k) for the Barabási-Albert model, the crucial issue on the rate of convergence has not been addressed formally. In this paper, we propose a simpler Markovian iterative method to compute P(k,t) for a class of growing network models. We also provide an upper bound estimation of the error of using P(k,t) to represent P(k) for sufficiently large t, and we show that with the iterative method, the rate of convergence of P(k,t) is root linear.