# On the Asymptotics of Graph Cut Objectives for Experimental Designs of
Network A/B Testing

Qiong Zhang<EMAIL_ADDRESS>School of Mathematical and Statistical
Sciences, Clemson University, SC, USA

###### Abstract

A/B testing is an effective way to assess the potential impacts of two
treatments. For A/B tests conducted by IT companies, the test users of A/B
testing are often connected and form a social network. The responses of A/B
testing can be related to the network connection of test users. This paper
discusses the relationship between the design criteria of network A/B testing
and graph cut objectives. We develop asymptotic distributions of graph cut
objectives to enable rerandomization algorithms for the design of network A/B
testing under two scenarios.

#### Keywords:

Network-correlated responses; Network interference; Design of controlled
experiments; Optimal design.

##  1 Introduction

IT companies such as Facebook and LinkedIn frequently conduct controlled
experiments to evaluate the performance of two versions (e.g., A and B) of
products, features, services, etc. This task is an experimental design problem
that requires assigning the users to one of the two versions and collecting
their responses for evaluation (Larsen et al., 2023). Often, the users are
connected through the apps and form a social network. We refer to network A/B
testing as the case that the users participating in A/B testing experiments
are connected in a social network, and the social connection may imply the
potential dependence between connected users. Therefore, network A/B testing
design requires assigning users to A or B version according to their network
connection with other users, some examples of recent works including Gui et
al. (2015); Parker et al. (2017); Basse and Airoldi (2018); Pokhilko et al.
(2019); Zhang and Kang (2022). In the literature of graph theory and
optimization (Ben-Tal and Nemirovski, 2001; Gross and Yellen, 2005), this
problem is related to cutting the graph into two partitions with respect to
some objectives. In this section, we first provide an overview of the graph
cut problem and then connect it with the experimental objectives of network
A/B testing.

###  1.1 Graph Cut Problems

Consider an undirected and unweighted graph with $n$ vertexes, each
representing a user in the social network given by the graph. We can express
the connection between two vertexes by an $n\times n$ adjacency matrix
$W=\\{w_{ij}\\}$ whose $(i,j)$-th entry is $w_{ij}$. The diagonal entries
$w_{ii}$’s of this matrix are loaded with zeros, whereas the off-diagonal
entries are

$w_{ij}=\begin{cases}1,\quad\text{if there is an edge between vertexes $i$ and
$j$}\\\ 0,\quad\text{otherwise}.\end{cases}$ (1)

Let $\mathbf{x}=(x_{1},\ldots,x_{n})^{\top}\in\\{-1,1\\}^{n}$ be the
assignments of two options to the $n$ users. This is equivalent to cutting the
graph into two disjoint subsets, each with the users assigned to one of the
two options, respectively. If there is a cut between two connected users $i$
and $j$ (i.e., $w_{ij}=1$), then $x_{i}$ and $x_{j}$ take different values 1
and -1.

A graph cut is minimum if the edges across two subsets resulting from the cut
are minimized (Gross and Yellen, 2005). Equivalently, two connected users are
more likely to receive the same treatment. This problem can be formulated by

$\mathrm{max}_{\mathbf{x}\in\\{-1,1\\}^{n}}w_{ij}x_{i}x_{j},~{}~{}\mathrm{s.t.}~{}~{}-n+1\leq\sum^{n}_{i=1}x_{i}\leq
n-1.$ (2)

By maximizing the objective, the solution to this problem tends to assign the
same value to $x_{i}$ and $x_{j}$ if $i$ and $j$ are connected. The constraint
$-n+1\leq\sum^{n}_{i=1}x_{i}\leq n-1$ rules out the situation that all
$x_{i}$’s are assigned with 1 or -1 as a trivial maximum of the objective. The
value of $\sum^{n}_{i=1}x_{i}$ can be constrained to be zero or in a small
interval containing zero if the sizes of the two sub-graphs are required to be
relatively the same. The minimum cut problem in (2) is polynomial-time
solvable (Lawler, 2001).

A graph cut is maximum if the edges across two subsets are maximized (Ben-Tal
and Nemirovski, 2001), which is equivalent to

$\mathrm{min}_{\mathbf{x}\in\\{-1,1\\}^{n}}w_{ij}x_{i}x_{j}.$ (3)

The solution of this problem tends to assign opposite signs to connected
vertexes $i$ and $j$. The graph cut problem is related to experimental designs
for network A/B testing. We describe the connections in the following section.

###  1.2 Optimal Designs in Network A/B Testing

Assume that the users’ responses are modeled by

$y_{i}=\alpha+x_{i}\beta+\delta_{i},$ (4)

where $\alpha$ is the intercept, $\beta$ represents the treatment effect, and
$\delta_{i}$ represents the network effect. Next, we describe two common
scenarios of the network effect models.

#### Scenario I: Network Correlated Responses.

Under this scenario, two connected users are assumed to share common features.
Thus, the responses of two connected users are correlated due to their common
features, examples include Basse and Airoldi (2018); Pokhilko et al. (2019);
Zhang and Kang (2022). Let
$\boldsymbol{\delta}=\\{\delta_{1},\ldots,\delta_{n}\\}^{\top}$ with
$\delta_{i}$ be the error term from (4). Following the assumption in (Zhang
and Kang, 2022), we have that

$\boldsymbol{\delta}\sim\mathcal{MVN}_{n}(0,\sigma^{2}R(W,\rho)^{-1}),$ (5)

with $\sigma^{2}$ being the variance parameter, $\rho$ being the correlation
parameter that characterizes the strength of the correlation between responses
of connected users. An example of $R(W,\rho)$ in (5) is the conditional auto-
regressive model (Besag, 1974) with

$R(W,\rho)=\mathrm{diag}\left(d_{1},\ldots,d_{n}\right)-\rho W$ (6)

where $d_{i}=\sum^{n}_{j=1}w_{ij}$ is the degree of the $i$-th vertex for
$i=1,\ldots,n$. According to Pokhilko et al. (2019), given the value of
$\rho$, the variance of the weighted least squared estimator of the treatment
effect $\widehat{\beta}$ is

$\mathrm{Var}\left(\widehat{\beta}\right)=\sigma^{2}\left(\sum_{i,j}w_{i,j}-\rho\sum_{i,j}w_{i,j}x_{i}x_{j}-\frac{(1-\rho)\left(\sum^{n}_{i=1}d_{i}x_{i}\right)^{2}}{\sum_{i,j}w_{i,j}}\right)^{-1}.$
(7)

