Convergence properties of the degree distribution of some growing network models

TY - JOUR

T1 - Convergence properties of the degree distribution of some growing network models

AU - Hagberg, Oskar

AU - Wiuf, Carsten

PY - 2006/8/1

Y1 - 2006/8/1

N2 - In this article we study a class of randomly grown graphs that includes some preferential attachment and uniform attachment models, as well as some evolving graph models that have been discussed previously in the literature. The degree distribution is assumed to form a Markov chain; this gives a particularly simple form for a stochastic recursion of the degree distribution. We show that for this class of models the empirical degree distribution tends almost surely and in norm to the expected degree distribution as the size of the graph grows to infinity and we provide a simple asymptotic expression for the expected degree distribution. Convergence of the empirical degree distribution has consequences for statistical analysis of network data in that it allows the full data to be summarized by the degree distribution of the nodes without losing the ability to obtain consistent estimates of parameters describing the network.

AB - In this article we study a class of randomly grown graphs that includes some preferential attachment and uniform attachment models, as well as some evolving graph models that have been discussed previously in the literature. The degree distribution is assumed to form a Markov chain; this gives a particularly simple form for a stochastic recursion of the degree distribution. We show that for this class of models the empirical degree distribution tends almost surely and in norm to the expected degree distribution as the size of the graph grows to infinity and we provide a simple asymptotic expression for the expected degree distribution. Convergence of the empirical degree distribution has consequences for statistical analysis of network data in that it allows the full data to be summarized by the degree distribution of the nodes without losing the ability to obtain consistent estimates of parameters describing the network.

KW - Biological network

KW - Markov chain

KW - Network model

KW - Randomly grown graphs

UR - http://www.scopus.com/inward/record.url?scp=33746804093&partnerID=8YFLogxK

U2 - 10.1007/s11538-006-9085-9

DO - 10.1007/s11538-006-9085-9

M3 - Journal article

C2 - 17149817

AN - SCOPUS:33746804093

SN - 0092-8240

VL - 68

SP - 1275

EP - 1291

JO - Bulletin of Mathematical Biology

JF - Bulletin of Mathematical Biology

IS - 6

ER -