Markovian iterative method for degree distributions of growing networks

Dinghua SHI, Huijie ZHOU, Liming LIU

Research output: Journal PublicationsJournal Article (refereed)

4 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)031105
JournalPhysical Review E
Volume82
Issue number3
DOIs
Publication statusPublished - 2 Sep 2010
Externally publishedYes

Fingerprint

Growing Networks
Degree Distribution
Network Model
Rate of Convergence
Iteration
Scale-free Networks
Numerical Methods
Roots
Upper bound
Predict
Numerical Results
Alternatives
Estimate
Demonstrate
Simulation
Model
Class

Cite this

SHI, Dinghua ; ZHOU, Huijie ; LIU, Liming. / Markovian iterative method for degree distributions of growing networks. In: Physical Review E. 2010 ; Vol. 82, No. 3. pp. 031105.
@article{92ffe0c0186646728345ffdc09fab087,
title = "Markovian iterative method for degree distributions of growing networks",
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.",
author = "Dinghua SHI and Huijie ZHOU and Liming LIU",
year = "2010",
month = "9",
day = "2",
doi = "10.1103/PhysRevE.82.031105",
language = "English",
volume = "82",
pages = "031105",
journal = "Physical Review E",
issn = "2470-0045",
publisher = "American Physical Society",
number = "3",

}

Markovian iterative method for degree distributions of growing networks. / SHI, Dinghua; ZHOU, Huijie; LIU, Liming.

In: Physical Review E, Vol. 82, No. 3, 02.09.2010, p. 031105.

Research output: Journal PublicationsJournal Article (refereed)

TY - JOUR

T1 - Markovian iterative method for degree distributions of growing networks

AU - SHI, Dinghua

AU - ZHOU, Huijie

AU - LIU, Liming

PY - 2010/9/2

Y1 - 2010/9/2

N2 - 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.

AB - 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.

UR - http://commons.ln.edu.hk/sw_master/159

U2 - 10.1103/PhysRevE.82.031105

DO - 10.1103/PhysRevE.82.031105

M3 - Journal Article (refereed)

C2 - 21230023

VL - 82

SP - 031105

JO - Physical Review E

JF - Physical Review E

SN - 2470-0045

IS - 3

ER -