Large-scale estimation of random graph models with local dependence

Abstract

A class of random graph models is considered, combining features of exponential-family models and latent structure models, with the goal of retaining the strengths of both of them while reducing the weaknesses of each of them. An open problem is how to estimate such models from large networks. A novel approach to large-scale estimation is proposed, taking advantage of the local structure of such models for the purpose of local computing. The main idea is that random graphs with local dependence can be decomposed into subgraphs, which enables parallel computing on subgraphs and suggests a two-step estimation approach. The first step estimates the local structure underlying random graphs. The second step estimates parameters given the estimated local structure of random graphs. Both steps can be implemented in parallel, which enables large-scale estimation. The advantages of the two-step estimation approach are demonstrated by simulation studies with up to 10,000 nodes and an application to a large Amazon product recommendation network with more than 10,000 products.

References in corpus (6)

• Latent Space Models for Dynamic Networks
• The method of moments and degree distributions for network models
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• Consistent structure estimation of exponential-family random graph models with block structure
• Fast Maximum Likelihood estimation via Equilibrium Expectation for Large Network Data

Cited by in corpus (5)

• Exponential random graph model parameter estimation for very large directed networks
• Consistent structure estimation of exponential-family random graph models with block structure
• Testing biological network motif significance with exponential random graph models
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• A Structural Model of Business Card Exchange Networks