Advances in Exponential Random Graph (p*) Models Applied to a Large Social Network

Recent advances in statistical network analysis based on the family of exponential random graph (ERG) models have greatly improved our ability to conduct inference on dependence in large social networks (Snijders 2002, Pattison and Robins 2002, Handcock 2002, Handcock 2003, Snijders et al. 2006, Hunter et al. 2005, Goodreau et al. 2005, previous papers this issue). This paper applies advances in both model parameterizations and computational algorithms to an examination of the structure observed in an adolescent friendship network of 1,681 actors from the National Longitudinal Study of Adolescent Health (AddHealth). ERG models of social network structure are fit using the R package statnet, and their adequacy assessed through comparison of model predictions with the observed data for higher-order network statistics.For this friendship network, the commonly used model of Markov dependence leads to the problems of degeneracy discussed by Handcock (2002, 2003). On the other hand, model parameterizations introduced by Snijders et al (2006) and Hunter and Handcock (2006) avoid degeneracy and provide reasonable fit to the data. Degree-only models did a poor job of capturing observed network structure; those that did best included terms both for heterogeneous mixing on exogenous attributes (grade and self-reported race) as well as endogenous clustering. Networks simulated from this model were largely consistent with the observed network on multiple higher-order network statistics, including the number of triangles, the size of the largest component, the overall reachability, the distribution of geodesic distances, the degree distribution, and the shared partner distribution. The ability to fit such models to large datasets and to make inference about the underling processes generating the network represents a major advance in the field of statistical network analysis.     

Exponential Family Models for sampled and census Network data

Much progress has been made on the development of statistical methods for network analysis in the past ten years, building on the general class of exponential family random graph (ERG) network models first introduced by Holland and Leinhardt (1981) . Recent examples include models for Markov graphs, "p*" models, and actor‐oriented models. For empirical application, these ERG models take a logistic form, and require the equivalent of a network census: data on all dyads within the network. In a largely separate stream of research, conditional log‐linear (CLL) models have been adapted for analyzing locally sampled ("egocentric") network data. While the general relation between log‐linear and logistic models is well known and has been exploited in the case of a priori blockmodels for networks, the relation for the CLL models is different due to the treatment of absent ties. For fully saturated tie independence models, CLL and ERG are equivalent and related via Bayes' rule. For other tie independence models, the two do not yield equivalent predicted values, but we show that in practice the differences are unlikely to be large. The alternate conditioning in the two models sheds light on the relationship between local and complete network data, and the role that models can play in bridging the gap between them.     

An introduction to exponential random graph (p) models for social networks

This article provides an introductory summary to the formulation and application of exponential random graph models for social networks. The possible ties among nodes of a network are regarded as random variables, and assumptions about dependencies among these random tie variables determine the general form of the exponential random graph model for the network. Examples of different dependence assumptions and their associated models are given, including Bernoulli, dyad-independent and Markov random graph models. The incorporation of actor attributes in social selection models is also reviewed. Newer, more complex dependence assumptions are briefly outlined. Estimation procedures are discussed, including new methods for Monte Carlo maximum likelihood estimation. We foreshadow the discussion taken up in other papers in this special edition: that the homogeneous Markov random graph models of Frank and Strauss [Frank, O., Strauss, D., 1986. Markov graphs. Journal of the American Statistical Association 81, 832–842] are not appropriate for many observed networks, whereas the new model specifications of Snijders et al. [Snijders, T.A.B., Pattison, P., Robins, G.L., Handock, M. New specifications for exponential random graph models. Sociological Methodology, in press] offer substantial improvement.     

Bayesian model selection for exponential random graph models

Exponential random graph models are a class of widely used exponential family models for social networks. The topological structure of an observed network is modelled by the relative prevalence of a set of local sub-graph configurations termed network statistics. One of the key tasks in the application of these models is which network statistics to include in the model. This can be thought of as statistical model selection problem. This is a very challenging problem—the posterior distribution for each model is often termed “doubly intractable” since computation of the likelihood is rarely available, but also, the evidence of the posterior is, as usual, intractable. The contribution of this paper is the development of a fully Bayesian model selection method based on a reversible jump Markov chain Monte Carlo algorithm extension of Caimo and Friel (2011) which estimates the posterior probability for each competing model.     

NEW SPECIFICATIONS FOR EXPONENTIAL RANDOM GRAPH MODELS

