Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T04:45:14.057Z Has data issue: false hasContentIssue false
  • English
  • Français

Joint Vertex Degrees in the Inhomogeneous Random Graph Model ℊ(n,{pij})

Part of: Operations research and management science Limit theorems Graph theory

Published online by Cambridge University Press:  04 January 2016

Kaisheng Lin  and
Gesine Reinert
Kaisheng Lin*
Affiliation:
University of Oxford
Gesine Reinert*
Affiliation:
University of Oxford
*
∗ Email address: [email protected]
∗∗ Postal address: Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In a random graph, counts for the number of vertices with given degrees will typically be dependent. We show via a multivariate normal and a Poisson process approximation that, for graphs which have independent edges, with a possibly inhomogeneous distribution, only when the degrees are large can we reasonably approximate the joint counts as independent. The proofs are based on Stein's method and the Stein-Chen method with a new size-biased coupling for such inhomogeneous random graphs, and, hence, bounds on the distributional distance are obtained. Finally, we illustrate that apparent (pseudo-)power-law-type behaviour can arise in such inhomogeneous networks despite not actually following a power-law degree distribution.

Keywords

Stein's methodsize-biased couplingvertex degreeinhomogeneous random graphpower law

MSC classification

Primary: 60F05: Central limit and other weak theorems
Secondary: 05C80: Random graphs 90B15: Network models, stochastic
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 44 , Issue 1 , March 2012 , pp. 139 - 165
Copyright
© Applied Probability Trust 

References

Barabasi, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.CrossRefGoogle ScholarPubMed
Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford University Press.Google Scholar
Bartroff, J. and Goldstein, L. (2009). A Berry-Esseen bound with applications to the number of multinomial cells of given occupancy and the number of graph vertices of given degree. Preprint.Google Scholar
Bollobás, B. (2001). Random Graphs. Cambridge University Press.Google Scholar
Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122.Google Scholar
Daudin, J-J., Picard, F. and Robin, S. (2008). A mixture model for random graphs. Statist. Comput. 18, 173–183.Google Scholar
Dorogovtsev, S. N. and Mendes, J. F. F. (2003). Evolution of Networks. Oxford University Press.Google Scholar
Erdös, P. and Rényi, A. (1959). On random graphs. Publ. Math. Debrecen 6, 290–297.CrossRefGoogle Scholar
Goldstein, L. and Rinott, Y. (1996). Multivariate normal approximations by Stein's method and size bias couplings. J. Appl. Prob. 33, 1–17.Google Scholar
Horn, R. A. and Johnson, C. R. (1985). Matrix Analysis. Cambridge University Press.CrossRefGoogle Scholar
Lin, K. (2008). Motif counts, clustering coefficients, and vertex degrees in models of random networks. , University of Oxford.Google Scholar
McKay, B. D. and Wormald, N. C. (1997). The degree sequence of a random graph. I. The models. Random Structures Algorithms 11, 97–117.3.0.CO;2-O>CrossRefGoogle Scholar
Newman, M. E. J., Moore, C. and Watts, D. J. (2000). Mean-field solution of the small-world network model. Phys. Rev. Lett. 84, 3201–3204.Google Scholar
Nowicki, K. and Snijders, T. A. B. (2001). Estimation and prediction for stochastic blockstructures. J. Amer. Statist. Assoc. 96, 1077–1087.Google Scholar
Rinott, Y. and Rotar, V. (1996). A multivariate CLT for local dependence with n −1/2log n rate and applications to multivariate graph related statistics. J. Multivariate Anal. 56, 333–350.Google Scholar
Solow, A. R., Costello, C. J. and Ward, M. (2003). Testing the power law model for discrete size data. Amer. Nat. 162, 685–689.Google Scholar
Stein, C. (1986). Approximate Computation of Expectations (Inst. Math. Statist. Lecture Notes—Monogr. Ser. 7). Institute of Mathematical Statistics, Hayward, CA.Google Scholar
Stumpf, M. P. H., Wiuf, C. and May, R. M. (2005). Subnets of scale-free networks are not scale-free: sampling properties of networks. Proc. Nat. Acad. Sci. USA 12, 4221–4224.CrossRefGoogle Scholar