For a given network $W$, a lower bound of (7) can be expressed by

$\mathrm{Var}\left(\widehat{\beta}\right)\geq\frac{\sigma^{2}}{(1+\rho)}\left\\{\sum_{i,j}w_{i,j}\right\\}^{-1}.$
(8)

As noted by Pokhilko et al. (2019), this lower bound is attained if
$\sum_{i,j}w_{ij}x_{i}x_{j}=-\sum_{i,j}w_{ij}$ and
$\sum^{n}_{i=1}d_{i}x_{i}=0$ hold exactly. The first condition
$\sum_{i,j}w_{ij}x_{i}x_{j}=-\sum_{i,j}w_{ij}$ requires that any pair of
connected users are assigned with different treatments, whereas the second
condition $\sum^{n}_{i=1}d_{i}x_{i}=0$ requires that the treatment allocation
is stratified with respect to the degrees of the vertexes. It is obvious that
this lower bound can not be exactly attained for all the networks. To reduce
the variance of the estimated treatment effect, it is desired to allocate
design points to produce smaller values of $\sum_{i,j}w_{ij}x_{i}x_{j}$ and
$\left(\sum^{n}_{i=1}d_{i}x_{i}\right)^{2}$. Also, $|\sum^{n}_{i=1}x_{i}|\leq
1$ are required sometimes to ensure that the design is balanced over the two
treatments.

#### Scenario II: Network Interference.

Under this scenario, the users’ responses are affected by the design
allocation of their connected users. A commonly used model (e.g., Gui et al.
(2015); Parker et al. (2017)) for $\delta_{i}$ is

$\delta_{i}=\sum^{n}_{j=1}w_{ij}\alpha+\left(\sum^{n}_{j=1}w_{ij}x_{j}\right)\gamma+\varepsilon_{i},$
(9)

where $\alpha$ and $\gamma$ are unknown parameters, and $\varepsilon_{i}$ is
an independent random error with mean zero and variance $\sigma^{2}$. Under
this model assumption, the variance of the least squared estimator of $\beta$
is

$\mathrm{Var}\left(\widehat{\beta}\right)=\sigma^{2}\left\\{{\mathbf{x}}^{\top}\left(I-F_{n}(F^{\top}_{n}F_{n})^{-1}F^{\top}_{n}\right){\mathbf{x}}\right\\}^{-1}$
(10)

where $F_{n}=\left[\mathbf{1}_{n}~{}W\mathbf{1}_{n}~{}W{\mathbf{x}}\right]$ is
an $n\times 3$ matrix and $\mathbf{1}_{n}$ is an $n$ dimensional vector loaded
with ones. It is obvious that

$\mathrm{Var}\left(\widehat{\beta}\right)\geq\frac{\sigma^{2}}{n}.$ (11)

The objective $\mathrm{Var}\left(\widehat{\beta}\right)$ is minimized if
${\mathbf{x}}^{\top}F_{n}(F^{\top}_{n}F_{n})^{-1}F^{\top}_{n}{\mathbf{x}}=0$.
Then, if $n$ is even, the sufficient condition to minimize
$\mathrm{Var}\left(\widehat{\beta}\right)$ is that

$\sum^{n}_{i=1}x_{i}=0,\quad\sum^{n}_{i=1}d_{i}x_{i}=0\quad\mathrm{and}\quad\sum^{n}_{i=1}\sum^{n}_{j=1}w_{ij}x_{i}x_{j}=0$

Through the two examples under the two scenarios, we see that the design
criteria for network A/B testing often contain three components:

$\displaystyle\mathbf{x}^{\top}W\mathbf{x}$
$\displaystyle=\sum^{n}_{i=1}\sum^{n}_{j=1}w_{ij}x_{i}x_{j},$ (12)
$\displaystyle\mathbf{x}^{\top}W\mathbf{1}_{n}$
$\displaystyle=\sum^{n}_{i=1}d_{i}x_{i},$ (13)
$\displaystyle\mathbf{x}^{\top}\mathbf{1}_{n}$
$\displaystyle=\sum^{n}_{i=1}x_{i}.$ (14)

If $|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq 1$, the design $\mathbf{x}$ is
balanced over the two treatments. If $\mathbf{x}^{\top}W\mathbf{1}_{n}=0$, the
design $\mathbf{x}$ is balanced with respect to the degrees of the network
connection of all $n$ users. Therefore, $|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq
1$ and $\mathbf{x}^{\top}W\mathbf{1}_{n}=0$ give two balanced constraints of
the designs. The objective $\mathbf{x}^{\top}W\mathbf{x}$ is minimized under
the scenario of network correlated responses, which is the objective of the
max-cut problem in (3). As noted by Pokhilko et al. (2019), the ideal case of
the optimal design is given by solving the max-cut problem with the two
balanced constraints:

$\displaystyle\mathrm{min}$ $\displaystyle\quad\mathbf{x}^{\top}W\mathbf{x}$
$\displaystyle\mathrm{s.t.}$
$\displaystyle\quad-\delta_{1}\leq\mathbf{x}^{\top}W\mathbf{1}_{n}\leq\delta_{1}$
$\displaystyle\quad-\delta_{2}\leq\mathbf{x}^{\top}\mathbf{1}_{n}\leq\delta_{2}$
$\displaystyle\quad\mathbf{x}\in\\{-1,1\\}^{n},$

for $\delta_{1}>0$ and $\delta_{2}>0$, where $\delta_{2}$ can be set to be one
if an exact balance over the two treatments is required. The objective
$\mathbf{x}^{\top}W\mathbf{x}$ should be close to zero under Scenario II. This
problem can not be directly solved as a min-cut or a max-cut problem. A
visualization of the ideal cases of the optimal designs is given by Figure 1.
The network contains 24 users, and the users form 12 pairs, with each pair of
users connected. The two colors denote the allocation of two treatments.

Figure 1: The optimal designs of A/B testing under Scenario I (Left) and
Scenario II (Right) for a network containing 24 users.

We observe that the left of Figure 1 shows an optimal design under Scenario I,
which allocates different treatments for each pair of connected users to
attain the minimized value of the objective in (12). The right of Figure 1
shows an optimal design under Scenario II. The resulting design contains three
pairs of users allocated with treatment 1, three pairs allocated with
treatment -1, and six allocated with different treatments. Therefore, the
value of the objective in (12) attains zero exactly. For an arbitrary network,
it is not guaranteed that the ideal optimal values in (8) and (11) can be
attained. Also, obtaining the exact optimal design for large social networks
without randomization can be inefficient in computation. Also, exact optimal
design without sufficient randomization can cause robustness concerns in
statistical inference (e.g., Morgan and Rubin (2012)). Next, we propose an
algorithm to obtain random designs that reduces the variance of estimated
treatment effects under each scenario.

