An official website of the United States government
In widely used models of biological contagion, interventions that randomly rewire edges (generally making them 'longer') accelerate spread. However, recent work has argued that highly clustered, rather than random, networks facilitate the spread of threshold-based contagions, such as those motivated by myopic best response for adoption of new innovations, norms and products in games of strategic complement. Here we show that minor modifications to this model reverse this result, thereby harmonizing qualitative facts about how network structure affects contagion. We analyse the rate of spread over circular lattices with rewired edges and show that having a small probability of adoption below the threshold probability is enough to ensure that random rewiring accelerates the spread of a noisy threshold-based contagion. This conclusion is verified in simulations of empirical networks and remains valid with partial but frequent enough rewiring and when adoption decisions are reversible but infrequently so, as well as in high-dimensional lattice structures.
more »
« less
A Dynamic Contagion Risk Model with Recovery Features
We introduce threshold growth in the classical threshold contagion model, or equivalently a network of Cramér-Lundberg processes in which nodes have downward jumps when there is a failure of a neighboring node. Choosing the configuration model as underlying graph, we prove fluid limits for the baseline model, as well as extensions to the directed case, state-dependent interarrival times and the case of growth driven by upward jumps. We obtain explicit ruin probabilities for the nodes according to their characteristics: initial threshold and in- (and out-) degree. We then allow nodes to choose their connectivity by trading off link benefits and contagion risk. We define a rational equilibrium concept in which nodes choose their connectivity according to an expected failure probability of any given link and then impose condition that the expected failure probability coincides with the actual failure probability under the optimal connectivity. We show existence of an asymptotic equilibrium and convergence of the sequence of equilibria on the finite networks. In particular, our results show that systems with higher overall growth may have higher failure probability in equilibrium.
more »
« less
- Award ID(s):
- 1653354
- PAR ID:
- 10309341
- Date Published:
- Journal Name:
- Mathematics of Operations Research
- ISSN:
- 0364-765X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Many applications, e.g., federated learning, require the aggregation of information across a large number of distributed nodes. In this paper, we explore efficient schemes to do this at scale leveraging aggregation at intermediate nodes across overlay trees. Files/updates are split into chunks which are in turn simultaneously aggregated over different trees. For a synchronous setting with homogeneous communications capabilities and deterministic link delays, we develop a delay optimal aggregation schedule. In the asynchronous setting, where delays are stochastic but i.i.d., across links, we show that for an asynchronous implementation of the above schedule, the expected aggregation delay is near-optimal. We then consider the impact that failures in the network have on the resulting Mean Square Error (MSE) for the estimated aggregates and how it can be controlled through the addition of redundancy, reattempts, and optimal failure-aware estimates for the desired aggregate. Based on the analysis of a natural model of failures, we show how to choose parameters to optimize the trade-off between aggregation delay and MSE. We present simulation results exhibiting the above mentioned tradeoffs. We also consider a more general class of correlated failures and demonstrate via simulation the applicability of our techniques in those settings as well.more » « less
-
Network connectivity, i.e., the reachability of any network node from all other nodes, is often considered as the default network survivability metric against failures. However, in the case of a large-scale disaster disconnecting multiple network components, network connectivity may not be achievable. On the other hand, with the shifting service paradigm towards the cloud in today’s networks, most services can still be provided as long as at least a content replica is available in all disconnected network partitions. As a result, the concept of content connectivity has been introduced as a new network survivability metric under a large-scale disaster. Content connectivity is defined as the reachability of content from every node in a network under a specific failure scenario. In this work, we investigate how to ensure content connectivity in optical metro networks. We derive necessary and sufficient conditions and develop what we believe to be a novel mathematical formulation to map a virtual network over a physical network such that content connectivity for the virtual network is ensured against multiple link failures in the physical network. In our numerical results, obtained under various network settings, we compare the performance of mapping with content connectivity and network connectivity and show that mapping with content connectivity can guarantee higher survivability, lower network bandwidth utilization, and significant improvement of service availability.more » « less
-
Fear of reprisals such as violence and punishment can inhibit citizens from speaking out, or make them more reluctant to act, in opposition to a repressive regime. Protests are one form of opposition, and their growth has been successfully modeled as an influence-based contagion process within a social network (representing a population). In these models, an individual joins a protest if a sufficient number of her neighbors has already joined. This required number of neighbors is often called a “threshold.” In this study, we model a regime’s ability to suppress protests by instilling fear in a subset of a population, and this fear is manifested by an increase in a person’s threshold. We consider different social networks, numbers of seed nodes, and amounts of fear. Through simulations, we present several results. For example, we demonstrate that, for the objective of reducing the size of a protest, inducing fear can be more advantageous than removing nodes from a network.more » « less
-
Althouse, Benjamin Muir (Ed.)Disease epidemic outbreaks on human metapopulation networks are often driven by a small number of superspreader nodes, which are primarily responsible for spreading the disease throughout the network. Superspreader nodes typically are characterized either by their locations within the network, by their degree of connectivity and centrality, or by their habitat suitability for the disease, described by their reproduction number ( R ). Here we introduce a model that considers simultaneously the effects of network properties and R on superspreaders, as opposed to previous research which considered each factor separately. This type of model is applicable to diseases for which habitat suitability varies by climate or land cover, and for direct transmitted diseases for which population density and mitigation practices influences R . We present analytical models that quantify the superspreader capacity of a population node by two measures: probability-dependent superspreader capacity, the expected number of neighboring nodes to which the node in consideration will randomly spread the disease per epidemic generation, and time-dependent superspreader capacity, the rate at which the node spreads the disease to each of its neighbors. We validate our analytical models with a Monte Carlo analysis of repeated stochastic Susceptible-Infected-Recovered (SIR) simulations on randomly generated human population networks, and we use a random forest statistical model to relate superspreader risk to connectivity, R , centrality, clustering, and diffusion. We demonstrate that either degree of connectivity or R above a certain threshold are sufficient conditions for a node to have a moderate superspreader risk factor, but both are necessary for a node to have a high-risk factor. The statistical model presented in this article can be used to predict the location of superspreader events in future epidemics, and to predict the effectiveness of mitigation strategies that seek to reduce the value of R , alter host movements, or both.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/moor.2021.1174
