The method of moments and degree distributions for network models

Abstract

Probability models on graphs are becoming increasingly important in many applications, but statistical tools for fitting such models are not yet well developed. Here we propose a general method of moments approach that can be used to fit a large class of probability models through empirical counts of certain patterns in a graph. We establish some general asymptotic properties of empirical graph moments and prove consistency of the estimates as the graph size grows for all ranges of the average degree including $\Omega (1)$. Additional results are obtained for the important special case of degree distributions.

Published in at http://dx.doi.org/10.1214/11-AOS904 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (7)

• Emergence of scaling in random networks
• Finding community structure in networks using the eigenvectors of matrices
• Stochastic blockmodels and community structure in networks
• The phase transition in inhomogeneous random graphs
• Spectral clustering and the high-dimensional stochastic blockmodel
• Modeling homophily and stochastic equivalence in symmetric relational data
• Quiet Planting in the Locked Constraint Satisfaction Problems

Cited by in corpus (27)

• Matrix estimation by Universal Singular Value Thresholding
• Pseudo-likelihood methods for community detection in large sparse networks
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• Centrality measures for graphons: Accounting for uncertainty in networks
• Subsampling bootstrap of count features of networks
• Co-clustering separately exchangeable network data
• Empirical Process Results for Exchangeable Arrays
• Statistical inference for network samples using subgraph counts
• Variational Bayes model averaging for graphon functions and motif frequencies inference in W-graph models
• Using bootstrap for statistical inference on random graphs
• Large-scale estimation of random graph models with local dependence
• Consistent structure estimation of exponential-family random graph models with block structure
• Consistency of Maximum Likelihood for Continuous-Space Network Models I
• Bootstrapping Exchangeable Random Graphs
• Estimating Graphlet Statistics via Lifting
• Random Walk Models of Network Formation and Sequential Monte Carlo Methods for Graphs
• Robust Vertex Classification
• On sparsity, power-law and clustering properties of graphex processes
• Motif Estimation via Subgraph Sampling: The Fourth Moment Phenomenon
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• A semiparametric extension of the stochastic block model for longitudinal networks
• Clique and cycle frequencies in a sparse random graph model with overlapping communities
• Asymptotic Analysis of Statistical Estimators related to MultiGraphex Processes under Misspecification
• Nonparametric Two-Sample Test for Networks Using Joint Graphon Estimation
• Econometric Models of Network Formation