Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Accounting for Degree Distributions in Empirical Analysis of Network Dynamics Tom A.B. Snijders University of Groningen * December 2002 Abstract Degrees (the number of links attached to a given node) play a particular and important role in empirical network analysis because of their obvious importance for expressing the position of nodes. It is argued here that there is no general straightforward relation between the degree distribution on one hand and structural aspects on the other hand, as this relation depends on further characteristics of the presumed mode] for the network. Therefore empirical inference from observed network characteristics to the processes that could be responsible for network genesis and dynamics cannot be based only, or mainly, on the observed degree distribution. As an elaboration and practical implementation of this point, a statistical model for the dynamics of networks' expressed as digraphs with a fixed vertex set, is proposed in which the outUegree distribution is governed by parameters that are not connected to the parameters for the structural dynamics. The use of such an approach in statistical modeling minimizes the influence of the observed degrees on the conclusions about the structural aspects of the network dynamics. The model is a stochastic actor-oriented model, and deals with the d~ grees in a manner resembling Tversky's Elimination by Aspects approach. A statistical procedure for parameter estimation in this model is proposed, and . . an example e 1S given. *Tom A.B. Snijders, ICS, Department of Sociology, Grote Rozenstraat 31, 9712 TG Groningen The Netherlands, email <t . a.b . sni jders@ppsw. rug.nl>. The preparation of this work has profited from stimulating discussions with Philippa Pattison and Mark Handcock and from participation in NIH grant 1 RO1 DA12831-OlA1, "Modeling HIV and STD in Drug User and Social Networks". I am very grateful to Jeffrey Johnson for putting at my disposal the data used in the example, and giving permission to use them here. 146 DYNAMIC SOCIAL N~TWO~ MODELING ED ANALYSIS

I. Introduction Consider a social network with the focus on one relation represented by a directed graph (digraph), referring to the nodes as actors (which could be individual humans or other primates but also, e.g., companies or websites). In such a network, the degrees represent an important aspect of network structure. The outUegree of an actor, defined as the number of ties from this actor to other actors, reflects the total amount of activity of the actor in this network, which could be dependent on the importance of the network for this actor, the average costs and benefits for this actor of having outgoing ties, and, if the outgoing ties are based on self-reports, the actor's response tendencies or constraints of the data collection methods. The indegree of an actor, defined as the number of ties from others to this actor, will reflect the importance and easiness for the others of extending a tie to this particular actor, etc. The importance of the degrees as an aspect of network structure is generally recognized (e.g., Wasserman and Faust, l99a=; Albert and Barabasi, 2002~. Degrees refer directly to the individual actors, which gives them an interesting position combining structural and individual relevance. Degrees often are constraints in, but also consequences of, the processes that generate networks and determine network dynamics. This has led to various proposals to control for degrees in the statistical evaluation of networks. One possibility for cloing this is to test observed network characteristics for the null hypothesis defined as the uniform dis- tribution given the out~egrees, the ~ ~ Xi+ distribution, or the uniform dis- tribution given the in- as well as the out~egrees, clenoted the U ~ Xi+, X+i distribution (Wasserman, 1977; Wasserman & Faust, 1994; SnijUers, 1991, 2002b). How to generate such graphs was studied by Snipers (1991) with a focus on Monte Cario simulation methods for the directed case, and by Mol- loy and Reed (1995) who proposed a simulation method for the undirected case which also can be fruitfully used to obtain asymptotic results for sparse undirected graphs with a given degree sequence. Various ways to take ac- count of the degree distribution in the context of the p* model of Wasserman & Pattison (1996) were discussed in SnijUers & van Duijn (2002~. Stimu- lated by observations of the long-tailed nature of the degree (listributions of links in the worldwide web, Barabasi and Albert (1999) proposed models for network dynamics (modeled as undirected graphs with a growing number of vertices) in which the creation of new links depends strongly on the current degrees, and is random conditional on the current degree vector. Newman, Strogatz, and Watts (2001) and Newman, Watts and Strogatz (2002) derived various asymptotic properties of random undirected graphs with given degree sequences. They followed the mentioned literature in unclerlining the impor- DYNAMIC SOCIAL N~TWORKHODELING AND ANALYSIS 147