##  2 A Random Design Algorithm for Network A/B Testing

Random designs with a certain amount of variance reduction can often be
obtained by rerandomization until satisfying some stopping criteria (e.g.,
Morgan and Rubin (2012); Li and Ding (2017)). Let

$g(\mathbf{x};W,\delta_{1},\delta_{2})=\begin{cases}1\quad\mathrm{if}\quad-\delta_{1}\leq\mathbf{x}^{\top}W\mathbf{1}_{n}\leq\delta_{1}\quad\mathrm{and}\quad-\delta_{2}\leq\mathbf{x}^{\top}\mathbf{1}_{n}\leq\delta_{2}\\\
0\quad\mathrm{o.w.}\end{cases},$ (15)

for $\delta_{1}>0$ and $\delta_{2}>0$. The value of this function indicates
whether or not the two balanced constraints are met. For Scenarios I & II, we
denote the stopping rule associated with the graph cut objectives by

$\phi_{1}(\mathbf{x};W,c)=\begin{cases}1\quad\mathrm{if}\quad\mathbf{x}^{\top}W\mathbf{x}\leq
c\\\
0\quad\mathrm{o.w.}\end{cases}\quad\mathrm{and}\quad\phi_{2}(\mathbf{x};W,c)=\begin{cases}1\quad\mathrm{if}\quad|\mathbf{x}^{\top}W\mathbf{x}|\leq
c\\\ 0\quad\mathrm{o.w.}\end{cases},$ (16)

respectively.

For given values of $\delta_{1}$, $\delta_{2}$, and $c$, we can obtain the
random design and check the values of $g(\mathbf{x};W,\delta_{1},\delta_{2})$
and $\phi_{1}(\mathbf{x};W,c)$ (or $\phi_{2}(\mathbf{x};W,c)$) in a sequence
to form a rerandomization algorithm (Pokhilko, 2019). For a stopping rule
containing two or more criteria, it can be challenging to investigate the
efficiency of the algorithm and control the running time. Therefore, we first
propose an algorithm that can generate random designs $\mathbf{x}$ under the
condition that $g(\mathbf{x};W,\delta_{1},\delta_{2})=1$ for some $\delta_{1}$
and $\delta_{2}$.

###### Algorithm 1

We obtain a random design $\mathbf{x}$ of size $n$ for a given network $W$
with degrees $d_{i}$’s.

  * Step 1:

Define

$\tilde{d}_{i}=d_{i}+u_{i},\quad\mathrm{with}\quad
u_{i}\sim\mathrm{i.i.d.}\quad U(0,1).$ (17)

Denote the rank of $\tilde{d}_{i}$ by $r_{i}$, which is taking value from 1 to
$n$.

  * Step 2:

Denote

$c_{i}=\begin{cases}\left\lfloor\frac{r_{i}}{2}\right\rfloor&\mathrm{if}\quad
n\quad\mathrm{is~{}even}\\\
\left\lfloor\frac{r_{i}-1}{2}\right\rfloor&\mathrm{if}\quad
n\quad\mathrm{is~{}odd}\end{cases},$

where $\lfloor r\rfloor$ takes the largest integer that is smaller or equal to
$r$. Then the vertexes are divided into $n/2$ or $(n+1)/2$ groups, each
sharing a common value of $c_{i}$ and with size one or two.

  * Step 3:

For the groups given by Step 2, we randomly shuffle $\\{-1,-1\\}$ within each
group independently to assign their corresponding design values for the
vertexes with $c_{i}>0$. If $n$ is odd, there will be one group containing a
single vertex with $c_{i}=0$. We randomly assigned with 1 or -1 to the user
associated with this vertex.

The purpose of step 1 is to make sure that there are no ties in the rank of
the vertexes, and in the meantime, the random variables $u_{i}$’s in step 1
provide extra randomness on the resulting design $\mathbf{x}$. The aim of step
2 and step 3 is to balance over the degrees of different vertexes. As a result
of utilizing this algorithm, $|\mathbf{x}^{\top}\mathbf{1}_{n}|$ will be set
as zero or one exactly and $\mathbf{x}^{\top}W\mathbf{1}_{n}$ will be set
close to zero by generating a vector $\mathbf{x}$ that balancing the degrees.
We state Proposition 1 below to formally demonstrate that the random design
$\mathbf{x}$ given by Algorithm 1 satisfies the balanced constraints in (15)
for some $\delta_{1}$ and $\delta_{2}$.

###### Proposition 1

Algorithm 1 leads a random design $\mathbf{x}$ that satisfying
$g(\mathbf{x};W,\delta_{1},\delta_{2})=1$ for any $\delta_{1}\geq c(W)$ and
any $\delta_{2}\geq 1$, where

$c(W)=\begin{cases}\sum^{n/2}_{i=1}\left(d_{(2i+1)}-d_{(2i)}\right)&\mathrm{if}\quad
n\quad\mathrm{is~{}even}\\\
d_{(1)}+\sum^{(n-1)/2}_{i=1}\left(d_{(2i+1)}-d_{(2i)}\right)&\mathrm{if}\quad
n\quad\mathrm{is~{}odd}\end{cases},$

with $d_{(i)}$’s be the ordered degrees based on the rank $r_{i}$’s in (17).
The value of $c(W)$ is a constant given the network adjacency matrix $W$.

The random design $\mathbf{x}$ given by Algorithm 1 meet the balanced criteria
in $g(\mathbf{x};W,\delta_{1},\delta_{2})$. By utilizing this algorithm, we
can rerandomize designs $\mathbf{x}$ to obtain a random design satisfying one
of the stopping rules in (16) for a given $c$. The proposed random design
algorithm is described below.

###### Algorithm 2

Let $T$ be the maximum number of randomizations. For $t\leq T$, we loop over
the following two steps until the stopping rule in the second step is met.

  * Step 1:

Generate a random design $\mathbf{x}_{t}$ using Algorithm 1.

  * Step 2:

Compute $\mathbf{x}^{\top}_{t}W\mathbf{x}_{t}$. For Scenario I (or II), stop
the loop if $\phi_{1}(\mathbf{x}_{t};W,c)=1$ (or
$\phi_{2}(\mathbf{x}_{t};W,c)=1$ for Scenario II) is satisfied.

