A Perturbative Solution to the Linear Influence/Network Autocorrelation Model Under Network Dynamics^†^†thanks: The author thanks Weihua An and David Jacho-Chavez for helpful discussions on bias in the network autocorrelation model.

Carter T. Butts Departments of Sociology, Statistics, Computer Science, and EECS, University of California, Irvine; [email protected]

(10/30/23)

Abstract

Known by many names and arising in many settings, the forced linear diffusion model is central to the modeling of power and influence within social networks (while also serving as the mechanistic justification for the widely used spatial/network autocorrelation models). The standard equilibrium solution to the diffusion model depends on strict timescale separation between network dynamics and attribute dynamics, such that the diffusion network can be considered fixed with respect to the diffusion process. Here, we consider a relaxation of this assumption, in which the network changes only slowly relative to the diffusion dynamics. In this case, we show that one can obtain a perturbative solution to the diffusion model, which depends on knowledge of past states in only a minimal way.
Keywords: linear diffusion model, social influence, network autocorrelation model, feedback centrality, network dynamics

The forced linear diffusion model is an important (and sometimes implicit) workhorse of network research, lying behind the feedback centrality scores (Koschützki et al.,, 2005), the Friedkin-Johnsen (F-J) model of social influence (Friedkin and Johnsen,, 1990), and the network (aka “spatial”) autoregressive model (Cliff and Ord,, 1973; Anselin,, 1988; Doreian,, 1989). In standard usage, this discrete time model is used to describe the evolution of vertex attributes within a fixed network, where the attribute of each vertex at a given time point is taken to be a linear combination of the attributes of its neighbors at the previous time point, plus an exogenous forcing term. This model is particularly attractive due to its long-run behavior, which under fairly mild conditions involves convergence to a unique fixed point that depends on the network and the forcing term, but not the past history of the system. This allows the model to be used in cross-sectional settings (as is typically the case for centrality score and autoregressive model applications), where intertemporal data is not available. Indeed, this latter use is sufficiently common that many authors using the model make no reference to the underlying dynamic assumptions, and may in some cases be unaware of them.

In real-world settings, however, these assumptions may be consequential. Among the more obvious is the treatment of the underlying network as fixed; or, more correctly, that any network dynamics are much slower than (i.e., timescale separated from) the convergence of the diffusion process. The need for timescale separation (and specific justifications for it, in the context of attitudinal influence) is discussed quite explicitly by Freidkin, (1998), but has more often been tacit or unrecognized (e.g., one finds no mention of comparative dynamics in Katz, (1953); Bonacich, (1987); Leenders, (2002); Koschützki et al., (2005); Butts, 2008c , among many others). When timescale separation does not hold, the network is no longer effectively fixed, and the behavior of the linear diffusion model is not in general history-independent.

Of course, the general notion that power, influence, or other quantities might diffuse on an effectively dynamic network has long been recognized. Indeed, such joint dynamics are a major motivation for work in the stochastic actor-oriented model (SAOM) tradition (Snijders et al.,, 2007; Steglich et al.,, 2010; Niezink and Snijders,, 2017), which has become the dominant approach for studying behavior in this regime. There has been less interest in the linear diffusion setting, possibly because this breaks the equilibrium condition that makes the model so easily used with cross-sectional data; we review this development in Section 1.1. Some exceptions include Friedkin and Johnsen, (1990; 2003) and work on STARIMA models (Pfeifer and Deutsch,, 1980); in particular, Friedkin and Johnsen, (2003) consider a case in which equilibrium is recovered by allowing the network itself to converge to a fixed point, but absent such special cases the interdependence between network and attribute dynamics has traditionally made the model unattractive when time-scale separation is violated.

Here, we return to this classic problem of linear diffusion on a dynamic network without time-scale separation of network and diffusive dynamics. Although (as we recapitulate) the behavior of this system is in general history dependent, we consider the regime in which network dynamics are relatively slow with respect to the convergence time of the diffusion process. As we show, this regime allows a perturbative, “near equilibrium” solution, in which the attribute distribution can be approximated in terms of the fixed-network equilibrium at the current time point, modified by a correction term that depends only on the local network dynamics (i.e., rates of change). This solution does not depend on the long-run history of the network, and hence may be more easily used in settings for which only short-term information is available. The solution also provides insight into how network change impacts the diffusion process. We demonstrate the solution (and its limitations) with a simulation study of a dynamic social influence process on networks with varying rates of change.

1 The Basic Model

The forced linear diffusion model is a discrete-time process defined by the recurrence

y_{t}=Ay_{t-1}+z,

(1)

where $y_{t}$ is the vector of vertex states at time $t$ , $A$ is an $N\times N$ matrix of diffusion weights, and $z$ is an exogenous forcing vector, describing the input to each vertex at each time period. Typically, all quantities are assumed to be real-valued. Eq. 1 arises in many settings, including several of particular significance in the context of social networks.

Social Influence:

The extensively studied Friedkin-Johnson model of social influence is specified its basic form (e.g. in Freidkin,, 1998) by

y_{t}=SGy_{t-1}+(I-S)y^{(0)},

