Analysis and Control of Cascades in Complex Networks

Abstract

Our modern societies are best described as complex systems consisting of a large number of interacting components. Understanding the nature of these interactions is crucial, not only for gaining insights, but also for shaping their evolution. Modeling complex systems using networks, where nodes represent interacting agents, while links represent the interactions between these agents, can be useful for analyzing these systems. For example, social systems can be represented using social networks, where nodes represent individuals and links represent interactions or relationships between them. Thanks to information and communication technologies, the large scale availability of data allows us to study the nature and function of these networks. For example, large scale data on social connections allows us to gain an understanding of the architecture of these networks, which in turn is very useful for a variety of tasks, like preventing the spread of infectious diseases, marketing products and services, or influencing a large section of the population. Taking advantage of this data, here we aim to (a) study the effects of network structure on processes like epidemics and failure cascades on networks, and (b) formulate cost effective policies for influencing cascades such as information and marketing campaigns.

We study contagion dynamics on a variety of networks such as time varying and interacting networks. In particular, we study (a) the impact of human behavior on biological epidemics in time varying networks, and (b) cascading node and link failures in a system consisting of two networks exhibiting dependent and antagonistic interactions. Our investigations reveal useful insights, e.g., in time varying networks, results suggest an existence of an adaptive threshold As for the interacting networks problem, we found that the phase transition observed in our system is very different from the one seen in commonly studied interacting networks.

After having studied cascades, we take the next step of controlling them. Campaigners, advertisers and activists are increasingly turning to social recommendation mechanisms provided by social media for promoting their products, services, brands and even ideas. One widely used promotion strategy is incentivizing individuals, using referral rewards or other discounts, for encouraging them to spread the word. Due to budget constraints on scarce monetary incentives, it may not be possible to provide incentives for the entire population. Thus, there is a need to allocate resources judiciously for ensuring the highest possible campaign size. We address this problem of maximizing the campaign penetration in social networks under budget constraints and the dual problem of minimizing campaigning cost while ensuring a given campaign size. We formulate the optimization problems using percolation theory. Although the problems turn out to be non-trivial, we show that they can be reduced to simple linear programs, which can be further simplified and solved using simple algorithms with linearithmic complexity. Simulations on real world networks suggest that the proposed solutions could work in a real world setting.