The most promising class of statistical models for expressing structural properties of social networks observed at one moment in time is the class of exponential random graph models (ERGMs), also known as p * models. The strong point of these models is that they can represent a variety of structural tendencies, such as transitivity, that define complicated dependence patterns not easily modeled by more basic probability models. Recently, Markov chain Monte Carlo (MCMC) algorithms have been developed that produce approximate maximum likelihood estimators. Applying these models in their traditional specification to observed network data often has led to problems, however, which can be traced back to the fact that important parts of the parameter space correspond to nearly degenerate distributions, which may lead to convergence problems of estimation algorithms, and a poor fit to empirical data.
This paper proposes new specifications of exponential random graph models. These specifications represent structural properties such as transitivity and heterogeneity of degrees by more complicated graph statistics than the traditional star and triangle counts. Three kinds of statistics are proposed: geometrically weighted degree distributions, alternating k -triangles, and alternating independent two-paths. Examples are presented both of modeling graphs and digraphs, in which the new specifications lead to much better results than the earlier existing specifications of the ERGM. It is concluded that the new specifications increase the range and applicability of the ERGM as a tool for the statistical analysis of social networks.     

A comparison of email networks and off-line social networks: A study of a medium-sized bank

Recently there has been a surge in the availability of online data concerning the connections between people, and these online data are now widely used to map the social structure of communities. There has been little research, however, on how these new types of relational data correspond to classical measures of social networks. To fill this gap, we contrast the structure of an email network with the underlying friendship, communication, and advice seeking networks. Our study is an explorative case study of a bank, and our data contains emails among employees and a survey of the ego networks of the employees. Through calculating correlations with QAP standard errors and estimating exponential random graph (ERG) models, we find that although the email network is related to the survey-based social networks, email networks are also significantly different: while off-line social networks are strongly shaped by gender, tenure, and hierarchical boundaries, the role of these boundaries are much weaker in the email network.     

The Statistical Evaluation of Social Network Dynamics

A class of statistical models is proposed for longitudinal network data. The dependent variable is the changing (or evolving) relation network, represented by two or more observations of a directed graph with a fixed set of actors. The network evolution is modeled as the consequence of the actors making new choices, or withdrawing existing choices, on the basis of functions, with fixed and random components, that the actors try to maximize. Individual and dyadic exogenous variables can be used as covariates. The change in the network is modeled as the stochastic result of network effects (reciprocity, transitivity, etc.) and these covariates. The existing network structure is a dynamic constraint for the evolution of the structure itself. The models are continuous-time Markov chain models that can be implemented as simulation models. The model parameters are estimated from observed data. For estimating and testing these models, statistical procedures are proposed that are based on the method of moments. The statistical procedures are implemented using a stochastic approximation algorithm based on computer simulations of the network evolution process.     

A comparison of various approaches to the exponential random graph model: A reanalysis of 102 student networks in school classes

This paper describes an empirical comparison of four specifications of the exponential family of random graph models (ERGM), distinguished by model specification (dyadic independence, Markov, partial conditional dependence) and, for the Markov model, by estimation method (Maximum Pseudolikelihood, Maximum Likelihood). This was done by reanalyzing 102 student networks in 57 junior high school classes. At the level of all classes combined, earlier substantive conclusions were supported by all specifications. However, the different specifications led to different conclusions for individual classes. PL produced unreliable estimates (when ML is regarded as the standard) and had more convergence problems than ML. Furthermore, the estimates of covariate effects were affected considerably by controlling for network structure, although the precise specification of the structural part (Markov or partial conditional dependence) mattered less.     

Stochastic weighted graphs: Flexible model specification and simulation

In most domains of network analysis researchers consider networks that arise in nature with weighted edges. Such networks are routinely dichotomized in the interest of using available methods for statistical inference with networks. The generalized exponential random graph model (GERGM) is a recently proposed method used to simulate and model the edges of a weighted graph. The GERGM specifies a joint distribution for an exponential family of graphs with continuous-valued edge weights. However, current estimation algorithms for the GERGM only allow inference on a restricted family of model specifications. To address this issue, we develop a Metropolis–Hastings method that can be used to estimate any GERGM specification, thereby significantly extending the family of weighted graphs that can be modeled with the GERGM. We show that new flexible model specifications are capable of avoiding likelihood degeneracy and efficiently capturing network structure in applications where such models were not previously available. We demonstrate the utility of this new class of GERGMs through application to two real network data sets, and we further assess the effectiveness of our proposed methodology by simulating non-degenerate model specifications from the well-studied two-stars model. A working R version of the GERGM code is available in the supplement and is incorporated in the GERGM CRAN package.     

Recent developments in exponential random graph (p*) models for social networks

