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.     

Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models

Social network data often involve transitivity, homophily on observed attributes, community structure, and heterogeneity of actor degrees. We propose a latent cluster random effects model to represent all of these features, and we develop Bayesian inference for it. The model is applicable to both binary and non-binary network data. We illustrate the model using two real datasets: liking between monks and coreaderships between Slovenian publications. We also apply it to two simulated network datasets with very different network structure but the same highly skewed degree sequence generated from a preferential attachment process. One has transitivity and community structure while the other does not. Models based solely on degree distributions, such as scale-free, preferential attachment and power-law models, cannot distinguish between these very different situations, but the latent cluster random effects model does.     

Conditionally exponential random models for individual properties and network structures: Method and application

Exponential random models have been widely adopted as a general probabilistic framework for complex networks and recently extended to embrace broader statistical settings such as dynamic networks, valued networks or two-mode networks. Our aim is to provide a further step into the generalization of this class of models by considering sample spaces which involve both families of networks and nodal properties verifying combinatorial constraints. We propose a class of probabilistic models for the joint distribution of nodal properties (demographic and behavioral characteristics) and network structures (friendship and professional partnership). It results in a general and flexible modeling framework to account for homophily in social structures. We present a Bayesian estimation method based on the full characterization of their sample spaces by systems of linear constraints. This provides an exact simulation scheme to sample from the likelihood, based on linear programming techniques. After a detailed analysis of the proposed statistical methodology, we illustrate our approach with an empirical analysis of co-authorship of journal articles in the field of neuroscience between 2009 and 2013.     

A comparison of estimators for the network autocorrelation model based on observed social networks

Network autocorrelation models (NAMs) are widely used to study a response variable of interest among subjects embedded within a network. Although the NAM is highly useful for studying such networked observational units, several simulation studies have raised concerns about point estimation. Specifically, these studies have consistently demonstrated a negative bias of maximum likelihood estimators (MLEs) of the network effect parameter. However, in order to gain a practical understanding of point estimation in the NAM, these findings need to be expanded in three important ways. First, these simulation studies are based on relatively simple network generative models rather than observed networks, thereby leaving as an open question how realistic network topologies may affect point estimation in practice. Second, although there has been strong work done in developing two-stage least squares estimators as well as Bayesian estimators, only the MLE has received extensive attention in the literature, thus leaving practitioners in question as to best practices. Third, the performance of these estimators need to be compared using both bias and variance, as well as the coverage rate of each estimator's corresponding confidence or credible interval. In this paper we describe a simulation study which aims to overcome these shortcomings in the following way. We first fit real social networks using the exponential random graph model and used the Bayesian predictive posterior distribution to generate networks with realistic topologies. We then compared the performance of the three different estimators mentioned above.     

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.     

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.     

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.     

Efficient Bayesian inference for exponential random graph models by correcting the pseudo-posterior distribution

Exponential random graph models are an important tool in the statistical analysis of data. However, Bayesian parameter estimation for these models is extremely challenging, since evaluation of the posterior distribution typically involves the calculation of an intractable normalizing constant. This barrier motivates the consideration of tractable approximations to the likelihood function, such as the pseudolikelihood function, which offers an approach to constructing such an approximation. Naive implementation of what we term a pseudo-posterior resulting from replacing the likelihood function in the posterior distribution by the pseudolikelihood is likely to give misleading inferences. We provide practical guidelines to correct a sample from such a pseudo-posterior distribution so that it is approximately distributed from the target posterior distribution and discuss the computational and statistical efficiency that result from this approach. We illustrate our methodology through the analysis of real-world graphs. Comparisons against the approximate exchange algorithm of Caimo and Friel (2011) are provided, followed by concluding remarks.     

EXPLOITING SPATIAL DEPENDENCE TO IMPROVE MEASUREMENT OF NEIGHBORHOOD SOCIAL PROCESSES