where $S$ is a diagonal matrix whose entries (constrained to the [0,1] interval) are taken to be susceptibilities to influence, $G$ is a matrix of influence weights, and $y^{(0)}$ is usually held to be a vector of initial attitudes (though, as noted below, $y^{(0)}$ will only coincide with an actual time-zero $y_{0}$ under specific conditions). $G$ is generally held to satisfy certain conditions, including source conservation and non-negative influence ( $0\leq G_{ij}\leq 1$ ), convexity ( $\sum_{j=1}^{N}G_{ij}=1$ ), and the defining condition for self-influence $G_{ii}=1-S_{ii}$ . Recognizing that we can take $A=SG$ and $z=(I-S)y^{(0)}$ , this can be seen as a special case of Eq. 1. This further clarifies the role of $y^{(0)}$ , which in practice acts as an exogenous source of influence on ego (whose strength is scaled by ego’s degree of “self-influence”). The identification of $y^{(0)}$ as an initial attitude (i.e., $y_{0}$ ) can be rationalized as follows. Let us assume that each individual is initially in some isolated state, prior to network exposure, in which they are allowed to equilibrate; in this environment, all elements of $S$ and $G$ are identically 0 (since there is no influence), and the vector of attitudes will then converge immediately to $y^{(0)}$ . If the individuals in question are then suddenly put into diffusive contact with each other, they will then start with attitudes $y_{0}=y^{(0)}$ , before evolving due to the influence process. Although this situation is arguably rare in many naturalistic settings, it accurately mirrors the experimental conditions in which most empirical work on the F-J model has been done, thus motivating the identification of $y^{(0)}$ with the initial attitude in much of the literature. In general, however, it is more accurate to regard $y^{(0)}$ simply as the amalgam of all influences on network members from outside the network itself, which then diffuse forward as individuals interact.

Feedback Centrality:

Variations of Eq. 1 (or the equilibrium equation described in Section 1.1) frequently arise in definitions of feedback centrality scores (Koschützki et al.,, 2005), often used as a priori predictors of power, influence, status, or prestige. Notable examples include the Katz $\alpha$ index (Katz,, 1953), with

y_{t}=\alpha Wy_{t-1}+\mathbf{1}

where $A=\alpha W$ with scalar parameter $\alpha>0$ , and $\mathbf{1}$ is a one-vector. The Bonacich power score (Bonacich,, 1987) can similarly be obtained from the recurrence

y_{t}=\beta Wy_{t-1}+\alpha W\mathbf{1}

where $A=\beta W$ with scalar parameter $\beta$ (not necessarily positive), and $\alpha W\mathbf{1}$ for positive scalar $\alpha$ is proportional to the outdegrees of $W$ . A third example is the family of Salancik power indices (Salancik,, 1986), whose recurrence is given by

y_{t}=Ay_{t-1}+MS

where $M$ is an $n\times m$ matrix of subgroup memberships, and $S$ is an $m$ -vector of subgroup “importance” scores (with $MS$ taken to be a measure of the “intrinsic importance” of each node, apart from the diffusion process). Perhaps the most famous of all (due to its importance in information retrieval) is PageRank (Brin and Page,, 1998), with the recurrence

y_{t}=\delta Py_{t-1}+(1-\delta)\mathbf{1}

where $\delta\in(0,1)$ is an attenuation parameter, and $P$ is a row-normalized adjacency matrix (in the original context, of hyperlinks). The similarity to the F-J model is particularly striking, as noted by Friedkin and Johnsen, (2014).

As these examples illustrate, most measures of this kind vary primarily by how they define the forcing term (taken as a measure of exogenous power, status, or influence) and whether/how the weight matrix is explicitly scaled (used e.g. in the Bonacich power score to emulate the effects of positive versus negative exchange relationships). It should be noted that, while not all such scores were originally defined using the recurrent form, the underlying mechanistic logic of an iterative process in which centrality flows through a focal network is ubiquitous in their description.

Network Autocorrelation:

The network autoregressive (NAR) model (see e.g. Cliff and Ord,, 1973; Anselin,, 1988; Doreian,, 1989) is typically specified in terms of the equilibrium solution shown in Section 1.1, but can be seen as arising from the recurrence

y_{t}=\alpha Wy_{t-1}+X\beta,

where $\alpha$ is a scalar (not necessarily positive), $A=\alpha W$ , $X$ is a matrix of nodal covariates, and $\beta$ is a vector of coefficients. In typical use cases, $W$ , $X$ , and $y$ are observed (the latter implicitly taken to be an equilibrium realization, with $t\to\infty$ ), and $\alpha$ and $\beta$ are taken as objects of inference. The NAR model is better known as the spatial autoregressive model (SAR), due to its widespread use in spatial statistics (where areal units are taken to be nodes, and some measure of contiguity or proximity serves as the weight matrix). However, there is nothing particularly spatial about the SAR model, and it is in fact simply a rebranded network model. Because the fit of the diffusion model to real data is never exact, an additional additive error is usually assumed; however, this is added to the equilibrium solution in ad hoc fashion, and does not appear in the recurrence. (In the network moving average (NMA) model, this additive error itself is taken to be the equilibrium of a similar recurrence. The two may be combined in the network ARMA model, among various other extensions.) The lack of attention to timescale separation may be particularly concerning in the NAR context, because of its inferential goals: when the system is out of equilibrium, the standard NAR solution will be badly misspecified, leading to biased (and worse, inconsistent) inference. We comment briefly on this issue in Section 4.

1.1 Equilibrium Solution

In general, the state of the recurrence in Eq. 1 depends on an initial condition $y_{0}$ , i.e.

	$\displaystyle y_{1}=Ay_{0}+z$
	$\displaystyle y_{2}=A^{2}y_{0}+Az+z$
	$\displaystyle\cdots$
	$\displaystyle y_{t}=A^{t}y_{0}+\left[\sum_{i=1}^{t}A^{i-1}\right]z.$		(2)