This article reviews new specifications for exponential random graph models proposed by Snijders et al. [Snijders, T.A.B., Pattison, P., Robins, G.L., Handcock, M., 2006. New specifications for exponential random graph models. Sociological Methodology] and demonstrates their improvement over homogeneous Markov random graph models in fitting empirical network data. Not only do the new specifications show improvements in goodness of fit for various data sets, but they also help to avoid the problem of near-degeneracy that often afflicts the fitting of Markov random graph models in practice, particularly to network data exhibiting high levels of transitivity. The inclusion of a new higher order transitivity statistic allows estimation of parameters of exponential graph models for many (but not all) cases where it is impossible to estimate parameters of homogeneous Markov graph models. The new specifications were used to model a large number of classical small-scale network data sets and showed a dramatically better performance than Markov graph models. We also review three current programs for obtaining maximum likelihood estimates of model parameters and we compare these Monte Carlo maximum likelihood estimates with less accurate pseudo-likelihood estimates. Finally, we discuss whether homogeneous Markov random graph models may be superseded by the new specifications, and how additional elaborations may further improve model performance.     

Exponential random graph model specifications for bipartite networks—A dependence hierarchy

In this paper, we review the development of dependence structures for exponential random graph models for bipartite networks, and propose a hierarchy of dependence structures within which different dependence assumptions may be located. Based on this hierarchy, we propose a new set of model specifications by including bipartite graph configurations involving more than four nodes. We discuss the theoretical significance of the various effects that the extended models afford, and illustrate application of this hierarchy of models to several bipartite networks related to the political mobilization in Brazil in the early 1990s (Mische, 2007).     

Latent Class Marginal Models for Cross-Classifications of Counts

The standard latent class model is a finite mixture of indirectly observed multinomial distributions, each of which is assumed to exhibit statistical independence. Latent class analysis has been applied in a wide variety of research contexts, including studies of mobility, educational attainment, agreement, and diagnostic accuracy, and as measurement error models in social research. One of the attractive features of the latent class model in these settings is that the parameters defining the individual multinomials are readily interpretable marginal probabilities, conditional on the unobserved latent variable(s), that are often of substantive interest. There are, however, settings where the local-independence axiom is not supported, and hence it is useful to consider some form of local dependence. In this paper we consider a family of models defined in terms of finite mixtures of multinomial models where the multinomials are parameterized in terms of a set of models for the univariate marginal distributions and for marginal associations. Local dependence is introduced through the models for marginal associations, and the standard latent class model obtains as a special case. Three examples are analyzed with the models to illustrate their utility in analyzing complex cross-classifications.     

A model for collaboration networks giving rise to a power-law distribution with an exponential cutoff

Recently several authors have proposed stochastic evolutionary models for the growth of complex networks that give rise to power-law distributions. These models are based on the notion of preferential attachment leading to the “rich get richer” phenomenon. Despite the generality of the proposed stochastic models, there are still some unexplained phenomena, which may arise due to the limited size of networks such as protein, e-mail, actor and collaboration networks. Such networks may in fact exhibit an exponential cutoff in the power-law scaling, although this cutoff may only be observable in the tail of the distribution for extremely large networks. We propose a modification of the basic stochastic evolutionary model, so that after a node is chosen preferentially, say according to the number of its inlinks, there is a small probability that this node will become inactive. We show that as a result of this modification, by viewing the stochastic process in terms of an urn transfer model, we obtain a power-law distribution with an exponential cutoff. Unlike many other models, the current model can capture instances where the exponent of the distribution is less than or equal to two. As a proof of concept, we demonstrate the consistency of our model empirically by analysing the Mathematical Research collaboration network, the distribution of which has been shown to be compatible with a power law with an exponential cutoff.     

MODELS FOR GENERALIZED LOCATION SYSTEMS

A formal framework is introduced for a general class of assignment systems that can be used to characterize a range of social phenomena. An exponential family of distributions is developed for modeling such systems, allowing for the incorporation of both attributional and relational covariates. Methods are shown for simulation and inference using the location system model. Two illustrative applications (occupational stratification and residential settlement patterns) are presented, and simulation is employed to show the behavior of the location system model in each case; a third application, involving occupancy of positions within an organization, is used to demonstrate inference for the location system. By leveraging established results in the fields of social network analysis, spatial statistics, and statistical mechanics, it is argued that sociologists can model complex social systems without sacrificing inferential tractability.     

Settings in Social Networks: A Measurement Model