A number of recent studies have used surveys of neighborhood informants and direct observation of city streets to assess aspects of community life such as collective efficacy, the density of kin networks, and social disorder. Raudenbush and Sampson (1999a) have coined the term "ecometrics" to denote the study of the reliability and validity of such assessments. Random errors of measurement will attenuate the associations between these assessments and key outcomes. To address this problem, some studies have used empirical Bayes methods to reduce such biases, while assuming that neighborhood random effects are statistically independent. In this paper we show that the precision and validity of ecometric measures can be considerably improved by exploiting the spatial dependence of neighborhood social processes within the framework of empirical Bayes shrinkage. We compare three estimators of a neighborhood social process: the ordinary least squares estimator (OLS), an empirical Bayes estimator based on the independence assumption (EBE), and an empirical Bayes estimator that exploits spatial dependence (EBS). Under our model assumptions, EBS performs better than EBE and OLS in terms of expected mean squared error loss. The benefits of EBS relative to EBE and OLS depend on the magnitude of spatial dependence, the degree of neighborhood heterogeneity, as well as neighborhood's sample size. A cross-validation study using the original 1995 data from the Project on Human Development in Chicago Neighborhoods and a replication of that survey in 2002 show that the empirical benefits of EBS approximate those expected under our model assumptions; EBS is more internally consistent and temporally stable and demonstrates higher concurrent and predictive validity. A fully Bayes approach has the same properties as does the empirical Bayes approach, but it is preferable when the number of neighborhoods is small.     

Stable exponential random graph models with non-parametric components for large dense networks

Exponential random graph models (ERGM) behave peculiar in large networks with thousand(s) of actors (nodes). Standard models containing 2-star or triangle counts as statistics are often unstable leading to completely full or empty networks. Moreover, numerical methods break down which makes it complicated to apply ERGMs to large networks. In this paper we propose two strategies to circumvent these obstacles. First, we use a subsampling scheme to obtain (conditionally) independent observations for model fitting and secondly, we show how linear statistics (like 2-stars etc.) can be replaced by smooth functional components. These two steps in combination allow to fit stable models to large network data, which is illustrated by a data example including a residual analysis.     

A measure of betweenness centrality based on random walks

Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the network. By counting only shortest paths, however, the conventional definition implicitly assumes that information spreads only along those shortest paths. Here, we propose a betweenness measure that relaxes this assumption, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths. The measure is based on random walks, counting how often a node is traversed by a random walk between two other nodes. We show how our measure can be calculated using matrix methods, and give some examples of its application to particular networks.     

Covariate-defined latent space random effects model

Latent factor models are a useful and intuitive class of models; one limitation is their inability to predict links in a dynamic network. We propose a latent space random effects model with a covariate-defined social space, where the social space is a linear combination of the covariates as estimated by an MCMC algorithm. The model allows for the prediction of links in a network; it also provides an interpretable framework to explain why people connect. We fit the model using the Adolescent Health Network dataset and three simulated networks to illustrate its effectiveness in recognizing patterns in the data.     

Overconfidence in absolute and relative performance: The regression hypothesis and Bayesian updating

Studies have found that people are overconfident in estimation involving difficult tasks but underconfident in easy tasks. Conversely, they are overconfident in placing themselves in easy tasks but underconfident in hard tasks. These findings can be explained by a regression hypothesis that implies random errors in estimation as well as by rational Bayesian updating (that implies no random error). We test these hypotheses in five experiments. We find overconfidence in estimation involving hard tasks but underconfidence in easy tasks. However, for placement (involving both easy and hard tasks) we find no overconfidence, regression effects due to low and high anchor points, and extreme underconfidence when people choose between multiple alternatives. On the other hand, when given precise information about absolute performance, people’s re-assessments of relative performance are consistent with the Bayesian model. Since placement judgments are important in many competitive settings, our results emphasize the need for more research to identify their determinants.     

Bayesian estimation of the network autocorrelation model