In most applied settings, such a boundary condition is not available, and it may in any event be unclear what timescale is appropriate for selection of the observation time $t$ (i.e., the pace of the updating process may not be known). However, these issues may in some cases be elided. In particular, when the spectral radius $\rho(A)$ of the weight matrix is less than unity, $y_{t}$ will converge to a stable fixed point as $t\to\infty$ . This state is usually derived by positing a hypothetical equilibrium state, $y_{\infty}$ , and noting that it must by definition be a fixed point of the dynamics. It can then be obtained as

$\displaystyle y_{\infty}$	$\displaystyle=Ay_{\infty}+z$
$\displaystyle(I-A)y_{\infty}$	$\displaystyle=z$
$\displaystyle y_{\infty}$	$\displaystyle=(I-A)^{-1}z,$	(3)

with the solution existing when $A$ is invertible. To foreshadow later developments, note that we can also see how this result arises from Eq. 2. Since $\rho(A)<1$ , we have $A^{t}y_{0}\to 0$ as $t\to\infty$ for all finite $y_{0}$ , and the first (“memory”) term containing dependence on $y_{0}$ vanishes. The second term in Eq. 2 then contains the infinite power series sum $I+A+A^{2},\cdots$ , which is equal to $(I-A)^{-1}$ under the same spectral radius condition. Substitution then yields Eq. 3.

We may ask what happens when $\rho(A)\geq 1$ . In this regime, the power series will not converge, and typically one observes a divergence of at least some states of $y$ ; intuitively this is because $A$ is not a long-run contractive mapping, and the associated diffusion process “blows up” by iterative amplification. The conditions of e.g. Friedkin and Johnsen, (1990) are indeed chosen to avoid this outcome. (See appendix B of Freidkin, (1998) for a particularly extensive discussion of convergence conditions.) While the system does not converge to a fixed point in this case, it should be noted that the system is still well-defined, and Eq. 2 (but not Eq. 3) remains valid. Note that (particularly if $\rho(A)=1$ ) there may be specific values of $y_{0}$ and $z$ that do not diverge (an obvious example arising when both are zero-vectors), but stability is guaranteed in general only for $\rho(A)<1$ .

The obvious practical value of Eq. 3 is that it allows us to speak of the behavior of the diffusion process without knowing its initial conditions, and indeed without knowing “how long” the system has been running: provided we think that the process of interest has iterated enough to be at (or near) equilibrium, we can describe its behavior using only the weight matrix and the forcing vector. The plausibility of this interpretation is aided by the fact that convergence to equilibrium is geometric; thus, so long as $A$ is reasonably contractive, few iterations are really needed to be close to equilibrium, and the approximation is easily rationalized. However, this interpretation still requires a number of assumptions, among them being that $A$ is fixed. Relaxing this complicates matters, as we now discuss.

2 Diffusion on Dynamic Networks

While Eq. 1 presumes a fixed diffusion network, this can be easily relaxed by taking $A$ to be time-dependent. This leads to the more general recurrence

y_{t}=A_{t}y_{t-1}+z,

(4)

where $A_{t}$ is the matrix of weights active at time $t$ . The consequence of this change can be appreciated by extending the recurrence backward in time to some arbitrary prior period $t-k$ :

$\displaystyle y_{t}$	$\displaystyle=A_{t}y_{t-1}+z$
	$\displaystyle=A_{t}[A_{t-1}y_{t-2}+z]+z$
	$\displaystyle=A_{t}A_{t-1}y_{t-2}+[I+A_{t}]z$
	$\displaystyle=A_{t}A_{t-1}[A_{t-2}y_{t-3}+z]+[I+A_{t}]z$
	$\displaystyle=A_{t}A_{t-1}A_{t-2}y_{t-3}+[I+A_{t}+A_{t}A_{t-1}]z$
	$\displaystyle=\left[\prod_{i=0}^{k-1}A_{t-i}\right]y_{t-k}+\left[I+\sum_{i=0}^{k-1}\prod_{j=0}^{i}A_{t-j}\right]z.$	(5)

$y_{t}$ is now a function of two terms (c.f. Eq. 5). The first represents the residual “memory” for the state of the system at time $t-k$ , while the second represents the accumulated influence of the forcing term through the time-accumulated temporally forward walks through the dynamic graph. Both, as may be expected, are history dependent: we cannot, in general, know the state of $y_{t}$ without knowing both an initial condition and the evolution of the diffusion weights in the intervening period.

It is intuitively useful to consider the conventional equilibrium solution in light of Eq. 5. Let us imagine that $A$ evolves so slowly that, over the timescale of the attribute dynamics, $A=A_{t}\approx A_{t-k}$ for all $t,k$ . (I.e., we say that we have complete timescale separation between the dynamics of $A$ and the dynamics of $y$ .) In that case, Eq. 5 simplifies to

	$\displaystyle y_{t}$	$\displaystyle\approx\left[\prod_{i=0}^{k-1}A\right]y_{t-k}+\left[I+\sum_{i=0}^{k-1}\prod_{j=0}^{i}A\right]z$
		$\displaystyle=A^{k}y_{t-k}+\left[I+A+A^{2}+\ldots+A^{k-1}\right]z.$

This is not by itself sufficient to guarantee equilibrium. However, if we assume that there exists finite $\delta$ such that $|y_{t-k}|<\delta$ for all $t-k$ , and $\rho(A)<1$ , then $\lim_{k\to\infty}A^{k}y_{t-k}=0$ , and we obtain

	$\displaystyle y_{t}$	$\displaystyle\approx\left[I+A+A^{2}+\ldots\right]z$
		$\displaystyle=\left[I-A\right]^{-1}z,$

