Convergence properties of the degree distribution of some growing network models
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Convergence properties of the degree distribution of some growing network models. / Hagberg, Oskar; Wiuf, Carsten.
I: Bulletin of Mathematical Biology, Bind 68, Nr. 6, 01.08.2006, s. 1275-1291.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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
VL - 68
SP - 1275
EP - 1291
JO - Bulletin of Mathematical Biology
JF - Bulletin of Mathematical Biology
SN - 0092-8240
IS - 6
ER -
ID: 203901024