The network autocorrelation model has been extensively used by researchers interested modeling social influence effects in social networks. The most common inferential method in the model is classical maximum likelihood estimation. This approach, however, has known problems such as negative bias of the network autocorrelation parameter and poor coverage of confidence intervals. In this paper, we develop new Bayesian techniques for the network autocorrelation model that address the issues inherent to maximum likelihood estimation. A key ingredient of the Bayesian approach is the choice of the prior distribution. We derive two versions of Jeffreys prior, the Jeffreys rule prior and the Independence Jeffreys prior, which have not yet been developed for the network autocorrelation model. These priors can be used for Bayesian analyses of the model when prior information is completely unavailable. Moreover, we propose an informative as well as a weakly informative prior for the network autocorrelation parameter that are both based on an extensive literature review of empirical applications of the network autocorrelation model across many fields. Finally, we provide new and efficient Markov Chain Monte Carlo algorithms to sample from the resulting posterior distributions. Simulation results suggest that the considered Bayesian estimators outperform the maximum likelihood estimator with respect to bias and frequentist coverage of credible and confidence intervals.     

BAYESIAN INFERENCE FOR HIERARCHICAL AGE-PERIOD-COHORT MODELS OF REPEATED CROSS-SECTION SURVEY DATA

This study applies methods of Bayesian statistical inference to hierarchical APC models for the age-period-cohort analysis of repeated cross-section survey data. It examines the impacts of small sample sizes of birth cohorts and time periods and unbalanced data on statistical inferences based on the usual restricted maximum likelihood–empirical Bayes (REML-EB) estimators through Monte Carlo simulations. A full Bayesian analysis using Gibbs sampling and MCMC estimation is developed to assess the robustness of REML-EB inferences when this extra uncertainty is taken into account and the numbers of higher-level units are small. For a substantive illustration, it applies cross-classified random effects models to vocabulary test data from the General Social Survey (1974 to 2000). It is concluded that the decline in verbal ability for birth cohorts born after 1950 was correlated with the levels of newspaper reading and television watching. Avenues for future research on mixed APC models are discussed.     

Closure,connectivity and degree distributions: Exponential random graph (p*) models for directed social networks

The new higher order specifications for exponential random graph models introduced by Snijders et al. [Snijders, T.A.B., Pattison, P.E., Robins G.L., Handcock, M., 2006. New specifications for exponential random graph models. Sociological Methodology 36, 99–153] exhibit substantial improvements in model fit compared with the commonly used Markov random graph models. Snijders et al., however, concentrated on non-directed graphs, with only limited extensions to directed graphs. In particular, they presented a transitive closure parameter based on path shortening. In this paper, we explain the theoretical and empirical advantages in generalizing to additional closure effects. We propose three new triadic-based parameters to represent different versions of triadic closure: cyclic effects; transitivity based on shared choices of partners; and transitivity based on shared popularity. We interpret the last two effects as forms of structural homophily, where ties emerge because nodes share a form of localized structural equivalence. We show that, for some datasets, the path shortening parameter is insufficient for practical modeling, whereas the structural homophily parameters can produce useful models with distinctive interpretations. We also introduce corresponding lower order effects for multiple two-path connectivity. We show by example that the in- and out-degree distributions may be better modeled when star-based parameters are supplemented with parameters for the number of isolated nodes, sources (nodes with zero in-degrees) and sinks (nodes with zero out-degrees). Inclusion of a Markov mixed star parameter may also help model the correlation between in- and out-degrees. We select some 50 graph features to be investigated in goodness of fit diagnostics, covering a variety of important network properties including density, reciprocity, geodesic distributions, degree distributions, and various forms of closure. As empirical illustrations, we develop models for two sets of organizational network data: a trust network within a training group, and a work difficulty network within a government instrumentality.     

Structure and bias in the network autocorrelation model

