key: cord-0458700-m072rq8g
authors: Li, Wenrui; Sussman, Daniel L.; Kolaczyk, Eric D.
title: Estimation of the Epidemic Branching Factor in Noisy Contact Networks
date: 2020-02-13
journal: nan
DOI: nan
sha: e1c358df289df682026f25cc89bcb8a27e122533
doc_id: 458700
cord_uid: m072rq8g

Many fundamental concepts in network-based epidemic models depend on the branching factor, which captures a sense of dispersion in the network connectivity and quantifies the rate of spreading across the network. Moreover, contact network information generally is available only up to some level of error. We study the propagation of such errors to the estimation of the branching factor. Specifically, we characterize the impact of network noise on the bias and variance of the observed branching factor for arbitrary true networks, with examples in sparse, dense, homogeneous and inhomogeneous networks. In addition, we propose two estimators, by method-of-moments and bootstrap sampling. We illustrate the practical performance of our estimators through simulation studies and social contact networks in British secondary schools.

The branching factor, κ, is a measure of heterogeneity of a network. It captures a notion of the average degree of the vertex reached by following an edge from a vertex and, therefore, measures the rate of spreading across the network. Many key concepts in mathematical epidemiology depend on the branching factor, for example, the basic reproduction number R 0 . The latter is generally defined as the number of secondary infections expected in the early stages of an epidemic by a single infective in a population of susceptibles (Anderson and May, 1991; Diekmann and Heesterbeek, 2000) . In network-based susceptible-infected-removed (SIR) models, R 0 can be shown to equal θ(κ − 1)/(θ + γ), where θ and γ are infection and recovery rates, respectively (Andersson (1997) ). The importance of R 0 in the study of epidemics arises from its role in so-called threshold theorems, which state under which conditions the presence of an infective individual in a population will lead to an epidemic (Whittle, 1955) . It is evident that knowing the value of κ is vital for effective control responses in the early stages of an epidemic. In addition, various thresholds in epidemiological and percolation theory rely on the branching factor. In the discussion section, we provide details on how our estimation of the branching factor can be extended to those statistics.

Increasingly, contact networks are playing an important role in the study of epidemiology. Knowledge of the structure of the network allows models to take into account individual-level behavioral heterogeneities and shifts. Network-based approaches have been explored for investigating disease outbreaks in human (Eubank et al. (2004) ), livestock (Kao et al. (2006) ) and wildlife (Craft et al. (2009)) populations. Moreover, contact network information generally is available only up to some level of error -also known as, network noise. For example, there is often measurement error associated with network constructions, where, by 'measurement error' we will mean true edges being observed as non-edges, and vice versa. Such edge noise occurs in self-reported contact networks where participants may not perceive and recall all contacts correctly (Smieszek et al. (2012) ). It can also be found in sensor-based contact networks where automated proximity loggers are used to report frequency and duration of contacts. (Drewe et al. (2012) ). We investigate how network noise impacts on the observed value of κ and, therefore, on our understanding of infectious diseases spreading.

Extensive work regarding uncertainty quantification has been done in the field of non-network epidemic modeling, where populations are assumed uniform and with homogeneous mixing. Given adequate data, estimates of the model parameters, such as θ and γ, can be produced with accompanying standard errors. Methods for this purpose are reviewed in Andersson and Britton (2012, Chapter 9-12) and Becker and Britton (1999) . Many studies have explored the effects of uncertainty in parameter estimation on basic epidemic quantities. For instance, there have been efforts to quantify uncertainty in R 0 around recent high profile emergent events, including severe acute respiratory syndrome (SARS) (Chowell et al. (2004a) ), the new influenza A (H1N1) (White et al. (2009)) , and Ebola ( Chowell et al. (2004b) ). But, to our best knowledge, there has been little attention to date given towards uncertainty analysis of κ and relevant quantities in network-based epidemic models. Exceptions include real-time estimation of R 0 at an early stage of an outbreak by considering the heterogeneity in contact networks (Davoudi et al. (2012) ), and measurability of R 0 in highly detailed sociodemographic data with the clustered contact structure assumed of the population (Liu et al. (2018) ).

