GLMLE Graph-Limit Enabled Fast Computation for Fitting Exponential Random Graph Models to Large Social Networks

• Activity Number: 250
• Type: Contributed
• Date/Time: Monday, August 4, 2014 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Graphics
• Author(s): Ran He*+ and Tian Zheng
• Companies: Columbia University and Columbia University
• Keywords: Exponential random graph models ; Graph limits ; Maximum likelihood estimator ; Social network

Abstract

Analyzing and modeling network data have become increasingly important in a wide range of scientific fields. Among popular models, exponential random graph models (ERGMs) have been developed to directly model network structures and features. For large networks, however, maximum likelihood estimation (MLE) of parameters in ERGMs can be very difficult, due to the unknown normalizing constant. Chatterjee and Diaconis (2011) propose a new theoretical framework for estimating ERGMs by approximating the normalizing constant using the emerging tools in graph theory--graph limits. In this paper, we construct a complete computational procedure built upon their results with practical innovations. Specifically, we evaluate the likelihood via simple function approximation of the corresponding ERGM's graph limit and iteratively maximize the likelihood to obtain the MLE. Through several simulation studies and real data analysis of two large social networks, we show that our new method outperforms the most popular existing method--MCMC-based algorithm, especially when the network size is large.