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.
45,878 characters · 22 sections · 26 citation commands
1 Testing for Differences in Stochastic Network Structure
This paper proposes analogues of a two-sample Kolmogorov-Smirnov (KS) test for networks. The KS test is a standard way to assess whether two random vectors come from the same distribution and has many applications in economics. One example is detecting distributional treatment effects imbensRubin2015. While tests that compare averages or ranks may ignore key differences between distributions, the KS test compares empirical distribution functions directly, and so with enough data can detect any fixed difference.
What is an analogous way to detect differences between networks? This paper proposes tests based on operator norms to assess whether two stochastic networks come from the same random graph model. While tests that compare network statistics such as measures of density, clustering, or centrality may ignore key differences between models banerjee2018changes, the proposed tests, like the KS test for distributions, with enough data can detect any fixed difference.
Section 2 describes the model, testing problem, and applications. The model is a nonparametric version of a class of dyadic regression models popular in the networks literature. The testing problem is that two networks are drawn from the same model. Applications include tests for network non-stationarity, treatment effects, externalities, and more.
Section 3 outlines a randomization test. The test is based on an implication of the model, that under the null hypothesis the joint distribution of links is invariant to exchanging the weight of a link in one network for its identically indexed counterpart in the other. The test controls size by construction. Power depends on a choice of test statistic.
Section 4 considers two test statistics that produce tests powerful against a large class of alternative hypotheses. The first test statistic is based on the $2\to2$ operator norm (also known as the spectral norm or radius) of the difference between the networks' adjacency matrices. The second test statistic is based on the $\infty\to1$ operator norm. The tests are easy to implement and quick to compute for networks connecting hundreds of agents. Evaluating their power properties, however, requires new tools from the random matrix theory literature.
A key result is that while both tests with enough data will detect any fixed difference between models, the test based on the $\infty\to1$ norm can be considerably more powerful when there is nontrivial heterogeneity in the row-variances of the networks' adjacency matrices. Such row-heteroskedasticity may occur when the networks are sparse or have heavy-tailed degree distributions, which characterizes many social and economic networks jackson2007meeting. This is why I recommend that researchers use the test based on the $\infty\to1$ norm when testing for differences between networks in practice.
Intuitively, the $2\to2$ norm may have low power under row-heteroskedasticity because the weight vector that maximizes this norm places most of its weight on the entries corresponding to the rows of the adjacency matrices with the highest variances. As a result, the test potentially ignores differences between networks that occur in the low-variance rows. The $\infty\to1$ norm addresses the problem by using the $\infty$-vector norm instead of the $2$-vector norm to define the unit weight vector. The entries of the weight vector that maximize this norm take values in $\{-1,1\}$ and so by construction necessarily place the same absolute weight on every entry. Consequently, if there are sufficiently large differences between the low-variance rows, the test based on the $\infty\to1$ norm will detect them. In some sense, this logic behind the $\infty$-vector norm is related to that behind the $1$ or $0$-vector norm penalizations common in the high-dimensional regression literature. Instead of imposing a sparse solution, however, the $\infty$-vector norm imposes a dense one.
Section 5 provides two empirical demonstrations using data from real-world social networks. In both examples, the $\infty\to1$ norm has sufficient power to detect the relevant difference, corroborating theoretical results. Alternatives are less reliable. Additional results, details, and simulation evidence can be found in an online appendix. R code for implementation can be found on my website.\footnote{\url{https://sites.google.com/site/ericjauerbach/}}
Sections 2.1 and 2.2 describe the model and testing problem. Section 2.3 provides example applications to testing problems in the network economics literature.
It is without loss to consider undirected unipartite networks. These networks are defined on a set of $N$ agents referred to as a community and indexed by $[N] := \{1,2,...,N\}$. Every pair of agents in a community is endowed with two real-valued random variables, each corresponding to a stochastic social relationship. For example, one weight might correspond to whether two agents are friends, another might give the amount of trade between them, etc. The variable $D_{ij,t}$ for $t = 1,2$ records the realized relationship $t$ between agents $i$ and $j$. The $N\times N$ dimensional symmetric adjacency matrix $D_{t}$ contains $D_{ij,t}$ in the $ij$th and $ji$th entries.
I suppose that the networks to be compared are defined on the same community of agents. In many settings, the community is defined so that this is the case. For instance, to study trade networks economists often define the unit of analysis to be countries and the links to be the amount of trade between countries in a year, even if the agents that actually trade are people and firms that change over time. Testing for differences between networks defined on different communities generally requires more structure concerning exactly how two communities ought to be compared. This is left to future work.
Directed or bipartite networks are incorporated in the following way. These networks are generally defined on a set of $N_{1}$ agents and $N_{2}$ markets indexed by $[N_{1}]$ and $[N_{2}]$ respectively. Every agent-market pair is endowed with two real-valued random variables, each corresponding to a stochastic social relationship. For example, one weight might correspond to whether the agent is employed in the market, another might give the amount of profit the agent makes in the market, etc. The variable $D^{\star}_{ij,t}$ records the realized relationship $t$ between agent $i$ and market $j$. The $N_{1} \times N_{2}$ dimensional matrix $D^{\star}_{t}$ contains $D^{\star}_{ij,t}$ in the $ijth$ entry. This asymmetric rectangular adjacency matrix is transformed into a symmetric square one by setting
where $(\cdot)^{T}$ is the transpose operator, $0_{N_{1}\times N_{1}}$ is an $N_{1}\times N_{1}$ matrix of zeros, and $D_{t}$ is a $N\times N$ symmetric matrix with $N = N_{1}+N_{2}$. It follows that the focus on undirected unipartite networks (symmetric and square adjacency matrices) is without loss.
The entries of $D_{1}$ and $D_{2}$ are assumed be equal to $0$ on the main diagonal (no self-links) and mutually independent above the main diagonal. This independence assumption is common in the dyadic regression literature (see below). The marginal distribution of $D_{ij,t}$ is denoted by $F_{ij,t}$ and the $N\times N$ dimensional matrix $F_{t}$ contains $F_{ij,t}$ in the $ij$th entry. A generic matrix of distribution functions $F_{t}$ is referred to as a random graph model.
A concrete example of a random graph model is $D_{ij,t} = \mu_{ij,t} + \varepsilon_{ij,t}$, where $\mu_{ij,t} = f_{t}(\alpha_{i,t},\alpha_{j,t},w_{ij,t})$, $\alpha_{i,t}$ is an agent-specific effect, $w_{ij,t}$ are agent-pair attributes, $f_{t}$ is a community link function, and $\varepsilon_{ij,t}$ is an idiosyncratic error that is independently distributed across agent-pairs with marginal distribution $G_{ij,t}$ graham2019network. I treat the effects $\{\alpha_{i,t}\}_{i \in [N],t\in[2]}$ and attributes $\{w_{ij,t}\}_{i,j \in [N],t\in[2]}$ as non-stochastic. That is, if these variables are drawn from some distribution, the random graph model is defined conditional on their realization. Such conditioning is standard in the literature.
The only remaining source of randomness are the $\{\varepsilon_{ij,t}\}_{i,j \in [N],t\in[2]}$ and so the $\{D_{ij,t}\}_{i < j \in [N],t\in[2]}$ are independent random variables with marginals given by $F_{ij,t}(s) = G_{ij,t}(s- \mu_{ij,t}) = G_{ij,t}(s- f_{t}(\alpha_{i,t},\alpha_{j,t},w_{ij,t}))$. The random graph model $F_{t}$ is thus parametrized by the agent effects, attributes, link function, and distribution of idiosyncratic errors. Informally, if a treatment alters any of these parameters, then the framework characterizes the change as a treatment effect. This is formalized by the statement of the testing problem below. Not every difference in model parameters can be detected using $D_{1}$ and $D_{2}$, however. To constitute evidence against the hypothesis of no treatment effect, the difference in parameters must yield a sufficiently large difference between $F_{1}$ and $F_{2}$. Other notions of a random graph model may imply other definitions of a treatment effect. Their study is left to future work.
The problem considered in this paper is to test the null hypothesis
against the alternative
$H_{0}$ is the hypothesis that $D_{1}$ and $D_{2}$ are drawn from the same random graph model.
For the concrete example of Section 2.1, the problem is equivalent to testing the hypothesis that $G_{ij,1}(s- f_{1}(\alpha_{i,1},\alpha_{j,1},w_{ij,1})) = G_{ij,2}(s- f_{2}(\alpha_{i,2},\alpha_{j,2},w_{ij,2}))$ for every $s \in \mathbb{R}$ and $i,j \in [N]$. The hypothesis may be false whenever the two random graph models have different agent-specific effects, agent-pair attributes, community link functions, or distributions of idiosyncratic errors. Distinguishing between these parameters generally requires more structure. For example, if the $\{\varepsilon_{ij,t}\}_{i \in [N_{T}],t\in[2]}$ are identically distributed, $\alpha_{i,1} = \alpha_{i,2}$, and $w_{ij,1} = w_{ij,2}$ for every $i,j \in [N]$, then the problem reduces to a test of whether the link functions $f_{1}$ and $f_{2}$ are the same. If the $\{\varepsilon_{ij,t}\}_{i \in [N_{T}],t\in[2]}$ are identically distributed, $f_{1} = f_{2}$, and $w_{ij,1} = w_{ij,2}$ for every $i,j \in [N]$, then the problem reduces to a test of whether $\alpha_{i,1} = \alpha_{i,2}$ for every $i \in [N]$. See Online Appendix Section B.2 for a discussion.
The logic behind this test is that any change in the distribution of idiosyncratic errors, agent fixed effects, link function, etc. reflects different incentives for agents to form or report links. Differences due to the idiosyncratic errors reflect only policy-irrelevant statistical noise. As previously motivated, the test is specifically designed to detect a large class of differences between two random graph models. Other testing problems tailored to detect more specific differences are discussed in the applications and extensions below.
Related testing problems have also been considered in the literature. ghoshdastidar2017two1,ghoshdastidar2017two2 propose a test statistic based on the $2\to2$ norm for a different testing problem. A literature on random dot product graph models tang2017nonparametric,nielsen2018multiple relies on a low-dimensional dot-product structure. A related application of randomization-based inference to networks is tests for interference aronow2012general,athey2018exact. Rather than study the influence of a treatment on network structure, this literature studies the influence of a network on agents' exposure to treatment.
I sketch six applications and three extensions of the framework to testing problems in the network economics literature. Details can be found in Online Appendix Section D.
goyal2006economics observe co-authorships between economists over time and argue that the profession has become more interconnected in response to new research technologies such as the internet. The above framework can be used to test whether the differences over time are statistically significant. The first example in Section 5 demonstrates this application to testing link stationarity.
banerjee2013diffusion collect data on a dozen social and economic ties between villagers. jackson2017economic suggest that this data may “encode richer information than simply identifying whether two people are close or not.” The above framework can be used to test whether the differences between the networks induced by different survey questions are statistically significant. The second example in Section 5 demonstrates this application to testing link homogeneity.
rose2004we finds that country participation in trade agreements such as the WTO does not significantly alter international trade. The above framework can be used to test whether program participation leads to a statistically significant change in network structure.
goldsmith2013social consider a model of student GPA and link formation, and test whether a determinant of GPA also drives link formation in the network. They propose a one-sample parametric test for such endogenous link formation. The above framework can be used for an alternative two-sample nonparametric test.
calvo2009peer specify a model of network peer effects in which any nomination of a friendship from one student to another indicates a social tie between both students. The above framework can be used to test for reciprocity or symmetry in link nominations.\footnote{I thank Vincent Boucher for suggesting the example.}
pelican2020optimal consider a model of link formation in which the decision for two agents to link may depend on other links that have been realized in the network. They propose a one-sample parametric test for such network externalities. The above framework can be used for an alternative two-sample nonparametric test.
banerjee2018changes collect data on connections between villagers in a number of villages before and after a microfinance agency offers loans to villagers in some but not all of the villages. They find that the program disincentivizes the formation of certain types of connections. The above framework can be modified to test whether the observed differences between the treatment and control villages are statistically significant.
fafchamps2007risk study a risk-sharing network and argue that the surveyed links are not related to the respondents' occupations. The above framework can be modified to test whether the network connections and respondent occupations are statistically independent.
jackson2007meeting argue that real-world social networks have features that are not explained by an Erd\"os-Renyi model of link formation. The above framework can be modified to test whether network data can be explained by a specific random graph model.
I outline a randomization procedure to construct tests for the problem of Section 2 lehmann2006testing. The procedure takes as given a test statistic $T(D_{1},D_{2})$. Any real-valued function of $D_{1}$ and $D_{2}$ can be used to construct the test statistic. Example test statistics include differences in centrality measures such as agent degree, eigenvector centrality, or clustering. Certain centrality measures may direct the power of the test towards specific alternatives.
For any positive integer $R$, let $\{\rho_{ij}^{r}\}_{i > j \in [N], r \in [R]}$ be a collection of ${N \choose 2} \times R$ independent Bernoulli random variables with mean $1/2$. Define $\rho_{ij}^{r} = \rho_{ji}^{r}$ if $i < j$. Then for each $r \in [R]$, the randomized $N \times N$ adjacency matrices $D_{1}^{r}$ and $D_{2}^{r}$ are generated by exchanging $D_{ij,1}$ and $D_{ij,2}$ whenever $\rho_{ij}^{r}$ equals $1$. That is,
where $D_{ij,1}^{r}$ is the $ij$th entry of $D_{1}^{r}$. For any $\alpha \in [0,1]$, the proposed $\alpha$-sized test based on $T(D_{1},D_{2})$ rejects $H_{0}$ if
and fails to reject $H_{0}$ otherwise.
Since $(D_{1},D_{2})$ and $(D_{1}^{r},D_{2}^{r})$ have the same distribution under $H_{0}$, lehmann2006testing, Theorem 15.2.1 implies the following. When $H_{0}$ is true the probability of an (incorrect) rejection does not exceed $\alpha$, or
This is true for any test statistic $T(D_{1},D_{2})$. When the researcher has a collection of network statistics, the tests can be combined in the usual way. One can also test whether any number of adjacency matrices are drawn from the same random graph model by permuting all of the corresponding entries.
Two tests based on operator norms are proposed in Section 4.1. Large sample power properties of the tests are characterized in Section 4.2 and Online Appendix Section B.
The randomization procedure of Section 3 produces a test for the problem of Section 2 that controls the probability of (incorrectly) rejecting the null hypothesis when it is true using any test statistic. However, not every statistic produces a test that is powerful in that it tends to (correctly) reject the null hypothesis when it is false. This section proposes two statistics that have power against a large class of alternative hypotheses. The statistics are based on $p\to q$ operator norms.
For any $p,q \geq 1$, the test statistic based on the $p\to q$ operator norm is given by
where $||\cdot||_{p}$ refers to the vector $p$-norm, $\varphi$ is a $N$-dimensional column vector with real-valued entries, and for any real number $s$ and matrix $X$, $\mathbbm{1}\{X \leq s\}$ contains $1$ in the $ij$th entry if $X_{ij} \leq s$ and $0$ otherwise. The test of $H_{0}$ based on $T_{p\to q}$ is as described in Section 3.
When the entries of $D_{1}$ and $D_{2}$ are $\{0,1\}$-valued,
which is the $p\to q$ operator norm of the entry-wise difference between two adjacency matrices. Intuitively, $T_{p\to q}\left(D_{1},D_{2}\right)$ compares the collection of weighted degree distributions of $D_{1}$ and $D_{2}$, indexed by the weight vector $\varphi$ and given by $\{\sum_{j\in[N]}D_{ij,t}\varphi_{j}\}_{i \in [N], \varphi: ||\varphi||_{p} =1}$. This weighted degree distribution function is a matrix analogue to the empirical distribution function for vectors. Instead of measuring the number of entries that fall below a point on the real line, it measures the magnitude of connections from each agent to the community as weighted by $\varphi$.
Not every $p\to q$ operator norm is either computable or produces a test that has power against a nontrivial class of alternatives. This is why I focus on two choices of $p$ and $q$.
The first test statistic is based on the $2\to2$ operator norm (also known as the spectral norm or spectral radius)
The $2\to2$ norm is a natural first choice because it is straightforward to compute in $O(N^3)$ time and its statistical properties have been well studied in the random matrix theory literature. However, as I demonstrate below, the resulting test may have low power under row-heteroskedasticity: nontrivial variation in the row-variances of the adjacency matrices. Intuitively, the problem is that the weight vector $\varphi$ that maximizes the program may place excessive weight on the high-variance rows of $\left[\mathbbm{1}\{D_{1} \leq s\}-\mathbbm{1}\{D_{2} \leq s\}\right]$ (see below). To address this problem, I consider a second test statistic.
The second test statistic is based on the $\infty\to1$ operator norm
The logic behind this test statistic is that the weight vector $\varphi$ that maximizes this problem necessarily places the same absolute weight on every entry and so is less sensitive to row-heteroskedasticity. Unfortunately, computing this norm is NP-hard. The proposed test is instead based on the semidefinite approximation
where $\Delta(s) = \mathbbm{1}\{D_{1} \leq s\}-\mathbbm{1}\{D_{2} \leq s\}$, $\left<\cdot\right>$ is the inner product operator (i.e. $\left<X,Y\right> = \sum_{i=1}^{2N}\sum_{j=1}^{2N}X_{ij}Y_{ij}$), and $\mathcal{X}_{2N}$ is the set of all $2N \times 2N$ positive semidefinite matrices with diagonal entries equal to 1, see generally alon2006approximating. This statistic can be computed in $O\left(N^{3.5}\right)$ time using programs available in many statistical software packages. Its substitution is justified by the fact that
for any $D_{1}$, $D_{2}$, and $N$ with $K = \frac{\pi}{2\ln{\left(1 + \sqrt{2}\right)}} \leq 1.783$. A derivation of the semidefinite approximation and justification of the inequalities can be found in Appendix Section A.2.
As discussed in Section 3, the $\alpha$-sized tests based on $T_{2\to 2}$ and $S_{\infty\to 1}$ (incorrectly) reject the null hypothesis when it is true with probability less than $\alpha$. This section provides conditions such that the tests (correctly) reject the null hypothesis when it is false. Specifically, it defines a class of sequences of alternative hypotheses such that the power of the tests tend to one uniformly over the class. Each sequence describes a collection of models and tests indexed by $N \in \mathbb{N}$. Each model is as described in Section 2. Each test is as described in Section 3. The parameters $F_{1}$, $F_{2}$, $R$, and $\alpha$ may all vary with $N$ subject to restrictions below. Limits are with $N \to \infty$. The statement of the results mirror those for the KS test in Chapter 14.2 of lehmann2006testing, although to my knowledge the underlying arguments are not related in any meaningful way.
The following assumptions on the size of the test are imposed.
I do not believe either to be restrictive in practice. The first is that the size of the test is not exponentially small relative to the number of agents. The second is that the size of the test is larger than twice the inverse of the number of simulations. They are required because if $\alpha$ is too small, the test will mechanically fail to reject $H_{0}$ regardless of the choice of $T$ or difference between $F_{1}$ and $F_{2}$. They follow if $\alpha$ is fixed and $R$ tends to infinity with $N$.
The following constructions are used.
In words, $\nu_{ij}(s)$ is the variance of $\Delta_{ij}(s)$, $\sqrt{\sum_{j \in [N]}\nu_{ij}(s)} $ is the root of the $i$th row-variance of $\Delta(s)$, $\max_{i \in [N]}\sqrt{\sum_{j \in [N]}\nu_{ij}(s)}$ and $\sum_{i \in [N]}\sqrt{\sum_{j \in [N]}\nu_{ij}(s)}$ are the maximum and average root-row-variance of $\Delta(s)$ respectively, and $\tau$ and $\sigma$ are the maximum of the maximum and average root-row-variances taken over $s$. Under $H_{0}$ and certain regularity conditions, $T_{2\to2}(D_{1},D_{2})$ is proportional to $\tau$ and $T_{\infty\to1}(D_{1},D_{2})$ is proportional to $\sigma$ with high probability. This is demonstrated by Lemmas 1 and 2 in Appendix Section A.
$T_{2\to2}(F_{1},F_{2})$ and $T_{\infty\to1}(F_{1},F_{2})$ are the test statistics applied to the (matrix of) distribution functions $F_{1}$ and $F_{2}$. These metrics quantify the extent to which $H_{0}$ is violated. Larger values correspond to more extreme violations. Under certain regularity conditions, $T_{2\to2}(F_{1},F_{2})$ large relative to $\tau$ or $T_{\infty\to1}(F_{1},F_{2})$ large relative to $\sigma$ eventually results in a rejection of $H_{0}$. This is the content of Theorems 1 and 2 below.
The main consistency result for the test based on the $2\to2$ norm is given by Theorem 1.
The hypothesis of Theorem 1 has two rate conditions. The first rate condition is that $T_{2\to2}(F_{1},F_{2})/\tau \to \infty$. This condition implies that the size of the violation of $H_{0}$ (as given by $T_{2\to2}(F_{1},F_{2})$) exceeds the magnitude of the test statistic $T_{2\to2}(D_{1},D_{2})$ under $H_{0}$ (which is on the order of $\tau$) with high probability. When $F_{t}$ is sufficiently dense in the sense that for some $s \in \mathbb{R}$, $F_{ij,t}(s)$ is uniformly bounded away from $0$ and $1$, it follows from $\sqrt{N}T_{2\to2}(F_{1},F_{2}) \to \infty$.
The second rate condition is that $\tau/\sqrt{\ln(N)} \to \infty$. This condition is sufficient for the reference distribution generated by $\{T_{2\to2}(D_{1}^{r},D_{2}^{r})\}_{r\in [R]}$ to concentrate below $\tau$. It is satisfied if $F_{t}$ is sufficiently dense in the sense that, for some $s \in \mathbb{R}$, $\frac{N}{\ln(N)}F_{ij,t}(s)$ and $\frac{N}{\ln(N)}(1-F_{ij,t}(s))$ are uniformly bounded away from $0$. In other words, agents have on expectation at least $\ln(N)$ connections. This suggests that the test based on the $2\to2$ norm may be poorly suited for networks in which agents have on expectation only a bounded number of connections.
The main result for the test based on the $\infty\to1$ norm is given by Theorem 2.
The two rate conditions in the hypothesis of Theorem 2 are similar to those in the hypothesis of Theorem 1. The first is that $T_{\infty\to1}(F_{1},F_{2})/\sigma \to \infty$ (or equivalently, that $S_{\infty\to1}(F_{1},F_{2})/\sigma \to \infty)$. This condition implies that the size of the violation of $H_{0}$ (as given by $T_{\infty\to1}(F_{1},F_{2})$) exceeds the magnitude of the test statistic under $H_{0}$ (which is on the order of $\sigma$) with high probability. When $F_{t}$ is dense in the sense that for some $s \in \mathbb{R}$, $F_{ij,1}(s)$ is uniformly bounded away from $0$ and $1$, it also follows from $\sqrt{N}T_{\infty\to1}(F_{1},F_{2}) \to \infty$.
The second rate condition is that $\sigma/\sqrt{\ln(N)} \to \infty$. This condition is sufficient for the reference distribution generated by $\{S_{\infty\to1}(D_{1}^{r},D_{2}^{r})\}_{r \in [R]}$ to concentrate below $\sigma$. It is satisfied if for some $s \in \mathbb{R}$, $\frac{N^3}{\ln(N)}F_{ij,t}(s)$ and $\frac{N^3}{\ln(N)}(1-F_{ij,t}(s))$ are uniformly bounded away from $0$. In contrast to the hypothesis of Theorem 1, it is sufficient that agents have on expectation at least $\ln(N)/N^2$ connections, which covers settings in which agents have a bounded number of connections. The condition is unlikely to be restrictive in practice.
The results predict two scenarios in which the test based on the $\infty\to1$ norm is potentially more powerful than that based on the $2\to2$ norm, in the sense that the hypothesis of Theorem 2 is satisfied but that of Theorem 1 is not. The first scenario is network sparsity. An example of this is when $F_{1}\wedge (1-F_{1})$ and $F_{2}\wedge(1-F_{2})$ are uniformly on the order of $1/N$. One can verify that $\tau/\sqrt{\ln(N)} \to 0$ but $ \sigma/\sqrt{\ln(N)} \to \infty$. The second scenario is degree-heterogeneity. An example of this is when, for some small positive integer $K$, $F_{ij,1} = F_{ij,2}$ is on the order of a constant if $i\wedge j \leq K$ but $F_{ij,1} \neq F_{ij,2}$ is on the order of $1/\sqrt{N}$ when $i\wedge j > K$. One can verify that $T_{2\to2}(F_{1},F_{2})/\tau \to 0$ but $T_{\infty\to1}(F_{1},F_{2})/\sigma \to \infty$.\footnote{Alternatively, the test based on the $2\to2$ norm is potentially more powerful under degree-heterogeneity when the differences between $F_{1}$ and $F_{2}$ occur in a small number of high-variance rows, although making inferences based on a small number of high-variance observations is not generally recommended.} Corroborating simulation evidence can be found in Online Appendix Section C.
Additional results about the near-optimality of the rate conditions, pointwise consistency, and nonasymptotic bounds on power can be found in Online Appendix Section B.
I provide two empirical demonstrations using publicly available data. In both settings the randomization test based on the $\infty\to1$ norm is sufficiently powerful to detect the relevant difference in network structure. Alternatives are less reliable.
The first is a test of network stationarity as described in Application 1 of Section 2.3. A sample of high school students are surveyed annually about their social connections. The networks appear to be less connected and more clustered over time, potentially because the students place increasing value on having friends in common as they age. The problem is to test whether the observed changes in reported relationships are statistically significant.
The data comes from the “Teenage Friends and Lifestyle Study” \citep*[see][]{michell1996peer} in which the researchers survey 160 Scottish students about friendship links during their second through fourth years of secondary school.\footnote{ The data can be found at \url{https://www.stats.ox.ac.uk/ snijders/siena/Glasgow_data.htm}.} This example uses the social network surveyed from the first and third waves when the students are respectively 13 and 15 years old. Only students who appear in all waves are included, yielding a sample size of $N = 129$.
Descriptive network statistics are provided in Panel A of Table 1. The table describes the means and standard deviations of four network statistics: the sequence of agent degrees $\{\sum_{j \in [N]}D_{ij}\}_{i \in [N]}$, eigenvector centralities, clustering coefficients $\frac{\sum_{i,j,k \in [N]}D_{ij}D_{ik}D_{jk}}{\sum_{i,j,k \in [N]}D_{ij}D_{ik}}$, and diameters of the connected component. The table indicates that while the total number of links appear to be roughly the same for both networks, the second network is less connected and more clustered than the first. Table 2 demonstrates that these differences are unlikely to be generated by the same random graph model.
Panel A of Table 2 reports the p-value of the randomization test proposed in Section 3 using seven test statistics. The first five test statistics are the absolute difference in average degree, the mean squared difference in agent degrees, the mean squared difference in eigenvector centralities, absolute difference in clustering coefficients, and absolute difference in diameters of the two networks. The last two test statistics are $T_{2\to2}$ and $S_{\infty\to1}$. Panel A indicates that the differences in the clustering and diameter are unlikely to be generated by the same random graph model. The implausibility of the null hypothesis is also clearly indicated by the tests based on $T_{2\to2}$ and $S_{\infty\to1}$.
An alternative way to detect differences in network structure is a regression-based approach where one computes a vector of network statistics for both networks, specifies a regression model in which the network statistics depend on a constant, an indicator for one of the networks, and an idiosyncratic error, and conducts a Wald test banerjee2018changes.\footnote{I thank an anonymous referee for suggesting the comparison. Formally, if $S_{it}$ is a network statistic associated with agent $i$ in network $t$ such as $i$'s degree or eigenvector centrality, then the test is based on the linear model $S_{it} = \alpha + \beta \mathbbm{1}_{t = 2} + \varepsilon_{it}$. It is assumed that the errors $\{\varepsilon_{it}\}_{i \in [N], t \in [2]}$ are independent and identically distributed with normal marginals. The null hypothesis is $\beta = 0$.} Panel A of Table 3 reports the OLS point estimates and p-values for three network statistics on the left-hand side: agent degree, eigenvector centrality, and agent clustering $\left\{\frac{\sum_{j,k \in [N]}D_{ij}D_{ik}D_{jk}}{\sum_{j,k \in [N]}D_{ij}D_{ik}}\right\}_{i \in [N]}$. In all three regressions, the coefficient in front of the network indicator is not statistically significant: the regression-based tests do not detect the change in structure of the Glasgow networks.
The second demonstration is a test for link heterogeneity as described in Application 2 in Section 2.3. Households in a village are surveyed about multiple types of relationships. Different survey questions appear to reveal information about different types of connections between agents. The problem is to test whether the observed differences in the network structure induced by the different survey questions are statistically significant.
The data comes from banerjee2013diffusion, who survey information about a dozen social and economic connections between households for $75$ villages in rural India.\footnote{ The data can be found at \url{https://hdl.handle.net/1902.1/21538}.} This demonstration uses data from the $77$ households in village $10$ and compares the social network in which two households are linked if a member of one of the households indicates that they “engage socially” with a member of the other household to the economic network in which two households are linked if a member of one of the households indicates that they “borrow money from,” “borrow kerosene or rice from,” “lend kerosene or rice to,” or lend money to” a member of the other household.
Panel B of Table 1 describes the same statistics as Panel A, but for this second application. It shows two main differences between the social and economic networks. The first difference is that the surveyed households have on average approximately one more economic link than social link. The second difference is that there is more clustering in the economic network. Table 2 demonstrates that these differences are unlikely to be generated by the same random graph model.
Panel B of Table 2 describes the same tests as Panel A, but for this second application. It indicates that the differences between the average degrees and clustering coefficients of the two networks are unlikely to be explained by the null hypothesis. However, this difference would not be detected by a reasonably-sized test based on the $2\to2$ norm because $T_{2\to2}(D_{1},D_{2})$ is in the third quartile of its reference distribution. On the other hand, $S_{\infty\to1}$ is firmly in the upper decile of its reference distribution, and so this test statistic provides evidence against the null hypothesis.
Panel B of Table 3 describes the same regressions as Panel A, but for this second application. The results from the tests based on agent degree and clustering also indicate a difference in the structure of the social and economic networks. The strength of this evidence, however, depends crucially on the regression model assumptions of linearity, normality, homoskedasticity, etc.
This paper considers a two-sample testing problem where the null hypothesis is that two networks are drawn from the same random graph model. Two tests based on the magnitude of the difference between the networks' adjacency matrices as measured by the $2\to2$ and $\infty\to1$ operator norms are proposed. Both tests with enough power can detect any fixed difference between random graph models, however, the test based on the $\infty\to1$ is shown to be substantially more powerful for the kinds of sparse and degree-heterogeneous networks common in economics.