An official website of the United States government
Abstract—There are myriad real-life examples of contagion processes on human social networks, e.g., spread of viruses, information, and social unrest. Also, there are many methods to control or block contagion spread. In this work, we introduce a novel method of blocking contagions that uses nodes from dominating sets (DSs). To our knowledge, this is the first use of DS nodes to block contagions. Finding minimum dominating sets of graphs is an NP-Complete problem, so we generalize a well-known heuristic, enabling us to customize its execution. Our method produces a prioritized list of dominating nodes, which is, in turn, a prioritized list of blocking nodes. Thus, for a given network, we compute this list of blocking nodes and we use it to block contagions for all blocking node budgets, contagion seed sets, and parameter values of the contagion model. We report on computational experiments of the blocking efficacy of our approach using two mined networks. We also demonstrate the effectiveness of our approach by comparing blocking results with those from the high degree heuristic, which is a common standard in blocking studies. Index Terms—contagion blocking, dominating sets, threshold models, social networks, simulation, high degree heuristic
more »
« less
This content will become publicly available on September 3, 2025
Blocking Social Contagions via Dominating Sets Using a Modified Integer Linear Program Formulation
Researchers have modeled contagion processes on social networks for wide ranging applications, including spreading of epidemics, financial defaults, actions such as joining social media sites, and rumors. So, too, researchers have developed a host of intervention methods to control harmful contagions on networks; among these approaches are node and edge removal, separating network communities, altering contagion properties, and introducing a second competing contagion. In this work, minimum dominating sets are used to identify blocking nodes—nodes that do not contract a contagion and therefore also do not assist in transmitting it. A novel, generalized method that utilizes integer linear programming to determine exact minimum dominating sets (which is an NP-hard problem) has been developed for a subgraph of any social network for any combination of covering distance and coverage requirement. Three social networks are used to understand and evaluate (i) the method itself and (ii) the efficacy of the blocking nodes that the method produces to stop contagion spread.
more »
« less
- Award ID(s):
- 2428625
- PAR ID:
- 10561405
- Publisher / Repository:
- IEEE
- Date Published:
- Subject(s) / Keyword(s):
- Social networks Contagion Blocking Dominating sets Integer linear programs
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
There are myriad real-life examples of contagion processes on human social networks, e.g., spread of viruses, information, and social unrest. Also, there are many methods to control or block contagion spread. In this work, we introduce a novel method of blocking contagions that uses nodes from dominating sets (DSs). To our knowledge, this is the first use of DS nodes to block contagions. Finding minimum dominating sets of graphs is an NP-Complete problem, so we generalize a well-known heuristic, enabling us to customize its execution. Our method produces a prioritized list of dominating nodes, which is, in turn, a prioritized list of blocking nodes. Thus, for a given network, we compute this list of blocking nodes and we use it to block contagions for all blocking node budgets, contagion seed sets, and parameter values of the contagion model. We report on computational experiments of the blocking efficacy of our approach using two mined networks. We also demonstrate the effectiveness of our approach by comparing blocking results with those from the high degree heuristic, which is a common standard in blocking studies.more » « less
-
null (Ed.)Many contagion processes evolving on populations do so simultaneously, interacting over time. Examples are co-evolution of human social processes and diseases, such as the uptake of mask wearing and disease spreading. Commensurately, multi-contagion agent-based simulations (ABSs) that represent populations as networks in order to capture interactions between pairs of nodes are becoming more popular. In this work, we present a new ABS system that simulates any number of contagions co-evolving on any number of networked populations. Individual (interacting) contagion models and individual networks are speci ed, and the system computes multi-contagion dynamics over time. This is a signi cant improvement over simulation frameworks that require union graphs to handle multiple networks, and/or additional code to orchestrate the computations of multiple contagions. We provide a formal model for the simulation system, an overview of the software, and case studies that illustrate applications of interacting contagions.more » « less
-
Many contagion processes evolving on populations do so simultaneously, interacting over time. Examples are co-evolution of human social processes and diseases, such as the uptake of mask wearing and disease spreading. Commensurately, multi-contagion agent-based simulations (ABSs) that represent populations as networks in order to capture interactions between pairs of nodes are becoming more popular. In this work, we present a new ABS system that simulates any number of contagions co-evolving on any number of networked populations. Individual (interacting) contagion models and individual networks are specified, and the system computes multi-contagion dynamics over time. This is a significant improvement over simulation frameworks that require union graphs to handle multiple networks, and/or additional code to orchestrate the computations of multiple contagions. We provide a formal model for the simulation system, an overview of the software, and case studies that illustrate applications of interacting contagions.more » « less
-
Common knowledge (CK) is a phenomenon where a group of individuals each knows some collection of information, and, in essence, everyone knows that everyone knows the information. There are many applications involving CK, including business decision making, protests and rebellions, and online advertising. CK can lead to contagion and collective action but in ways that are fundamentally different from classic (e.g., Granovetter) threshold models used in the social sciences. Researchers developed CK models to enable the computation of contagion in networked populations. But these models have largely not been investigated using experiments with human subjects. In this work, we conduct a successive analysis of online CK experiments. We devise a flexible and interpretable statistical method to investigate the effects of significant factors, such as network structure and communication type. Among our findings, we demonstrate a phase change in group payout in the games that is caused by prohibiting player communication.more » « less
