Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
101,083 characters · 23 sections · 82 citation commands
Normal Approximation in Large Network Models
\onehalfspacing
\addcontentsline{toc}{part}{Main Paper}
Network models have attracted considerable attention as tractable representations of non-market interactions, such as peer effects and social learning, and of economic relationships, such as financial and trade networks. The economic perspective on networks emphasizes the importance of strategic interactions or externalities jackson2016networks. One strand of the literature studies social interactions, how an individual's behavior interacts with those of her social contacts. A second strand studies network formation, why an individual chooses particular social contacts, and how their choices affect those of others. In both cases, externalities generate a wedge between choices that are optimal from the individual's perspective and those that are efficient for society. This has important consequences for policymaking, for instance motivating policies of “associational redistribution” that intervene on the network structure durlauf1996associational. However, when preferences are misaligned with the policy objective, the endogenous response to a policy intervention may diverge from the intended outcome carrell_natural_2013. It is therefore of interest to develop econometric methodologies for measuring network externalities.
The focus of our paper is models of network formation, which have diverse applications ranging from risk sharing in the rural Philippines fg2007 to research partnerships in the biotechnology industry pwko2005. They can be used to distinguish between different theoretical mechanisms for link formation, including preferential attachment barabasi1999emergence, strategic transitivity mele2022structural,ridder2022two, and homophily mpslc2001. They enable policymakers to forecast the effects of counterfactual interventions on a social network mele2017segregation and to account for dependence between the network and unobservables of a social interactions model badev2021nash.
We augment a class of latent space hrh2002 and geometric graph py2003 models with strategic interactions. In such models, nodes are positioned in a possibly latent social or economic space such that the rate of link formation decays with distance in space. However, due to strategic interactions, link formation depends not only on the attributes of the node pair involved in the link but also on links between other pairs. This induces a non-standard form of cross-sectional dependence between network units. The challenge for large-sample theory lies in establishing conditions under which the “amount of independent information” increases with the network size.
We establish a CLT for a large class of network moments computed from a single large network. The moments are averages of node-level statistics $n^{-1} \sum_{i=1}^n \psi_i$, where $\psi_i$ is some function of the network and node types. Examples include the {\em degree} of node $i$, which is the number of links involving $i$; the average clustering coefficient; and subnetwork counts which have been utilized for inference in econometric models of network formation sheng2014. We discuss practical inference procedures justified by the result.
We emphasize two technical contributions. The first is an abstract CLT that holds under high-level conditions, which is an extension of limit theorems from the literature on geometric graphs penrose2007gaussian. The key condition is a modification of “stabilization” assumptions from that literature that provide a useful formulation of weak dependence for our purposes. Stabilization essentially requires $\psi_i$ to only be a function of a random subset of nodes whose size has a distribution with exponential tails. This implies that the size is asymptotically bounded, so node $i$'s statistic only depends on a small fraction of alters. In this sense, $\{\psi_i\}_{i=1}^n$ is weakly dependent.
In our applications, this random subset involves a union of network components, which are disconnected subnetworks that are challenging combinatorial objects to analyze (a formal definition is provided at the end of this section). Our primary contribution is to develop a methodology for deriving the tail bounds required for stabilization. We employ techniques from branching process theory commonly used to bound component sizes in the literature on random graphs. Using the methodology, we derive interpretable primitive sufficient conditions for stabilization in models of strategic network formation.
One of the main conditions restricts the strength of strategic interactions. These induce cross-sectional dependence since the realization of a link can depend on the existence of “neighboring” links, which in turn can depend on other links, and so on. The longer the lengths of these chains of dependent links, the stronger the degree of cross-sectional dependence. We adopt a well-known technique in random graph theory to bound the lengths of these chains by branching processes whose sizes can more tractably be proven to have exponential tails, provided the processes are “subcritical” or non-explosive in growth. We argue that conditions for subcriticality in our context are analogous to weak dependence conditions imposed on spatial and temporal autoregressive models that bound the magnitude of the autoregressive parameter below one.
The other main condition is a restriction on the equilibrium selection mechanism. Even if strategic interactions are sufficiently weak, strong cross-sectional dependence may exist if nodes can globally “coordinate” on the equilibrium network through a common signal such as the type of a particular node. We instead require equilibrium selection to be sufficiently “decentralized,” which holds for instance under myopic best-response dynamics. This is the single-network analog of the usual requirement under many-network asymptotics that equilibrium selection is independent across networks.
A growing literature studies frequentist inference in network formation models when the econometrician observes a single network. leung2016 and menzel2016 develop laws of large numbers for models of strategic network formation. The former paper modifies a weaker stabilization condition due to py2003 and uses branching processes to derive primitive sufficient conditions. Our paper tackles the more difficult problem of obtaining a normal approximation, which naturally requires a stronger stabilization condition, and discusses practical inference procedures newly justified by the result. We prove the CLT by adapting results from the literature on geometric graphs penrose2005normal,penrose2007gaussian; a more detailed discussion of our contributions relative to this literature can be found in (ref). kuersteiner2019limit takes a different approach, using a novel conditional mixingale type assumption defined in terms of a random metric of distance.
leung2015a and ridder2022two study strategic network formation under incomplete information. In this setting, links are independent conditional on observables, whereas the models we study can be microfounded as games of complete information. These allow for unobserved heterogeneity, which generates dependence between potential links even conditional on observables.
charbonneau2017multiple, dzemski2019, graham2017, and jochmans2018semiparametric consider dyadic link formation models without strategic interactions but allow for node-level fixed effects. A large literature in statistics studies models without strategic interactions, for example stochastic block models bickel2011method and latent-space models hrh2002. These are useful for their parsimony and tasks such as community detection. cj2015 and bm2015 study statistical models allowing for interdependence between links.
kojevnikov2021limit prove a CLT for node-level data conditional on the network. This does not apply to network formation models since the network is the outcome. We prove an unconditional CLT that may be applied to network formation as well as network processes leung2019inference.
The next section presents a model of strategic network formation and defines network moments. In (ref), we state high-level conditions for a CLT and outline its proof. Readers interested in the low-level CLT for strategic network formation may skip (ref) for (ref), which presents primitive sufficient conditions. We also outline a general methodology for verifying the high-level condition that can be applied to other network models. In (ref), we discuss practical inference procedures. We present results from a simulation study in (ref), and (ref) concludes. Proofs can be found in the supplemental appendix.
We introduce standard notation and terminology for networks. We represent a network on a set of $n$ nodes by an $n\times n$ adjacency matrix, where the $ij$th entry $A_{ij}$, termed the {\em potential link}, is an indicator for whether nodes $i,j$ are connected. We assume $A_{ii} = 0$ for all nodes $i$, meaning that there are no self-links, and we focus on undirected networks, so $A_{ij} = A_{ji}$. For two networks $\bm{A},\bm{A}'$, we say that $\bm{A}$ is a {\em subnetwork} of $\bm{A}'$ if every link in $\bm{A}$ is a link in $\bm{A}'$. A {\em path} in a network from node $i$ to $j$ is a sequence of distinct nodes starting with $i$ and ending with $j$ such that for each consecutive node pair $k,k'$ in this sequence, $A_{kk'}=1$. Its {\em length} is the number of links it involves. The {\em path distance} between two nodes $i\neq j$ in $\bm{A}$ is the length of the shortest path that connects them if a path exists and $\infty$ otherwise. The path distance between a node and itself is defined as zero. The {\em $K$-neighborhood} of a node $i$ in $\bm{A}$, denoted by $\mathcal{N}_{\bm{A}}(i,K)$, is the set of nodes of path distance at most $K$ from $i$. Finally the {\em component} of a node $i$ in a network $\bm{A}$ is the set of nodes at finite path distance from $i$.
Let $\mathcal{N}_n = \{1,\dots,n\}$ be a set of nodes, and endow each $i\in\mathcal{N}_n$ with an i.i.d.\ vector-valued {\em type} $(X_i,Z_i) \in \mathbb{R}^d \times \mathbb{R}^{d_z}$. We distinguish $X_i$ as the {\em position} of node $i$, a continuously distributed vector of {\em homophilous} (defined below) attributes with density $f$ that has bounded support. Endow each node pair $(i,j)$ with an i.i.d.\ $\mathbb{R}$-valued random utility shock $\zeta_{ij} = \zeta_{ji}$ independent of types.
The network $\bm{A}$ satisfies, for all $i\neq j$,
where the {\em joint-surplus function} $V(\cdot)$ is an $\mathbb{R}$-valued function, $\lVert\cdot\rVert$ a norm on $\mathbb{R}^d$, and $S_{ij}$ a vector of statistics that captures strategic interactions through its dependence on $\bm{A}$. As discussed below, the sparsity of $\bm{A}$ will in part be determined by the positive constant $r_n$. Model (ref) corresponds to the well-known {\em pairwise-stability} solution concept under transferable utility jackson2010.
As explained in the next subsection, the assumptions we impose for a CLT in many cases require $S_{ij}$ to be uniformly bounded over $i,j\in\mathcal{N}_n$ and $n\in\mathbb{N}$. Existing work on large-network asymptotics for network formation shares this limitation bm2015,menzel2016,ridder2022two. Statistics such as (ref) may be modified to satisfy uniform boundedness by truncation, for example $\min\{\sum_{k=1}^n A_{ik}, \Delta\}$ for some user-specified constant $\Delta$.
The next subsection states a restriction on $V(\cdot)$ that generates homophily and sparsity. In (ref), we formalize how $S_{ij}$ may depend on $\bm{A}$ and introduce the equilibrium selection mechanism. Finally, in (ref), we define the class of network moments for which we provide a CLT.
A common feature of social networks is {\em homophily}, the tendency for those with similar characteristics to associate. We require homophily in position, specifically that the joint-surplus function $V(\cdot)$ is decreasing in the first component, so nodes dissimilar in position are less likely to form links. Positions may represent latent node locations in an abstract “social space,” as in latent-space models hrh2002, or attributes such as income and geographic location.
Another common feature is {\em sparsity}, meaning that the number of connections formed by the typical node is of significantly smaller order than $n$ barabasi2015. This is often accomplished by scaling the sequence of models such that the expected degree $n^{-1} \sum_{i=1}^n \sum_{j=1}^n {\bf E}[A_{ij}]$ is asymptotically bounded.
Our first assumption restricts the joint-surplus function $V(\cdot)$ and the distribution of $\zeta_{ij}$, so that the network generated by model (ref) exhibits homophily in positions and sparsity. Let $\bar{\Phi}_\zeta(z) = {\bf P}(\zeta_{ij} \geq z)$. Define $\bar{V}(r_n^{-1}\lVertX_i-X_j\rVert, \zeta_{ij}) = \sup_{s,z,z'} V(r_n^{-1}\lVertX_i-X_j\rVert, s, z, z', \zeta_{ij})$, where the supremum is taken over $(s,z,z')$ in the support of $(S_{ij},Z_i,Z_j)$ (which will be identical across $i,j$ under assumptions below). Finally, recall that $d$ is the dimension of $X_1$.
Homophily is a consequence of the first sentence because ${\bf P}(A_{ij}=1 \mid r_n^{-1}\lVertX_i-X_j\rVert=\delta) \leq \bar{\Phi}_\zeta(\bar{V}^{-1}(\delta, 0))$, which is required to decrease exponentially with $\delta$. If $V(\cdot)$ is not too nonlinear in its first component and the distribution of $\zeta_{ij}$ has exponential tails, then this assumption is satisfied, as shown in the next example.
Lastly we discuss the role of (ref) for sparsity. As $n$ increases, there are more opportunities to form links, which increases expected degree, corresponding to a denser network. By sending $r_n$ to zero with $n$, we increase the “cost” of link formation due to homophily, thereby decreasing the expected degree. Our choice of $r_n$ balances these two forces to achieve a sparse network in which the expected degree is asymptotically bounded. To see this, notice that expected degree is
by a change of variables $x' \mapsto x+r_n(x'-x)$. By (ref), if $f$ is continuous, this converges to
which is finite because the integrand decays exponentially with $\lVertx-x'\rVert$ by (ref).
We next define the statistics $S_{ij}$ that capture strategic interactions. For any $H\subseteq\mathcal{N}_n$, let $r_n^{-1}\bm{T}_H = ((r_n^{-1}X_i,Z_i))_{i \in H}$ be the array of (scaled) types for nodes in $H$ and $\bm{\zeta}_H = (\zeta_{ij})_{i,j \in H}$ (with $\zeta_{ii} \equiv 0$ for all $i$) be the corresponding array of random-utility shocks. In the case where $H = \mathcal{N}_n$, we abbreviate $r_n^{-1}\bm{T}_n \equiv r_n^{-1}\bm{T}_{\mathcal{N}_n}$ and $\bm{\zeta}_n \equiv \bm{\zeta}_{\mathcal{N}_n}$. Let $\bm{A}_H = (A_{ij})_{i,j\in H}$ denote the subnetwork of $\bm{A}$ on $H$. We define
where $\{S_n\}_{n\in\mathbb{N}}$ is a sequence of permutation-invariant functions.\footnote{For any bijection $\pi\colon \mathcal{N}_n \rightarrow \mathcal{N}_n$, we abuse notation by defining $\pi(r_n^{-1}\bm{T}_n) = ( (r_n^{-1}X_{\pi(i)}, Z_{\pi(i)}) )_{i\in \mathcal{N}_n}$ and $\pi(\bm{A}) = (A_{\pi(i)\pi(j)})_{i,j}$. We say $S_n(\cdot)$ is {\em permutation-invariant} if $S_n(i, j, r_n^{-1}\bm{T}_n, \bm{A}) = S_n(\pi(i), \pi(j), \pi(r_n^{-1}\bm{T}_n), \pi(\bm{A}))$. This means that the function does not directly depend on node labels which have no economic content in our model. }
We next impose the common restriction that $S_{ij}$ only depends on its arguments through the 1-neighborhoods of $i$ and $j$, recalling the definition from (ref).
That is, $S_{ij}$ is only a function of nodes linked to either $i$ or $j$. Most statistics used in the literature satisfy this assumption, including those in Examples (ref) and (ref), which appear to be the most common choices christakis2020empirical,leung2016,mele2017,sheng2014. Dependence of $S_n(\cdot)$ on types also allows for covariate-weighted versions of these examples, such as the weighted degree $\sum_{k=1}^n A_{ik} Z_k$.
The model thus far is incomplete since multiple networks $\bm{A}$ may satisfy (ref) due to strategic interactions. Let $\mathcal{E}(r_n^{-1}\bm{T}_n, \bm{\zeta}_n)$ denote the set of such networks, which corresponds to the set of pairwise stable equilibria. To complete the model, we introduce a {\em selection mechanism}, which is the reduced-form mapping from primitives to the observed network. It is a representation of the latent social process by which nodes coordinate on an equilibrium.
Our objective is to prove a CLT for network moments that are averages of {\em node statistics}
where $\{\psi_n\}_{n\in\mathbb{N}}$ is a sequence of $\mathbb{R}^{d_\psi}$-valued, permutation-invariant functions (see (ref)). We often abbreviate $\psi_i(\mathcal{N}_n) \equiv \psi_n(i,r_n^{-1}\bm{T}_n, \bm{\zeta}_n, \bm{A})$.
More generally, we consider the following class of node statistics that includes the previous examples. Recall that $\mathcal{N}_{\bm{A}}(i,K)$ is $i$'s $K$-neighborhood, defined in (ref).
This states that the node statistic only depends on the types, random-utility shocks, and subnetwork of nodes on $i$'s $K$-neighborhood. The average degree and triangle count satisfy this for $K=1$. A more complex example is the number of nodes at most path distance $D$ from node $i$, which satisfies this assumption for $K=D$.
This section provides high-level conditions for a CLT. Readers interested in the application to strategic network formation may wish to skip to (ref) where we state primitive sufficient conditions.
Recall from (ref) that for any $H \subseteq \mathcal{N}_n$, $\lambda_{\lvertH\rvert}(r_n^{-1}\bm{T}_H, \bm{\zeta}_H)$ is the equilibrium network under the counterfactual model in which the set of nodes is $H$ rather than $\mathcal{N}_n$. Abusing notation, for $i \in H$, we define $i$'s {\em counterfactual node statistic}
For $H=\mathcal{N}_n$, this coincides with the original definition. For $H\subset \mathcal{N}_n$, the counterfactual interpretation is due entirely to the last argument. Contrast (ref) with
For example, if $\psi_i(\mathcal{N}_n)$ is the degree of node $i$ on the full network, then (ref) is $i$'s degree in the observed subnetwork restricted to $H$, which can be directly computed from observation of $\bm{A}$. Generally, this does not equal (ref) because the networks $\bm{A}_H$ and $\lambda_{\lvertH\rvert}(r_n^{-1}\bm{T}_H, \bm{\zeta}_H)$ do not coincide due to strategic interactions, which induce nodes in $H$ to form different links when nodes $\mathcal{N}_n\backslash H$ are absent from the model.
Recall that $d$ is the dimension of $X_1$. For any $B \subseteq \mathbb{R}^d$, let $\mathcal{N}_n(B) = \{i\in\mathcal{N}_n\colon r_n^{-1}X_i \in B\}$, the set of nodes with scaled positions lying in the set $B$. For $x \in \mathbb{R}^d$ and $R \geq 0$, let $B(x,R) = \{y \in \mathbb{R}^d\colon \lVertx-y\rVert \leq R\}$.
This is the smallest radius $R$ such that $i$'s node statistic has the same value under all counterfactual models that drop nodes positioned outside of $i$'s neighborhood $B(r^{-1}X_i, R)$.
The main idea is as follows. If this radius were “small,” then $\psi_i(\mathcal{N}_n)$ would primarily depend on a small fraction of nodes, specifically those positioned near $i$, in which case node statistics should be weakly dependent. To establish a law of large numbers (LLN), leung2016 requires the radius to be $O_p(1)$, analogous to a condition due to py2003. However, a CLT seems to require stronger conditions on the distribution of the radius, in particular the thickness of its tails penrose2007gaussian.
We first define some notation and the sequence along which we take limits. Let $\{(X_i,Z_i)\}_{i\in\mathbb{N}}$ and $\{\zeta_{ij}\colon i\in\mathcal{N}_n, j>i\}$ both be i.i.d.\ and independent, and assume the density $f$ of $X_1$ is bounded. We consider a sequence indexed by $n\in\mathbb{N}$ such that the $n$th element of the sequence is given by the tuple
The first three components are structural primitives that determine $\bm{A}$, while the last is the node statistic function.
For technical reasons, we need to consider sequences of models indexed by $n$ in which the network size is not $n$ but rather of the same asymptotic order as $n$. Let $\{N_n\}_{n\in\mathbb{N}}$ be a sequence of random variables independent of all model primitives such that
A de-Poissonization argument discussed below requires us to consider two different network sizes: a random size $N_n+k$, where $k$ is a constant, and a non-random size $m+k$, where $m=m_n$ with $m_n/n \rightarrow c \in (0,\infty)$. Our original setup with $n$ nodes corresponds to $m=n$ and $k=0$, and no intuition is lost to the reader who only considers this case. The need to consider models with different network sizes is purely for technical reasons clarified in (ref).
Define $\mathcal{T} = \text{supp}(X_1,Z_1)$, $\mathcal{T}^k = \bigtimes_{i=1}^k \mathcal{T}$, and $\bm{T}_k = ((X_i,Z_i))_{i=1}^k$. Our first assumption is the key high-level weak dependence condition that controls the tail behavior of the distribution of the radius of stabilization, or more formally the conditional probability ${\bf P}(\bm{R}_1(m+k,r_n) > w \mid \bm{T}_k = \bm{t}_k)$. Since probabilities conditional on continuous random variables are not uniquely defined, we require some additional notation to phrase the assumption in terms of a {\em version} of the conditional probability. Let $m,k \in \mathbb{N}$ and $\bm{t}_k \in \mathcal{T}^k$. Construct $r_n^{-1}\bm{T}_{m+k}^\star(\bm{t}_k)$ from $r_n^{-1}\bm{T}_{m+k}$ by replacing the types of the first $k$ nodes $\bm{T}_k$ with fixed values $\bm{t}_k$. Define $\bm{R}_1^\star(m+k,r_n;\bm{t}_k) \equiv \bm{R}(1, r_n^{-1}\bm{T}_{m+k}^\star(\bm{t}_k), \bm{\zeta}_{m+k}, \lambda_{m+k})$. Then ${\bf P}(\bm{R}_1^\star(m+k,r_n;\bm{t}_k) > w)$ is a version of the conditional probability ${\bf P}(\bm{R}_1(m+k,r_n) > w \mid \bm{T}_k = \bm{t}_k)$.
For $\eta=1$, this says that the distribution of the radius of stabilization has an exponential tail under models with $N_n+k$ and $m+k$ nodes, uniformly over the types of the first $k$ nodes.\footnote{The first $k$ is an arbitrary choice of $k$ nodes. Note that nodes are exchangeable in our model since types and random-utility shocks are i.i.d.\ and the equilibrium selection mechanism is permutation-equivariant.} Technically the assumption allows for slower than exponential decay with $\eta < 1$, but it is otherwise analogous to conditions used by penrose2005normal and penrose2007gaussian. Our method of proof for the result below is based on theirs but with important differences in setup discussed in (ref).
Contrast (ref) with the more familiar concept of $m$-dependence, which states that an observation is only correlated with nodes in some non-random neighborhood of known radius $m$. Stabilization generalizes this to allow neighborhoods to be node-specific, random, and complex functions of the primitives. In general, bounding the size of this set is far from trivial, and one of our main contributions is to demonstrate that branching processes can be used for this purpose to derive primitive sufficient conditions, as discussed in (ref).
The next assumption imposes a moment condition. Similar to the previous assumption, we require additional notation to phrase the condition in terms of a version of a conditional expectation. Let $k\in\mathbb{N}$, $\bm{t}_k \in \mathcal{T}^k$, and $H \subseteq \mathbb{N}$ be a finite set containing $\{1, \ldots, k\}$. Construct $r_n^{-1}\bm{T}_H^\star(\bm{t}_k)$ from $r_n^{-1}\bm{T}_H$ by replacing the types of the first $k$ nodes $\bm{T}_k$ with fixed values $\bm{t}_k$. Define $\psi_1^\star(H; \bm{t}_{k}) \equiv \psi_{\lvertH\rvert}(1, r_n^{-1}\bm{T}_H^\star(\bm{t}_k), \bm{\zeta}_H, \lambda_{\lvertH\rvert})$, so that ${\bf E}[\psi_1^\star(H; \bm{t}_{k})]$ is a version of the conditional expectation ${\bf E}[\psi_1(H) \mid \bm{T}_k = \bm{t}_k]$. Finally, let $\lVertx\rVert_\infty$ denote the entry-wise maximum of a vector or matrix $x$.
Part (a) requires node statistics to have bounded $p>2$ moments, uniformly over the types of $k$ nodes. We provide primitive conditions in (ref) for the case of subnetwork counts ((ref)).
Part (b) says that node statistics and the selection mechanism are invariant to additive shifts in scaled positions $\{r^{-1}X_i\}_{i=1}^n$, which holds if these only enter through scaled distances $r^{-1}\lVertX_i-X_j\rVert$. Because $X_i$ and $Z_i$ may be arbitrarily dependent, this still allows $X_i$ (unscaled) to enter the model as a subvector of $Z_i$. In Examples (ref) and (ref), the latent index only depends on types through scaled distances or $Z_i$, so requiring the selection mechanism and node statistics to satisfy the same property does not apparently rule out any economically interesting applications.\footnote{For example, (ref)(b) disallows network moments such as $n^{-1} \sum_{i=1}^n \sum_{j=1}^n r^{-1} X_j A_{ij}$, but since $X_i$ and $Z_i$ may be arbitrarily correlated, it allows for $n^{-1} \sum_{i=1}^n \sum_{j=1}^n X_j A_{ij}$.}
Let $\bm{\Sigma}_n = n^{-1} \text{Var}(\sum_{i=1}^n \psi_i(\mathcal{N}_n))$, $\lambda_\text{min}(\bm{\Sigma}_n)$ be its smallest eigenvalue, and $\bm{I}$ denote the $d_\psi$-dimensional identity matrix.
The proof does not rely on the setup or assumptions in (ref), other than the distributional assumptions at the top of (ref) and the requirement that $\lambda_n(\cdot)$ is a deterministic, permutation-equivariant function of the structural primitives. The other assumptions will be used in the next section to verify (ref) for strategic network formation.\footnote{(ref) can be applied to other network models. For instance, in leung2019inference, $\lambda_n(\cdot)$ is the reduced-form mapping that takes as input the structural primitives and outputs both the network and the outcome of a second-stage social interactions model given the network.}
{\bf Step 1.} We first establish a CLT for the “Poissonized” model in which the number of nodes is $N_n$ defined in (ref), so-called because $\{X_i\}_{i=1}^{N_n}$ has the same distribution as a Poisson point process with intensity function $nf(\cdot)$ penrose2003. Specifically, we show
where $\tilde{\bm{\Sigma}}_n = n^{-1} \text{Var}(\sum_{i=1}^{N_n} \psi_i(\mathcal{N}_{N_n}))$. This is simpler to prove directly because, unlike $\{X_i\}_{i=1}^n$, the Poisson process $\{X_i\}_{i=1}^{N_n}$ possesses a well-known spatial independence property: for any disjoint subsets $S_1,S_2 \subseteq \mathbb{R}^d$, $\lvert\{X_i\}_{i=1}^{N_n} \cap S_1\rvert \perp\!\!\!\perp \lvert\{X_i\}_{i=1}^{N_n} \cap S_2\rvert$.
We prove (ref) by adapting a theorem due to penrose2005normal (see our (ref)). We proceed by first partitioning the support of $X_1$ into cubes $Q_1, \dots, Q_{V_n}$ of slowly growing volume and representing the moment $n^{-1} \sum_{i=1}^{N_n} \psi_i(\mathcal{N}_{N_n})$ as a double sum over cubes and nodes within cubes $n^{-1} \sum_{i=1}^{V_n} \sum_{j=1}^{N_i} \psi_{ij}(\mathcal{N}_{N_n})$, where $N_i$ is the number of nodes positioned in $Q_i$ and $ij$ indexes the $j$th node in $Q_i$. Spatial independence of the Poisson process implies independence of node positions across cubes. However, node statistics are complex functionals of the process and hence are not generally independent across cubes.
Since stabilization implies that node statistics $\psi_{ij}(\mathcal{N}_n)$ are primarily determined by nodes relatively proximate to $ij$, and hence cubes relatively proximate to $Q_i$, it can be shown that the dependence structure of $\{\sum_{j=1}^{N_i} \psi_{ij}(\mathcal{N}_{N_n})\}_{i=1}^{V_n}$ is “approximately” characterized by a certain “dependency graph.” This is a network in which, roughly speaking, two observations are linked if and only if they are dependent. In our case, observations are cubes, which we connect if and only if they are relatively proximate. Careful construction of the cubes ensures a small approximation error for the dependency graph characterization, and applying a CLT for dependency graphs chen2004normal delivers the result. For precise details, see (ref).
{\bf Step 2.} Since $N_n/n \stackrel{p}\longrightarrow 1$, $\{X_i\}_{i=1}^n$ and $\{X_i\}_{i=1}^{N_n}$ should be “similar,” so given (ref), we expect a similar result for the original model. The second “de-Poissonization” step of the proof, which follows penrose2007gaussian, shows that this intuition is correct, provided we properly adjust $\tilde{\bm{\Sigma}}_n$ downward to obtain the correct variance $\bm{\Sigma}_n$ (see our (ref)). This is needed because $N_n$ contributes additional randomness to the asymptotic distribution.
More specifically, define the {\em add-one cost}
This is the aggregate counterfactual impact on the total $\sum_{i=1}^n \psi_i(\mathcal{N}_n)$ from adding a new node labeled $n+1$ to the model. The first term is the direct effect of adding $n+1$, which is its own node statistic. The second term is the indirect effect, which is the new node's impact on the statistics of all other nodes. A key step of the proof establishes that
This may be viewed as a first-order expansion in the number of nodes, comparing $N_n$ to $n$. The “derivative” is ${\bf E}[\Xi_{N_n}]$ since it captures the change in moments as a result of a unit increment in the number of nodes. By (ref), the left-hand side is asymptotically normal, and by the Poisson CLT, so is $n^{-1/2}(N_n-n){\bf E}[\Xi_{N_n}]$. Because $N_n$ is independent of all other primitives, we can then establish that the first term on the right-hand side is asymptotically normal by an argument using characteristic functions; for details see the end of (ref).
The proof is closely based on arguments in penrose2005normal and penrose2007gaussian, whose results pertain to geometric graphs without strategic interactions. The innovation in (ref) is primarily conceptual, namely, the recognition that an appropriate modification of stabilization allows us to adapt their results to econometric models. Our main technical innovation will be discussed in (ref), namely the use of branching processes to derive primitive conditions for stabilization in models with strategic interactions. leung2016 uses branching processes to establish an LLN, while we tackle the more difficult task of proving a CLT, which requires us to establish new tail bounds for the radius of stabilization ((ref)).
The setup and assumptions used in Penrose's work are not directly applicable to our setting, so we cannot simply verify their conditions. However, we show that their proofs can be translated to our setting, which differs in three main aspects. The first is the definition of the radius of stabilization. We reformulate the definition in terms of counterfactual models (ref) and require invariance of $i$'s node statistic to the removal of nodes outside of $\mathcal{N}_n(\mathcal{B}_i)$. Existing definitions demand invariance to the removal {\em and addition} of new nodes, but invariance to addition is typically violated in the models we study due to strategic interactions. Second, $X_i$ may be correlated with $Z_i$ in our setup, whereas the literature requires independence, but this turns out to have little effect on the proofs. Third, our model includes pair-specific shocks $\zeta_{ij}$, which pose little problem due to their high degree of independence. These are independent across pairs, in contrast to type pairs $((X_i,Z_i),(X_j,Z_j))$ which are correlated across pairs sharing a common node, for example $(i,j)$ and $(i,k)$.
Exponential stabilization ((ref)) provides a high-level formulation of weak dependence. This section derives primitive conditions for the network formation model in (ref), so throughout this section we work under its setup. We begin in (ref) by introducing key definitions used in (ref) to explain two sources of cross-sectional dependence induced by the model. These motivate the weak dependence conditions stated in (ref) and (ref). In (ref) we present the main result, that these conditions imply exponential stabilization. We outline the method of proof in (ref).
Recall the definition of the joint surplus from (ref), and let
This is an indicator for whether the potential link $A_{ij}$ is {\em non-robust}. If $\inf_s V(r_n^{-1}\lVertX_i-X_j\rVert,s,Z_i,Z_j,\zeta_{ij}) > 0$, then $A_{ij}=1$, and the link is {\em robust} in that the joint surplus is positive regardless of what other links are formed. This is because $\bm{A}$ enters $V(\cdot)$ only through $S_{ij}$. Likewise, if $\sup_s V(r_n^{-1}\lVertX_i-X_j\rVert,s,Z_i,Z_j,\zeta_{ij}) \leq 0$, then $A_{ij}=0$, and the link is {\em robustly absent} in that the joint surplus is negative regardless of what other links are formed. In either case, $D_{ij}=0$. If instead $D_{ij}=1$, then $A_{ij}$ may be 0 or 1, and the potential link is non-robust in that the sign of the joint surplus is responsive to links formed by others.
Let $\bm{D}$ be the network of non-robustness indicators with $ij$th entry $D_{ij}$. Let $C_i$ denote $i$'s component in $\bm{D}$, recalling from (ref) that a component is a connected subnetwork that is disconnected from the rest of the network. Let $\bm{\Pi}$ be the network of robust link indicators with $ij$th entry
Recall that $\mathcal{N}_{\bm{\Pi}}(i,1)$ denotes $i$'s 1-neighborhood in $\bm{\Pi}$, which includes $i$ itself. A crucial concept for what follows is a node's {\em strategic neighborhood}, given by
This adds to $C_i$ the set of all nodes that possess a robust link to some member of $C_i$.
The previous example illustrates how $D_{ij}$ is increasing in the strength of strategic interactions. Stronger interactions then imply that $C_i^+$ is a larger set for any given realization of the primitives. This suggests that, {\em when strategic neighborhoods are likely small in size, we expect weaker strategic interactions and hence weaker cross-sectional dependence.} We elaborate on this point in the next subsection.
Models of strategic network formation induce two forms of cross-sectional dependence, one due to link interdependencies directly induced by strategic interactions, and the other due to equilibrium selection. To illustrate, consider a model with $n=9$ nodes and realized structural primitives such that (ref) depicts the resulting robust and non-robust potential links. Consider the impact on the realized network $\bm{A}$ of a hypothetical intervention that perturbs the value of $\zeta_{56}$.
The perturbation changes the joint surplus $V_{56}$ to some new value $V_{56}^{(1)}$, both evaluated under $\bm{A}$. If the signs of these values differ, then $A_{56}$ is no longer pairwise stable, so suppose in response the pair updates their potential link $A_{56}$ to $A_{56}^{(1)} = \bm{1}\{V_{56}^{(1)} > 0\}$, resulting in the network $\bm{A}_1$. This update may affect the joint surplus of other potential links, for instance $V_{67}$ via $S_{67}$. However, because $A_{67}$ is a robust link, $V_{67}$ is always positive, whether evaluated under $\bm{A}$ or $\bm{A}_1$, so there is no subsequent update to $A_{67}$. On the other hand, $A_{45}$ is non-robust ($D_{45}=1$), so the update to $A_{56}$ may change the value of $V_{45}$ evaluated under $\bm{A}$ to a new value $V_{45}^{(2)}$ evaluated under $\bm{A}_1$ that has a different sign. Suppose in response the pair updates $A_{45}$ to $A_{45}^{(2)} = \bm{1}\{V_{45}^{(2)} > 0\}$, resulting in a new network $\bm{A}_2$. This in turn affects the joint surplus of any other node pair containing nodes 4 and 5. The only such pairs with non-robust potential links are $(3,4)$ and $(5,6)$ since $D_{34}=D_{56}=1$, so {\em only} those potential links may update in response to the update to $A_{45}$.
Suppose we iterate these best-response dynamics indefinitely. At no point do potential links other than those of pairs $(3,4)$, $(4,5)$, and $(5,6)$ update during the process. This is because they are the only pairs connected to nodes 5 or 6, the target of the initial perturbation, through a chain of non-robust potential links, or more formally a path in $\bm{D}$. These paths constitute the furthest extent that best-response chains extending from nodes 5 and 6 can travel. By definition, the component of $\bm{D}$ containing nodes 5 and 6 contains all such paths.
The previous example pertains to interventions that perturb non-robust potential links, specifically $A_{56}$. Interventions that perturb robust links, such as $A_{67}$, trigger best-response dynamics in all strategic neighborhoods containing the link, which would be the two right-most strategic neighborhoods in (ref).
These examples demonstrate that the sizes of components $C_i$ and strategic neighborhoods $C_i^+$ (since they contain the components) are indicative of the degree of cross-sectional dependence. The key idea is that {\em if strategic neighborhoods are relatively small, then best-response chains cannot extend too far from the initial perturbation, corresponding to weaker dependence.} To control the length of best-response chains, in (ref), we state a “subcriticality” condition that ensures that component sizes are asymptotically bounded. From the discussion following (ref), this should hold if strategic interactions are sufficiently weak.
To derive the condition, we employ a well-known technique used in random graph theory for bounding the size of a component, which is to construct a branching process (see (ref) for a formal definition) whose size stochastically dominates that of the component bollobas2012simple. The basic idea is to explore each $C_i$ via breadth-first search by starting at $i$, branching to its neighbors, neighbors of its neighbors, and so on. This is akin to growing a branching process, a model of population growth in which individuals in a given generation independently produce a random number of offspring, which corresponds to a node's neighborhood size. Subcriticality ensures that the average number of offspring is less than one, in which case the size of the process does not diverge and $\lvertC_i\rvert$ is asymptotically bounded.
While this is enough to establish an LLN leung2016, a CLT additionally requires the distribution of $\lvertC_i\rvert$ to have exponential tails. We utilize a tail bound for subcritical branching processes to obtain the desired result; see (ref) which is proven by leung2019compute using an argument due to turova_asymptotics_2012. This is a key ingredient for verifying (ref).
The second source of dependence is due to equilibrium selection. Let us shut down the first source of dependence by supposing the perturbation to $\zeta_{56}$ is small enough not to change the sign of $V_{56}$, so there is no change to the network at any point in the best-response dynamics outlined above. However, if equilibrium selection is governed by a mechanism different from best-response dynamics, the perturbation may still substantially affect the network structure.
Suppose $\lvert\mathcal{E}(r_n^{-1}\bm{T}_n, \bm{\zeta}_n)\rvert = 2$. Since the perturbation does not change $V_{56}$, the set of equilibria is identical before and after the perturbation. However, one can construct a selection mechanism $\lambda_n(\cdot)$ that outputs one equilibrium under the structural primitives before the perturbation but outputs the other after the perturbation. Hence, the perturbation can alter potential links involving nodes external to $C_5$ even though any best-response chain must be limited to this component. This illustrates how, {\em under unrestricted equilibrium selection, all nodes may coordinate on the same “signal” ($\zeta_{56}$), resulting in strongly dependent potential links whose realizations all depend on this random variable}.
In (ref), we state a condition that ensures coordination is “decentralized” in that strategic neighborhoods “separately select” their pairwise stable subnetworks. A consequence is that any perturbation to a node pair's types or random-utility shocks only affects the selection of the equilibrium subnetwork on strategic neighborhoods involving the pair. For example, in (ref), it will be the case that a perturbation to $\zeta_{56}$ only changes the equilibrium subnetwork on $\{2, \ldots, 7\}$ since no other neighborhood contains $\{5,6\}$. Combined with the subcriticality condition that ensures strategic neighborhood sizes are asymptotically bounded, this implies that the perturbation can only shift equilibrium selection within a bounded subset of nodes, ensuring weak cross-sectional dependence. This will allow us to construct a radius of stabilization that is asymptotically bounded.
We next state a condition that controls the sizes of strategic neighborhoods, and hence length of best-response chains described in (ref), by restricting the magnitude of strategic interactions. We measure strategic interaction strength by
This is the effect on link formation of changing $S_{ij}$ from its “lowest” to its “highest” possible value, conditional on types. In other words, it is the maximal change in linking probability induced by the strategic component of $V(\cdot)$.
Let $\Phi_z(\cdot \,|\, x)$ be the conditional distribution of $Z_i$ given $X_i=x$. Recall that $f$ is the density of $X_1$, $\mathcal{T} = \text{supp}(X_1,Z_1)$, and $d_z$ is the dimension of $Z_i$. For any $h\colon \mathbb{R}^d \times \mathbb{R}^{d_z} \rightarrow \mathbb{R}$, define the mixed norm
where $\Phi^*$ is a measure defined in the next assumption. Finally, for $\bar{f} = \sup_{x\in\mathbb{R}^d} f(x)$ and $\kappa$ in (ref), let
Part (a) is a regularity condition corresponding to Assumption 2 of leung2019compute that replaces $\Phi_z(\cdot \mid x')$ with a “dominating” measure $\Phi^*$. The substantive requirement is (b), which is a slightly stronger version of Assumption 6 of leung2016. Its formulation is as primitive as possible at this level of generality, but we may obtain further insight by specializing to a particular joint surplus function. The next example demonstrates how the condition restricts the magnitude of strategic interactions.
The example illustrates how $\lVerth^*\rVert_\mathbf{m} < 1$ {\em constitutes the network formation analog of well-known weak dependence conditions for linear spatial or temporal autoregressive models}, which require the magnitude of the autoregressive coefficient to be bounded below one. For instance, in the linear-in-means model of peer effects, it is assumed that the endogenous peer effect satisfies $\lvert\beta\rvert<1$ bramoulle2009identification. For nonlinear models such as ours, the analogous condition is necessarily more complicated to state. Equation (9) of de_jong_dynamic_2011 states the condition for dynamic binary choice time series models, which shares some visual similarities with our assumption.
The connection between (ref) and the discussion in (ref) regarding the size of $C_i$ is that $\eqref{L_r} = {\bf E}[D_{ij} \mid X_i, Z_i, X_j, Z_j]$, so by Jensen's inequality and the change of variables argument in (ref), $h^*(x,z) \geq {\bf E}[\sum_j D_{ij} \mid X_i=x, Z_i=z]$. The expectation of the right-hand side is the expected degree in $\bm{D}$, so by (ref), this is upper bounded by one in expectation. This implies that, as we explore $C_i$ by branching from $i$ to its neighbors in $\bm{D}$, neighbors of neighbors, and so on, each node has fewer than one neighbor on average. That is, a node at each step is typically replaced by fewer than one node in the next step, so the process is below the replacement rate, and $\lvertC_i\rvert$ should be asymptotically bounded.
The second weak dependence condition restricts the selection mechanism, ruling out coordination of the type described in (ref). It requires selection to be “decentralized” in that each strategic neighborhood $C^+$ selects its pairwise stable subnetwork based on the types and random-utility shocks of nodes in $C^+$ alone. In this sense, there is no coordination across disjoint strategic neighborhoods.
Before stating the assumption, we need to clarify why such a restriction is possible. Initially, it may appear incoherent because the pairwise stability of a subnetwork on $H \subseteq \mathcal{N}_n$ can depend on the state of the network outside of $H$. If nodes $\mathcal{N}_n\backslash H$ are removed from the model, we would expect nodes in $H$ to adjust their links in best response. This suggests that coordination across subsets of nodes is generally unavoidable.
However, if $H$ is specifically a strategic neighborhood, then under (ref), its subnetwork is in fact pairwise stable regardless of the state of the ambient network. Consider (ref) and a counterfactual intervention that removes all nodes from the network outside of $C_5^+ = \{2, \ldots, 7\}$. The intervention has no impact on the pairwise stability of $A_{23}$ and $A_{67}$ since these are robust links. It also has no impact on the pairwise stability of non-robust potential links between nodes in $C_5^+$, for example $A_{45}$ since neither nodes 4 nor 5 are linked to $\mathcal{N}_n\backslash C_5^+$ in $\bm{A}$ and strategic interactions are local by (ref). That is, the non-robust potential links in $C_5^+$ are separated from $\mathcal{N}_n\backslash C_5^+$ by a “buffer” of robust links, so the intervention does not trigger a chain of best-responses that affects $\bm{A}_{C_5^+}$. This illustrates the following result.
The left-hand side is the set of pairwise stable networks under the counterfactual model in which the set of nodes is $C^+$, rather than $\mathcal{N}_n$. The right-hand side takes the set of pairwise stable networks on $\mathcal{N}_n$ and restricts them to $C^+$. The proposition asserts the two sets are equivalent, which says that the pairwise stability of subnetworks on $C^+$ only depends on the structural primitives of nodes in $C^+$. We emphasize that this property is unique to strategic neighborhoods and is not true for arbitrary subsets of nodes. leung2019compute exploits (ref) to devise an algorithm that computes $\mathcal{E}(r_n^{-1}\bm{T}_n,\bm{\zeta}_n)$ in polynomial time under (ref). We utilize it to establish a CLT.
Recall that our objective is to impose the assumption that strategic neighborhoods “separately select” their own pairwise stable subnetworks. (ref) ensures that it is coherent to refer to the pairwise stability of a subnetwork on a strategic neighborhood in isolation from the rest of the network. However, a second concern is that strategic neighborhoods do not necessarily partition $\mathcal{N}_n$, so such an assumption may still appear incoherent. For instance, in (ref), the left and middle strategic neighborhoods share nodes 2 and 3 in common, so it is not clear how the two neighborhoods can separately select equilibria.
Recall that components of $\bm{D}$ do partition $\mathcal{N}_n$, while strategic neighborhoods are obtained by adding nodes that are robustly linked to components. Then {\em the link between any node pair that lies in multiple strategic neighborhoods must necessarily be robust and therefore have the same realization under any pairwise stable equilibrium.} That is, any pairwise stable subnetwork on the left strategic neighborhood in (ref) sets $A_{23}=1$, as does any pairwise stable subnetwork on the middle strategic neighborhood. Consequently, it is a logically coherent operation to select an equilibrium subnetwork for each strategic neighborhood and then take a “union” to obtain the overall network $\bm{A}$ leung2019compute.
We are now prepared to state the assumption. Let $\lambda_n(r_n^{-1}\bm{T}_n, \bm{\zeta}_n)\big|_H$ be the restriction of the range of $\lambda_n(\cdot)$ to subnetworks on $H$. For example, under (ref), $\lambda_n(r_n^{-1}\bm{T}_n, \bm{\zeta}_n) = \bm{A}$, so $\lambda_n(r_n^{-1}\bm{T}_n, \bm{\zeta}_n)\big|_H = \bm{A}_H$.
This corresponds to Assumption 7 of leung2016. It is important to understand the difference between the left- and right-hand sides of the equality. On the left, we have the model involving all nodes $\mathcal{N}_n$; the selection mechanism produces a network $\bm{A}$, and we take its subnetwork $\bm{A}_{C^+}$. On the right, we have the counterfactual model involving only nodes in $C^+$, and the selection mechanism $\lambda_{\lvertC^+\rvert}(\cdot)$ produces a network $\lambda_{\lvertC^+\rvert}(r^{-1}\bm{T}_{C^+}, \bm{\zeta}_{C^+})$. The assumption asserts that the two outputs are the same.
sheng2014 does not require this assumption because she considers a setting with many small independent networks, which means equilibrium selection is necessarily independent across network observations. (ref) is the single-network analog of this requirement, requiring selection to operate separately across latent strategic neighborhoods.
The assumption rules out selection mechanisms in which all nodes coordinate through a common signal, such as a single node's type. Coordination is only allowed to occur within strategic neighborhoods. In the special case where there exists a unique equilibrium on $\mathcal{N}_n$, for instance if there are no strategic interactions, the assumption holds trivially. More generally, the condition is satisfied by variants of myopic best-response dynamics, which are widely used in the theoretical and econometric literature on dynamic network formation jackson2010,mele2017.
The last assumption we require is a regularity condition.
The case $p_r(X_1,Z_1;X_2,Z_2)=0$ corresponds to a model without strategic interactions, which is only mentioned for completeness. In the more interesting case, the assumption essentially requires that strategic interactions are sufficiently nontrivial for all nodes in that $p_{r_n}(X_1,Z_1;X_2,Z_2)$ is at least order $n^{-1}$. This is a mild requirement that is typically satisfied because the two probabilities in (ref) are upper and lower bounds on the probability of link formation, and the upper bound is order $n^{-1}$ under sparsity by (ref).
From Theorems (ref) and (ref) we immediately obtain the following CLT for strategic network formation.
At this level of generality, these conditions are close to as primitive as possible, but with additional structure we can derive lower-level conditions.
We present the method of proof for (ref) for the case of the average degree, whose node statistic is $\psi_i(\mathcal{N}_n) = \sum_{j=1}^n A_{ij}$. The approach can be applied to other network models with strategic interactions.\footnote{A previous version of the paper presents applications to dynamic network formation leung2019normal, and leung2019inference applies the methodology to games on networks.} We construct an upper bound on the radius of stabilization that has a distribution with sufficiently thin tails.
{\bf Step 1.} Recalling (ref), we construct a set of nodes $J_i \subseteq \mathcal{N}_n$ positioned near $i$ such that
That is, $i$'s node statistic is invariant to the counterfactual removal of nodes outside of $J_i$. The challenge is to find a set that is relatively small so that the distribution of the set's size has thin tails. Supposing such a set could be found, the radius of stabilization $\bm{R}_i(n,r_n)$ ((ref)) would be upper bounded by the radius of the smallest ball centered at $r_n^{-1}X_i$ containing the positions of $J_i$ (plus one):
Since $\psi_i(\mathcal{N}_n) = \sum_{j=1}^n A_{ij}$ is simply the 1-neighborhood size, an initial guess for $J_i$ might be $i$'s 1-neighborhood. However, this does not generally satisfy (ref). To see why, consider node $i=6$ in (ref) whose 1-neighborhood is contained in $\{4,5,7\}$. Since $D_{56}=1$, the potential link $A_{56}$ is non-robust and therefore may differ under the counterfactual that removes node 3 from the model, even though 3 is not $i$'s neighbor.
Instead we take $J_i = C_i^+$. The pairwise stability of $\bm{A}_{C_i^+}$ is invariant to the removal of nodes outside of $C_i^+$ (see (ref) and (ref)), and under (ref), $\bm{A}_{C_i^+}$ remains the selected equilibrium subnetwork on $C_i^+$ after removal of $\mathcal{N}_n\backslash C_i^+$. That is, for $H = C_i^+$, $\bm{A}_H = \lambda_n(r_n^{-1}\bm{T}_n, \bm{\zeta}_n)|_H = \lambda_{\lvertH\rvert}(r_n^{-1}\bm{T}_H, \bm{\zeta}_H)$. Since $C_i^+$ contains $i$'s 1-neighborhood, (ref) holds.
{\bf Step 2.} Next we show that $\lvertJ_i\rvert$ has a distribution with exponential tails. First, (ref) establishes that $\lvertJ_i\rvert$ is stochastically dominated by the size of a certain branching process when $J_i$ is constructed from components and $K$-neighborhoods of dyadic networks. (ref) shows that the size of the branching process has a distribution with exponential tails using Assumptions (ref) and (ref).
In the case of average degree, our choice of $J_i=C_i^+$ is the union of a component of $\bm{D}$ and 1-neighborhoods in $\bm{\Pi}$, as defined in (ref), which are dyadic networks. For more general $K$-neighborhood node statistics satisfying (ref), the construction of $J_i$ is more complicated but still involves similar objects. (ref) in (ref) shows how to construct $J_i$ for a general node statistic satisfying (ref). The lemmas in (ref) can then be applied to obtain the desired tail bounds.
{\bf Step 3.} We translate the tail bound for $\lvertJ_i\rvert$ into one for $\tilde\bm{R}_i(n,r_n)$. Intuitively, if $\lvertJ_i\rvert$ is small, then so will be $\tilde\bm{R}_i(n,r_n)$ since nodes are homophilous in positions ((ref)), so each $j\in J_i$ will typically be close to $i$ in terms of distance $r_n^{-1}\lVertX_i-X_j\rVert$. (ref) provides the formal argument.
We discuss two inference procedures applicable to network data generated by the model in (ref). Our results provide the first formal justification for their use in the subsequent applications.
Since our objective is to establish a CLT, thus far we have made no distinction between what aspects of the model are known or observed by the econometrician. In what follows, the only requirement is that the econometrician must be able to compute the relevant network moments, but it is application-specific which structural primitives need to be observed for this to be possible.
In the network statistics applications, only $\bm{A}$ needs to be observed. In structural applications, $V(\cdot)$ is typically known up to a vector of parameters, $\bm{A}$ is observed, and $\zeta_{ij}$ is unobserved, but any subvector of $(X_i, Z_i)$ could potentially be unobserved. In particular, the procedures can be implemented when positions are unobserved, as in the literature on latent-space models. Typically the distribution of the unobserved component of types, conditional on observables, is assumed known up to a vector of parameters.
Define $\mu_0 = {\bf E}[\psi_1(\mathcal{N}_n)]$ and $\hat\mu = n^{-1} \sum_{i=1}^n \psi_i(\mathcal{N}_n)$. Consider testing the null hypothesis
This is relevant for the reporting of stylized facts in the networks literature. Such facts are obtained by computing various statistics from $\bm{A}$ but are seldom accompanied by formal uncertainty quantification due to a lack of available methods. leung2018dependence discusses two particular examples: testing for nontrivial clustering (his \S3.3) and testing for a power law degree distribution (his \S3.4). We next discuss two generic tests justified by our CLT. Confidence regions for $\mu_0$ can be obtained by test inversion.
{\bf Single large network.} If the sample consists of a single network, we may apply the resampling procedure due to song_ordering-free_2016 and leung2018dependence. Let $\alpha$ be the desired level of the test, $R_n = (n/2)^{4/3}$ rounded to the nearest integer, $\Pi$ be the set of all bijections (permutation functions) on $\{1, \dots, n\}$, and $\pi = (\pi_r)_{r=1}^{R_n}$ be i.i.d.\ uniform draws from $\Pi$. Let $\hat{\bm{V}} = n^{-1} \sum_{i=1}^n (\psi_i(\mathcal{N}_n) - \hat\mu)(\psi_i(\mathcal{N}_n) - \hat\mu)'$, the sample variance. Define the test statistic
recalling that $d_\psi$ is the dimension of the range of $\psi_n(\cdot)$. Let $z_{1-\alpha}$ be the $1-\alpha$ quantile of the standard normal distribution. The test rejects if and only if
Validity of this test hinges on the high-level weak dependence condition that $\hat\mu$ is $\sqrt{n}$-consistent. leung2016 provides an LLN for $\hat\mu$ but not a rate of convergence. Our paper is the first to provide primitive conditions for $\sqrt{n}$-consistency in the context of strategic network formation.
For intuition on the importance of $\sqrt{n}$-consistency for the test's validity, consider a simpler test statistic studied by leung2018dependence:
for $R_n^M = \sqrt{n}$ rounded to the nearest integer. To understand its asymptotic behavior, we add and subtract its mean conditional on the data:
Conditional on the data $\{\psi_i(\mathcal{N}_n)\}_{i=1}^n$, the permutations $\pi_r$ are independent, so the first term is an average of $R_n^M$ conditionally independent observations and can be shown to be asymptotically $\mathcal{N}(\bm{0},\bm{I})$ under $H_0$. The second is a bias term that can be shown to equal $(R_n^M/n)^{1/2} \hat{\bm{V}}^{-1/2} \sqrt{n}(\hat\mu-\mu)$. Hence, under $H_0$ and $\sqrt{n}$-consistency, the bias is order $(R_n^M/n)^{1/2} = o(1)$.
{\bf Multiple large networks.} A drawback of the previous procedure is that it is inefficient, having a rate of convergence slower than $\sqrt{n}$ since $R_n^M = o(n)$. If the sample consists of sufficiently many independent large networks, then more powerful methods are available from the cluster-robust inference literature. Consider a sequence of $L$ independent networks indexed by $n$, where $L$ is fixed with respect to $n$ and each network $\ell=1,\dots,L$ has size $n_\ell$ satisfying $n_\ell/n \rightarrow c_\ell \in (0,\infty)$ as $n\rightarrow\infty$. Let $\hat{\mu}^\ell = n_\ell^{-1} \sum_{i=1}^{n_\ell} \psi_i(\mathcal{N}_{n_\ell})$, the network moment computed on network $\ell$. Assume there exists a universal population moment $\mu_0$ such that ${\bf E}[\hat{\mu}^\ell] = \mu_0 + o(n^{-1/2})$ for all $\ell$. We seek to test the null $H_0\colon \mu_0=\mu$.
We consider the randomization test proposed by canay2017randomization. For $S_{n,\ell} = \sqrt{n_\ell}(\hat{\mu}^\ell - \mu)$ and $S_n = (S_{n,\ell})_{\ell=1}^L$, define the Wald statistic
We obtain critical values from the randomization distribution $\{T(\pi S_n)\colon \pi \in \{-1,1\}^L\}$ where $\pi S_n = ( \pi_\ell S_{n,\ell} )_{\ell=1}^L$ for $\pi = (\pi_\ell)_{\ell=1}^L$. Let $\alpha$ be the desired level of the test, $q = 2^L(1-\alpha)$ rounded up to the nearest integer, and $c_{L,1-\alpha}$ be the $q$th largest value of $\{T(\pi S_n)\colon \pi \in \{-1,1\}^L\}$. The test rejects if and only if
The test is asymptotically level $\alpha$ under the high-level condition that the limit distribution of the vector of network moments is asymptotically normal. We provide the first primitive sufficient conditions in the literature for strategic network formation. Intuitively, under $H_0$ and asymptotic normality, $\{S_{n,\ell}\}_{\ell=1}^L$ are independent draws from a mean-zero, approximately normal distribution. Hence, multiplying these draws by $\pm 1$ does not change the asymptotic distribution of $T(S_n)$, which is the key justification for the validity of randomization tests.
We revisit (ref), which concerns inference on structural parameters using moment inequalities proposed by sheng2014. Recalling the setup there, let $\theta_0$ denote the true parameters of $V(\cdot)$. To test the hypothesis $H_0\colon \theta_0=\theta$, we test the moment inequality
When the data consists of a single large network, we can employ a test due to leung2018dependence. Let $\mu_k$ be the $k$th component of $\mu_0$, $\psi_{ik}(\mathcal{N}_n)$ the $k$th component of $\psi_i(\mathcal{N}_n)$, and $T_{U,k}(\mu_k; \pi)$ the U-type statistic defined in the previous subsection but computed with scalar data $\{\psi_{ik}(\mathcal{N}_n)\}_{i=1}^n$. Also let $\hat\mu_k$ be the $k$th component of $\hat\mu$ and $\hat{\bm{V}}_{kk}$ the $k$th diagonal entry of $\hat{\bm{V}}$. Define the test statistic
Let $\tilde\pi_1, \dots, \tilde\pi_L$ be i.i.d.\ with the same distribution as $\pi$. Let $q = L(1-\alpha)$ rounded up to the nearest integer and $c_{L,1-\alpha}$ be $q$th largest value of $\{\max_{1\leq k\leq d_\psi} T_{U,k}(\hat\mu_k;\tilde\pi_\ell)\}_{\ell=1}^L$. The test rejects if and only if
Theorem 2 of leung2018dependence provides conditions under which the test is asymptotically level $\alpha$ under $H_0$. The main assumption that needs to be verified is $\sqrt{n}$-consistency of $\hat\mu$, which is a consequence of our CLT. Like the test in the previous subsection, this procedure is inefficient with a slower than $\sqrt{n}$-rate of convergence. To construct more powerful tests, we require either a consistent estimate of $\bm{\Sigma}_n$ or a valid resampling procedure, topics we leave to future research.
We conduct a simulation study to assess the quality of the normal approximation and finite-sample performance of the inference procedures in (ref). We simulate data according to the model in (ref) with $\lVert \cdot\rVert$ equal to the Euclidean norm, $\theta = (1, 0.25, 1)$, $X_i \stackrel{iid}\sim \mathcal{U}([0,1]^2)$, and $\zeta_{ij} \stackrel{iid}\sim \mathcal{N}(0,1)$. To satisfy (ref), we set $\kappa = 0.8\theta_3\pi^{-1}(q(\theta_1+\theta_2) - q(\theta_1))^{-1}$ following the notation in (ref), which implies $\lVerth^*\rVert_{\mathbf{m}} = 0.8 < 1$. To satisfy (ref), we select the equilibrium network using myopic best-response dynamics ((ref)) starting from the network $\bm{\Pi}$ defined in (ref). The model generates networks with fairly realistic properties; the largest component comprises about 75 percent of the network, while the average degree and clustering are respectively about 4.3 and 0.4.
We consider equality tests involving the following network moment. Define the node statistic $\psi_i(\mathcal{N}_n) = \psi_i^c - \psi_i^f$ where
Then $n^{-1} \sum_{i=1}^n \psi_i^c$ is the average clustering coefficient, a measure of triadic closure, while $n^{-1} \sum_{i=1}^n \psi_i^f$ is the link frequency. The motivation for the network moment $n^{-1} \sum_{i=1}^n \psi_i(\mathcal{N}_n)$ is as follows. Under the “null” Erd\H{o}s-R\'{e}nyi model, the moment is approximately zero. However, a well-known stylized fact is that real-world networks typically feature nontrivial clustering in that the statistic is far from zero barabasi2015. While this fact is based only on the point estimate, the inference procedures in (ref) enable us to formulate this as a statistical test.
We simulate rejection rates for three different tests of hypotheses of the form
where $c \in (0,1]$ and $\mu$ is the true value of ${\bf E}[\psi_1]$, computed using 40k simulation draws. To simulate size, we set $c=1$, and to simulate power, we set $c \in \{0.8, 0.9\}$. We consider the following tests at the 5-percent level. To assess the quality of the normal approximation, we use the “oracle” $t$-test with test statistic $(n^{-1} \sum_{i=1}^n \psi_i - c\mu) / \sigma$, where $\sigma$ is the true standard error, computed by taking the standard deviation of the network moment across 40k simulation draws. We then consider the dependence-robust test (ref) and randomization test from (ref). The randomization test will use data from 5, 6, or 8 independent networks of identical size, while the other tests only utilize data from one of the networks. We simulate size and power using 5k simulation draws.
(ref) shows the results. From the first three columns, we see that the oracle $t$-test controls size well across all sample sizes, illustrating the quality of the normal approximation. The randomization test (the Rand rows in the table) controls size well across all $n$, while the dependence-robust test (the DR row in the table) exhibits some over-rejection, particularly in smaller samples. Section 6 of leung2018dependence provides additional simulation results for the dependence-robust test under a variety of data-generating processes, including a network formation model similar to the present design. His results show that the test has good properties for different choices of the tuning parameter $R_n$.
The last six columns of (ref) compare power. The differences between the oracle and dependence-robust tests are due to the latter's slower rate of convergence. A comparison of the power of the randomization and dependence-robust tests is not apples-to-apples because the former utilizes 5 to 8 times the sample size. However, we see that the randomization test requires at least 6 networks to obtain nontrivial power. These results confirm the discussion in (ref).
This paper develops a large-sample theory for a model of network formation with strategic interactions and homophilous agents when the data consists of a small sample of large networks or possibly a single network. We prove a general CLT under a high-level weak dependence condition and provide a general methodology for its verification. We apply the methodology to obtain primitive conditions for a CLT for moments of pairwise stable networks.
There are several important directions for future work. Concentration inequalities for stabilization would be useful, for example, for deriving lower-level conditions for uniform convergence of nonparametric or high-dimensional estimators using network data. It is also of interest to develop efficient alternatives to the inference procedures in (ref) in the case where the data is a single network observation.