tance of studying for empirical networks whether observed network structure can be accounted for by the degree sequence plus randomness; if the answer is negative, there is evidence for structural mechanisms in addition to the degrees. It is argued here that the degree distribution is a primary characteris- tic for the structure of digraphs but many other features, such as transi- tivity, occurrence of cycles, segmentation into subgroups, etc., are also of great importance. Although the degree distribution may pose constraints to the values of these other structural features (SnijUers, 1991; Newman, Strogatz, and Watts, 2001; Newman, Watts and Strogatz, 2002), it does not determine them and an empirical focus on degrees exclusively would close our eyes to much that network analysis can tell us. This paper presents a two-step model for network dynamics, in which the determination of the out~egrees is separated from the further determination of network structure. This gives a greater flexibility in modeling, and allows to mode] structural network dynamics without contamination by unfortunate assumptions about the dynamics of the outUegrees. 11. A two-step mocte! for network dynamics: first outHegrees, then network structure This paper is concerned with the statistical modeling of network evolution for data consisting of two or more repeated observations of a social network for a given fixed set of actors, represented by a directed graph with a given vertex set. When proposing statistical models for network evolution, theo- retical credibility of the mode! has to be combined with empirical applicabil- ity. The stochastic actor-oriented model of SnijUers (2001, 2003), extended to networks of changing composition by Huisman & Snipers (2003), tried to do just this, embedding the discret~time observations in an unobserved continuous-time network evolution process in which the network changes in small steps where just one arc is added or deleted at any given moment. The network changes are determined stochastically in steps modeled by random utility models for the actors. The present paper adapts this model to have more freedom in fitting observed distributions of outUegrees. The following features of the earlier mode] are retained. The model is a stochastic process in continuous time, in which the arcs in the network can change only one at the time. It is actor- oriented in the sense that the mode! is described in such a way that network changes take place because actors create a new outgoing tie, or withdraw an existing outgoing tie. The actor who changes an outgoing tie is designated 148 DYNAAlIC SOCKS NETWO=MODELING ED ISIS

randomly, with probabilities that may depend on the actors' characteristics as reflected by covariates and by network positions. Given that an actor changes some tie, (tithe selects the tie to be changecI according to a random utility model, which is based on effects reflecting network structure (e.g. transitivity). The precise way in which it is determined stochastically which actor will make a change, and what is the change to be made, is defined differently than in the earlier papers, so as to allow modeling a diversity of degree distributions in a more natural way. The focus here is on the distribution of the outUegrees; of course, by reversing direction, this can be applied equally well to modeling the distribution of the indegrees. The model proposed here is composed of two substeps in a manner comparable to Tversky's (lg72) Elimination by Aspects approach. In the first substep, the actor is chosen, and the actor decides whether to create a new outgoing tie, or to delete an existing tie. In the second step, if the result of the first substep was to add a tie, the actor chooses to which of the other actors the new tie will be created; and if the first substep led to the decision to delete a tie, the actor chooses which existing tie will be withdrawn. Thus, the first aspect that the actor takes into consideration is his or her out~egree; the second aspect is the further position of the actor in the network structure. Notation The network is represented by a directed graph on n vertices with adjacency matrix x = (xij), where xij indicates whether there is a tie directed from actor i to actor j (i,j = 1,...,n) (in which case xij = 1) or not (xij = 0~. The diagonal is formally defined by xii = 0. It is supposed that a time- series x~t),t ~ {t~,...,tM3 of social networks is available where the tm are strictly increasing and M > 2. These observed networks are regarded as M discrete observations on a stochastic process X(~) on the space of all digraphs on r1 vertices, evolving in continuous time. This process is taken to be left-continuous, i.e., X(t) = limX(t') for all t. The state of the network immediately after time t is denoted X(~+) = limX(t') . No assumption of stationarity is made for the marginal distributions of X(~), and therefore the first observation Sty) is not used to give direct information on the distribution of this stochastic process, but the statistical analysis conditions on this first observed network. DYNAMIC SOCIAL NETWORK MODE ED ISIS 149