As remarked above, there appears to be little in the way of a formal and general treatment of the error propagation problem in network-based epidemic models. However, there are several areas in which the probabilistic or statistical treatment of uncertainty enters prominently in network analysis. Model-based approaches include statistical methodology for predicting network topology or attributes with models that explicitly include a component for network noise (Jiang et al. (2011) , Jiang and Kolaczyk (2012) ), the 'denoising' of noisy networks (Chatterjee et al. (2015) ), and the adaptation of methods for vertex classification using networks observed with errors (Priebe et al. (2015) ). The other common approach to network noise is based on a 'signal plus noise' perspective. For example, Balachandran et al. (2017) introduced a simple model for noisy networks that, conditional on some true underlying network, assumed we observed a version of that network corrupted by an independent random noise that effectively flips the status of (non)edges. Later, Chang et al. (2018) developed method-of-moments estimators for the underlying rates of error when replicates of the observed network are available. In a somewhat different direction, uncertainty in network construction due to sampling has also been studied in some depth. See, for example, Kolaczyk (2009, Chapter 5) or Ahmed et al. (2014) for surveys of this area. However, in this setting, the uncertainty arises only from sampling-the subset of vertices and edges obtained through sampling are typically assumed to be observed without error.

Our contribution in this paper is to quantify how such errors propagate to the estimation of the branching factor, and to provide estimators for κ when replicates of the observed network are available. Adopting the noise model proposed by Balachandran et al. (2017) , we characterize the impact of network noise on the bias and variance of the observed branching factor for arbitrary true networks, and we illustrate the asymptotic behaviors on networks for varying densities and degree distributions. Additionally, we propose two estimators of the branching factor, by parametric and nonparametric approaches. The parametric estimate is motivated by Chang et al. (2018) , who recently developed method-of-moments estimators for network subgraph densities and the underlying rates of error when replicates of the observed network are available. The nonparametric approach is based on bootstrap sampling, inspired by Kucharski et al. (2018) . Numerical simulation suggests that high accuracy is possible for networks of even modest size. We illustrate the practical use of our estimators in the context of social contact networks in British secondary schools, where a small number of replicates are available.

The organization of this paper is as follows. In Section 2 we provide background on the noise model and branching factor. In Section 3 we then present a general result for the bias of the observed branching factor, with examples provided for sparse, dense, homogeneous and inhomogeneous networks. Section 4 deals with the variance of the observed branching factor. Section 5 proposes our two estimators for the true branching factor. Numerical illustration is reported in Section 6. Proofs of our key results can be found in the appendix. All other proofs are relegated to supplementary materials.

In this section, we provide essential notation and background.

We assume the observed graph is a noisy version of a true graph. Let G = (V, E) be an undirected graph and G obs = (V, E obs ) be the observed graph, where we implicitly assume that the vertex set V is known. Denote the adjacency matrix of G by A = (A i,j ) Nv×Nv and that of G obs byà = (à i,j ) Nv×Nv . Hence A i,j = 1 if there is a true edge between the i-th vertex and the j-th vertex, and 0 otherwise, whilẽ A i,j = 1 if an edge is observed between the i-th vertex and the j-th vertex, and 0 otherwise. And denote the degree of the i-th vertex in G and G obs by d i andd i , respectively. We assume throughout that G and G obs are simple.

