×

Testing goodness of fit of random graph models. (English) Zbl 1461.05183

Summary: Random graphs are matrices with independent 0–1 elements with probabilities determined by a small number of parameters. One of the oldest models is the Rasch model where the odds are ratios of positive numbers scaling the rows and columns. Later Persi Diaconis with his coworkers rediscovered the model for symmetric matrices and called the model beta. Here we give goodness-of-fit tests for the model and extend the model to a version of the block model introduced by P. W. Holland and S. Leinhardt [J. Am. Stat. Assoc. 76, 33–64 (1981; Zbl 0457.62090)].

MSC:

05C80 Random graphs (graph-theoretic aspects)
62H15 Hypothesis testing in multivariate analysis

Citations:

Zbl 0457.62090
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Rasch, G.; ; Studies in Mathematical Psychology: I. Probabilistic Models for Some Intelligence and Attainment Tests: Oxford, UK 1960; .
[2] Andersen, E.B.; Sufficient statistics and latent trait models; Psychomretrika: 1977; Volume 42 ,69-81. · Zbl 0356.62081
[3] Linacre, J.M.; Predicting responses from Rasch measures; J. Appl. Meas.: 2010; Volume 11 ,1-10.
[4] Ponicny, I.; Nonparametric goodness-of-fit tests for the Rasch model; Psychometrika: 2001; Volume 66 ,437-460. · Zbl 1293.62252
[5] Verhelst, N.; Testing the unidimensionality assumption of the Rasch model; Meth. Psychol. Res. Online: 2001; Volume 6 ,231-271.
[6] Bickel, P.J.; Chen, A.; A nonparametric view of network models and Newman-Girvan and other modularities; Proc. Natl. Acad. Sci. USA: 2009; Volume 106 ,21068-21073. · Zbl 1359.62411
[7] Barvinok, A.; Hartigan, J.A.; An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums; ; . · Zbl 1269.05006
[8] Barvinok, A.; Hartigan, J.A.; The number of graphs and a random graph with a given degree sequence; ; . · Zbl 1264.05125
[9] Blitzstein, J.; Diaconis, P.; A sequential importance sampling algorithm for generating random graphs with prescribed degrees; J. Int. Math.: 2010; Volume 6 ,489-522. · Zbl 1238.60084
[10] Chatterjee, S.; Diaconis, P.; Sly, A.; Random graphs with a given degree sequence; Ann. Stat.: 2010; Volume 21 ,1400-1435. · Zbl 1234.05206
[11] Ogawa, M.; Hara, H.; Takemura, A.; Graver basis for an undirected graph and its application to testing the beta model of random graphs; Ann. Inst. Stat. Mat.: 2012; . · Zbl 1440.13114
[12] Bolla, M.; Tusnády, G.; Spectra and optimal partitions of weighted graphs; Discret. Math.: 1994; Volume 128 ,1-20. · Zbl 0796.05066
[13] Csiszár, V.; Rejtő, L.; Tusnády, G.; Statistical Inference on Random Structures; Horizon of Combinatorics: Berlin/Heidelberg, Germany 2008; ,37-67. · Zbl 1148.62003
[14] Csiszár, V.; Hussami, P.; Komlós, J.; Móri, T.; Rejtő, L.; Tusnády, G.; When the degree sequence is a sufficient statistic; Acta Math. Hung.: 2011; Volume 134 ,45-53. · Zbl 1263.62029
[15] Hussami, P.; Statistical Inference on Random Graphs; Ph.D. Thesis: Budapest, Hungary 2010; .
[16] Nepusz, T.; Négyessy, L.; Tusnády, G.; Bazsó, F.; Reconstructing cortical networks: Case of directed graphs with high level of reciprocity; Dyn. Syst. Appl.: 2009; Volume 18 ,335-362.
[17] Newman, M.; Barabási, A.-L.; Watts, D.; The Structure and Dynamics of Networks; Princeton Studies in Complexity: Princeton, NJ, USA 2007; .
[18] Holland, P.; Laskey, K.B.; Leinhardt, S.; Stochastic blockmodels: Some first steps; J. Am. Stat. Assoc.: 1981; Volume 76 ,33-50.
[19] Bickel, P.; Choi, D.; Chang, X.; Zhang, H.; Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels; Ann. Stat.: 2012; . · Zbl 1292.62042
[20] Flynn, C.J.; Perry, P.O.; Consistent biclustering; ; .
[21] Chung, F.; Lu, L.; Vu, V.; Spectra of random graphs with given expected degrees; Proc. Natl. Acad. Sci. USA: 2003; Volume 27 ,6313-6318. · Zbl 1064.05138
[22] Chaudhuri, K.; Chung, F.; Tsiatas, A.; Spectral clustering of graphs with general degrees in the extended planted partition model; J. Mach. Learn. Res.: 2012; Volume 1 ,1-23.
[23] Mossel, E.; Neeman, J.; Sly, A.; Reconstruction and estimation in the planted partition model; ; . · Zbl 1320.05113
[24] Karrer, B.; Newman, M.E.J.; Stochastic blockmodels and community structure in networks; Phys. Rev. E: 2011; Volume 83 ,016107.
[25] Rohe, K.; Chatterjee, S.; Yu, B.; Spectral clustrering and high-dimensional stochastic block model; Ann. Stat.: 2011; Volume 39 ,1878-1915. · Zbl 1227.62042
[26] Chung, F.; ; Spectral Graph Theory: Providence, RI, USA 1997; . · Zbl 0867.05046
[27] Chung, F.; Lu, L.; ; Complex Graphs and Networks: Boston, MA, USA 2006; . · Zbl 1114.90071
[28] Lovász, L.; Very large graphs; ; . · Zbl 1179.05100
[29] Lu, L.; Peng, X.; Spectra of edge-independent random graphs; ; . · Zbl 1295.05211
[30] Nadakuditi, R.R.; Newman, M.E.J.; Spectra of random graphs with arbitrary expected degrees; ; .
[31] Chatterjee, S.; Diaconis, P.; Estimating and understanding exponential random graph models; ; . · Zbl 1293.62046
[32] Palla, G.; Lovász, L.; Vicsek, T.; Multifractal network generator; Proc. Natl. Acad. Sci. USA: 2010; Volume 107 ,7641-7645.
[33] Chen, Y.; Diaconis, P.; Holmes, S.P.; Liu, J.S.; Sequential Monte Carlo methods for statistical analysis of tables; J. Am. Stat. Assoc.: 2005; Volume 100 ,109-120. · Zbl 1117.62310
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.