Summation is denoted by replacing the summation index by a + sign: e.g., xi+ is the outUegree and x+i the indegree of actor i. Mode/ definition: rates of change At random moments, one of the actors i is 'permitted' to change one of his or her outgoing tie variables Xij. For the different actors, these random moments are independent conditionally given the present network. The rate, in the time interval tm < t ~ tom' at which actor ~ adds a tie is denoted Pm >`i+ (0~' x); the rate at which this actor deletes a tie is Pm Ai- (act' x). Here x is the current network and or is a parameter indicating how the rate function depends on the position of i in the current network (e.g., as a function of the out~egree or indegree of i) and/or on covariates if these are available. The multiplicative parameters Pm depend on m (the index number of the observation interval) to be able to obtain a good fit to the observed amounts of change between consecutive observations. Together, these two change rates imply that for actor i, during the time interval tm < t < to+, these random moments of change follow a non-homogeneous Poisson process with intensity function )Li(X) = Pm(>i+(ct~x) + ~i_(X,Ol)), (1) conditional on X(t) = x. Given that actor i makes a change at moment t' the probability that the changes amounts to creating a new tie is P {Xi+(t+)Xi+(t) + 1 ~ change by actor i at time t, X(t) = x) _ ~i+~,X) - Ai~ (ot, x) ~ Ai- (x, or) (2) This separation between the rates of adding and deleting ties allows to focus specifically on the distribution of the degrees. Mode/ definition: objective function Given that actor i makes a change at some moment t for which the current network is given by X(t) = x, the particular change made is assumed to be determined by the so-called objective function - which gives the numerical evaluation by the actor of the possible states of the network - together with a random element - accounting for 'unexplained changes', in other words, for the limitations of the model. This objective function could be different between the creation of new ties and the deletion of existing ties. Denote these two objective functions by fi+~3,x) and f:_~d,x), respectively. These functions indicate what the actor strives to maximize when adding or deleting 150 DYNAMIC SOCL4L NETWO=MODEL~G ED ISIS

ties, respectively; they depend on a parameter vector A. In a simple mode] specification, it can be assumed that fi+ -fi_ . (This corresponds to a zero gratification function in the model of SnijUers, 2001~. The way in which the objective functions and a random element together define the changes in the outgoing relation of actor i is defined as follows. Suppose that at some moment t, actor i changes one of his outgoing relations. The current state of the network is x(~. At this moment, actor i determines the other actor j to whom he will change his tie variable xij. Denote by xti ~ j) the adjacency matrix that results from x when the single element xij is changed into 1xij (i.e., from 0 to 1 or from 1 to 0~. If at moment t actor i adds a tie, then he chooses the other actor j, among those for which xij = 0, for which fi+~g,X(i~j)) + Ui~t,x,j) is maximal; where Ui~t,x,j) is a random variable, indicating the part of the actor's preference not represented by the objective function, and assumed to be distributed according to the type l extreme value distribution with mean O and scale parameter 1 (Maddala, 1983~. Similarly, if at moment t actor i deletes a tie, then he chooses the other actor j, among those for which xij = 1, for which fi_~B,x(`i~j)) + Ui(t,x,j) is maximal. The type 1 extreme value distribution is conventionally used in random utility modeling (cf. Maddala, 1983~; it yields the choice probabilities for j given by the multinomial logit (or potential function) expressions (3, x) (1xij) exp (fi+(~3, xti ~ jig) ~h=l,h~i ~ 1 Bib) exp (fi+ (5, xti ~ hit) for adding a tie, and (`j 74 i) (3) if,, ~ xij exp (fz_~) =(i ~ j))) (A 74 i) (4) ~,`_17~ - '` it- ~ \_ ~ `, , ~ for deleting a tie. The specification of the objective function is discussed extensively in Snij- clers (2001~. It is proposed there to use objective functions fi+ and fi- of the form fits, X) = ~ ink SiktX), (5' k DYNAMIC SOCIAL NETWORK MODELING AND ANALYSIS 151

where the 3k are statistical parameters and the Sik are network statistics. A basic network statistic is the number of reciprocated relations Sik (X) = Xij Xji - (6) Network closure, or transitivity, can be expressed by various terms in the objective function, e.g., by the number of transitive patterns in i's relations (ordered pairs of actors (j, h) to both of whom i is related, while also j is related to h), Sikh) = ~ Xtj Xih Xjh; j,h (7) or by a negative effect for the number of other actors at geodesic distance equal to 2, Sikh) = ttj ~ Phi, j) = 2), where d=(i, j) is the oriented geodesic distance, i.e., the length of the shortest directed path from i to j. Many other examples of possibly relevant functions Sik are proposed in Snifflers (2001~. intensity matrix The intensity matrix qtx, y), for x 7t y, of the continuous-time Markov chain defined by this model, indicates the rate at which the current value x changes into the new value y. Since relations here are allowed to change only one at a time, the intensity matrix can be represented by the change rates qij~x)' from x to Hi ~ j) for j id i, defined by qij(X) = Jim P{X(t + Ott = xti ~ j) ~ X(~) = x3 The model definition given above corresponds to an intensity matrix given by q ( ) pm z+ ~ pi + ,x for zz, _ O { Pm )2-~) pi_ for x Ill. Rate functions and stationary distributions In a simple model definition, the rates Ai+ and Ai- depend only on the outclegree of actor i. This will be assumed henceforth, and it implies that the 152 DYNAMIC SOCIAL NETWORK HODEL~G ED ISIS