where we have exploited the convergence of the matrix power series under our assumed conditions on $A$ . This recapitulates the development of Eq. 3, but clarifies what is required for equilibrium to hold in the dynamic matrix case: we need to lose the memory of prior states (which occurs when the matrix product in the first term of Eq. 5 is driven to the zero matrix), and we require convergence of the diffusion of $z$ through the network (which occurs because the high-order terms in the associated matrix sum vanish). The specific functional form of the solution depends on $A$ being fixed. Although this last cannot hold in the general case, we observe that the first two conditions do not depend on fixed $A$ , and could be generalized to the dynamic setting. We now turn to this possibility.

2.1 Behavior with Slow Network Dynamics

We now attempt to relax the condition of complete timescale separation, instead invoking a “slow network dynamics” condition in which changes in $A$ are weakly dominated by the relaxation in $y$ ; $y$ is then close to its corresponding static equilibrium, but slightly perturbed by the network dynamics. Importantly, in this regime we lose long-range dependence on past states, allowing for a solution that can be described without reference to initial conditions.

We begin the development by returning to Eq 5, and imposing weaker conditions on $A_{t}$ . We start with the assumption that $A_{t-k}$ is always contractive ( $\rho^{*}(A_{t-k})<1$ for all $t,k$ , where $\rho^{*}$ is the maximum singular value) and that $y$ is bounded (i.e., there exists finite $\delta$ such that $|y_{t-k}|<\delta$ for all $t,k$ ). It then follows that $\lim_{k\to\infty}\left[\prod_{i=0}^{k-1}A_{t-i}\right]y_{t-k}=0$ , leaving us with the limiting expression

\displaystyle y_{t}

\displaystyle=\left[I+\sum_{i=0}^{k-1}\prod_{j=0}^{i}A_{t-j}\right]z

which is “memoryless” with respect to the past history of $y$ . For convenience in describing dynamics with respect to the focal time $A_{t}$ , we introduce the matrix difference $D_{k}=A_{t-k}-A_{t}$ , giving us

	$\displaystyle y_{t}$	$\displaystyle=\left[I+\sum_{i=0}^{k-1}\prod_{j=0}^{i}(A_{t}+D_{j})\right]z$
		$\displaystyle=\left[I+A_{t}+A_{t}(A_{t}+D_{1})+A_{t}(A_{t}+D_{1})(A_{t}+D_{2})\cdots\right]z$
		$\displaystyle=\left[I+A_{t}+A_{t}^{2}+A_{t}^{3}+\cdots+A_{t}D_{1}+A_{t}^{2}D_{1}+A^{2}_{t}D_{2}+A_{t}D_{1}D_{2}+\cdots\right]z$
		$\displaystyle=\left[I+A_{t}\right]^{-1}z+\left[A_{t}D_{1}+A_{t}^{2}D_{1}+A^{2}_{t}D_{2}+A_{t}D_{1}D_{2}+\cdots\right]z.$

Now, let us consider the slowly varying regime in which $\rho^{*}(D_{k})\ll\rho^{*}(A_{t})<1$ , and $D_{k}\approx kD$ for small $k$ . We then have

\displaystyle y_{t}

\displaystyle\approx\left[I+A_{t}\right]^{-1}z+\left[A_{t}D+A_{t}^{2}D+2A^{2}_{t}D+2A_{t}D^{2}+\cdots\right]z.

Since $D$ and $A$ are “small” (i.e., highly contractive), higher powers contribute little to the sum, giving us the first-order dynamic approximation

\displaystyle y_{t}

\displaystyle\approx\left[\left[I+A_{t}\right]^{-1}+A_{t}D\right]z.

(6)

This can immediately be seen as a perturbed version of the equilibrium solution in Eq. 3, with the solution being linearly displaced from equilibrium by $A_{t}Dz$ ; intuitively, this is the diffusion of $z$ through all two-walks involving, respectively, the base weight matrix at time $t$ and the change in the weight matrix (which is itself a weight matrix). As with the past history of $y$ , the detailed past history of $A$ is not required: the direction of weight change near the observed time point is sufficient in this regime. Indeed, it should be observed that the local linearization condition $D_{k}\approx kD$ is not strictly necessary (although it is convenient): the important condition is $D_{k}$ is sufficiently contractive that higher-order products involving $D$ contribute little to the final state.

3 Numerical Examination: Power on a Dynamic Network

To examine the behavior of the perturbative solution - and, in particular, the extent to which it improves on the fixed equilibrium solution under incomplete timescale separation - we perform a simulation study of power dynamics on evolving organizational networks. We employ a Salancik-like process (Salancik,, 1986) for power updating, with each individual having an exogenous “power base” that acts as a forcing term to their current, realized power level. I.e., we posit a dynamically evolving “power score,” $y_{t}$ , whose evolution is governed by

y_{t}=\alpha G_{t}y_{t-1}+f

where $\alpha$ is an attenuation parameter, $G_{t}$ is the state of the relevant power-transmission network at time $t$ , and $f$ is vector of exogenous inputs (representing the basis of each individual’s capabilities external to the diffusion process).