A class of statistical models is proposed that aims to recover latent settings structures in social networks. Settings may be regarded as clusters of vertices. The measurement model is based on two assumptions. (1) The observed network is generated by hierarchically nested latent transitive structures, expressed by ultrametrics, and (2) the expected tie strength decreases with ultrametric distance. The approach could be described as model–based clustering with an ultrametric space as the underlying metric to capture the dependence in the observations. Bayesian methods as well as maximum–likelihood methods are applied for statistical inference. Both approaches are implemented using Markov chain Monte Carlo methods.     

A comparative study of social network models: Network evolution models and nodal attribute models

This paper reviews, classifies and compares recent models for social networks that have mainly been published within the physics-oriented complex networks literature. The models fall into two categories: those in which the addition of new links is dependent on the (typically local) network structure (network evolution models, NEMs), and those in which links are generated based only on nodal attributes (nodal attribute models, NAMs). An exponential random graph model (ERGM) with structural dependencies is included for comparison. We fit models from each of these categories to two empirical acquaintance networks with respect to basic network properties. We compare higher order structures in the resulting networks with those in the data, with the aim of determining which models produce the most realistic network structure with respect to degree distributions, assortativity, clustering spectra, geodesic path distributions, and community structure (subgroups with dense internal connections). We find that the nodal attribute models successfully produce assortative networks and very clear community structure. However, they generate unrealistic clustering spectra and peaked degree distributions that do not match empirical data on large social networks. On the other hand, many of the network evolution models produce degree distributions and clustering spectra that agree more closely with data. They also generate assortative networks and community structure, although often not to the same extent as in the data. The ERGM model, which turned out to be near-degenerate in the parameter region best fitting our data, produces the weakest community structure.     

Missing data in networks: exponential random graph (p1) models for networks with non-respondents

Survey studies of complete social networks often involve non-respondents, whereby certain people within the “boundary” of a network do not complete a sociometric questionnaire—either by their own choice or by the design of the study—yet are still nominated by other respondents as network partners. We develop exponential random graph (p¹) models for network data with non-respondents. We model respondents and non-respondents as two different types of nodes, distinguishing ties between respondents from ties that link respondents to non-respondents. Moreover, if we assume that the non-respondents are missing at random, we invoke homogeneity across certain network configurations to infer effects as applicable to the entire set of network actors. Using an example from a well-known network dataset, we show that treating a sizeable proportion of nodes as non-respondents may still result in estimates, and inferences about structural effects, consistent with those for the entire network.If, on the other hand, the principal research focus is on the respondent-only structure, with non-respondents clearly not missing at random, we incorporate the information about ties to non-respondents as exogenous. We illustrate this model with an example of a network within and between organizational departments. Because in this second class of models the number of non-respondents may be large, values of parameter estimates may not be directly comparable to those for models that exclude non-respondents. In the context of discussing recent technical developments in exponential random graph models, we present a heuristic method based on pseudo-likelihood estimation to infer whether certain structural effects may contribute substantially to the predictive capacity of a model, thereby enabling comparisons of important effects between models with differently sized node sets.     

Network autocorrelation models with egocentric data

Network autocorrelation models have been widely used for decades to model the joint distribution of the attributes of a network's actors. This class of models can estimate both the effect of individual characteristics as well as the network effect, or social influence, on some actor attribute of interest. Collecting data on the entire network, however, is very often infeasible or impossible if the network boundary is unknown or difficult to define. Obtaining egocentric network data overcomes these obstacles, but as of yet there has been no clear way to model this type of data and still appropriately capture the network effect on the actor attributes in a way that is compatible with a joint distribution on the full network data. This paper adapts the class of network autocorrelation models to handle egocentric data. The proposed methods thus incorporate the complex dependence structure of the data induced by the network rather than simply using ad hoc measures of the egos’ networks to model the mean structure, and can estimate the network effect on the actor attribute of interest. The vast quantities of unknown information about the network can be succinctly represented in such a way that only depends on the number of alters in the egocentric network data and not on the total number of actors in the network. Estimation is done within a Bayesian framework. A simulation study is performed to evaluate the estimation performance, and an egocentric data set is analyzed where the aim is to determine if there is a network effect on environmental mastery, an important aspect of psychological well-being.     

Networks and geography: Modelling community network structures as the outcome of both spatial and network processes

This paper focuses on how to extend the exponential random graph models to take into account the geographical embeddedness of individuals in modelling social networks. We develop a hierarchical set of nested models for spatially embedded social networks, in which, following Butts (2002), an interaction function between tie probability and Euclidean distance between nodes is introduced. The models are illustrated by an empirical example from a study of the role of social networks in understanding spatial clustering in unemployment in Australia. The analysis suggests that a spatial effect cannot solely explain the emergence of organised network structure and it is necessary to include both spatial and endogenous network effects in the model.