outUegTee processes Xi+~) are independent continuous-time random walks on the set {0, . . ., n13. For the sake of brevity, and with a slight abuse of notation, denote the rates of adding and withdrawing ties by A+(s) and A_(s), where s = xi~ is the outUegree of actor i. Thus, A+(xi+) is shorthand for Ni+(or,x) and similarly for A_(xi+~. It is assumed that these rates are strictly positive except for the boundary conditions A_~0) = A+~n1) = 0. The network evolution model is not necessarily assumed to be stationary, and indeed it is likely that in empirical observations, networks often will be far from the stationary distributions of the corresponding evolution processes. It is interesting nevertheless to consider the stationary distribution of the process, as this indicates the direction into which the evolution is going. The probability distribution pts) on the set {0, . . ., nl) is the stationary distribution for the random walk process of the outUegrees if and only if pts)A+(s) = pts+1)A_(s~1) for 0 < s < n2. (10) (This follows directly from the fact that this is the condition for detailed balance, cf. Norris, 1997.) As a benchmark situation, it Is instructive to consider the stationary dis- tribution of the outUegrees in the actor-oriented mode] of SnijUers (2001) with the very simple objective function fibs) = p~ xi~ . In this model, the choice of which actor changes an outgoing tie variable is made strictly randomly. In this mode! also, the outUegrees of the different vertices are independent stochastic processes. This mode] can be obtained in the formulation of the present paper by defining Din (s) = Az_ (s) = (nsl)exp(3l) (ns1) exp(3~ ) + s exp(Al ) s exp( - 31) (ns1) exp(,Jl) + s exp(>1) as can be checked from the intensity matrices (see (5) and (a) in Snipers, 2001, and (9), (3), (4) above). This implies Az+(s) - Ai- (s + 1) (ns1) exp(pl) (r1 - s2) exp(31) ~ (s + 1) exp()1) . (s + 1) exp( - 31) (ns1) exp(3l) + s exp(~l) which is close to p(s + 1)/p(s) for the binomial distribution with denominator n1 and succes probability exp(23~)/(1 +exp(23~)). Thus, for this model, DYNAMIC SOCIAL NETWORK MODEL~G~D ISIS 153

the out~egrees are for ~ ~ oo close to binomially distributed with these parameters. The change rates Fin and Ai- together reflect two aspects of the evolution process of the outUegrees: the distributional tendency, Ye., the equilibrium distribution towards which the outUegree distribution tends; and the volatil- ity, i.e., how quickly the ties are changing. It follows from (10) that the distributional tendency clepencis on ((s), defined by fifed= Wi+(s) ~i-(S + 1) It is mathematically convenient to express the volatility by vest = Ai+ (s) ~ Ai- (s + 1) . These definitions imply that the rates are given by A2+ (s) = Ai- (s, = uts) ((s) 1 + ((s) ' ants1) 1 + Its - 1) With these definitions, p is the stationary distribution if and only if pts) s=O,...,r1 - 2. (11) (12) (13) (14) For the purpose of statistical modeling, it is necessary to consider parametric families of distributions p. If pest is a member of an exponential family p(S) = po(S) exp(ort(s)¢(~)) where test is a vector of sufficient statistics, ~ is a parameter vector, and ¢~) is a normalizing constant, then this yields poesy exp (or(t(s + 1)this))) E.g., for a truncated Poisson distribution (po(S) comes 154 ((s) = s + 1 = = exp (orlog(s ~ 1)) D YNAMIC SOCIAL NETWORK MODELING AND Anal YSIS (15) 1/s!, t(s) = s), this bet (16)

For a truncated power distribution (pO(S) = 1, tts) = loges + 1), of < 0), the rate functions are ~ s + 1 J is ~ 9\ ~ , ~ exp ~s+1 ) (17) The Poisson distribution is short-tailed, corresponding to ((s) becoming small as s gets large, in contrast to the long-tailed power distribution, for which ((s) becomes close to 1. A model containing the tendencies toward either of these distributions as submodels is obtained by defining its) = exp (oilFlogs+ 1) s + 1) (18) For the volatility function cyst, the dependence on s could be linear, anal- ogous to what was proposed in SnijUers (2001~. This is unattractive, however, if one considers digraphs with arbitrarily large numbers rz of vertices. A hy- perbolic function, tending to a finite constant as s grows indefinitely, seems more attractive: e.g., ( HIS) = ~ 1 + ~4 S + 1 ) (19) where the restriction must be made that ~4 ~1. The functions ~ and z' can also be made to depend on covariates, e.g., through an exponential link function. IV. Parameter estimation For the estimation of parameters of this type of network evolution models for observations made at discrete moments to, . . ., tM, SnijUers (2001) proposed an implementation of the method of moments based on stochastic approxi- mation, using a version of the Robbins-Monro (1951) algorithm. The method of moments is carried out by specifying a suitable vector of statistics of the network and determining (in this case, approximating) the parameters so that the expected values of these statistics equal the observecI values. To apply this approach, statistics must be found that are especially informative about these parameters. First consider the parameters of I. For a model of the general exponen- tial form (15), e.g., (18), the statistic t(S) is a sufficient statistic for the DYNAMIC SOCIAL N~TWORKMOl)~LING AND ANALYSIS 155