For $t<T$, return the design $\mathbf{x}_{t}$. For $t=T$, return the design
$\mathbf{x}_{t^{\ast}}$ with

$t^{\ast}=\begin{cases}\mathrm{argmin}_{t=1,\ldots,T}\mathbf{x}^{\top}_{t}W\mathbf{x}_{t}&\mathrm{for~{}Scenario~{}I}\\\
\mathrm{argmin}_{t=1,\ldots,T}|\mathbf{x}^{\top}_{t}W\mathbf{x}_{t}|&\mathrm{for~{}Scenario~{}II}\\\
\end{cases}$

This algorithm is provided for a given threshold value $c$ for (16) and some
specific values of $\delta_{1}$ and $\delta_{2}$ in Proposition 1. It is
important to understand how small those values are compared with the
distributions of the objectives in (14) under random designs. In the next
section, we propose some asymptotic results to support the investigation of
their distributions with random designs.

##  3 Asymptotic Results on the Graph Cut Objectives

Proposition 1 gives the sufficient lower bounds of $\delta_{1}$ and
$\delta_{2}$ given by Algorithm 1. In practice, the value of
$\mathbf{x}^{\top}W\mathbf{1}_{n}$ given by this randomization algorithm can
be smaller than $c(W)$. Although Proposition 1 specifies some values of
$\delta_{1}$ and $\delta_{2}$ that meet the balanced constraints in (15), it
is also necessary to justify how small those values are compared with the
results from complete random designs. First of all, the value of
$|\mathbf{x}^{\top}\mathbf{1}_{n}|$ given by Algorithm 1 is taking the minimum
possible value. Given that $|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq 1$, we now
develop the asymptotic distribution of $\mathbf{x}^{\top}W\mathbf{1}_{n}$ to
compare the lower bound of $\delta_{1}$ for justification purpose.

###### Proposition 2

For a random allocation of $\mathbf{x}$ satisfying
$|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq 1$, and

$\frac{\mathrm{max}_{1\leq i\leq
n}(d_{i}-\bar{d})^{2}}{\sum^{n}_{i=1}(d_{i}-\bar{d})^{2}}\rightarrow
0,\quad\mathrm{with}\quad\bar{d}=n^{-1}\sum^{n}_{i=1}d_{i}$

as $n\rightarrow\infty$, we have that

$\frac{\sum^{n}_{i=1}d_{i}x_{i}}{\sqrt{\sum^{n}_{i=1}(d_{i}-\bar{d})^{2}}}\rightarrow
N(0,1)$

in distribution as $n\rightarrow\infty$.

The asymptotic distribution is used to compute the probability of more extreme
cases compared to a given threshold value $c$

$\mathrm{P}\left(\left|\mathbf{x}^{\top}W\mathbf{1}_{n}\right|\leq
c\Bigg{\rvert}|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq 1\right)\approx
2\Phi\left(\frac{c}{\sqrt{\sum^{n}_{i=1}(d_{i}-\bar{d})^{2}}}\right)-1$ (18)

where $\Phi(\cdot)$ is the CDF of the standard normal distribution. Once the
network adjacency matrix $W$ is given, we are able to compute this
probability. For example, by specifying $c=c(W)$, the above probability tells
the possibility of a random design $\mathbf{x}$ satisfying
$|\mathbf{x}^{\top}W\mathbf{1}_{n}|\leq c(W)$ given that
$|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq 1$. Also, given a specific design
$\mathbf{x}_{0}$, we can specify $c=\mathbf{x}^{\top}_{0}W\mathbf{1}_{n}$ to
validate if this design can lead to a sufficiently small value.

For both scenarios, the value of $c$ can be chosen as a smaller quantile
according to the distributions of the graph cut objective
$\mathbf{x}^{\top}W\mathbf{x}$ or $|\mathbf{x}^{\top}W\mathbf{x}|$ for a
random design $\mathbf{x}$ generated from Algorithm 1. We first define some
convenient notation and then provide the asymptotic distribution of
$\mathbf{x}^{\top}W\mathbf{x}$. Let $\tilde{W}$ be the adjacency matrix
reorder by $r_{i}$ in (17) from the smallest to the largest. If $n$ is an odd
number, $r_{i}=1$ is removed before reordering. Then the size of $\tilde{W}$
is even. We further define

$W_{0}=\left(\mathbf{I}\otimes[1,-1]\right)\tilde{W}\left(\mathbf{I}\otimes[1,-1]^{\top}\right)$
(19)

with $\mathbf{I}$ be the identity matrix with size $n/2$ or $(n-1)/2$ for $n$
being even or odd.

###### Proposition 3

Given $W_{0}$ in (19), we assume that

$\frac{\mathrm{min}_{i=1,\ldots,n}d_{i}}{\sum_{i\neq
j}w^{2}_{0,ij}}\rightarrow
0\quad\mathrm{and}\quad\frac{\lambda_{\mathrm{max}}(\tilde{W}_{0})}{\sqrt{\sum_{i\neq
j}w^{2}_{0,ij}}}\rightarrow 0\quad\mathrm{as}\quad n\rightarrow\infty,$

where $\tilde{W}_{0}$ is a matrix with off-diagonal entries equal to the
corresponding entries of $W_{0}$ in (19), and diagonal entries equal to 0 and
$w_{0,ij}$ is the $i,j$-th entry of $W_{0}$ in (19). The notation
$\lambda_{\mathrm{max}}(A)$ gives the maximum eigenvalue of a symmetric matrix
$A$. Then we have that

$\frac{\mathbf{x}^{\top}W\mathbf{x}-\mathrm{trace}(W_{0})}{2\sqrt{\sum_{i<j}w^{2}_{0,ij}}}\rightarrow
N(0,1)$

in distribution as $n\rightarrow\infty$.

Under this proposition, we can set $c$ in Algorithm 2 based on the asymptotic
normal distribution

$\mathbf{x}^{\top}W\mathbf{x}\sim
AN\left(\mathrm{trace}(W_{0}),4\sum_{i<j}w^{2}_{0,ij}\right)$

For $\phi_{1}$, we set the stopping threshold as the $\alpha$-th quantile of
$\mathbf{x}^{\top}W\mathbf{x}$, i.e.

$c=\mathrm{trace}(W_{0})+2\sqrt{\sum_{i<j}w^{2}_{0,ij}}\Phi^{-1}(\alpha),$