The basis of our model is a case studied by Krackhardt, (1990), who investigated power and influence in a mid-sized information technology company (referred to as “Silicon Systems”). Krackhardt reports measurements of perceived friendship and advice-seeking ties within the organization, as well as members’ mean ratings of individuals’ “charisma” (“influence derived from personal magnetism”) and “potency” (“ability to get things done that the power-holder wants done”). In line with the observations of e.g. Krackhardt, (1990) and Krackhardt and Hanson, (1993) that different relations can be conduits for distinct types of power and influence, we model two hypothetical power-generating processes within the network: “soft” power through the friendship network (for which charisma is taken to act as an exogenous source); and power related to expertise or authority through the advice-seeking network (for which potency is taken to act as an exogenous source). Power in the former is obtained from a combination of charisma and being seen as a friend by charismatic alters (who are themselves seen as friends by charismatic alters), and power in the latter is obtained from a combination of personal potency and being sought-out for advice by potent alters (who are themselves sought-after by potent alters). While both cases are stylized – and here employed primarily as an examination of the perturbative solution to the linear updating model under network dynamics – they thus illustrate basic processes of interest to network researchers.

Network evolution is here modeled using continuous-time ERGM generating processes (Butts, 2023a, ) whose equilibrium behaviors¹¹1Note that, while the equilibrium of the linear model is a single fixed point, the EGP equilibrium is a graph distribution; the process is ergodic, but remains dynamic over time. are respectively calibrated to the empirically observed friendship and advice networks; as Krackhardt, (1990) reports cognitive social structure data (self and proxy reports of ties among all network members), we estimate the underlying network structures using the approach of Butts, (2003) (with the graph mixture priors of Butts, (2017), and dividing self and proxy reports as recommended by Lee and Butts, (2018)). By varying the rate of change in the ERGM generating process (EGP), we vary the difference between networks at successive time steps, from near-fixed to radically altered.²²2Although the EGP itself is continuous, we use it here solely to generate discrete time dynamics that are compatible with linear updating model; this allows us to easily scale the expected changes between time points, but we do not otherwise treat the system as continuous. In the former limit, we would expect the fixed-network equilibrium solution to offer a serviceable approximation to the final state of the power dynamics, while in the latter we would expect the system to be too far from equilibrium for a local solution to hold. Between these extremes, we would expect to see the “slow dynamics” regime in which the fixed-network equilibrium fails, but the perturbative solution offers a reasonable approximation to the exact state.

3.1 Simulation Study Design

The simulation study is organized as follows. We obtain an equilibrium graph distribution by fitting an ERGM to each reference network, then simulating dynamics from an EGP with the fitted ERGM equilibrium. Using the EGP, we create network time series whose steps reflect differing levels of network change; specifically, we calibrate the EGP such that adjacent networks reflect an average of 1 to 4096 edge change events (in powers of 2). We generate one time series at each change rate for each of 250 draws from the equilibrium ERGM (using the ERGM draw as the initial state), creating 250 independent replicates at each of 13 change rates. We simulate time series of 20 network cross-sections, including the initial state. For each time series, we then simulate a linear updating process, obtaining in each case the final distribution of power scores. These are then compared with the power scores obtained by a hypothetical equilibrium solution on the final graph in each time series, and with the power scores obtained by the corresponding perturbative solution. Below, we elaborate on each aspect of the study in detail; results are shown in Section 3.2.

Network Estimation:

We estimate friendship and advice networks for Silicon Systems using the full cognitive social structure (CSS) data, using the protocol of Lee and Butts, (2018). Analysis and data manipulation was performed using the sna (Butts, 2008b, ) and network (Butts, 2008a, ) libraries from the statnet (Handcock et al.,, 2008) suite for the R statistical computing system (R Core Team,, 2023). Symmetric Beta(1,11) error rate priors were used for all informants (with separate self and proxy reporting error rates), and Dirichlet-categorical network priors were used for the graph structure (with hyperparameters set to the Jeffreys prior). Five independent Markov chains were used for estimation, with 500 burn-in iterations followed by 500 draws per chain. The edgewise posterior mode was used as the graph estimate for each network. Because neither self nor proxy reports are available for three actors (and the model hence has no information about their relationships), ties involving these three actors were coded as missing for subsequent ERGM analysis. Visualizations of the networks are shown in Figure 1.

Refer to caption — Figure 1: Posterior mode estimates for the advice and friendship networks; nodes are colored by potency and charisma scores (respectively). (Missing edges not shown.)

Equilibrium Network Model:

To serve as a realistic base case, we use equilibrium distributions of network structures derived from the respective friendship and advice networks. Specifically, we fit ERGMs to both networks; each network contains ties among the 36 members of the organization, with covariates for organizational rank, assessed potency and charisma, and membership in the potential bargaining unit for a unionization drive occurring during the study period (Krackhardt,, 1992). As we interpret being sought for advice or friendship as a source of power to the recipient, we retain the directed character of the data; missing edges are handled using the method of Handcock and Gile, (2010). In addition to baseline density and mutuality effects, we consider differential mixing by membership in the (politically salient) bargaining unit, absolute differences in rank, and target potency and charisma. (Charisma was neither significant ( $p=0.94$ ) nor AIC-favored in the advice network (AIC 512.4 vs. 479.2), and was thus dropped from this model.) Absolute difference in rank was favored versus signed difference in rank (even in the advice-seeking network, where the signed effect was neither significant ( $p=0.37$ ) nor AIC-favored (481.3 vs. 497.2)) and hence was used in both models. Directed GWESP (outgoing two-paths) was employed to capture tendency towards transitive closure. The models were fit using the ergm library (Hunter et al.,, 2008; Krivitsky et al.,, 2023), using default (Geyer-Thompson-Hummel) settings; adequacy checking was performed using standard simulation-based (“gof”) assessments. Coefficients for the estimated models are shown in Tables 1 and 2.