limiting distribution, and therefore it seems advisable to use the statistic hi t(Xi+~tm+~), or for multiple observation periods M1 n ~ ~ t(X'+(tm+~) m=1 i=1 (20) For model (18), some simplifying approximations may be used; e.g., for pa- rameter 0~2, this can be based on Stirling's formula. This leads for the three parameters in this model to the fitting statistics M~ 72 ~ ~ Xi+(tm+l) m=1 i=1 M1 n ~ Z(Xi+(tm+l)+ 2)(1°g(Xi+(tm~l)+l)1) m=1 i=1 M1 n ~ ~ lOg(Xi,+ (tm+1 ) ) m=1 i=1 (21) For the parameters in the volatility function z,, the same approach can be taken as in Section 7.4 of SnijUers (2001). This leads for parameter Pm to the statistic n ~ | X2.j(tm+l) Xii(tm) I 3,j=1 and for.parameter 0~4 in (19) to the statistic Xi j (tm+ 1~) ~ Xij (tm ) ~ S~ . . ._ m=i I,= Xi+(tm) + V. Example (22) (23) As a numerical example of the analysis, the dynamics of a network of political actors is considered, based on a study by Johnson and Orbach (2002~. The data used here are from a second and third wave of data collection between 46 actors, most of whom the same individuals as those in the first wave of which results are presented in Johnson and Orbach (2002~. They are self-reported dyadic interaction data, rated on a 0-10 scale which here was dichotomized as 0-6 vs. 7-10. Space limitations prohibit (loin" justice to the richness of the original data and the social processes involved in the network dynamics. 156 DYNAMIC SOCIAL NETWO=MODELING AND AWALYSIS

Preliminary analyses indicated that there is evidence for a network closure effect, expressed better by the number of geodesic distances equal to two, cf. All, than by the number of transitive triplets, see (7~; and that there is evidence for a gentler popularity effect. Sets of estimates are presented here for two corresponding models, differing as to how the degrees are modeled. The first model is according to the specification in SnijUers (2001), with a constant rate function and without the differentiation between adding and withdrawing ties proposed in the present paper. The objective function is specified as fi(3,X) = toxic ~ 92 ~XiiXii + 33#{j~(i,j) =2) + p4 ~ Xij Zj where Zj indicates the gender of actor j. ' fit 1 ' ~ ~ _% ~ - . The second model follows the spec~ncat~on proposed above. rem nary analyses showed that a good fit is obtained by using mode] (18) with Ct2 = 0~3 = 0. The volatility function is held constant, ~- 1. The objective function here is defined as fi+~3,X) = ft_~3,X) = 32 ~XijXji ~ 33~{j~t,j)=2) j +34~XijZj j (note that in this model, it is meaningless to include a term ,B~ xi+ in the objective function; the role that this term has in the earlier model is here taken over by the rate function). The parameter estimates, obtained from the STENA program (version 1.98; see SnijUers & Huisman, 2002) are presented in Table 1. Gender is coded 1 (female) vs. 0 (male), and centered in the program by subtracting the average value of 0.17. Parameters can be tested by approximate z-tests based on the t-ratios (parameter estimate divided by standard error). Using this procedure, all effects mentioned in Table 1 are significant (p < .001~. The fit of the two models can be compared by considering the fitted distributions of the degree sequences. A rather subtle way of doing at this is to look at the observed ranked outUegrees ancT their fitted distributions. Figures 1 and 2 show, for these two models, the observed ranked outUegrees combined with simulated 90-~o intervals for the distributions of the ranked outbegrees. Figure 1 indi- cates a poor fit: the distributions of the 9 highest outUegrees in the fitted model are concentrated on too Tow values compared to the observed highest outUegrees; in the middle low range, the fitted distribution of the ranked DYNAMIC SOCIAL NE:TWORKMOI)EL~G ED ISIS 157

Table 1. Parameter estimates for two model fits for the Johnson-Orbach political actor data (waves 2-3~. Effect . Mode! 1 Mode! 2 par. (s.e.) par. (s.e.) 23.09 22.78 -0.57 (0.07) -1.14 (0.19) 1.37 (0.11) 1.77 (0.23) -0.50 (0.21) -0.62 (0.30) 0.28 (0.10) 0.39 (0.11) Rate factor (pi) Rate function: OutUegrees Boil ) Objective function OutUegrees Reciprocated ties Indirect relations Gender (F) popularity outUegrees is too low compared to the observations. Combined, this implies that the fitted out~egree distribution is too closely peaked about its mean value. On the other hand, Figure 2 indicates a good fit for the second model, each observed ranked outUegree being situated within the 90-% interval of its fitted distribution. degrees 30 - 25 - 20 - 15 - 10 - 10 HI jIIi;~] . a** TttIT: . , , 20 30 40 k Fig. 1. Observed (*) and 90% intervals for ranked outdegrees, Model 1. (k = rank) The parameter estimates and standard errors In Table 1 for both models point to the same conclusions. In the network dynamics there is clear evi- dence for reciprocity of choices, for a network closure effect, and for a greater popularity of female actors. (A gender similarity effect also was tested, but 158 DYNAMIC SOCIAL NETWORK MODELING ED ANALYSIS

degrees 30 - 25 - 20 - 15 - 10 5- III ~1 ELI 10 20 30 40 k Fig. 2. Observed (*) and 90% intervals for ranked outdegrees, Model 2. (k = rank) this was not significant.) If there would have been important differences be- tween the results of the two models, then mode] 2 would have been the more trustworthy, given that it shows a better fit for the outOegree distribution. VI. Discussion The degree distribution is an important characteristic of networks and has received much attention in recent work. However, attention for the degrees should be combined with sufficient attention paid to other aspects of network structure. The current paper proposes a modification of the model presented in SnijUers (2001), addressing the following points of criticism that could be addressed to the earlier model. First, it may be hard to specify the earlier mode] in a way that gives a satisfactory fit for the very skewed degree distributions that are sometimes empirically observed (cf. the many examples mentioned in Newman, Strogatz, and Watts, 2001~. The model proposed here gives almost unlimited possibilities with respect to the outUegree distribution that is generated. Second, the extrapolation properties of the earlier model may be unrealistic in the sense that, depending on the parameters of the model, letting the model run on for a long hypothetical time period may lead to unrealistic phase transitions. More specifically, similarly to what is explained in Snipers (2002a), the earlier model can be specified so that quite a good fit is obtained for the evolution over a limited time period of a network with, say, a rather low density and a relatively high amount of transitivity, but that the graph evolution process so defined will with probability one lead to an explosion' in the sense that at some moment, the graph density very DYNAMIC SOCIAL N~TWORKMOD~WG ED ISIS 159

rapidly increases to a value of 1 and remains 1, or almost 1, for a waiting time that is infinite for aB practical purposes. (A closely related property, but for the case of a graph evolution process where the number of vertices tends to infinity, was noticed by Strauss, 1986. This phenomenon also resembles the phase transitions known for the Ising mode] and other spatial models in statistical physics discussed, e.g., in Newman and Barkema, 1999.) Such phase transitions can be avoided in the model proposed below because the out~egree distribution is determined independently of the further structural network properties. A third reason, of a more theoretical nature, for proposing this model, is to demonstrate that quite plausible models are possible for digraph evolution in which the distribution of the outUegrees is dissociated completely from the other structural network properties such as transitivity and subgroup formation. This implies that we can learn little about the processes leading to transitivity and related structural properties of graphs and digraphs by looking only at degree distributions, or by limiting attention to network evolution processes that are based only on degrees. REFERENCES Albert. R.. and Barabasi ANT, tonne , ~ ~ 7 _____ x~ I_ Statistical mechanics of complex networks. Review of modern physics, 74, 47-97. Barabasi, A.-I,., and Albert, R., (1999~. Emergence of scaling in random networks. Science, 286, 509-512. Huisman, M.E., and T.A.B. Snifflers. 2003. Statistical analysis of Tongitudi- nal network data with changing composition. Submitted for publication. Johnson, J.C., and M.K. Orbach. 2002. Perceiving the Political Landscape: Ego Biases in Cognitive Political Networks. Social Networks, 24, 291 - 310. Maddala, G.S. 1983. Limited-dependent and qualitative variables in econo- metrics. Cambridge: Cambridge University Press. Molloy, M., and B. Reed. 1995. A critical point for random graphs with a given degree sequence. Random Structures and Aigorathms, 6, 161-179. Newman, M.E.~., and Barkema, G.T. (1999~. Monte Cario methods in sta- tistical physics. Oxford: CIarendon Press. Newman, M.E.J., Strogatz, S.H., and D.J. Watts. 2001. Random graphs with arbitrary degree distributions and theor applications. Physical Re- views E 64, 026118. Newman, M.E.J., Watts, D.J., and Strogatz, S.H. 2002. Random graph mod- els of social networks. Proceedings of the National Academy of Sciences 160 DYNAMIC SOCIAL NETWORK MODELING ED ISIS

USA, 99, 2566-2572. Norris, J.R. 1997. Markov Chains. Cambridge: Cambridge University Press. Robbins, H., and S. Monro. 1951. A stochastic approximation method. Annals of Mathematical Statistics, 22, 400 - 407. SnijUers, T.A.B. 1991. Enumeration and simulation methods for 0-1 matrices with given marginals. Psychometraka, 56, 397-417. Snipers, T.A.B. 2001. The Statistical Evaluation of Social Network Dynam- ics. M.E. Sobe! and M.P. Becker feds.), Sociological Methodology-2001, 361-395. Boston and London: Basil Blackwell. SnijUers, T.A.B. 2002a. Markov Chain Monte Cario Estimation of Expm nential Random Graph Models. Journal of Social Structure vol. 3 no. 2. SnijUers, T.A.B. 2002b. Manual for ZO version 2.3. Groningen: {CS, Uni- versity of Groningen. Obtainable from http://stat.gamma.rug.nI/snijUers/socnet. htm Snifflers, T.A.B. 2003. Models for Longitudinal Network Data. In: P.~. Carrington, J. Scott, and S. Wasserman feds.), Models and Methods in Social Network Analysis. New York: Cambridge University Press, in preparation. Snipers, T.A.B., and Huntsman, J.M. 2002. Manual for SIENA version 1.95. Groningen: ICS, University of Groningen. Obtainable from http://stat.gam ma.rug.nI/snij~ers/socnet.htm Snipers, T.A.B., and van Duijn, M.A.~. 2002. Conditional maximum likeli- hood estimation under various specifications of exponential random graph models. Pp. 117-134 in Jan Hagberg fed.), Contributions to Social Net- work Analysis, Information Theory, and Other Topics in Statistics; A Festschraft in horzour of Ove Frank. University of Stockholm: Depart- ment of Statistics. Strauss, D. 1986. On a general class of models for interaction. SIAM Review, 28, 513-527. Tversky, A. 1972. Choice by elimination. Journal of Mathematical Psychol- ogy, 9, 341-367. Wasserman, S. 1977. Random directed graph distributions and the triad census in social networks. Journal of Mathematical Sociology, 5, 61-86. Wasserman, S., and K. Faust. 1994. Social Network Analysis: Methods and; Applications. New York and Cambridge: Cambridge University Press. Wasserman, S., and P. Pattison. 1996. Logit models and logistic regres- sion for social networks: I. An introduction to Markov graphs and p*. Psychometrika, 61, 401 - 425. DYNAMIC SOCKS N~TWO~ MODELING ED ISIS 161