where $\Phi^{-1}$ is the inverse function of the standard normal cumulative
distribution function. For $\phi_{2}$, we set the stopping threshold as the
$\alpha$-th quantile of $|\mathbf{x}^{\top}W\mathbf{x}|$, which asymptotically
follows the folded normal distribution with parameters $\mathrm{trace}(W_{0})$
and $4\sum_{i<j}w^{2}_{0,ij}$. Therefore, the process of rerandomization in
Algorithm 2 constructs a Geometric distribution with the success probability
approximated by $\alpha$. Then we can set the maximum number of randomization
$T$ according to this distribution. Throughout the numerical results of this
paper, we set $T=5000$, $\alpha=0.005$ for Scenario I, and $\alpha=0.1$ for
Scenario II.

##  4 Numerical Study

We evaluate the performances of the proposed design approach by computing two
performance measures. We first generate 1000 random balanced designs
satisfying that $\sum^{n}_{i=1}x_{i}=0$, where $n$ is set to be an even number
in the numerical study for convenience. We compute the percentile of
$\mathrm{Var}(\widehat{\beta})$ led by the proposed design approach among the
variances from the 1000 random designs:

$\mathrm{Percentile}=\frac{\sum^{1000}_{i=1}I(v_{i}\leq v_{opt})}{1000},$ (20)

where $v_{i}$’s are the variances of $\widehat{\beta}$ led by the 1000 random
balanced designs, whereas $v_{opt}$ is that led by the proposed design
approach. We also compute the optimality gap of the proposed design with
respect to the lower bounds (denoted by $v_{lb}$) given by (8) and (11):

$\mathrm{Gap}=1-\frac{v_{lb}}{v_{opt}}.$ (21)

For comparison purposes, we compute the optimality gap of the median variance
of the 1000 random balanced designs:
$\mathrm{Gap_{median}}=1-v_{lb}/v_{median}$ with $v_{median}$ be the median
variance.

###  4.1 Example I: Synthetic Networks

In this section, we evaluate the performances of the proposed approach using
synthetic networks. Given the total number of vertexes $n$ and network density
$p$, for $i<j$, $w_{ij}$’s are generated as iid Bernoulli random variables
with the probability equal to one be $p$. We remove the isolated vertexes, so
the actual size of the generated network can be smaller than $n$. For
convenience of implementation, we force the resulting size of the network to
be even.

We first check the probability in (18) for the synthetic networks. The results
are depicted in Figure 2. In the left of Figure 2, we set $c$ in (18) be
$c(W)$. The results show that the probability of the upper bound is at most
0.1 for networks with a size above 1000, but for networks with a size 100 and
smaller density, the probability might be as high as 0.5. For networks with
size 1000 or above, the guaranteed upper bound $c(W)$ for
$\sum^{n}_{i=1}d_{i}x_{i}$ is small with respect to its asymptotic
distribution. In the right of Figure 2, we set $c$ in (18) be
$\sum^{n}_{i=1}d_{i}x_{i}$ with 100 copies of the design $\mathbf{x}$
generated by Algorithm 1. The average probability values are reported. The
actual values of $\sum^{n}_{i=1}d_{i}x_{i}$ can be significantly smaller than
its upper bound $c(W)$ with small probability values compared to their
asymptotic distributions.

Figure 2: The resulting probability in (18) with $c=c(W)$ (left, probability
of upper bound) and and the average probability of
$c=|\sum^{n}_{i=1}d_{i}x_{i}|$ (right, ave probability of the actual values)
for 100 random designs generated by Algorithm 1 with synthetic networks.

Next, we compute the Percentile and Gap in (20) and (21) for the designs
generated by the proposed method. The results of Scenarios I and II are given
in Table 1. We vary the size of network $n$ and network density $p$, and
generate ten networks under each setting. In the results, we provide the
averages of Percentile and Gap over the ten networks under each setting. For
comparison purposes, we also give the average value of
$\mathrm{Gap}_{\mathrm{median}}$ in the tables. For Scenario I, all the
percentiles are below 0.004, which shows that the variance led by the proposed
design is nearly optimal among the 1000 random designs. And the Gap values of
the proposed design are all smaller than $\mathrm{Gap}_{\mathrm{median}}$. The
advantage of the proposed design in terms of Gap becomes smaller for $n$
larger than 1000. For Scenario II, the percentiles of the proposed design
approach are around 0.01 for smaller $n$ and drop to around 0.005 for larger
$n$. The Gap values are smaller than in the case of Scenario I. For $n=1000$
and 2000, the Gap values to the ideal designs are nearly zero.

Table 1: Averages of Percentile, Gap, and $\mathrm{Gap}_{\mathrm{median}}$ over ten generated networks under each setting Scenario | $n$ | $p$ | Percentile | Gap | $\mathrm{Gap}_{\mathrm{median}}$
---|---|---|---|---|---
| 50 | 0.1 | 0.0021 | 0.2471 | 0.3278
|  | 0.3 | 0.0032 | 0.2836 | 0.3271
| 100 | 0.1 | 0.0019 | 0.2853 | 0.3302
I |  | 0.3 | 0.0027 | 0.3080 | 0.3299
| 1000 | 0.01 | 0.0019 | 0.3191 | 0.3331
|  | 0.1 | 0.0024 | 0.3289 | 0.3330
| 2000 | 0.01 | 0.0028 | 0.3267 | 0.3332
|  | 0.1 | 0.0033 | 0.3311 | 0.3332
| 50 | 0.1 | 0.0120 | 0.0005 | 0.0448
|  | 0.3 | 0.0145 | 0.0011 | 0.0466
| 100 | 0.1 | 0.0153 | 0.0004 | 0.0211
II |  | 0.3 | 0.0080 | 0.0003 | 0.0228
| 1000 | 0.01 | 0.0046 | 0.0000 | 0.0020
|  | 0.1 | 0.0053 | 0.0000 | 0.0021
| 2000 | 0.01 | 0.0037 | 0.0000 | 0.0010
|  | 0.1 | 0.0051 | 0.0000 | 0.0010

###  4.2 Example II: Real Networks from Facebook

We evaluate the performances of the proposed method using real networks from
Facebook (Leskovec and Mcauley, 2012). This data contains ten sampled social
networks collected from survey participants using Facebook app. After removing
completely isolated users, the sizes of the ten networks range from 52 to 1034
and the network densities range from 0.034 to 0.150. Similar to Figure 2, we
first check the probability of more extreme situations given by the upper
bound $c(W)$ and the actual values of $|\sum^{n}_{i=1}d_{i}x_{i}|$ for 100
random designs from Algorithm 1 in Figure 3. The figure shows that the
resulting design given by this Algorithm can achieve smaller values of
$|\sum^{n}_{i=1}d_{i}x_{i}|$ to balance over the degrees of vertexes.