Term	Estimate	Std. Error	$z$ -value	$\Pr(>\|z\|)$
Edges	-7.7357	0.6730	-11.494	$<1e-04$	$***$
Mutuals	0.9529	0.4519	2.108	$0.034992$	$*$
Nodemix-Bargaining Unit-In $\to$ Out	-0.5897	0.2743	-2.150	$0.031567$	$*$
Nodemix-Bargaining Unit-Out $\to$ In	-1.6934	0.5817	-2.911	$0.003600$	$**$
Nodemix-Bargaining Unit-In $\to$ In	0.8659	0.2429	3.565	$0.000364$	$***$
Absdiff-Rank	-1.0690	0.2035	-5.252	$<1e-04$	$***$
Nodeicov-Potency	1.1633	0.1648	7.057	$<1e-04$	$***$
GWESP-OTP( $\phi=0.25$ )	1.1509	0.2500	4.603	$<1e-04$	$***$
*: $p<0.001$ ; : $p<0.01$ ; *: $p<0.05$ ; .: $p<0.1$

Table 1: Parameter estimates for the equilibrium advice network model.

Term	Estimate	Std. Error	$z$ -value	$\Pr(>\|z\|)$
Edges	-7.950295	0.756614	-10.508	$<1e-04$	$***$
Mutuals	6.556689	0.647518	10.126	$<1e-04$	$***$
Nodemix-Bargaining Unit-In $\to$ Out	-0.005268	0.485911	-0.011	0.991351
Nodemix-Bargaining Unit-Out $\to$ In	-0.676298	0.519403	-1.302	0.192894
Nodemix-Bargaining Unit-In $\to$ In	0.431477	0.200935	2.147	0.031766	$*$
Absdiff-Rank	-0.281091	0.119672	-2.349	0.018832	$*$
Nodeicov-Potency	0.184826	0.096936	1.907	0.056563	.
Nodeicov-Charisma	0.611103	0.173803	3.516	0.000438	$***$
GWESP-OTP( $\phi=0.5$ )	0.306050	0.103848	2.947	0.003208	$**$
*: $p<0.001$ ; : $p<0.01$ ; *: $p<0.05$ ; .: $p<0.1$

Table 2: Parameter estimates for the equilibrium friendship network model.

Given the equilibrium network models, we then simulate 250 independent realizations from each to use as starting points for our simulated trajectories. These were drawn using the standard (Tie/Random Dyad) MCMC algorithm from the ergm library, with a thinning interval of $10^{5}$ . Note that this process automatically generates edges for all nodes (i.e., since we simulate from the full graph distribution, there are no missing edge states).

Network Evolution Calibration:

We employ longitudinal ERGM (LERGM) dynamics (Koskinen and Snijders,, 2007) for evolution of the underlying networks. The LERGM EGP for each network is specified by the equilibrium models of Tables 1 and 2, together with a single rate parameter in each network that governs the overall pace of change. In the present case, this rate is only meaningful relative to the dynamics of the linear updating model. To establish a timescale for the network dynamics, we thus adjust the rate so that the expected waiting time to the first event across all 250 equilibrium network draws was approximately 1 (i.e., approximately 1 tie change per unit time, on average). All hazard calculations and simulations for the EGPs were performed using the ergmgp library (Butts, 2023b, ).

Joint Evolution Model:

Our joint evolution model proceeds as follows. We begin by generating a sequence of 20 networks starting from each equilibrium network, using realizations from the calibrated EGP initialized with the equilibrium draw; this is done by saving the current network state every $r$ time units, where $r$ is a rate multiplier governing the expected number of tie changes between steps. (I.e., when $r=16$ , adjacent time steps reflect an average of 16 tie change events.) We then initialize individual power levels with $y_{0}$ based either on reported potency (for the advice case) or charisma scores (for the friendship case). Updating is performed using the linear model, with the diffusion matrix $A_{t}=\alpha G_{t}$ , where $G_{t}$ is the network state at time $t$ , $\alpha=1/(2\rho_{m})$ , and $\rho_{m}$ is the maximum spectral radius observed over the 250 network equilibrium sample (thus ensuring that the model is convergent). Our focus is then on the comparison of the final power scores at $y_{20}$ from the dynamic model with (1) the state obtained from the fixed-graph equilibrium at $G_{20}$ (i.e., ignoring dynamics), and (2) the state obtained from the perturbative solution at $G_{20}$ (i.e., using the one-step correction). This is done for the final states arising from each rate multiplier for each initial graph, resulting in a total of $13\times 250$ sets of comparisons in each case.

3.2 Results

Equilibrium Models:

Tables 1 and 2 show the coefficients for the ERGM potentials used to drive the respective network dynamics (see Butts, 2023a, ). Both networks show tendencies towards reciprocity (though much more so for friendship than advice-seeking) and transitive closure. Mixing across ranks is disfavored, and there is a tendency to select alters with higher potency (though this effect is above the 0.05 significance threshold for friendship, its inclusion is favored by AIC/BIC). Charismatic actors are favored for friendship selection, and there is homophily among members of the bargaining unit; for the advice network, we also see some tendency for unit members to specifically avoid seeking advice from non-members (relative to non-member/non-member ties), and a strong tendency for non-members to avoid seeking advice from unit members. The LERGM EGP preserves these tendencies, with unfavorable edges breaking more rapidly than favorable ones (and favorable edges forming at a higher rate then ones that would be unfavorable).

Events Versus the Pace of Network Change:

We simulate trajectories seeded with our 250 equilibrium network draws using an expected $2^{0}-2^{12}$ tie changes per step; note that tie change events can involve “churn” in which the network returns to earlier states, and thus the number of change events is not equivalent to accumulated change per time step. Figure 2 shows the average change between time steps for each model, in terms of Hamming velocity (total edge differences between networks) and graph correlation. As expected, the realized rate of change increases with the event rate, ultimately leveling off at high event rates. In this regime, the dynamics are sufficiently well-mixed that one is observing approximately independent draws from the network equilibrium; these networks are still (marginally) correlated, however, due to the presence of covariates that produce persistent structure in the graph. Figure 2 thus confirms that our simulations span the full range from extremely slow dynamics (with roughly one edge change per time step) to “saturated” dynamics in which the network states are roughly independent draws from the equilibrium distribution. Since our interest is in the relationship between approximation error due to ignoring dynamics and the pace of network change, we use the mean Hamming velocity in subsequent analysis.

Accuracy of the Perturbative Solution:

Figure 3 shows the approximation error (root mean square deviation) for the equilibrium and perturbative power score solutions, versus the actual final states. For both models (advice/potency and friendship-charisma), approximation errors start near zero in the approximately static case, increasing with the rate of network change; our conditions saturate for very large numbers of edge change events, since (per Figure 2) successive states approach independent draws from the equilibrium ERGM in this regime. Although errors increase with both approximations, the perturbative solution retains lower levels of error at much higher velocities. For instance, the error observed for the equilibrium approximation at a rate of 20 edge changes per time step is not attained under the perturbative approximation in the advice network until a rate of approximately 60 edge changes per step; the equivalent gap is 20/40 for equilibrium versus perturbative under the friendship network. Averaging over the full range of errors produced by both solutions, the perturbative solution obtains a given error level under velocities that are approximately 2.5 times higher for the advice network, and over 4.5 times higher for the friendship network. It also shows advantages in the high-velocity limit, with the perturbative solution offering a nearly 50% reduction in error at the extremes. Thus, while the perturbative solution is still an approximation, it does show consistent improvement on the equilibrium alternative.

4 Discussion

Before concluding, we briefly consider two issues brought into focus by the above results, specifically their implications for inference in the context of network autocorrelation models, and the potential value of fully continuous alternatives.

4.1 Inferential Implications

As noted in Section 1, the difference between the timescale separated equilibrium of the diffusion model and its behavior when timescale separation fails is particularly concerning in network autoregression applications, since the equation used to define the NAR (based on Eq. 3) can be a very poor approximation to the behavior of the observed system. In general, there is no solution that avoids explicit treatment of dynamics; the so-called “STARIMA” models (Pfeifer and Deutsch,, 1980) have been proposed for modeling network autocorrelation when all dynamics are observed, but often this is not the case. In the slow change regime, our result suggests that

y=\left[\left[I+\rho W\right]^{-1}+\rho WD\right]X\beta+\epsilon,

where $W$ is the observed weight matrix and $D$ is the associated matrix of weight changes, might be a better approximation than the usual (fixed network) model. This still requires either knowledge of local dynamics (i.e., $D$ ) or some estimate of thereof, but is less demanding than the fully dynamic solution. Regardless, we would expect for the conventional solution for $y$ to be off by an additive term approximately equal to $\rho WDX\beta$ , which notably involves all model parameters, the weight matrix, the local dynamics, and the attribute covariates. Inference for both $\rho$ and $\beta$ will thus be impacted by its omission.

4.2 Continuous Attribute Dynamics

To produce the dynamics for our simulation study, we exploited the continuous-time property of the EGP to smoothly vary the rate of change between sequential networks. The convenience of such continuous-time dynamics strongly suggests applying them to the diffusion model as well. To date, continuous-time diffusion of continuous attributes has not been widely studied in the social network community, and given the additional complexities involved with such models we have not considered them here. However, given the quantitative importance of competing timescales for the behavior of diffusion on dynamic networks, moving away from discrete time (which is both cumbersome and arguably unphysical) may have merit. Indeed, Niezink and Snijders, (2017) propose a model of exactly this type, albeit with latent network dynamics and stochastic diffusion (a modified Wiener process). The most natural deterministic parallel to the linear diffusion model in the continuous case is the matrix differential equation

\frac{d}{dt}y_{t}=Ay_{t}+z,

which has the stable fixed point

y_{\infty}=-A^{-1}z

under appropriate conditions on $A$ . While such models seem of obvious interest for social network applications, a more systematic consideration of the timing of the diffusion process (backed up by more systematic measurement thereof) seems important to effectively constrain them.

5 Conclusion

While venerable, the linear diffusion model remains an important tool for modeling processes on graphs. Given the that much of its appeal comes from its utility in equilibrium modeling, it is useful to ask how far that scenario can be “stretched” in the presence of network dynamics. As shown here, perturbative corrections for out-of-equilibrium behavior are in some cases feasible, leading to a solution that is still independent of long-run history (though dependent on temporally local dynamics). It is interesting to consider how many other such cases may also be subject to analytical treatment; Friedkin and Johnsen, (2003), for instance, consider the case where joint dynamics lead to a stable fixed point for both attitudes and network structure, demonstrating that other solvable regimes exist. Such developments may further extend the life of this old mathematical workhorse.

References

