Title

Markovian iterative method for degree distributions of growing networks

Document Type

Journal article

Source Publication

Physical Review E

Publication Date

9-2-2010

Volume

82

Issue

3

First Page

031105

Abstract

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 et al. [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 Barabasi-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.

DOI

10.1103/PhysRevE.82.031105

Print ISSN

15393755

E-ISSN

15502376

Publisher Statement

Copyright © American Physical Society

Access to external full text or publisher's version may require subscription.

Full-text Version

Publisher’s Version

Recommended Citation

Shi, D., Zhou, H., & Liu, L. (2010). Markovian iterative method for degree distributions of growing networks. Physical Review E, 82(3), 031105. doi: 10.1103/PhysRevE.82.031105