We express the marginal distributions of theà i,j in the form (Balachandran et al. (2017) 

Drawing by analogy on the example of network construction based on hypothesis testing, α i,j can be interpreted as the probability of a Type-I error on the (non)edge status for vertex pair {i, j} ∈ E c , while β i,j is interpreted as the probability of Type-II error, for vertex pair {i, j} ∈ E.

Our interest is in characterizing the manner in which the uncertainty in theà i,j propagates to the branching factor. Here we focus on a general formulation of the problem in which we make the following three assumptions.

Assumption 1 (Constant marginal error probabilities). Assume that α i,j = α and β i,j = β for all i < j, so the marginal error probabilities are P(Ã i,j = 0|A i,j = 1) = β and P(Ã i,j = 1|A i,j = 0) = α.

Assumption 2 (Independent noise). The random variablesà i,j , for all i < j, are conditionally independent given A i,j .

Assumption 3 (Large Graphs). N v → ∞.

In Assumption 1, we assume that both α and β remain constant over different edges. Under Assumption 2, the distributions ofd i is

Assumption 2 is not strictly necessary. See Remark 5 in Section 5.1. Assumption 3 reflects both the fact that the study of large graphs is a hallmark of modern applied work in complex networks and, accordingly, our desire to understand the asymptotic behavior of the branching factor and provide concise descriptions in terms of the bias and variance for large graphs.

Remark 1. Note that α and β can be constants or o(1) as N v → ∞. For example, under Assumption 4, if β is constant and |E| = o(|E c |), then α = o(1). Thus, α and β are actually α(N v ) and β(N v ). For notational simplicity, we omit N v .

In addition to the core Assumptions 1 -3, we add a fourth assumption, upon which we will call periodically throughout the paper when desiring to illustrate our results in the special case.

Assumption 4 (Edge Unbiasedness). α|E c | = β|E|, so that the expected number of observed edges equals the actual number of edges.

Our use of Assumption 4 reflects the understanding that a 'good' observation G obs of the graph G should at the very least have roughly the right number of edges.

Remark 2. Assumption 4 cannot guarantee the unbiasedness of higher-order subgraph counts. (Balachandran et al. (2017) )

Let G be a network graph describing the contact structure among N v elements in a population. The branching factor is defined as follows.

Definition 1. For graph G with N v nodes, the branching factor is

where d i is the degree of node i.

Accordingly, we denote the branching factor in the noisy network byκ. Besides the basic reproduction number, R 0 , described in the introduction, there are other quantities depending on the observed branching factor. These include the percolation threshold 1/(κ−1), the epidemic threshold 1/(κ−1), and the immunization threshold 1 − 1/(λκ), where λ is the spreading rate (Pastor-Satorras et al. (2015) ).

In this section, we first quantify the asymptotic bias of the observed branching factor for arbitrary true networks. We then show specific results for four typical classes of networks: sparse and homogeneous, sparse and inhomogeneous, dense and homogeneous, and dense and inhomogeneous.

Theorem 1. We define X = Nv i=1d i 2 , Y = Nv i=1d i and we assume EY > 0, and EY = Ω(N v ) (N v → ∞). Then, under Assumption 2, for any η > 0, we have

Remark 3. Theorem 1 reflects the fact that, under certain assumptions, EX/EY is a good approximation of E(X/Y · I {Y >0} ), i.e., E(κ).

Theorem 2. Under assumptions in Theorem 1 and Assumption 1 and 4, for any η > 0, we have

Theorem 1 shows the asymptotic bias of the observed branching factor in terms of the expectations of the first and second moments of the observed under Assumption 2. Theorem 2 relies on Assumptions 1 -4 and provides a more explicit expression for the leading term of the asymptotic bias in this special case.

By making assumptions on the network density and degree distribution, we can obtain a more nuanced understanding of the limiting behavior of the observed branching factor in terms of bias when the number of nodes tends towards infinity. Specifically, we consider the combinations of sparse versus dense and homogeneous versus inhomogeneous networks. By the term sparse we will mean a graph for which the average degreed = Θ(log N v ), and by dense,d = Θ(N c v ), where 0 < c < 1. By the term homogeneous we mean the degrees follow a Poisson distribution, and by inhomogeneous, the degrees follow a truncated Pareto distribution.

Corollary 1 (Sparse and homogeneous). In the sparse homogeneous graph, where the average degreed = Θ(log N v ) and the asymptotic degree distribution is the Poisson distribution with meand, under the assumptions in Theorem 2 and β = O(1) (N v → ∞), for any η > 0, we have

Corollary 2 (Sparse and inhomogeneous). In the sparse inhomogeneous graph where the average degreed = Θ(log N v ) and the asymptotic degree distribution is truncated Pareto distribution with shape ζ, lower bound d L and upper bound N v −1, under the assumptions in Theorem 2 and β = O(1) (N v → ∞), for any η > 0, we have

Remark 4. In Corollary 2, by the definition of expectation, ζ, d L ,d and N v satisfy the equationd

Under the conditiond = Θ(log N v ), the relationship among them can be simplified. See the supplementary materials for details. Similar relationships also hold in Corollary 4, 6 and 8.

Note that the O term in Corollary 2 is dominated by the corresponding κ asymptotically, so Bias(κ) = Θ(κ), reflecting the challenges of estimating κ in under heterogeneous degree distributions. In contrast, Bias(κ) = o(κ) in Corollary 1.

In the dense homogeneous graph where the average degreed = Θ(N c v ), 0 < c < 1, and the asymptotic degree distribution is the Poisson distribution with meand, under the assumptions in Theorem 2

. Corollary 4 (Dense and inhomogeneous). In the dense inhomogeneous graph where the average degreed = Θ(N c v ), 0 < c < 1, and the asymptotic degree distribution is truncated Pareto distribution with shape ζ, lower bound d L and upper bound N v − 1, under the assumptions in Theorem 2 and β = O(1) (N v → ∞), for any η > 0, we have

Note that the O term in Corollary 4 is dominated by the corresponding κ asymptotically, so Bias(κ) = Θ(κ). In contrast, Bias(κ) = o(κ) in Corollary 3.

In summary, the observed branching factor is asymptotically unbiased in the homogeneous network setting, but asymptotically biased in the inhomogeneous network setting. The bias of the observed branching factor is negative which reflects the fact that the observed graph is typically more homogeneous then the true graph in the inhomogeneous setting. The bias depends on α, β, and ζ, and when the shape ζ > 2, the bias decreases as ζ increases. The different results in the homogeneous and inhomogeneous network setting also reflect Remark 2 since the branching factor is related to the second-order moment.

In this section, we first compute the asymptotic variance of the observed branching factor for arbitrary true networks. We then show specific results for the same four types of networks as in Section 3.2.

Under certain assumptions, we provide upper bounds for asymptotic variances of the observed branching factors and derive good approximations of asymptotic variances for arbitrary true networks. Considering that variances are important and involved, we briefly show a main outcome here and give details in Appendix 9.2.

We assume EY > 0, EY = Ω(N v ), and 1 − β = Ω(N v ). Then, under Assumption 1, 2, and 4, we have

This provide upper bounds for asymptotic variances of the observed branching factors. By making additional assumptions on the network density and degree distribution, we can obtain the order of O term and therefore the order of the variance.

Again, by making assumptions on the network density and degree distribution, we can describe the limiting behavior of the observed branching factor in term of variance when the number of nodes tends towards infinity.

Corollary 5 (Sparse and homogeneous). In the sparse homogeneous graph where the average degreed = Θ(log N v ) and the asymptotic degree distribution is the Poisson distribution with meand, under the assumptions in Theorem 2 and

Corollary 6 (Sparse and inhomogeneous). In the sparse inhomogeneous graph where the average degreed = Θ(log N v ) and the asymptotic degree distribution is truncated Pareto distribution with shape ζ, lower bound d L and upper bound N v −1, under the assumptions in Theorem 2 and

Corollary 7 (Dense and homogeneous). In the dense homogeneous graph where the average degreed = Θ(N c v ), 0 < c < 1, and the asymptotic degree distribution is the Poisson distribution with meand, under the assumptions in Theorem 2

Corollary 8 (Dense and inhomogeneous). In the dense inhomogeneous graph where the average degreed = Θ(N c v ), 0 < c < 1, and the asymptotic degree distribution is truncated Pareto distribution with shape ζ, lower bound d L and upper bound N v − 1, under the assumptions in Theorem 2 and

Note that the orders of the variances are asymptotically dominated by the corresponding biases for all four cases. Therefore, in noisy contact networks, bias would appear to be the primary concern for the observed branching factor. The O notations for variances in the homogeneous networks are bounded above by those in the inhomogeneous networks of the same network density.

As we saw in Section 3, the observed branching factor is biased in the inhomogeneous network setting. Due to the presence of heterogeneity in most real-world network data, it is important to have new estimators for bias reduction. We present a method-of-moments estimator in Section 5.1 and a bootstrap sampling estimator in Section 5.2. Both estimators require network replicates. The method-of-moments estimator needs a minimum of three replicates, and the bootstrap sampling estimator requires a minimum of two replicates.

We adapt the method-of-moments estimators (MME) of subgraph density in Chang et al. (2018) , which require at least three replicates of the observed network. Let C V1 and C V2 denote the edge density and the two-stars density, respectively. Then

whereĈ V1 andĈ V2 are method-of-moments estimators of C V1 and C V2 , which we will define later. Thus, our estimator of κ is given by:

Note thatκ is an asymptotically unbiased estimator for κ and its asymptotic distribution is normal. Details can be obtained from Chang et al. (2018) Section 4.3. Specifically, Chang et al. (2018) provide joint inference of higher-order subgraph densities with unknown error rates. Mimicking their proofs, we can easily obtain the asymptotic joint normal distribution ofĈ V1 andĈ V2 . Then, by the delta method, we can derive the asymptotic normal distribution ofκ.

To computeκ, we first estimate C V1 and C V2 by methods used in Chang et al. (2018) . Define relevant quantities as follows:

where δ is the edge density in the true network, u 1 is the expected edge density in one observed network, u 2 is the expected density of edge differences in two observed networks, and u 3 is the average probability of having an edge between two arbitrary nodes in one observed network but no edge between same nodes in the other two observed networks. The method-of-moments estimators for u 1 , u 2 and u 3 arê

Nv×Nv are independent and identically distributed replicates ofÃ. Calculation of the estimatorκ in (5.1) and the estimation of its asymptotic variance can be accomplished as detailed in Algorithm 1 below and Algorithm 3 in the Appendix, respectively. The variance estimation is based on a nonstandard bootstrap.

Algorithm 1 Method-of-moments estimatorκ

Remark 5. Since our estimation of the unknown parameters is based on moment estimation, the independent noise dictated by Assumption 2 is not strictly necessary. As is shown in the proof of Chang et al. (2018) , the convergence rate for the moment estimation of the unknown parameters is determined by the convergence rates ofû 1 − u 1 ,û 2 − u 2 andû 3 − u 3 . When some limited dependency among observed edges is present, the convergence rates

A generic bootstrap method has been proposed in the context of contact networks by Kucharski et al. (2018) , for the purpose of assessing various summaries of network structure. We adapt and formalize this method to undirected networks, and obtain a bootstrap sampling estimator for κ when a minimum of two replicates of the observed network are available.

where m ≥ 2. In each iteration, we construct a bootstrap resample matrixà b as follows: for entriesà b i,j , 1 ≤ i < j ≤ N v , we randomly select one of m observed adjacency matrices, and use the (i, j) entry of the selected matrix as the value of A b i,j . Then, we let the lower triangular elements equal to the corresponding upper triangular elements and make the diagonal elements to be 0s. This generates a bootstrap network from which we can calculate the branching factor. We then perform iterations of bootstrap sampling to estimate the mean and confidence interval. See Algorithm 2 for details.

In general, the bootstrap sampling estimator does not work well since bootstrap samples are drawn from observed degree distributions, which introduce errors into the branching factor. When error rates are small and satisfy Assumption 4, we expect performance to be better. Recall Remark 2 that higher-order subgraph counts may not be unbiased under Assumption 4. Thus, Assumption 4 can't guarantee the good performance of the bootstrap sampling estimator. The performance also depends on other network characteristics, such as the degree distribution. For the sake of comparison, we show results of the bootstrap sampling estimator using Algorithm 2 in Section 6. Moreover, extensive work has been done on bootstrapping networks without replicates. For example, Bhattacharyya et al. (2015) proposed bootstrap subsampling methods for finding empirical distribution of count features.

Randomly select one element from {1, · · · , m}, denoted by l; A

Compute the branching factors forà bn b , denoted by κ nb .

We conduct some simulations and experiments to illustrate the finite sample properties of the proposed estimation methods. We consider the data and network construction described in Kucharski et al. (2018) . These data were collected from 460 unique participants across four rounds of data collection conducted between January and June 2015 in year 7 groups in four UK secondary schools, with 7,315 identifiable contacts reported in total. They used a process of peer nomination as a method for data collection: students were asked, via the research questionnaire, to list the six other students in year 7 at their school that they spend the most time with. For each pair of participants in a specific round of data collection, a single link was defined if either one of the participants reported a contact between the pair (i.e. there was at least one unidirectional link, in either direction). Our analysis focuses on the single link contact network. We consider two settings, a simulation setting where noise is added to a 'true' network and an application setting where the four replicates are each treated as noisy versions of an unknown true network.

For each school, we construct a 'true' adjacency matrix A: if an edge occurs between a pair of vertices more than once in four rounds, we view that pair to have a true edge. The noisy, observed adjacency matricesÃ,Ã * ,Ã * * are generated according to (2.1). We set α = 0.005 or 0.010, and β = 0.01, 0.15, or 0.20. We assume that both α and β are unknown.

We evaluate the two types of point estimates for κ and 95% confidence intervals. For the method-of-moments estimator, we follow Algorithms 1 and 3. For the bootstrap sampling estimator, we perform 10,000 iterations of bootstrap sampling to estimate the mean and 95% confidence interval. Figure 6 .1 shows the simulation results, in which we replicate 500 times for each setting. The mean absolute errors (MAE) for the point estimates for the branching factor κ and the relative frequency (RF) of coverage for the estimated 95% confidence interval for κ are shown in Figure  6 .1. Note that, for the method-of-moments estimator, MAE(κ) = 1 500 500 i=1 |κ i − κ|, whereκ 1 , · · · ,κ 500 denote the estimated values in 500 replications of simulation, and κ denotes the true value. For the bootstrap sampling estimators, we define MAE(κ) = 1 500 500 i=1 |κ b i − κ|, whereκ b 1 , · · · ,κ b 500 denote the mean of estimates across 10,000 bootstrap samples in 500 replications of simulation.

For the method-of-moments estimator, the estimation errors for κ increase when α and β increase. And the estimated coverage probabilities are indeed around 95%. The average interval lengths are slightly larger than those of bootstrap sampling estimators. For the bootstrap sampling estimators, the estimation errors and estimated coverage probabilities depend on the relationship of α and β and the degree distribution. For example, when β/α = 20 in school 2, the estimation of κ is quite accurate and the estimated coverage probability is high. This may due to the fact that α and β satisfy Assumption 4. When α = 0.005 and β = 0.2, the estimated coverage probabilities are low for all four schools.

Again, we use the British secondary school contact networks. Considering the nodes in four rounds are not same, we choose the common nodes in four rounds and their edges to obtain four replicates of the noisy networks. Since our estimation methods only need three replicates, we select rounds 1, 2, and 3.

We evaluate the two types of point estimates for κ, 95% confidence intervals, and the observed branching factorκ. Point estimates and 95% confidence intervals for α and β are reported in Table 6 .2. Figure 6 .2 show the point estimates for the Fig. 6 .1. Mean absolute errors (MAE) ofκ, and 95% confidence intervals for κ in the simulation with 500 replications for noisy networks in four schools. Reported in the plots are the relative frequencies (RF) of the event that a confidence interval covers the corresponding true value, and also the average Length of the intervals. branching factor κ and the observed branching factorκ in each round. The error bars are the estimated 95% confidence interval for κ. Table 6 .2 indicates there exist nontrivial noise in all four schools. Figure 6 .2 show that, in schools 2 and 3, the resulting method-of-moments estimates for κ are lower than all of their observed values, indicating a nontrivial downward adjustment for network noise. And the observed branching factors are not in the estimated 95% confidence intervals, which further reinforces the evidence that the true branching factor is less than those observed empirically. In schools 1 and 4, the resulting method-of-moments estimates for κ are close to their observed values. For all four schools, the bootstrap sampling estimators tend to be closer to the observed branching factors than the method-of-moments estimators. Additionally, the interval lengths are relatively small, which is consistent with the simulation results. The simulation results would suggest that the method-of-moments estimates are preferable here, and hence that the bootstrap approach is less able to adjust for the bias induced by noise in our observed networks.

Ultimately, we see that the ability to account for network noise appropriately in reporting the branching factor can lead to subtantially different conclusions than use of the original, empirically observed branching factor.

Here we have quantified the bias and variance of the observed branching factor in noisy networks and developed a general framework for estimation of the true branching factor in contexts wherein one has observations of noisy networks. One of our approaches requires as few as three replicates of network observations, and employs method-of-moments techniques to derive estimators and establish their asymptotic consistency and normality. The other approach relies on bootstrapping of the observed networks to construct many sample networks, from which in turn we obtain estimators and confidence intervals. Simulations demonstrate that substantial inferential accuracy by method-of-moments estimators is possible in networks of even modest size when nontrivial noise is present. And our application to social contact networks in British secondary schools shows that the gains offered by our approach over presenting the observed branching factor can be pronounced.

We have pursued a frequentist approach to the problem of uncertainty quantification for the branching factor. If the replicates necessary for our approach are unavailable in a given setting, a Bayesian approach is a natural alternative. For Round 1 Round 2 Round 3 Round 4 MME Bootstrap example, posterior-predictive checks for goodness-of-fit based on examination of a handful of network summary measures is common practice (e.g., Bloem-Reddy and Orbanz (2018)). Note, however, that the Bayesian approach requires careful modeling of the generative process underlying G and typically does not distinguish between signal and noise components. Our analysis is conditional on G, and hence does not require that G be modeled. It is effectively a 'signal plus noise' model, with the signal taken to be fixed but unknown. Related work has been done in the context of graphon modeling, with the goal of estimating network motif frequencies (e.g., Latouche and Robin (2016) ). However, again, one typically does not distinguish between signal and noise components in this setting. Additionally, we note that the problem of practical graphon estimation itself is still a developing area of research. Our work here sets the stage for extensions to various thresholds and statistics which depend on the branching factor. Recall that these include the percolation threshold 1/(κ−1), the epidemic threshold 1/(κ−1), and the immunization threshold 1 − 1/(λκ), where λ is the spreading rate (Pastor-Satorras et al. (2015)). Replacing κ withκ, we obtain asymptotically unbiased estimators for the corresponding thresholds. The asymptotic distributions can be derived from the delta method. In addition, the total branching factor of the network is important for epidemic spreading and immunization strategy in multiplex networks (e.g., Buono et al. (2014) ).

Our choice to work with independent network noise is both natural and motivated by convenience. And our results of method-of-moments estimators still hold when there is some dependency across (non)edges. A precise characterization of the dependency is typically problem-specific and hence a topic for further investigation.

This work was supported in part by ARO award W911NF1810237. This work was also supported by the Air Force Research Laboratory and DARPA under agreement number FA8750-18-2-0066 and by a grant from MIT Lincoln Labs.

In the appendix, you will find proofs of theorems for bias of the observed branching number, theorems for variance of the observed branching number and the proofs, and the algorithm for estimation of asymptotic variance of method-of-moments estimator κ. Proofs of corollaries can be found in supplementary materials.

Proof (Theorem 1). Recall X = id 2 i and Y = id i . Note that

(9.1) By Jensen's inequality, we have

Then by additivity of expectation, for 0 < δ < 1,

Next, we find the upper bounds of two terms in (9.3). For the first term, by definitions of X and Y ,

Then, by Chernoff Bound, we obtain

For the second term, when

By (9.2), we show

Let L 1 (N v ) and L 2 (N v ) denote two terms on the right sides in (9.4). We choose δ = (EY ) −1/(2+η) , η > 0, such that

These imply (9.1).

Proof (Theorem 2). We compute EY and EX under Assumption 1 and 2,

Then, under Assumption 4, (9.5) leads to

Plugging the value of EX/EY into the bias expression in Theorem 1 completes the proof.

9.2. Theorems for variance of the observed branching number in arbitrary network topology Theorem 3. We assume EY > 0, and EY = Ω(N v ) (N v → ∞). Then, under Assumption 2, (i)

(ii) For any η, λ > 0,

Theorem 4. Under the assumptions in Theorem 3, Assumption 1 and 4, and

(ii) For any η, κ > 0,

Theorem 3 (i) and Theorem 4 (i) provide upper bounds for variances of the observed branching factors. And Theorem 3 (ii) and Theorem 4 (ii) derive good approximations of variances if the O terms are dominated by the corresponding first terms asymptotically.

To show Theorem 3 and Theorem 4, we first introduce a useful lemma.

Lemma 1. Under assumptions in Theorem 3, for any η > 0, we have

By triangle inequality and Jensen's inequality, we obtain

· Pr(Y = 0). (9.6) Next, we find an upper bound of

By additivity of expectation, for any δ ∈ (0, 1), (9.7) equals

For the first term in (9.8), by definitions of X and Y , we

Then, by Chernoff Bound, we obtain

For the second term in (9.8), when

By (9.6), we show

(9.10) L 1 (N v ) and L 2 (N v ) denote the first two terms on the right sides in (9.10). We choose δ = (EY ) −1/(2+η) , η > 0, such that

These complete the proof.

(i) By Lemma 1, for any η > 0, we obtain

(ii) By triangle inequality, we have

Apply Lemma 1 and Theorem 1 and the rest follows.

Proof (Theorem 4). Under assumptions in Theorem 4, we have

and there exist η 0 , λ 0 > 0, such that

Apply Theorem 3 and the rest follows.

9.4. Algorithm for estimation of asymptotic variance of method-of-moments estimatorκ To evaluate the asymptotic variance of method-of-moments estimatorκ, we first estimate the asymptotic variance of (Ĉ V1 ,Ĉ V2 ) by the method in Section 4 of Chang et al. (2018) . Then, we use the delta method to obtain the estimation of the asymptotic variance ofκ. The detail is shown in Algorithm 3.

wherek

,V 2,Nv =∆ĜΣĜ ∆ , V 3,Nv = (ĤĜ ∆ +∆ĜĤ )/2,∆,Ĝ,Σ, andĤ defined in (9.11);

A.1. Proof of Corollary 1 By homogeneity, we obtain

By edge unbiasedness, we have

By Theorem 2, for any η > 0, we have 

First, we compute the first and second moments of truncated Pareto distribution.

By edge unbiasedness, we have

By Theorem 2, for any η > 0, we have

By Theorem 2, for any η > 0, we have

By homogeneity, we obtain

By edge unbiasedness, we have

and

By Theorem 2, for any η > 0, we have

Note that the asymptotic notations for d L and Nv i=1 d 2 i / Nv i=1 d i are same as equation (A.4) and equation (A.5).

By edge unbiasedness, we have

By Theorem 2, for any η > 0, we have

By Theorem 2, for any η > 0, we have

To prove corollaries for variances of the observed branching number, we first

Under Assumption 1, 2 and 4, we have

B.1. Proof of Corollary 5

By edge unbiasedness, we have

Besides, by Young's inequaility, we have

Thus, we obtain

Then, we have

By Theorem 4,

By edge unbiasedness, we have

In addition, by Young's inequaility, we have

Then, we have

By Theorem 4,

Then, we have

By Theorem 4,

Then, we have

By Theorem 4,

Then, we have

By Theorem 4,

(v) 2 < ζ < 5/2 Note that EX EY = Θ log N v ,

Then, we have

By Theorem 4,

Then, we have

By Theorem 4,

By edge unbiasedness, we have

By homogeneity, we obtain

Besides, by Young's inequaility, we have

Thus, we obtain 

if ζ > 3.

In addition, by equation (B.4), we obtain

if ζ > 2.

(i) 0 < ζ < 1 Note that

By Theorem 4,

(ii) ζ = 1 Note that

By Theorem 4,

By Theorem 4,

Then, we have

By Theorem 4,

(v) 2 < ζ < 5/2

Note that

Then, we have

By Theorem 4,

(vi) ζ ≥ 5/2 Note that

Then, we have

By Theorem 4,

Network sampling: From static to streaming graphs

Infectious diseases of humans

Epidemics in a population with social structures

Stochastic epidemic models and their statistical analysis

On the propagation of low-rate measurement error to subgraph counts in large networks

Statistical studies of infectious disease incidence

Subsampling bootstrap of count features of networks

Random-walk models of network formation and sequential monte carlo methods for graphs

Epidemics in partially overlapped multiplex networks

Estimation of subgraph density in noisy networks

Matrix estimation by universal singular value thresholding

Model parameters and outbreak control for sars

The basic reproductive number of ebola and the effects of public health measures: the cases of congo and uganda

Distinguishing epidemic waves from disease spillover in a wildlife population

Early real-time estimation of the basic reproduction number of emerging infectious diseases

Mathematical epidemiology of infectious diseases: model building, analysis and interpretation

Performance of proximity loggers in recording intra-and inter-species interactions: a laboratory and field-based validation study

Modelling disease outbreaks in realistic urban social networks

Network-based auto-probit modeling for protein function prediction

A latent eigenprobit model with link uncertainty for prediction of protein-protein interactions

Demographic structure and pathogen dynamics on the network of livestock movements in great britain

Statistical Analysis of Network Data

Structure and consistency of self-reported social contact networks in british secondary schools

Variational bayes model averaging for graphon functions and motif frequencies inference in w-graph models

Measurability of the epidemic reproduction number in data-driven contact networks

Epidemic processes in complex networks

Statistical inference on errorfully observed graphs

Collecting close-contact social mixing data with contact diaries: reporting errors and biases

Estimation of the reproductive number and the serial interval in early phase of the 2009 influenza a/h1n1 pandemic in the usa

The outcome of a stochastic epidemic-a note on bailey's paper