Anselin, (1988) Anselin, L. (1988). Spatial Econometrics: Methods and Models. Kluwer, Norwell, MA.
Bonacich, (1987) Bonacich, P. (1987). Power and centrality: A family of measures. American Journal of Sociology, 92:1170–1182.
Brin and Page, (1998) Brin, S. and Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1-7):107–117.
Butts, (2003) Butts, C. T. (2003). Network inference, error, and informant (in)accuracy: a Bayesian approach. Social Networks, 25(2):103–140.
(5) Butts, C. T. (2008a). network: a package for managing relational data in R. Journal of Statistical Software, 24(2).
(6) Butts, C. T. (2008b). Social network analysis with sna. Journal of Statistical Software, 24(6).
(7) Butts, C. T. (2008c). Social networks: A methodological introduction. Asian Journal of Social Psychology, 11(1):13–41.
Butts, (2017) Butts, C. T. (2017). Baseline mixture models for social networks. arXiv:1710.02773.
(9) Butts, C. T. (2023a). Continuous time graph processes with known ERGM equilibria: Contextual review, extensions, and synthesis. Journal of Mathematical Sociology, forthcoming.
(10) Butts, C. T. (2023b). ergmgp: Tools for modeling ERGM generating processes. Electronic Data File.
Cliff and Ord, (1973) Cliff, A. D. and Ord, J. K. (1973). Spatial Autocorrelation. Pion, London.
Doreian, (1989) Doreian, P. (1989). Two regimes of network autocorrelation. In Kochen, M., editor, The Small World, pages 280–295. Ablex, Norwood.
Freidkin, (1998) Freidkin, N. (1998). A Structural Theory of Social Influence. Cambridge University Press, Cambridge.
Friedkin and Johnsen, (1990) Friedkin, N. and Johnsen, E. C. (1990). Social influence and opinions. Journal of Mathematical Sociology, 15:193–206.
Friedkin and Johnsen, (2003) Friedkin, N. and Johnsen, E. C. (2003). Attitude change, affect control, and expectation stats in the formation of influence networks. Advances in Group Processes, 20:1–29.
Friedkin and Johnsen, (2014) Friedkin, N. E. and Johnsen, E. C. (2014). Two steps to obfuscation. Social Networks, 39:12–13.
Handcock and Gile, (2010) Handcock, M. S. and Gile, K. J. (2010). Modeling networks with sampled data. Annals of Applied Statistics, 4(1):5–25.
Handcock et al., (2008) Handcock, M. S., Hunter, D. R., Butts, C. T., Goodreau, S. M., and Morris, M. (2008). statnet: Software tools for the representation, visualization, analysis and simulation of network data. Journal of Statistical Software, 24(1):1–11.
Hunter et al., (2008) Hunter, D. R., Handcock, M. S., Butts, C. T., Goodreau, S. M., and Morris, M. (2008). ergm: A package to fit, simulate and diagnose exponential-family models for networks. Journal of Statistical Software, 24(3).
Katz, (1953) Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43.
Koschützki et al., (2005) Koschützki, D., Lehmann, K. A., Peeters, L., Richter, S., Tenfelde-Podehl, D., and Zlotowski, O. (2005). Centrality indices. In Brandes, U. and Erlebach, T., editors, Network Analysis: Methodological Foundations, chapter 3, pages 16–61. Springer-Verlag, Berlin.
Koskinen and Snijders, (2007) Koskinen, J. H. and Snijders, T. A. (2007). Bayesian inference for dynamic social network data. Journal of Statistical Planning and Inference, 137(12):3930 – 3938. 5th St. Petersburg Workshop on Simulation, Part {II}.
Krackhardt, (1990) Krackhardt, D. (1990). Assessing the political landscape: Structure, cognition, and power in organizations. Administrative Science Quarterly, 35:242–260.
Krackhardt, (1992) Krackhardt, D. (1992). The strength of strong ties: the importance of philos in organizations. In Nohria, N. and Eccles, R., editors, Networks and Organizations: Structures, Form, and Action, pages 216–239. Harvard Business Press, Boston, MA.
Krackhardt and Hanson, (1993) Krackhardt, D. and Hanson, J. R. (1993). Informal networks: The company behind the chart. Harvard Business Review, 71:104–111.
Krivitsky et al., (2023) Krivitsky, P. N., Hunter, D. R., Morris, M., and Klumb, C. (2023). ergm 4: New features for analyzing exponential-family random graph models. Journal of Statistical Software, 105(6):1–44.
Lee and Butts, (2018) Lee, F. and Butts, C. T. (2018). Mutual assent or unilateral nomination? a performance comparison of intersection and union rules for integrating self-reports of social relationships.
Leenders, (2002) Leenders, T. T. A. J. (2002). Modeling social influence through network autocorrelation: Constructing the weight matrix. Social Networks, 24(1):21–47.
Niezink and Snijders, (2017) Niezink, N. M. D. and Snijders, T. A. B. (2017). Co-evolution of social networks and continuous actor attributes. The Annals of Applied Statistics, 11:1948–1973.
Pfeifer and Deutsch, (1980) Pfeifer, P. E. and Deutsch, S. J. (1980). A STARIMA model-building procedure with application to description and regional forecasting. Transactions of the Institute of British Geographers, 5(3):330–349.
R Core Team, (2023) R Core Team (2023). R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria.
Salancik, (1986) Salancik, G. R. (1986). An index of subgroup influence in dependency networks. Administrative Science Quarterly, 31(2):194–211.
Snijders et al., (2007) Snijders, T. A. B., Steglich, C. E. G., and Schweinberger, M. (2007). Modeling the co-evolution of networks and behavior. In Van Montfort, K., Oud, H., and Satorra, A., editors, Longitudinal Models in the Behavioral and Related Sciences, pages 41–71. Cambridge University Press, New York.
Steglich et al., (2010) Steglich, C., Snijders, T. A. B., and Pearson, M. (2010). Dynamic networks and behavior: Separating selection from influence. Sociological Methodology, 40(1):329–393.

A Perturbative Solution to the Linear Influence/Network Autocorrelation Model Under Network Dynamics††thanks: The author thanks Weihua An and David Jacho-Chavez for helpful discussions on bias in the network autocorrelation model.