Below are the first 10 and last 10 pages of uncorrected machineread text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapterrepresentative searchable text on the opening pages of each chapter.
Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.
OCR for page 303
Random Effects Models for Network Data
Peter D. Hoff*
Department of Statistics
University of Washington
Seattle, Washington
hoff@stat.washington. edu
www. stat . washington. edu/hoff
Abstract
One impediment to the statistical analysis of network data has been the difficulty
in modeling the dependence among the observations. In the very simple case of binary
(0~1) network data, some researchers have parameterized network dependence in terms
of exponential family representations. Accurate parameter estimation for such models
is quite difficult, and the most commonly used models often display a significant lack of
fit. Additionally, such models are generally limited to binary data. In contrast, random
effects models have been a widely successful tool in capturing statistical dependence
for a variety of data types, and allow for prediction, imputation, and hypothesis test
ing within a general regression context. We propose novel random effects structures
to capture network dependence, which corn also provide graphical representations of
network structure and variability.
~ Network Dependence
ordered pair of nodes i. i = 1 .... 
Network data typically consist of a set of n nodes and a relational tie Yi,j, measured on each
~ ~ ~~ _7 __7~)_ This framework has many applications, including the
study of war, trade, the behavior of epidemics, the interconnectedness of the World Wide
Web, and telephone calling patterns.
It is often of interest to relate each network response Yi,j to a possibly parspecific vector
valued predictor variable xi,j. A flexible framework for doing so is the generalized linear
mode! (see, for example McCullagh and Welder 1983), in which the expected value of the
response is modeled as a function of a linear predictor 3',, where ~ is an unknown vector
of regression coefficients to be estimated from the data. The ordinary regression mode!
¢tYi,jJ p!Xi,j is perhaps the most commonly used model of this the.
1;~ ~1~1 ~ ~ _ {n ~ ~ ~ ~ 1 _ _4 · 1 . 1 ~ . . ~
A generalized
'~ ~~ ~~ my flu ~ J Clara Is ~og~s~c regression, wn~cn relates the expectation of the
response to the regression variable via the relation g(E[yi,j]) = 3'xi,j, where g(p) = log UPS.
*This research was supported by Once of Naval Research grant N0001~0211011.
DYNAMIC SOCIAL NETWORK MODELING kD ISIS
303
OCR for page 303
As an example of the use of such statistical models, consider the analysis of strong
friendship ties among 13 boys and 14 girts in a s~xthgrade classroom, as collected by Hansell
(1984). Each student was asked if they liked each other student "a lot", "some", or "not
much". A strong friendship tie is considered present if a student likes another student "a lot "
Also recorded is the sex of each student. The data, presented in Figure 1, suggest a general
preference for samesex friendship ties. Of potential interest is statistical estimation of this
preference, as well as a confidence interval for its value. One approach for such statistical
analysis would be to formulate the logistic regression mode} g(Etyi~j~xi~i7 35) = 30 + >~xi,j,
where xi,j is one if children i and j are of the same sex, and zero otherwise, and it = (30 ,3~)
~ a)
11000001 I 030 a 1000001000300
1 0 0 0 0 0 0 0 0 0 ~ O 0 1 0 0 0 0 0 0 0 0 0 ~ O O
1 ~ 0000010031 10000001001300
111 l l l l I 11 ~ 1 000 I G 000000 ~ C O
1100 000 I l O 10 11011000111100
01001 0001031 10 11000010100
000011 010031 00000000000000
1000110 11101 00000000000000
00010010 0031 9000Q000000300
000000000 030 00000000000300
0000000000 30 00010000000300
00000100010 0 00000100000300
O O O O O O O O O O O tO O O 0 1 0 0 0 1 0 0 0 ~ O O
ODOO 1 000000OO
O O O ~ O O ~ ~ O O O ~ I) 1 ~ 0 1 ~ U 1 1 ~—~ 1
l l O l l l O l O l l ~ O 11 1 I l O l l l l l O l
0000000000030 000 1000000300
OOOOOOOOOOODO OOOO O01100OOO
00 ~ 1 ~ 0 ~ 00001 d l l . l l 01101100
1010111000110 0 I 0110 0001 ~ 00
() () () () () () () ~ () () O ~ O 1 1 O O O O O () ~ 1 ~ O
0000010000030 01001100 11101
OOOOOODOOOODO 0 1 · 1 000 1 1 1 1 00
0000000000030 1 I 00000000 100
OO0OOOOOOOO DO 11; 11001011 00
0000000000030 000000000003 0
00 ~000 OOOC ~ Do 0000000000000
:  9i1 1
Figure 1: (a) Sociomatrix for friendship data: Rows and columns 113 are boys, 1427 are
girls; (b) Graphical representation of friendship data: Dark blue lines are reciprocated ties.
are parameters to be estimated.
Estimation of regression coefficients 3 typically proceeds under the assumption that the
observations are conditionally independent given ~ and the xi,j's. However, this assumption
is often violated by many network datasets. For example, the data on friendship ties display
several types of dependence:
Withinnode dependence: The number of ties sent by each student varies considerably,
ranging from 0 to 19 with a mean of 5.8 and a standard deviation of 4.7 (the standard
deviation of the number of ties received was 3.2~. This node level variability suggests
that responses from the same individual are positively dependent, in that the proba
bility that Yi,j = ~ (i sends a tie to j), is high if we know York ~ for lots of other nodes
k, and Tower if Yi,k is mostly zero. More formally, we may wish to have a mode! in
which Pr~yi,j = EYE,,  , Yi,3i, Hi j+i,  . , Yi,n) is an increasing function of Yi,k, k ~ j.
Reciprocity: For directed relations, it is often expected that pi,' and yji are positively
dependent. The classroom data exhibit a sizable degree of reciprocity' in that the
number of pairs in which y:,j Yj i—~ is 24, which is more than we would expect due
to just random chance: In only 11 of 500 (2~2~o) random permutations of the network
clata, holding constant the number of ties sent by each student, did the number of
304
DYNAMIC SOCLAL N~TWO~MODEL~G ED ^=YSIS
OCR for page 303
such reciprocal dyacis exceed 24. The average number of reciprocal dyads in the 500
permutations was 17.2. This suggests an appropriate mode} would be one which allowed
for positive clependence between Yi,j and yj:.
Transitivity and Balance: In many situations we expect that two nodes with a positive
relation will relate similarly to other nodes. For relations which are positive or negative,
this has led to the concept of "balance" in which a positive value for pi j implies Yi,k an]
Yj,k are likely to be of the same sign for other nodes k. A related concept is transitivity,
in which a large value of yi,j together with a large value of Yj,k implies a large value of
Yi,k (see Wasserman and Faust, 1994, Chapter 6~.
The classroom data exhibit a large degree of transitivity, in that the number of non
vacuously transitive ordered triples (see Wasserman and Faust, page 244), is 400. In
500 random permutations of the network data, holding constant the number of ties
sent by each student, the largest observed number of transitive triples was 347. This
indicates the data exhibit significantly more transitivity than would be expected due to
just random chance and nodelevel variability, and an appropriate mode} should allow
for some form of transitive dependence.
In this article, we discuss statistical regression models which can describe such types of
network depenclence. This is done by incorporating random effects structures in a general
ized linear model setting. We discuss parameter estimation for these models in a Bayesian
framework, and provide example statistical analyses of the classroom data described above
and of a dataset on alliances and conflict among New Guinean tribes.
2 Network Random Effects Models
Generalized linear models, or glm's, are ubiquitous tools which extend linear regression
models to nonnormal data and transformable additive covariate effects (McCullagh and
Nelder, 1983). A standard glm assumes the expectation of the response variable Yi,j can be
written as a function of a linear predictor '7 )/xi j. Assuming observations are conditionally
independent given the x: j7s and 37 the model is:
Pr(yl,27 1 Yn,n—1X7 3) ~P(Yi,jlXi,j7 3)
it
g(E[yi,jlxi,j, 3]) ~7i,j ~ /X ,j
~7
Examples of glm's include ordinary linear regression, logistic regression, Poisson regression,
and quasilikelihood methods.
As discussed above, one feature that distinguishes network data is the likely dependence
among the yi,j's. This lack of independence makes standard glm models inappropriate. In
other settings which involve dependent data, a common approach to parameter estimation
has been the generalized linear mixedeffects model (McCulloch and Searle, 2002) in which
it is assumed the network observations can be modeled as conditionally independent given
DYNAMIC SOCIAL NETWORK HODF:LING AND ANALYSIS
305
OCR for page 303
appropriate random effects terms which can be incorporated into the gIm framework. The
mode! above becomes
Pr~y:,2,...,y7`n_~X,>7'Y) IIptyii~Xi,i' 3~:i,j) (~'
it
g(Etyi,j~X,J,wi,j]) hi,j >'Xi,j +:i,j,
where ~Yi,j is an unobserved random effect. The distribution of and dependence among the
~yi,j's determines the dependence among the yi,j's. For many kinds of network data, we may
wish to find a form for the Pi j's that induces the kinds of clependence described above, such
as w~thinnode dependence, reciprocity, transitivity, and balance.
A simple approach to modeling the node variability that gives rise to withinnode de
pendence is the use of random intercepts, that is, to let ~Yi,j a: + bj + ci,j, where a: and bj
represent independently distributed sender and receiverspecific effects. Such a distribution
on the ai's and bj's induces a positive dependence among responses involving a common
node. Typically, the distribution of these effects are taken to be normal distributions with
means equal to zero, and variances to be estimated from the data.
Modeling other forms of network dependence is not as straightforward. In the case of
binary logistic regression, Hoff, Raftery, and Handcock (2002) propose using a latentvariable
approach as a means of modeling balance, transitivity, and reciprocity in network data. As
applied to the aim above, such an approach presumes the error ci,j can be written as a
function f of independent kdimensional latent variables zi, z; ~ flak SO that ci,j f(Zi, zj),
i, j I, . . ., n. The function f is chosen to be simple and to mimic the forms of network
dependence described above. Incorporating both the random intercepts and the zi's into the
model, and assuming independent normal distributions, (~) becomes
71i,j ~ Xi,j + ai + bj + f(Zi, Zj)
al, . . ., an ~ i.i.~. Normal(O,cJ2)
be, ..,bn ~ i.i.~. Normal,
Z~' ~ An ~ i~i.~. Normai(O,ik X CT2),
where 3, CJ2, CJb, and ~2 are parameters to be estimated, and Ok is the k x k identity matrix.
Additionally, if the researcher is interested in local network structure, it may be desirable to
estimate ai, hi, zi for each node.
It remains to choose a suitable function I. One approach is to presume reciprocity,
transitivity, and balance arise due to the existence of unobserved node characteristics, and
that nodes relate preferentially to other nodes with similar values of those characteristics
This motivates letting f be a measure of "similarity" between the random effects zi and Zj,
which gives rise to a "latent position" interpretation as discussed in Hoff et se. (2002~. For
example, consider the following forms for I:
· (distance model) f (Eli, Zj) —All—Zj I;
· (inner product model) f (zi, Zj) = ZtZj
306
DYNAMIC SOCIAL N~TWO=MODEL~G ID ANALYSIS
OCR for page 303
In the case of directed responses, each of the above functions induces a degree of reciprocity
as ci,j = f(zi,zj)  f(zj,zi) = Hi, due to the symmetry of f. The common error term
induces a positive dependence between yi j and Yj i
The above functions also give rise to higherorder dependence. For example, the distance
model gives an error structure that is inherently transitive since zi—Zj  < Izi—ok  + Ink—Zj I
by the triangle inequality. The observation of strong ties from i to k and k to j suggests
that zi  zk and zk—zjl are small, and therefore zi—zjl cannot be too large and we
might expect strong ties from i to j. The inner product model satisfies a similar but more
complicated relation: in the special case that the vectors zi are of unit length, Z'Zj >
ZtZk + ZkZj ( 1 + 2 :(1—ZkZi ) ( 1—ZkZi ) )
An undirected signed graph is said to be balanced if the product of the relations in all
cycles is nonnegative, i.e. Yii,i2 X Yi2,i3 X · · X Yik_l,ik > 0 for all sequences of indices for which
the corresponding data ale available (Wasserman and Faust 1994, Chapter 6) As f(zi, zj)
exists in the mode! for each pair i, j, balance in terms of this random effect is equivalent to the
balance of the complete graph formed by the sociomatrix with i, jth entry equal to f (Hi, Zj)
For a complete signed graph, all cycles are balanced if and only if each triad is balanced,
ie f(Zi,Z') X f(Zj,Zk) X f(Zk,Zi) > 0 for all triples i,j,k. Interestingly, this is satisfied
by the inner product model in one dimension (zi ~ R), as (zzzj) x (ZJZk) X (ZkZj) > 0. For
Pi ~ ~k' k > 1, these terms are not necessarily balanced' although they are ``probabilistically"
balanced in the following sense: if the directions of the zi's are uniformly distributed, then
the expected number of balanced triads exceeds the number of imbalanced triads, with the
difference decreasing with increasing k. An additional feature of the inner product model is
that if the directions of the z's are uniformly distributed, then in general E(z'zj) = 0. In
particular, if each zi is a vector of k independent normal random variables with mean 0 and
variance cry, then ZiZj will have mean 0 and variance ken, furthering the interpretation of
ziz; as an error term.
On the other hand,—~zi—zig is always negative, and so we lack this interpretation for
the distance model. However, the distance model may be easier to interpret as a spatial
representation of network structure: The zi's can be interpreted as positions in a latent
"social space," with nodes having strong ties to one another being estimated as close together,
and subsets of nodes with strong w~thingroup ties being estimated as clusters in this social
space. Additionally, plotting estimates and confidence regions for the zi's gives a graphical,
modelbased representation of the network data
3 Parameter Estimation
Given network data Y = {Yi,j} and possible regressor variables X = {xi,j}, the goal is to
make statistical inference on the unknown model parameters, which we generically denote
as §. The parameter ~ may include the regression coefficients 3, the variances of the random
effects, and possibly the random effects themselves. We take a Bayesian approach to param
eter estimation, in that we posit a (potentially diffuse) prior probability distribution pa),
and base our inference on the posterior, or conditional distribution of the parameters given
the information in the data, which is given by Bayes' rule, pithy) = phyla) x p(~)/pt
however we can make approximate random samples from this distribution using Markov
chain Monte Carlo (MCMC) simulation (Gelfand and Smith l99O, Besag, Green, Higdon,
and Mengersen 1995). MCMCbased inference constructs a dependent sequence of 9values
as follows: Given the ithvalue 0` in the sequence,
· sample a parameter value d* from a proposal distribution A);
· compute the acceptance probability
( Pi*; )
· set ELI—§* with probability r, otherwise set 0~ = 8~.
The particular details, such as the choice of the proposal distribution J. will depend on the
model and the data. See Hoff et al. (2002) for MCMC algorithms designed specifically for
such latent variable models.
The result of the algorithm is a sequence of ~ values having a distribution that is approx
imately equal to the target distribution P(§IY). Statistical inference can be based on these
samples. For example, a point estimate of ~ is often taken to be the posterior mean, which
is approximated by the average of the sampled Bvalues. Posterior confidence intervals can
be based on the sample quartiles.
4 Example Data Analyses
We now apply the methods described above to the statistical analysis of two example
datasets. In the first example, we use the inner product model as a means of making
inference on the preference for same sex friendship ties in Hansell's classroom data. In the
second example, we use the distance model to make inference on the network of alliances
among sixteen New Guinean tribes studied by Read (1954). Both datasets involve binary
network data, although the methods are easily adapted to other types of network data via
an appropriate generalized linear model.
4.] Classroom Friendships
Hansell's (1984) data exhibit a tendency of children to form same sex friendship ties, in that
72~o of the ties are sam~sex. We consider a statistical analysis of this preference, in which
we estimate the log odds of a samesex tie, as well as make a confidence interval for its value.
This is done via the logistic regression model with random effects described above
g(Etyt,'~g, xi,j, :z,j]) To + 3~xi,j + ~i,j,
where xi,j is the indicator that i and j are of the same sex, 3 = {30, id} are parameters to
be estimated, and hi j is a random effect. In this parametrization, ,30 is the log odds of a
friendship between children of opposite sexes, and 30 + >~ is the log odds for children of the
same sex.
308
DYNAMIC SOCIAL N~TWO~MODEL~G ED ISIS
OCR for page 303
As described in the introduction, Hansell's (1984) classroom data exhibit several forms
of network dependence, including nod~level variability, reciprocity, and transitivity. This
suggests we model the data with nodespecific rates of sending and receiving ties, as well as
a term which captures reciprocity and transitivity. We choose the following innerproduct
model with random sender and receiver effects:
log oddstyi j—I) >~, + '3~xi,j + ai + bj + z'zj
al, . . ., an ~ i.i.~. Normal(O, ~2)
bi ~ . . . ~ be ~ i.i.d. Normal(O, orb ~
Z~'  In ~ i.i.d. Normal(O, ~2)
The parameters in this model are the regression coefficients pe and id, as well as the variance
terms ~2, cab ~ ~2, which determine the dependencies between ties.
A Bayesian analysis was performed using the methods outlined in Section 3. The prior
distributions for,l]O and ,B~ were taken to be independent, diffuse normal distributions, both
having mean zero and variance 100. The variance terms ~2' (Jb ~ ~2 were given diffuse inverse
Gamma(2,1) distributions, having an expectation of one but an infinite variance. An MCMC
algorithm was used to obtain the 500,000 approximate samples from the posterior distribu
tion p(,Bo, lit, ~2, ~b' (J2~y) Marginal posterior distributions of IBM, ~27 Cub' ~2 are presented in
Figure 2. The results suggest a significant preference for same sex friendship ties, in that the
posterior distribution for ,5~ is centered around a median of 1.49, and a 95~o quartilebased
confidence interval for 3~ is (0.84, 2.~), which does not contain zero. The posterior dis
tributions of ~2 and ~2 have deviated from their prior distributions and have moved to the
right, giving evidence for senderspecific variability as weli as the need for the latent variables
Z~' . ~ An The posterior for orb concentrates mass on Tow values, and is not much different
from the prior distribution, indicating little evidence for strong receiverspecific variability.
In comparison, a naive approach to inference would be to treat each possible tie as a
Bernoulli random variable, independent of all other ties. Using standard logistic regression,
our estimate of ,3~ is I.3 with a standard error of 0.2, giving an approximate 95~o confidence
interval of (0.9l,1.70), which is of substantially smaller width than the interval obtained
with the random effects model. Of course, we might expect the confidence interval based on
this naive analysis to be too small, as it incorrectly assumes all ties between indiv~duais are
independent and thus overestimates the precision of the parameter estimate.
4.2 Tribal alliances
Read (1954) describes a number of network relations between sixteen New Guinean tribes.
Here we consider the network of alliances between tribes, letting yi j = ~ if tribes i and j
have an alliance, and pi j—O otherwise. We analyze these data using the simple distance
mode! with no covariates or separate sender and receiverspecific random effects:
log odds Prays j—~ ~ 30, zoo, A) = 30—Pi—Zj ~ ~
where >0 represents the baseline odds of a tie between two nodes that have the same latent
position (i.e. ,50 the maximum Tog odds of a tie), and the zi's are latent positions in E:2
DYNAMIC SOCIAL NETWORK ~IOIDE~WG AND ANALYSIS
309
OCR for page 303
en
~ 
o
~ 
0 
o
TO 
o
~ 
~  /
o I I 1 1 , ,
0.0 0.5 1.0 1.5 2.0 2.5
p(betalY)
it__
r ~
0 1 2 3 4 5
6 7
p(sigma_z^21Y)