Figure 3: The resulting probability in (18) with $c=c(W)$ (left, probability
of upper bound) and the average probability of $c=|\sum^{n}_{i=1}d_{i}x_{i}|$
(right, ave probability of the actual values) for 100 random designs generated
by Algorithm 1 with the ten sampled networks from Facebook

For both Scenarios, the percentile values of the ten networks are given in
Figure 4, whereas the gap values are given in Figure 5. The percentiles of
Scenario I are all below 0.0025, whereas the percentiles of Scenario II are
all below 0.015, which shows that the proposed design leads to smaller
variance than the variances from complete random designs. The comparison of
Gap and $\mathrm{Gap}_{\mathrm{median}}$ is similar to the synthetic networks.

Figure 4: The percentile in (20) for the ten sampled networks from Facebook
Figure 5: The Gap (opt, blue triangles) and $\mathrm{Gap}_{\mathrm{median}}$
(median, red dots) in (21) for the ten sampled networks from Facebook

##  5 Conclusion

This paper discovered the relationship between the design criteria of network
A/B testing and graph cut objectives. We developed asymptotic distributions of
two graph cut objectives to enable rerandomization algorithms to design
network A/B testing. The numerical results show that the proposed algorithm
effectively generates random designs under certain constraints to reduce the
variance of parameter estimation from complete random designs. The proposed
asymptotic results can also serve as stopping rules of other random algorithms
for graph cut-related problems.

## Appendix: Proofs and Additional Numerical Validation

### Proof of Proposition 1

Note that $d_{(i)}$’s are the ordered degrees based on the rank $r_{i}$’s in
(17). Therefore, for $i<i^{\prime}$, $d_{(i)}\leq d_{(i^{\prime})}$. If $n$ is
an even number, after applying this algorithm, we have that

$\sum^{n}_{i=1}x_{i}d_{i}=\sum^{n}_{i=1}x_{i}d_{(i)}=\sum^{n/2}_{i=1}\left[d_{(2i)}x_{2i}-d_{(2i-1)}x_{2i-1}\right],$

where $x_{2i}$ and $x_{2i-1}$ are assigned to different treatments, 1 or -1.
We can express

$\sum^{n}_{i=1}x_{i}d_{i}=\sum^{n/2}_{i=1}\left[d_{(2i)}-d_{(2i-1)}\right]z_{i},$

with $z_{i}\in\\{-1,1\\}$. Then, we have that

$-\sum^{n/2}_{i=1}\left[d_{(2i)}-d_{(2i-1)}\right]\leq\mathbf{x}^{\top}W\mathbf{1}_{n}\leq\sum^{n/2}_{i=1}\left[d_{(2i)}-d_{(2i-1)}\right]$

and

$\mathbf{x}^{\top}\mathbf{1}_{n}=0.$

If $n$ is an odd number, we have that

$-d_{(1)}-\sum^{(n-1)/2}_{i=1}\left(d_{(2i+1)}-d_{(2i)}\right)\leq\mathbf{x}^{\top}W\mathbf{1}_{n}\leq
d_{(1)}+\sum^{(n-1)/2}_{i=1}\left(d_{(2i+1)}-d_{(2i)}\right)$

and

$-1\leq\mathbf{x}^{\top}\mathbf{1}_{n}\leq 1.$

We denote

$c(W)=\begin{cases}\sum^{n/2}_{i=1}\left(d_{(2i+1)}-d_{(2i)}\right)&\mathrm{if}\quad
n\quad\mathrm{is~{}even}\\\
d_{(1)}+\sum^{(n-1)/2}_{i=1}\left(d_{(2i+1)}-d_{(2i)}\right)&\mathrm{if}\quad
n\quad\mathrm{is~{}odd}\end{cases},$

then the conclusion holds.

### Proof of Proposition 2

Note that the asymptotic results for $\sum^{n}_{i=1}d_{i}x_{i}$ is described
in Pokhilko (2019) under random allocations without
$|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq 1$ constraint. Under
$|\mathbf{x}^{\top}\mathbf{1}_{n}|\leq 1$, we derive the asymptotic
distribution based on finite population asympototics (Li and Ding, 2017). We
first state a Lemma to support the proof of Proposition 2.

###### Lemma 1

Let $z_{n}$ be a sequence of random variables that converge in distribution to
the standard normal distribution. Let $s$ be a binary random variable with

$\mathrm{P}(s=1)=\mathrm{P}(s=-1)=\frac{1}{2},$

and $s$ is independent with $z_{n}$. Then $g_{n}=sz_{n}$ converges in
distribution to the standard.

Proof:  Let $\Phi(t)$ be the cumulative distribution function (CDF) of
$\mathcal{N}(0,1)$. The CDF of $g_{n}$ is

$\displaystyle\mathrm{P}(sz_{n}\leq t)$ $\displaystyle=\mathrm{P}(sz_{n}\leq
t|s=1)\mathrm{P}(s=1)+\mathrm{P}(sz_{n}\leq t|s=-1)\mathrm{P}(s=-1)$
$\displaystyle=\frac{1}{2}\left[\mathrm{P}(z_{n}\leq
t)+\mathrm{P}(z_{n}\geq-t)\right]$

Since $z_{n}$ converges in distribution to $N(0,1)$, we have that

$\mathrm{P}(z_{n}\leq
t)\rightarrow\Phi(t)\quad\mathrm{and}\quad\mathrm{P}(z_{n}\geq-t)\rightarrow
1-\Phi(-t)=\Phi(t)$

as $n\rightarrow\infty$. Accordingly, $\mathrm{P}(z_{n}\leq
t)\rightarrow\Phi(t)$ as $n\rightarrow\infty$. The conclusion holds.

We now state proof of Proposition 2. We first assume that the $n$ vertexes
have been randomly split into two balanced groups with sizes $n_{1}$ and
$n_{2}$. Without loss of generality, we assume that $n_{1}=n_{2}=n/2$ if $n$
is even, whereas $n_{1}=n_{2}+1=(n+1)/2$ if $n$ is odd. Let $\bar{d}_{1}$ and
$\bar{d}_{2}$ be the average degrees of the vertexes in the first and second
groups, respectively. Then, according to Theorem 1 in Li and Ding (2017), we
have that

