Spread of influence is one of the most widely studied propagation processes in the literature on complex networks. Examples include the rise of collective action to join a riot and diffusion of beliefs, norms, and cultural fads, to name a few. Most existing works on modeling influence propagation consider a single content (e.g., an opinion, decision, product, political view, etc.) spreading over a network independent from everything else. However, most real-life examples involve multiple correlated contents spreading simultaneously and exhibiting positive (e.g., opinions on same-sex marriage and gun control) or negative (e.g., opinions on universal health care and tax-relief for the “rich”) correlation. To accommodate these cases, this paper proposes the vector threshold model, as an extension of the widely used Watts threshold model for complex contagions. Here, the state of a node is represented by a binary vector representing their opinion on a number of content items. Nodes switch their states based on the influence they receive from their neighbors in the network. The influence is represented by a vector containing the proportion of neighbors who support each content; both positively and negatively correlated contents can be captured in this formulation by using different rules for switching node states. Our main result is concerned with the expected size of global cascades, i.e., cases where a randomly chosen node can initiate a propagation that eventually reaches a positive fraction of the whole population. We also derive conditions on network structure for global cascades to be possible. Analytic results are supported by a numerical study.
more »
« less
Influence Propagation with Multiple Stages over Random Multiplex Networks
Complex contagion models have been developed to understand a wide range of social phenomena such as adoption of cultural fads, the diffusion of belief, norms, and innovations in social networks, and the rise of collective action to join a riot. Most existing works focus on contagions where individuals’ states are represented by binary variables, and propagation takes place over a single isolated network. However, characterization of an individual’s standing on a given matter as a binary state might be overly simplistic as most of our opinions, feelings, and perceptions vary over more than two states. Also, most real-world contagions take place over multiple networks (e.g., Twitter and Facebook) or involve multiplex networks where individuals engage in different types of relationships (e.g., co-worker, family, etc.). To this end, this paper studies multi-stage complex contagions that take place over multi-layer or multiplex networks. Under a linear threshold based contagion model, we first give analytic results for the expected size of global cascades, i.e., cases where a randomly chosen node can initiate a propagation that eventually reaches a positive fraction of the whole population. Then, analytic results are confirmed by an extensive numerical study. In addition, we demonstrate how the dynamics of complex contagions is affected by the structural properties of the networks. In particular, we reveal an interesting connection between the assortativity of a network and the impact of hyper-active nodes on the cascade size.
more »
« less
- Award ID(s):
- 1813637
- NSF-PAR ID:
- 10196221
- Date Published:
- Journal Name:
- 2019 IEEE Global Communications Conference (GLOBECOM)
- Page Range / eLocation ID:
- 1 to 6
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Nonpharmaceutical interventions (NPIs) such as mask wearing can be effective in mitigating the spread of infectious diseases. Therefore, understanding the behavioral dynamics of NPIs is critical for characterizing the dynamics of disease spread. Nevertheless, standard infection models tend to focus only on disease states, overlooking the dynamics of “beneficial contagions,” e.g., compliance with NPIs. In this work, we investigate the concurrent spread of disease and mask-wearing behavior over multiplex networks. Our proposed framework captures both the competing and complementary relationships between the dueling contagion processes. Further, the model accounts for various behavioral mechanisms that influence mask wearing, such as peer pressure and fear of infection. Our results reveal that under the coupled disease–behavior dynamics, the attack rate of a disease—as a function of transition probability—exhibits a critical transition. Specifically, as the transmission probability exceeds a critical threshold, the attack rate decreases abruptly due to sustained mask-wearing responses. We empirically explore the causes of the critical transition and demonstrate the robustness of the observed phenomena. Our results highlight that without proper enforcement of NPIs, reductions in the disease transmission probability via other interventions may not be sufficient to reduce the final epidemic size.more » « less
-
We consider SIS contagion processes over networks where, a classical assumption is that individuals' decisions to adopt a contagion are based on their immediate neighbors. However, recent literature shows that some attributes are more correlated between two-hop neighbors, a concept referred to as monophily. This motivates us to explore monophilic contagion, the case where a contagion (e.g. a product, disease) is adopted by considering two-hop neighbors instead of immediate neighbors (e.g. you ask your friend about the new iPhone and she recommends you the opinion of one of her friends). We show that the phenomenon called friendship paradox makes it easier for the monophilic contagion to spread widely. We also consider the case where the underlying network stochastically evolves in response to the state of the contagion (e.g. depending on the severity of a flu virus, people restrict their interactions with others to avoid getting infected) and show that the dynamics of such a process can be approximated by a differential equation whose trajectory satisfies an algebraic constraint restricting it to a manifold. Our results shed light on how graph theoretic consequences affect contagions and, provide simple deterministic models to approximate the collective dynamics of contagions over stochastic graph processes.more » « less
-
Abstract We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.more » « less
-
We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/GLOBECOM38437.2019.9013531