1 1
0.0 0.5 1.0 1.5 2.0 2.5 3.0
Figure 2: Marginal posterior distributions for the classroom data: Dashed lines represent
the prior distributions for the variance parameters, solid lines the posterior. Vertical lines
give the posterior median.
Without separate sender and receiverspecific effects, we may expect that tribes with many
alliances will be estimated as being more centrally located' and those with few ties as being
on the periphery.
Bayesian estimates and confidence intervals for 30 and the zi's are obtained using the
methods outlined in Section 3. In particular, samples of latent positions from the posterior
distribution p(z~, . . ., zippy) are plotted in the first panel of Figure 1 (colors are chosen so
that nearby node locations will have similar colors). Additionally, a black line drawn between
nodes indicates the presence of an alliance.
Adhoc approaches, or simple point estimates of latent locations, might uncover some of
the structure of the network. Our method goes beyond this by providing posterior confidence
regions for node locations which in turn give us a modelbased measure of uncertainty about
the network structure. Additionally, forms of predictive inference can be obtained from such
a model. For example, suppose that the presence or absence of an alliance between pair (i, j)
is unobserved or missing. The model can be fit with all available information (excluding the
unknown Yi,j), and from the available information the posterior distributions of zi and z;
can be obtained. From these' predictive inference about the value of Yi,j can be made.
310
DYNAMIC SOCIAL NETWO~MOD~LING ED ANALYSIS
OCR for page 303
Figure 3: Tribal alliance network and marginal posterior distributions of locations.
Also collected by Read (1954) were data on conflicts between the tribes. It is interesting
to note that, based on a clustering of nodes (l,2,15,16), (3,4,6,7,S,1l,12), and (5,9,10,13,14),
there were no w~thincluster conflicts, even though not every tribe within a cluster had an
alliance with every other cluster Member. Additionally, node 7, towards the center of
the alliance structure, had no conflicts with any of the other 15 tribes. We note that both
responses (conflict and alliance) couicl be modeled concurrently by a similar method, in
which a multinomial logistic random effects mode! is employed in place of the binary logistic
random effects model above.
5 Discussion
This article proposes a form of generalized linear mixedeffects mode} for the statistical
analysis of network data for which parameter estimation is practical to implement. The
approach has some advantages over existing social network models and inferential procedures:
the approach allows for prediction and hypothesis testing; lends itself to a modelbased
method of network visualization; is highly extendable and interpretable in terms of well
known statistical pro ceclures such as regression and generalized linear models; and has a
feasible means of exact parameter estimation.
The models discussed here can capture some types of network dependence, although it is
possible (or even likely) that in many datasets there are types of dependencies that cannot
DYNAMIC SOCKS NETWO=MODEL~G ED CYSTS
3 1 1
OCR for page 303
be wellrepresented with these models. It then becomes important to develop methods for
assessing mode! lack of fit, and determining the effect of lack of fit on the estimation of
regression coefficients. Furthermore, it may be useful to combine the types of random effects
discussed here with other types of random effects, or latent variables. For example, Nowicki
and Snijders (2001) discuss a latent class model, a useful model for identifying clusters of
Rhodes that relate to others in similar ways. Their latent class model, combined with types
of random effects models presented here and possibly other random effects structures, could
provide a rich class of models for dependent network data.
References
Besag, J., Green, P., Higdon, D., and Mengersen, K. (1995), "Bayesian computation and stochastic
systems," Statist. Sci., 10, 366, With comments and a reply by the authors.
Gelfand, A. E. and Smith, A. F. M. (1990), "Samplin~hm~1 ~nDron.~.h~R t.n r.~.lr,~l~t.in~ m~r~n~1
densities," ]. Amer. Statist. Assoc., 85, 398409.
O = = ~ ,= ^~