$\frac{\bar{d}_{1}-\bar{d}}{\sqrt{\mathrm{Var}(\bar{d}_{1})}}\rightarrow
N(0,1)$

in distribution as $n\rightarrow\infty$ under the assumptions given in this
proposition. Note that
$\mathrm{Var}(\bar{d}_{1})=(n^{-1}_{1}-n^{-1})(n-1)^{-1}\sum^{n}_{i=1}(d_{i}-\bar{d})^{2}$.
Therefore, we have that

$\frac{n_{1}\bar{d}_{1}-n_{2}\bar{d}_{2}}{\sqrt{\sum^{n}_{i=1}(d_{i}-\bar{d})^{2}}}=\frac{2n_{1}\bar{d}_{1}-n\bar{d}}{\sqrt{\sum^{n}_{i=1}(d_{i}-\bar{d})^{2}}}=\frac{2n_{1}}{\sqrt{(n-1)n_{1}n/n_{2}}}\frac{\bar{d}_{1}-\bar{d}}{\sqrt{\mathrm{Var}(\bar{d}_{1})}}+\frac{2n_{1}-n}{\sqrt{(n-1)n_{1}n/n_{2}}}\frac{\bar{d}}{\sqrt{\mathrm{Var}(\bar{d}_{1})}}$

As $n\rightarrow\infty$,

$\frac{2n_{1}}{\sqrt{(n-1)n_{1}n/n_{2}}}\rightarrow
1\quad\mathrm{and}\quad\frac{2n_{1}-n}{\sqrt{(n-1)n_{1}n/n_{2}}}\rightarrow 0$

Therefore,

$\frac{n_{1}\bar{d}_{1}-n_{2}\bar{d}_{2}}{\sqrt{\sum^{n}_{i=1}(d_{i}-\bar{d})^{2}}}\rightarrow
N(0,1)$

in distribution as $n\rightarrow\infty$. A random allocation of the design
vector $\mathbf{x}$ with the balanced constraint can be equivalently
implemented by a random split with fixed size $n_{1}$ and $n_{2}$ and then
randomize 1 and -1 over the two groups. Therefore, the conclusion holds
according to Lemma 1.

### Proof of Proposition 3

Notice that the entries in $\mathbf{x}$ from Algorithm 1 are dependent. Then,
it is not straightforward to develop the distribution of
$\mathbf{x}^{\top}W\mathbf{x}$ directly. To investigate this, we first provide
an alternative expression of the objective $\mathbf{x}^{\top}W\mathbf{x}$ to
simplify the derivation of the asymptotic distribution of
$\mathbf{x}^{\top}W\mathbf{x}$ in the following proposition for the case with
an even value of $n$.

###### Lemma 2

Assume that $n$ is even. Let $\mathbf{z}=(z_{1},\ldots,z_{n/2})^{\top}$ with
$z_{i}\in\\{-1,1\\}$ for $i=1,\ldots,n/2$. Denote
$\mathbf{x}=\mathbf{z}\otimes[1,-1]^{\top}$. We have that

$\mathbf{x}^{\top}W\mathbf{x}=\mathbf{z}^{\top}\left(\mathbf{I}_{n/2}\otimes[1,-1]\right)W\left(\mathbf{I}_{n/2}\otimes[1,-1]^{\top}\right)\mathbf{z}.$

The conclusion of this Lemma is obvious, since
$\left(\mathbf{I}\otimes[1,-1]^{\top}\right)\mathbf{z}=\mathbf{x}$.

For a random design $\mathbf{x}$ given by Algorithm 1, we reordered by
$r_{i}$s in (17) from the smallest to the largest. Denote $\tilde{\mathbf{x}}$
be the reordered random design. According to the definition of $\tilde{W}$ and
$W_{0}$ in (19) and Algorithm 1, we have that

$\mathbf{x}^{\top}W\mathbf{x}=\tilde{\mathbf{x}}^{\top}\tilde{W}\tilde{\mathbf{x}}=\mathbf{z}^{\top}W_{0}\mathbf{z},$

where $\mathbf{z}\in\\{-1,1\\}^{n/2}$ is a random vector representing the
independent random shuffle of $\\{-1,1\\}$ within each group in Step 3 of
Algorithm 1. Therefore, we can alternatively evaluate the asymptotic
distribution of $\mathbf{z}^{\top}W_{0}\mathbf{z}$ with the entries of
$\mathbf{z}$ being iid random variable.

We consider $\mathbf{z}=(z_{1},\ldots,z_{n/2})^{\top}$ be independent and
identically distributed from the distribution with
$\mathbb{P}(z_{i}=1)=\mathbb{P}(z_{i}=-1)=0.5$. Then

$\mathbb{E}(z_{i})=0,\quad\mathrm{Var}(z_{i})=1,\quad\mathbb{E}|z_{i}|^{3}=1.$

Let $A$ be a matrix with $ij$-th element
$a_{ij}=\frac{w_{0,ij}}{\sqrt{\sum_{i\neq j}w^{2}_{0,ij}}}$ if $i\neq j$, and
$a_{ii}=0$ for $i=1,\ldots,n/2$. We have that

$\sum_{ij}a^{2}_{ij}=\frac{\sum_{i\neq j}w^{2}_{0,ij}}{\sum_{i\neq
j}w^{2}_{0,ij}}=1$

According to Theorem 1 in Gotze and Tikhomirov (1999), we have that

$\sup_{u}\left\lvert\mathbb{P}\left(\frac{\mathbf{z}^{\top}A\mathbf{z}}{\sqrt{\mathrm{Var}(\mathbf{z}^{\top}A\mathbf{z}})}\leq
u\right)-\Phi(u)\right\rvert\leq C|\lambda_{\mathrm{max}}(A)|,$

for some constant $C$. Since

$\lambda_{\mathrm{max}}(A)=\frac{\lambda_{\mathrm{max}}(\tilde{W}_{0})}{\sqrt{\sum_{i\neq
j}w^{2}_{0,ij}}},$

we have that