In a recent paper (Mizruchi and Neuman, 2008), we showed that estimates of ρ in the network autocorrelation model exhibited a systematic negative bias and that the magnitude of this bias increased monotonically with increases in network density. We showed that this bias held regardless of the size of the network, the number of exogenous variables in the model, and whether the matrix W was normalized or in raw form. The networks in our simulations were random, however, which raises the question of the extent to which the negative bias holds in various structured networks. In this paper, we reproduce the simulations from our earlier paper on a series of networks drawn to represent well-known structures, including star, caveman, and small-world structures. Results from these simulations indicate that the pattern of negative bias in ρ continues to hold in all of these structures and that the negative bias continues to increase at increasing levels of density. Interestingly, the negative bias in ρ is especially pronounced at extremely low-density levels in the star network. We conclude by discussing the implications of these findings.     

Exponential random graph models for multilevel networks

Modern multilevel analysis, whereby outcomes of individuals within groups take into account group membership, has been accompanied by impressive theoretical development (e.g. Kozlowski and Klein, 2000) and sophisticated methodology (e.g. Snijders and Bosker, 2012). But typically the approach assumes that links between groups are non-existent, and interdependence among the individuals derives solely from common group membership. It is not plausible that such groups have no internal structure nor they have no links between each other. Networks provide a more complex representation of interdependence. Drawing on a small but crucial body of existing work, we present a general formulation of a multilevel network structure. We extend exponential random graph models (ERGMs) to multilevel networks, and investigate the properties of the proposed models using simulations which show that even very simple meso effects can create structure at one or both levels. We use an empirical example of a collaboration network about French cancer research elites and their affiliations (0125 and 0120) to demonstrate that a full understanding of the network structure requires the cross-level parameters. We see these as the first steps in a full elaboration for general multilevel network analysis using ERGMs.     

Bayesian analysis for partially observed network data,missing ties,attributes and actors

We consider partially observed network data as defined in Handcock and Gile (2010). More specifically we introduce an elaboration of the Bayesian data augmentation scheme of Koskinen et al. (2010) that uses the exchange algorithm (Caimo and Friel, 2011) for inference for the exponential random graph model (ERGM) where tie variables are partly observed. We illustrate the generating of posteriors and unobserved tie-variables with empirical network data where 74% of the tie variables are unobserved under the assumption that some standard assumptions hold true. One of these assumptions is that covariates are fixed and completely observed. A likely scenario is that also covariates might only be partially observed and we propose a further extension of the data augmentation algorithm for missing attributes. We provide an illustrative example of parameter inference with nearly 30% of dyads affected by missing attributes (e.g. homophily effects). The assumption that all actors are known is another assumption that is liable to be violated so that there are “covert actors”. We briefly discuss various aspects of this problem with reference to the Sageman (2004) data set on suspected terrorists. We conclude by identifying some areas in need of further research.     

Detecting interaction links in a collaborating group using manually annotated data

Identification of network linkages through direct observation of human interaction has long been a staple of network analysis. It is, however, time consuming and labor intensive when undertaken by human observers. This paper describes the development and validation of a two-stage methodology for automating the identification of network links from direct observation of groups in which members are free to move around a space. The initial manual annotation stage utilizes a web-based interface to support manual coding of physical location, posture, and gaze direction of group members from snapshots taken from video recordings of groups. The second stage uses the manually annotated data as input for machine learning to automate the inference of links among group members. The manual codings were treated as observed variables and the theory of turn taking in conversation was used to model temporal dependencies among interaction links, forming a Dynamic Bayesian Network (DBN). The DBN was modeled using the Bayes Net Toolkit and parameters were learned using Expectation Maximization (EM) algorithm. The Viterbi algorithm was adapted to perform the inference in DBN. The result is a time series of linkages for arbitrarily long segments that utilizes statistical distributions to estimate linkages. The validity of the method was assessed through comparing the accuracy of automatically detected links to manually identified links. Results show adequate validity and suggest routes for improvement of the method.