concentrated on node-level characteristics such as node degree [Hol04, MH07, MvdDW13, WKB13] . For instance, models can be used to explore the impact of vaccination strategies that target highly connected nodes, or various different approaches to contact tracing [Hol04, MH07, MvdDW13, WKB13] .
Earlier network modelling efforts focused on strategies for node-level characteristics because data on the structure of entire contact networks was once rare. However, such data is becoming increasingly available, making it possible to address strategies that target the larger-scale features of network structure such as how connected communities are to one another. It has been shown in simulated networks that vaccination targeted at individuals that bridge different communities in the network are more effective than targeting individuals with high node degree [SJ10] . These approaches detect important nodes and edges based on edge-betweenness measures. In particular, edge-betweenness is a measure of the influence an edge has over a diffusion process through the network (e.g., spread of infectious diseases). A classical example is that of shortest-path betweenness, which quantifies edge importance based on the assumption that information spreads only along shortest paths. However, it has been noted [SJ10] that this approach can overlook important connections in a network. For example, in Figure 1a we see that shortest-path betweenness only recognizes the shorter "bridge" in the middle, while completely neglecting the two longer, but still highly influential, side bridges. Random walk betweenness [New05] fixes this problem of shortest-path betweenness by assuming that information spreads along random paths in the network while giving more weight to shorter paths. It is also named current-flow betweenness [BF05] due to the relation to network electrical current flows. Figure 1b shows that edge-betweenness that takes into account all possible walks captures the relative importance of all bridges. However, we note that human movement in large networks tends to be local [LLDM09, JBP + 15] . Thus, containing the spread of infectious diseases usually requires identification and control of contact bottlenecks at a local scale rather than global. For example, cutting off all three bridges in Figure 1b would be terribly ineffective at slowing down the disease spread, if there was at least one infectious node in each of the two "square" clusters. In this paper we develop a new edge-betweenness measure that we call λ-local flow betweenness, which is based purely on local diffusion in the network and offers a very flexible and localized quantification of edge importance. More precisely, when λ is small, λ-local flow betweenness tends to detect locally important edges as opposed to global bottlenecks that have little influence on local structure or processes. For example, Figure 1c shows that when λ = 1, it detects the same global bottlenecks as found by current-flow betweenness, but when we shrink λ = 2/5, it detects locally important bottlenecks within each block as shown in Figure 1d . Removing these bottlenecks would reduce disease transmission even if the infection is initially present in both sides. The proposed definition of edge-betweenness is based on p-norm flow diffusion [YWF20] . This diffusion is defined as a convex optimization problem that models the phenomenon of diffusing mass from a given node to nearby nodes that have non-zero capacities. More details are given in Section 2. The origin of p-norm flow diffusion is in local graph clustering methods. Because of this, the proposed edge-betweenness method induces locality and clustering biases, which we discuss in Sub-section 2.1. These inductive biases are crucial to the good performance of the proposed methods. Details are provided in Section 3.
We demonstrate that λ-local flow betweenness gives rise to better intervention strategies on all real datasets that we tested, and we discuss in detail why it is a more suitable measure for identifying disease transmission bottlenecks. We conduct exhaustive simulations and the conclusions we draw from all experiments are consistent.
In this section we define λ-local flow betweenness and determine its computational complexity. λ-local flow betweenness relies on p-norm flow diffusion [YWF20] , which is used to solve the local graph clustering problem [FGM17] . There exist spectral [ST13, ACL06, ZLM13, AP09, FRKS + 17] and combinatorial [AL08, OZ14, FLGM20, FGM17, WFH + 17] local graph clustering methods. However, p-norm flow diffusion is as simple and as fast as spectral methods, but it has better conductance guarantees in theory and in practice. Moreover, p-norm diffusion requires less parameter tuning than combinatorial methods. For these reasons, we use it to define our edge-betweenness.
Given an undirected graph G = (V, E) and signed incidence matrix B 1 using arbitrary orientation, we follow [YWF20] and define a diffusion process on G as the following convex optimization problem:
where ∆, T ∈ R |V | specify the amount of initial mass and sink capacity at each node, respectively, and f ∈ R |E| are edge flow variables. The vector B f + ∆ gives the amount of final mass at each node if we start with initial mass ∆ on nodes and send the mass around according to flow routing f , and we call a flow feasible if the final mass at each node is at most its capacity. The objective of (1) is to find a feasible flow f * p having the minimum p-norm 2 . Naturally, in a diffusion we start with ∆ having high density, i.e., there is a large amount of initial mass concentrated on a small set of nodes, and the sink capacities enforce we spread the mass to get lower density.
To take into account all relevant diffusion processes that start from arbitrary nodes and arbitrary sink capacities, we consider ∆ and T in (1) as random variables following a probability distribution P, under which its expected optimal objective value is finite. For p ∈ (1, ∞), we define, in the most general sense, the p-norm flow edge-betweenness for an edge e as 
Of course, the specific inductive biases of p-norm flow edge-betweenness depend on the distribution P. For example, let U V denote the discrete uniform distribution on the set of one-hot vectors {1 v : v ∈ V }, then one obtains the current-flow betweenness as a special case:
Theorem 1. For an edge e ∈ E, the current-flow betweenness [BF05] c CB (e) normalized by 1/|V | 2 satisfies c CB (e) = B 2 (e; U V × U V ) = E ∆∼U V ,T ∼U V [|f * 2 (e)|].
In order to introduce locality and clustering bias in (2), we let ∆ ∼ U V and fix T = d λ·vol (G) where d is the degree vector, vol(G) equals the sum of degrees of all nodes in G, and λ ∈ (0, 1). We call the resulting specialized p-norm flow edge-betweenness as λ-local flow betweenness, as the locality of edge flows is controlled by λ, which we state formally in the following.
Theorem 2 (adapted to our problem from [YWF20] ). For T = d λ·vol(G) and any fixed realization ∆ = 1 v , the number of edges with nonzero flow crossing them is bounded by f * p 0 < 2λ|E|.
When p = 2, for any fixed ∆ and T , one can compute f * 2 up to -accuracy in time O(λ|E|d 2 log 1 ) whered < max i∈V d i [YWF20] . Therefore, λ-local flow betweenness for all edges can be computed in time O(λ|V ||E|d 2 log 1 ). For sparse networks whend is constant, if 1 |E| × |V | matrix where the row of edge (u, v) has two non-zero entries, -1 at column u and 1 at column v. 2 In general, we use subscripts p, ∆, T and write f * p,∆,T to indicate the dependence of optimal solution to input parameters. We drop ∆, T from the subscript when they are clear from context and simply write f * p .
we set λ = O(1/|V |) = O(1/|E|), then the computation time reduces to O(|V | log 1 ). Note that small λ is what we rely on to detect local contact bottlenecks. In Section 3 we demonstrate that computing λ-local flow betweenness can be several orders of magnitude faster than computing shortest-path or current-flow betweenness, while the intervention strategies based on it achieve better disease containment. Besides locality, one can show that f * p induces a strong local graph clustering bias in sparse networks for appropriately chosen λ. This local graph clustering bias will play a crucial role in our experiment. Formally, we quantify how "well-knit" a cluster is by measuring its conductance 3 .
Theorem 3 (adapted to our problem from [YWF20] ). Fix p ∈ (1, ∞), T = d λ·vol(G) , and ∆ = 1 v for some node v. The optimal solution to the dual of problem (1) gives a clusterC such that the conductance φ(C) ≤ O(α · φ(C) 1−1/p ) holds simultaneously for any subset C containing v, where α = O( λvol(G) dv ) and d v is the degree of v. In particular, in sparse graphs when we set
We compare the effectiveness of interventions for the control of COVID-19 transmission that target edges 4 meeting certain criteria, based on λ-local flow (LF(λ)) betweenness against other network centrality measures. We compare the following techniques: 1) Uniform Intervention (UI): reduce all contacts (i.e., edge weights) by a fixed amount, 2) High Degree (HD) intervention: reduce only the contacts of high degree nodes; and two state-of-the-art betweenness measures, 3) and 4) Shortest-Path (SP) and Current-Flow (CF) interventions: reduce important contacts recognized by SP and CF betweenness, respectively. In the past, SP and CF betweenness have been applied to wide range of problems including cancer diagnosis [Ram17] , immunization modelling [SJ10] , power grid contingency analysis [JHC + 10], terrorist networks analysis [CKS02]. Hence, they are ideal candidates for comparison purposes. We use two SEIR network models to predict how COVID-19 infections will spread: 1) an ordinary differential equation (ODE) model where each node corresponds to a population in which an SEIR epidemic is occurring that can spread between nodes according to the network's adjacency matrix, 2) an agent-based model where each node corresponds to a person, and the infection is transmitted from one node to the next with a certain probability per timestep. Details about the models and their parameter tuning are given in the supplementary material. We present the most informative figures in this section. Additional figures appear in the supplementary. WKB13] . The network consists of 1.6 million nodes and 31 million edges. We also make use of a sub-sampled version of this dataset that has 10, 000 nodes and 199, 168 edges [WKB13] . 3 The conductance of a subset of nodes S ⊆ V is defined as φ(S) :=
is the sum of degrees of all nodes in S. 4 We reduce targeted contact edge weights by 90%, e.g., physical contact reduction is naturally modelled as edge weight reduction or deletion. For more experiments under other weight reduction settings, see appendix.
In Figure 2 we demonstrate the Network Community Profile (NCP), the degree distribution and epidemic curves without intervention. The NCP captures clustering pattern of a network, i.e., the lower the NCP is the better. Details about the NCP are given in the supplementary material. In Figure 2a we demonstrate that the datasets correspond to the three distinct NCP classifications from [LLDM09, JBP + 15]. In particular, FB-county has a downward sloping NCP, i.e., conductance decreases as size increases, Wi-Fi Montreal has roughly flat NCP, i.e., conductance does not change much as a function of size, and Portland, Oregon has upward slopping NCP, i,e, conductance are small at small sizes and increases as the size increases. We will exploit the NCP structure to define the initially infected nodes in our experiments. In Figure 2b we illustrate the degree distribution for the datasets. Note that the degree distribution for Montreal WiFi is heavily concentrated around nodes with degree ≤ 2, which is more than half of the nodes in the network. This will play crucial role in the analysis of our experiments later on in this section. In Figure 2c we show the percentage of total active COVID-19 cases (prevelance of infection) against time (in days). 5 
The time required for computing LF(λ) betweenness depends linearly on λ. If the network is sparse and λ is proportional to 1/|V |, then computing LF(λ) to accuracy can be done in O(|V | log 1 ) time. For comparison, the computation time is at least O(|V | 2 ) for SP betweenness and O(|V | 2 log |V |) for CF betweenness on sparse unweighted graphs 6 . In Figure 3 we compare the empirical computation times for SP, CF, and LF(λ) betweenness on FB-county, Port. Sub., and Wi-Fi Montreal networks. All computations are carried out on a personal laptop with 32GB RAM and 2.9 GHz 6-Core Intel Core i9. We used NetworkX [HSS08] for computing SP and CF and implemented LF(λ) computation in Julia. Observe that as λ becomes larger and LF(λ) becomes more global, the time for computing LF(λ) is similar to that of SP or CF. On the other hand, as λ becomes smaller, computing LF(λ) gets several orders of magnitudes faster. This is crucial for scaling up our method to huge networks. For example, LF(λ) is the only betweenness measure we are able to compute for the full Portland network. 5 The curve for FB-county is very different from the other datasets because the data represent a nationwide geographic region and it takes a longer amount of time for the infection to spread from the Northeastern states to the rest of the country. This is also the reason that for FB-county the curves have multiple peaks, since there are multiple outbreaks in multiple cities as the disease progresses. In contrast, the other datasets correspond to outbreaks in a single urban centre that tend to unfold over weeks instead of months. 
We apply the ODE model to simulate the spread of COVID-19 on the FB-county network, since each node represents an entire county population. We assume that all county populations are initially susceptible and we pick infected counties for which we initialize 0.1% of the county population as infectious. We use three different ways to select initially infected counties to account for variations in where outbreaks could have started: (i) populated cosmopolitan cities (e.g., New York, Los Angeles), (ii) a tightly-knit cluster of 67 densely connected counties, highlighted in Figure 4a and also captured by the green star on the NCP in Figure 2a , and (iii) a random selection of 1% of all counties. Figure 4b and 4c demonstrate the predicted epidemic curves and the final outbreak sizes during the epidemic under different levels of intervention for each method, for scenario (iii). (Results are similar for scenario (i) and (ii), see supplementary material.) Note that the epidemic curve using LF(λ) intervention starts late, ends earlier, and has the lowest epidemic peak compared to the interventions based on SP or CF betweenness. Our results also show that for all three initial conditions and at all levels of intervention, LF(λ) leads to the highest reduction in the epidemic size. To study what makes LF(λ) betweenness a much better indicator for local contact bottlenecks, we fix the intervention level at 25% of all edges and analyze the resulting networks. In Figure 5 we color each county according to how many edges incident to it have been targeted for contact reduction. We observe a significant difference in the patterns demonstrated by the three methods. Intervention based on SP results in scattered targets distributed over the country, whereas CF emphasizes the central east region, which consists of a large number of concentrated small counties. Both methods demonstrate a global pattern as being either globally dispersed or globally clustered. On the other hand, the targets of LF(λ) betweenness form groups of small local clusters that spread across the country and loosely partition both east and west coasts into several smaller connected components. This observation is further supported in Figure 6a in which the NCP of the modified graph based on LF(λ) has much lower conductance when cluster sizes are small. In Figure 6b we investigate this range by plotting the distribution of clusters of size less than 100 against conductance. Not surprisingly, the intervened network based on LF(λ) betweenness contains more well-defined small clusters than the networks obtained from targeting high SP or CF betweenness, which has a more global focus. Finally, in Figure 6c we measure the percentage of out-link edges from the initial infected cluster (Figure 4a ) that are targeted by different intervention strategies. Observe that the top 5% edges based on LF(λ) betweenness already include all edges in the cut of the initial cluster. This explains why the epidemic curve under LF(λ) starts rising later than others: because all out-link contacts have already been reduced. Note that LF(λ) is un-supervised, i.e., it is not aware of the initially infected nodes, which demonstrates that local flow betweenness induces clustering bias, as promised by Theorem 3. 
We apply the agent-based SEIR network model to Wi-Fi Montreal, since each node now represents an individual person. We assign the initial state Susceptible to each person and then pick Infectious persons in two ways that cover very distinct scenarios: (i) as a group of 120 densely connected persons captured by the black circle on the NCP in Figure 2a , and (ii) as 0.1% of total population selected uniformly at random. We simulate the model until all state transitions reach equilibrium. The results for scenario (i) are shown in Figure 7 (see supplementary material for similar results for scenario (ii)), where in Figure 7b we also plot the peak of the epidemic curves at different intervention levels. Observe that in most cases, and in particular when targeting more than 20% of contact edges, LF(λ) offers both significantly smaller epidemic size and a lower epidemic peak. CF is omitted for this network due to prohibitive computation time 7 . We explain qualitatively what makes LF(λ) work better than SP. As discussed earlier, more than half of the nodes in Wi-Fi Montreal have degree one or two (cf. Figure 2b) , perhaps because these nodes represent visitors. Hence, this network presents an extreme case where disconnecting all those small degree nodes could be a trivial yet effective solution. On the other hand, partitioning the entire graph into groups of clusters may not be as effective as it is for FB-county. In Figure 8 we demonstrate that LF(λ) captures the degree irregularity in Wi-Fi Montreal and exploits this local information (i.e., many nodes have low degree). In particular, Figure 8a shows that intervention based on LF(λ) does not necessarily generate more small clusters when the underlying graph has too many degree-one nodes. This is supported by Figure 8b where we see that the distribution of clusters of all sizes in the modified networks are similar. On the other hand, as shown in Figure 8c , where we measure how many singleton nodes are there if we were to remove all targeted edges, we notice that LF(λ) separates far more singletons than SP does, thanks to its locality bias. 
We apply the agent-based model on both sub-sampled and full Portland contact networks. The sub-sampled network (Port. Sub.) is used first because the computation of both SP and CF betweenness measures do not scale to the full Portland dataset. We use Port. Sub. for comparison among different intervention methods and full Portland to demonstrate the effectiveness of LF(λ) after scaling it up for large networks. We consider two initialization techniques for the model. First, we use well-connected clusters illustrated by the purple square and the blue diamond on the NCP in Figure 2a . Second, we select randomly 0.1% nodes from the entire population. For both datasets, the simulation results for both cluster and random initialization are shown in Figure 9 . Observe that the results from different initialization schemes are very similar. In both scenarios, the smaller the λ, the smaller the total epidemic size. On the other hand, there is a trade-off between epidemic peak and epidemic size: on Port. Sub., λ = 1/50 gives the most reduction in epidemic size, whereas a slightly larger λ = 1/10 offers less reduction in total cases but gives a flatter epidemic curve (lower peak). For Port. Sub., all three methods produce similar NCPs when cluster sizes are more than 30 as shown in Figure 9a . So NCP does not explain why LF(λ) leads to the most reduction in epidemic size. We further investigate the degree distributions in Figure 9b . Notice that more than 30% of all nodes in the LF(λ) intervention have degrees close to 0, which is more than double the amount created from SP or CF. This large amount of almost-isolated nodes (as they have degrees close to 0) makes it very difficult for an epidemic to spread across the entire population, and explains why intervention strategies based on LF(λ) leads to the mildest outbreak in terms of total infection. It also reveals that LF(λ) offers a better utilization of "budget" in the sense that most efforts in contact reduction are spent to create and isolate low degree nodes. Finally, for the full Portland network, while Figure 10c shows that there is a small difference in NCP, such difference is not as significant as it is demonstrated on the Facebook County network, and the major benefit of using LF(λ) on the full network still lies in the large amount of low degree nodes it created, as we show in Figure 10d .
Infection control methods that target features of network structure instead of features of individual nodes are increasingly feasible as empirical data on full contact networks becomes more abundant. At the same time, our network algorithms continue to improve. As we show here, λ local flow betweenness is orders of magnitude faster than competing methods, and physical distancing interventions based on λ local flow betweenness mitigate a simulated COVID-19 epidemic on realistic contact networks more effectively than other state-of-the-art approaches.
Large-scale pandemic interventions like school and workplace closure and other forms of physical (social) distancing can have enormous social and economic impacts. Highly optimized interventions that target key features of contact network architecture show promise to significantly reduce epidemic spread with minimal impact on the population, relative to "blunt instruments" like lockdown that impact the entire network. Our paper introduces a very fast method that can identify key network features and reduces COVID-19 spread more than competing state-of-the-art methods. However, implementing these methods in real time during a real-world epidemic would likely require large-scale digital monitoring of the population, which has negative implications for invasion of privacy and data protection. In this paper we use two different types of COVID-19 transmission models. Both assume an SEIR disease progression in the host where individuals are in one of four mutually exclusive compartments: susceptible to infection (S), infected but not yet infectious (E), infectious (I), and removed (R). The first model described below is based on a system of ordinary differential equations (ODEs) [Het00] while the second is an agent-based model [GBB + 06, GBD + 10, WKB13].
Our ODE network SEIR model assumes that the proportion of susceptible, exposed, infectious and removed individuals in each population evolves according to an SEIR ODE model, and that transmission between populations occur through a network that connects these populations at rates determined by the network structure (connectivity and edge weights) of the Facebook County network. We define the following compartments: The corresponding ODE SEIR network model is
For our simulations we assume σ i = σ and γ i = γ for all i.
To model infection spread in a network of individuals, we introduce an agent-based network SEIR simulation model [GBB + 06, GBD + 10, WKB13 ]. An individual can be placed into one of following four states: (1) Susceptible (can contract the infection given contact with an infected individual), (2) Exposed (contracted the infection, but not yet infectious), (3) Infectious (with or without symptoms), and (4) Removed (either dead or obtained immunity and hence cannot infect others). The number of Susceptible, Exposed, Infectious, Removed, and total individuals can be denoted as S, E, I, R, N, respectively. When an infectious individual passes the infection to a susceptible individual, the susceptible agent is activated. The algorithm allows us to keep track of the Exposed and Infectious agents over time. As the number of activated agents increases so does the computational expense. We assumed that all edges have the same weight. The total number of individuals within each of these disease states is given as:
• S(t): number of susceptible persons at time t,
• E(t): number of exposed persons (infected but not yet infectious) at time t,
• I(t): number of infectious persons at time t,
• R(t): number of removed persons at time t,
• N : number of persons in the population (constant), and the parameters are:
• β: transmission probability along a network edge, per unit time,
• σ: probability that a person transitions from exposed to infectious, per unit time,
• γ: probability that a person transitions from infectious to removed, per unit time,
Each timestep in the discrete-time simulation corresponds to one day. The corresponding algorithm is as follows 1. Loop over all nodes (each node is a person) for each time step. For each node, the following may happen
• If a person is in state S, then each infected neighbouring person has a probability β of infecting him/her, in which case the susceptible person moves from state S → E. • If a person is in state E, s/he becomes infectious with probability σ and the status changes from E → I. • If a person is in state I, s/he recovers with probability γ and the status changes from I → R.
2. Update status of each person according to the events the person went through.
3. Repeat the steps for desired number of time steps.
We set the average duration of the latent period 1/σ = 2.5 days and the average duration of the infectious period 1/γ = 5 days based on epidemiological data on COVID-19 serial interval and incubation period [NLA20, NKY + 20]. (We note that the latent and infectious periods do not correspond to the incubation period and duration of illness [Fin03].) We assumed a basic reproduction number R 0 = 2.5 for COVID-19 [LGWSR20, HK20]. We use the same values of σ, γ, and R 0 for both models. Calibration of the differential equation SEIR model for the Facebook County network and the agent-based SEIR model for the Wi-Fi Montreal and Portland networks required calibrating the value of β. In the agent-based network model, β is simply the transmission probability per edge per timestep. In the differential equation model, β is the coefficient of transmission in front of the adjacency matrix A ji . In order to ensure comparability between these two model outputs, we calibrated their respective β values to obtain the outcome that 89% of the population eventually becomes infected in the absence of any interventions, in both models (i.e., lim t→∞ i R i /N i = 0.89). This percentage was based on the SEIR epidemic final size formula Z = 1 − exp(−ZR 0 ) where Z is the final size [ME06] , and our assumption that R 0 = 2.5. We modelled edge weight reduction due to interventions by reducing β values on the targeted edges accordingly. 
Theorem 2 comes directly from Lemma 1 in [YWF20] . Theorem 3 is a straightforward application of Theorem 2 in [YWF20] to our setting.
In the seminal papers [LLDM09, JBP + 15] the authors studied how clustering structure of social networks changes as the size of the clusters increases. In particular, the NCP [LLDM09, JBP + 15] function is defined as:
The NCP function takes as input the size k and asks for the minimum conductance that can be found in the graph such that the set S has size k. The NCP can be used to calculate the clustering resolution profile of the network as the size of the set increases. Based on the NCP, many real-world networks can be classified into three distinct cases according to their "size-resolved community structure", (i) the best small communities have lower conductance than the best large communities (upward slopping NCP), (ii) the best small communities have comparable conductance to the best medium-sized and large communities (flat NCP), and (iii) the best small communities have higher conductance than the best large groups (downward slopping NCP D More details about the datasets FB-county network [BCK + 18, BB18]. This Facebook social network consists of 3100 counties (nodes) and 22138 edges. Two counties are connected with an edge if there exists strong social interaction between them as measured by Facebook interactions. In this report, out of all the edges we keep only those that correspond to counties less than 500 miles apart. The resulting graph is still a connected graph. The post-processed graph maintains the structural properties that are discussed in the original article and paper [BCK + 18, BB18], that is, social interaction tends to happen mostly among nearby counties.
Wi-Fi hotspots Montreal network [HHE + 15]. This is a public WIFI hotspot network which we interpret as a contact network. WIFI networks are commonly used as proxies of human contact networks for studying transmsision of infection across a network of individuals [HHE + 15, HSB + 16] This particular network is by Île Sans Fil (ÎSF), a not-for-profit organization established in 2004 in Montreal, Canada, that operates a system of public internet hotspots. Each individual user is a node and concurrent usage of the same hotspot is an edge. We use the post-processed network by [HHE + 15], which consists of 103425 nodes and 630893 edges.
Portland, Oregon network [EGK + 04]. This synthetic network was generated from time use and census data for the city of Portland, Oregon. It has also been widely used in infectious disease modelling [EGK + 04, BaLBB + 06, WKB13]. The full dataset consists of 1.6 million nodes and 31 million edges. We also make use of a sub-sampled version of this dataset that has 10, 000 nodes and 199, 168 edges [WKB13] . The reason that we sub-sample the original network is because the SP and CF betweenness methods do not scale to the initial network.
In this section we show complete simulation results for all four networks: Facebook County, Wi-Fi Montreal, Portland Sub-sampled, and Portland, including the plots that are omitted in the main text due to page limit. Predicted epidemic dynamics for intervention strategies that reduce 90% edge weights on targeted edges on the Facebook County network are shown in Figure 11 . Note that targeting edges according to LF(λ) betweenness leads to the most reduction in epidemic outbreak sizes for all initialization scenarios, and it consistently lowers the epidemic peaks by a large amount, which is more stable than other methods. For example, intervention based on the current-flow (CF) betweenness can give rise to very unstable epidemic peaks, as shown in Figure 11e when the epidemic starts from Los Angeles, California. Furthermore, observe that targeting high degree nodes can be less effective than uniformly reducing contacts throughout the network, as shown in Figure 11e and 11f. Figure 12 demonstrates the results on the Wi-Fi Montreal network, where LF(λ) is shown to be the most effective at reducing both epidemic peaks and total outbreak sizes.
The complete simulation results for both Portland Sub-sampled and full Portland networks, including the epidemic curves at 25% intervention level, are shown in Figure 13 and Figure 14 . Overall, LF(λ) still delivers the best outcome. The predicted epidemic results on Portland Sub-sampled demonstrates a trade-off in λ: a smaller λ = 1/50 yields the most reduction in total infections, and a larger λ = 1/4 or λ = 1/10 lowers the epidemic peaks more.
We carry out an additional complete set of experiments where the targeted edge weights are reduced by 99% in various intervention strategies. This can model, for example, situations where only emergency contacts are allowed over intervened contact channels in the network. Simulation results for this setting are shown in Figures 15, 16, G Additional experiments on LF(λ) with general p-norm for p larger than 2
Recall that LF(λ) is a special case of the more general p-norm flow betweenness defined in the main text, where p ∈ (1, ∞). Until now we have used p = 2 for LF(λ) because of its computational efficiency, but we don't necessarily need to restrict ourselves to the case p = 2. Furthermore, Theorem 3 states that a larger p > 2 induces a stronger clustering bias. In this section, we experiment with using different p values in the definition of λ-local betweenness. In particular, we take p = 4 and compute the corresponding LF(λ) betweenness, for λ ∈ {1/10, 1/50}. We pick p = 4 because, it has been empirically demonstrated in the local graph clustering settings [YWF20] that, p = 4 is large enough to produce a significantly stronger clustering bias than p = 2. The following empirical results demonstrate that this is indeed the case. For each of the four datasets, we compare interventions that reduce 90% edge weights on targeted edges based on LF(λ) for p = 2 and p = 4. The results are shown in Figures 19, 20, 21, 22 . As demonstrated and discussed in the main text, clustering bias plays a major role in the efficacy of interventions on the Facebook County network. Therefore, as expected and also as shown in Figure 19 , when p = 4 and λ = 1/50, LF(λ) produces larger reduction (up to 5% of total population) in the total outbreak sizes, while maintaining a similar outbreak peak level (up to 0.5% difference). On the other hand, the Wi-Fi Montreal network is a special network where more than half of nodes have degree one or two, so clustering should not help at all. This is Figure 11 : Simulation results for the Facebook County network when reducing 90% of the weights on targeted edges. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for four different initialization scenarios. In Scenario 1, the epidemic starts from New York, New York; In Scenario 2, the epidemic starts from Los Angeles, California; In Scenario 3, the epidemic starts from a well-connected cluster of 67 counties; In Scenario 4, the epidemic starts from a random selection of 1% of all counties across the country. We plot all epidemic curves at 25% intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization.
reflected in Figure 20 , where for λ = 1/50, the results for p = 2 and p = 4 are almost identical 8 . We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 101 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We plot epidemic curves at 25% intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization.
Finally, on the Portland Sub-sampled and full Portland, we see a trade-off between p = 2 and p = 4, that is, p = 4 does not always guarantee the largest reduction in both epidemic peak and outbreak size. Our results in this section demonstrate that if local clusters of the graph play an important role in spreading a disease (e.g., the Facebook County network), then using p = 4 can significantly improve intervention results; otherwise, p = 2 would suffice.
Even though our definition of p-norm flow betweenness naturally applies to edges due to its physical interpretation of expected optimal flow in a diffusion process, there is a straightforward extension to node-betweenness measures, by aggregating flows on all incident edges of a node, i.e., For example, a special case of this node-betweenness measure when P = U V × U V is the node current-flow betweenness [BF05].
In the rest of this section we show simulation results for intervention strategies that target important nodes based on node-betweenness measures. We compare node λ-local flow (LF(λ)) betweenness with a baseline method that targets High Degree (HD) nodes, and two nodebetweenness measures, namely, Shortest-Path (SP) and Current-Flow (CF). For each intervention method, we fix the number of intervened nodes, and we reduce edge weights by 90% on all edges incident to the targeted nodes. The results are shown in Figures 23, 24, 25, 26 . Observe that the advantage of LF(λ) is even more pronounced in this setting. In particular, LF(λ) clearly Figure 13 : Simulation results for the Portland Sub-sampled network when reducing 90% of the weights on targeted edges. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 80 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We plot epidemic curves at 25% intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization.
outperforms all other methods on the Facebook County network at reducing both the epidemic peak and the outbreak size. On the Wi-Fi Montreal and Portland Sub-sampled networks, all methods give similar results 9 , except that HD has a noticeably worse performance. Figure 14 : Simulation results for the full Portland network when reducing 90% of the weights on targeted edges. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 37 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We used λ = 1/1000 for scalability. The epidemic curves are drawn at 25% intervention level. We average over 50 trials for random initialization. Figure 15 : Simulation results for the Facebook County network when reducing 99% of the weights on targeted edges. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for four different initialization scenarios. In Scenario 1, the epidemic starts from New York, New York; In Scenario 2, the epidemic starts from Los Angeles, California; In Scenario 3, the epidemic starts from a well-connected cluster of 67 counties; In Scenario 4, the epidemic starts from a random selection of 1% of all counties across the country. We plot all epidemic curves at 25% intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization. Figure 16 : Simulation results for the Wi-Fi Montreal network when reducing 99% of the weights on targeted edges. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 101 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We plot epidemic curves at 25% intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization. Figure 17 : Simulation results for the Portland Sub-sampled network when reducing 99% of the weights on targeted edges. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 80 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We plot epidemic curves at 25% intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization. Figure 18 : Simulation results for the full Portland network when reducing 99% of the weights on targeted edges. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 37 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We used λ = 1/1000 for scalability. The epidemic curves are drawn at 25% intervention level. We average over 50 trials for random initialization. Figure 19 : Intervention results on the Facebook County network using LF(λ) for different p-norm objectives. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for four different initialization scenarios. In Scenario 1, the epidemic starts from New York, New York; In Scenario 2, the epidemic starts from Los Angeles, California; In Scenario 3, the epidemic starts from a well-connected cluster of 67 counties; In Scenario 4, the epidemic starts from a random selection of 1% of all counties across the country. Epidemic curves are drawn at 25% intervention level. We average over 50 trials for random initialization. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 101 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. Epidemic curves are drawn at 25% intervention level. We average over 50 trials for random initialization. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak), for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 80 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. Epidemic curves are drawn at 25% intervention level. We average over 50 trials for random initialization. Figure 22 : Intervention results on the full Portland network using LF(λ) for different p-norm objectives. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 37 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We used λ = 1/1000 for scalability. Epidemic curves are drawn at 25% intervention level. We average over 50 trials for random initialization. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for four different initialization scenarios. In Scenario 1, the epidemic starts from New York, New York; In Scenario 2, the epidemic starts from Los Angeles, California; In Scenario 3, the epidemic starts from a well-connected cluster of 67 counties; In Scenario 4, the epidemic starts from a random selection of 1% of all counties across the country. We plot all epidemic curves at 25% node intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 101 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We plot epidemic curves at 25% node intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 80 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We plot epidemic curves at 25% node intervention level, and we highlight the original epidemic curve (i.e., no intervention) along with the top 3 curves that achieve the mildest outbreak sizes. We average over 50 trials for random initialization. We illustrate Predicted epidemic curves, epidemic peaks (i.e., maximum daily active cases), and outbreak sizes (i.e., total number of infections throughout the outbreak) for two different initialization scenarios. In Scenario 1, the epidemic starts from a well-connected cluster of 37 infected persons; In Scenario 2, the epidemic starts from a random selection of 0.1% of all population as initially infectious. We used λ = 1/1000 for scalability. The epidemic curves are drawn at 25% intervention level. We average over 50 trials for random initialization.