$\frac{\mathbf{x}^{\top}W\mathbf{x}-\mathrm{E}\left(\mathbf{z}^{\top}W_{0}\mathbf{z}\right)}{\sqrt{\mathrm{Var}(\mathbf{z}^{\top}W_{0}\mathbf{z}})}=\frac{\mathbf{z}^{\top}W_{0}\mathbf{z}-\mathrm{E}\left(\mathbf{z}^{\top}W_{0}\mathbf{z}\right)}{\sqrt{\mathrm{Var}(\mathbf{z}^{\top}W_{0}\mathbf{z}})}=\frac{\mathbf{z}^{\top}\tilde{W}_{0}\mathbf{z}}{\sqrt{\mathrm{Var}(\mathbf{z}^{\top}\tilde{W}_{0}\mathbf{z}})}=\frac{\mathbf{z}^{\top}A\mathbf{z}}{\sqrt{\mathrm{Var}(\mathbf{z}^{\top}A\mathbf{z}})}\rightarrow
N(0,1)$

in distribution as $n\rightarrow\infty$. We see that

$\mathrm{E}\left(\mathbf{z}^{\top}W_{0}\mathbf{z}\right)=\mathrm{trace}(W_{0})$

and

$\mathrm{Var}(\mathbf{z}^{\top}W_{0}\mathbf{z})=4\sum_{i<j}w^{2}_{0,ij}$

which concludes the case for $n$ being even.

If $n$ is an odd number, the difference between the original objective and the
alternative expression comes from the vertex with the minimum degree. We have
that

$\mathbf{x}^{\top}W\mathbf{x}=\tilde{\mathbf{x}}^{\top}\tilde{W}\tilde{\mathbf{x}}+2x_{i_{1}}\sum_{j\neq
i_{1}}w_{i_{1},j}x_{j}=\mathbf{z}^{\top}W_{0}\mathbf{z}+2x_{i_{1}}\sum^{n}_{j=1}w_{i_{1},j}x_{j},$

where $i_{1}$ is the index of the vertex with the smallest $\tilde{d}_{i}$ and
$x_{i_{1}}$ is randomly allocated with 1 or -1 independent with $x_{j}$ for
$j\neq i_{1}$. Let $d_{(1)}=\mathrm{min}_{i=1,\ldots,n}d_{i}$. Note that

$d_{(1)}\left(1-\frac{d_{(1)}}{n-1}\right)\leq\mathrm{Var}\left(x_{i_{1}}\sum^{n}_{j=1}w_{i_{1},j}x_{j}\right)\leq\sum^{n}_{j=1}w_{i_{1},j}=d_{(1)}.$

Then if $d_{(1)}/{\sum_{i<j}w^{2}_{0,ij}}\rightarrow 0$ holds

$\frac{x_{i_{1}}\sum^{n}_{j=1}w_{i_{1},j}x_{j}}{\sqrt{\sum_{i<j}w^{2}_{0,ij}}}\rightarrow
0\quad\mathrm{as}\quad n\rightarrow\infty$

in probability. We also have the conclusion holds for $n$ being odd. This
concludes the proof.

### Numerical Validation of the Assumptions in Proposition 3

In this section, we provide numerical validation for the assumptions in
Proposition 3. We generate random networks as in Section 4.1. We vary the
values of $n$ (size of network) from 100 to 5000, and the values of network
density as 0.01, 0.1, and 0.3. Left of Figure 6 shows how
$\mathrm{min}_{i=1,\ldots,n}d_{i}/\sum_{i\neq j}w^{2}_{0,ij}$ change with the
size of network and network density, whereas right of Figure 6 shows how
$\lambda_{max}(\tilde{W}_{0})/\sqrt{\sum_{i\neq j}w^{2}_{0,ij}}$ change with
the size of network and network density. The trends in the Figures show
evidences of the convergences of those values for randomly generated networks
as in Section 4.1.

Figure 6: The probability of the constraint in (18) for generated networks
with different sizes and network densities.

## References

  * Basse and Airoldi (2018) Basse, G. W. and Airoldi, E. M. (2018), “Model-assisted design of experiments in the presence of network-correlated outcomes,” Biometrika, 105, 849–858.
  * Ben-Tal and Nemirovski (2001) Ben-Tal, A. and Nemirovski, A. (2001), Lectures on modern convex optimization: analysis, algorithms, and engineering applications, SIAM.
  * Besag (1974) Besag, J. (1974), “Spatial interaction and the statistical analysis of lattice systems,” Journal of the Royal Statistical Society: Series B (Methodological), 36, 192–225.
  * Gotze and Tikhomirov (1999) Gotze, F. and Tikhomirov, A. N. (1999), “Asymptotic distribution of quadratic forms,” Annals of probability, 1072–1098.
  * Gross and Yellen (2005) Gross, J. L. and Yellen, J. (2005), Graph theory and its applications, CRC press.
  * Gui et al. (2015) Gui, H., Xu, Y., Bhasin, A., and Han, J. (2015), “Network a/b testing: From sampling to estimation,” in Proceedings of the 24th International Conference on World Wide Web, pp. 399–409.
  * Larsen et al. (2023) Larsen, N., Stallrich, J., Sengupta, S., Deng, A., Kohavi, R., and Stevens, N. T. (2023), “Statistical challenges in online controlled experiments: A review of a/b testing methodology,” The American Statistician, 1–32.
  * Lawler (2001) Lawler, E. L. (2001), Combinatorial optimization: networks and matroids, Courier Corporation.
  * Leskovec and Mcauley (2012) Leskovec, J. and Mcauley, J. (2012), “Learning to discover social circles in ego networks,” Advances in neural information processing systems, 25.
  * Li and Ding (2017) Li, X. and Ding, P. (2017), “General forms of finite population central limit theorems with applications to causal inference,” Journal of the American Statistical Association, 112, 1759–1769.
  * Morgan and Rubin (2012) Morgan, K. L. and Rubin, D. B. (2012), “Rerandomization to improve covariate balance in experiments,” The Annals of Statistics, 40, 1263–1282.
  * Parker et al. (2017) Parker, B. M., Gilmour, S. G., and Schormans, J. (2017), “Optimal design of experiments on connected units with application to social networks,” Journal of the Royal Statistical Society. Series C (Applied Statistics), 455–480.
  * Pokhilko et al. (2019) Pokhilko, V., Zhang, Q., Kang, L., and Mays, D. (2019), “D-optimal Design for Network A/B Testing,” Journal of Statistical Theory and Practice, 13.
  * Pokhilko (2019) Pokhilko, V. V. (2019), “Statistical Designs for Network A/B Testing,” Ph.D. thesis, Virginia Commonwealth University.
  * Zhang and Kang (2022) Zhang, Q. and Kang, L. (2022), “Locally Optimal Design for A/B Tests in the Presence of Covariates and Network Dependence,” Technometrics, 64, 358–369.