skip to main content


Title: 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
Author(s) / Creator(s):
;
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
  1. 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
  2. null (Ed.)
    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 infected nodes subject to a budget constraint on the total number of nodes that can be vaccinated. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. Since the optimization problem is NP-hard, we develop a heuristic based on a generalization of the set cover problem. Using experiments on three real-world networks, we compare the performance of the heuristic with some baseline methods. 
    more » « less
  3. null (Ed.)
    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 infected nodes subject to a budget constraint on the total number of nodes that can be vaccinated. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. Since the optimization problem is NP-hard, we develop a heuristic based on a generalization of the set cover problem. Using experiments on three real-world networks, we compare the performance of the heuristic with some baseline methods. 
    more » « less
  4. 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
  5. 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