Zhifeng Sun

Thesis Proposal

Title: Enabling and Controlling Diffusion Processes in Networks


Diffusion processes are important models for many real-world phenomena, such as the spread of disease or rumors. We propose to study different aspects of diffusion processes in networks, focusing on designing efficient distributed algorithms for positive diffusion processes and good intervention strategies to control harmful diffusions.

First, we design and analyze various distributed algorithms for diffusion processes. We want to devise efficient distributed algorithms, which are easy to implement, to help the spreading of positive/useful information. We refer to these processes as positive diffusions. Earlier work has studied this for a variety of models, mainly based on static networks. The major point that separates our research with previous work is that we consider dynamically changing networks, which extends previous models to a larger range of real-life situations. Depending on the ways that networks are altered, we propose to study diffusion processes over the following two types of dynamic networks: (1) networks are changed due to individuals' decisions or behaviors; (2) networks are controlled by an adversary.

Secondly, we study how to devise good intervention strategies to control diffusion processes. This problem is crucial when we deal with harmful information like human diseases or computer viruses. We refer to these processes as harmful diffusions. We distinguish between centralized and decentralized intervention strategies. In centralized intervention strategies, there is a controller who has a limited amount of intervention resources (e.g. vaccinations or antidotes in the case of diseases). We study the problem of allocating these limited resources among the network agents so that the spread of the diffusion process is minimized. In decentralized intervention strategies, each individual in the network makes their own decision on protecting themselves, based on their individual utility and local knowledge. In such settings, we are interested in questions such as: is there a stable set of intervention strategies? What's the cost of decentralized solutions compared with an optimal centralized one? Lastly, we augment our studies of intervention strategies with the consideration about individual behavior changes which would lead to a new kind of network dynamics. Earlier work has shown that the combination of behavior change and intervention failure (e.g. failed vaccination) can lead to perverse outcomes where less (intervention resources) is more (effective). However, the extent of the perversity and its dependence on network structure as well as the precise nature of the behavior change has remained largely unknown.

[Thesis proposal] [Presentation]


Entire dissertation

Table of Contents
Chapter 1: Introduction
Chapter 2: Diffusion under organic dynamics
Chapter 3: Diffusion under adversarial dynamics
Chapter 4: Controlling negative diffusion
Chapter 5: Controlling negative diffusion in the presence of risk behavior changes.
Chapter 6: Conclusion

Committee members

Rajmohan Rajaraman (advisor)
Ravi Sundaram
Emanuele Viola
Devavrat Shah (external member, MIT)

Justification for thesis committee composition: Ravi Sundaram is an expert in networking and algorithms and has closely worked with Zhifeng on the second part of his thesis proposal -- control of diffusion processes. Emanuele Viola is an expert in theoretical computer science and can situate the contributions of the thesis in the wider body of theory research. Devavrat Shah works in the area of complex networks and distributed computing, and has influential results in the area of gossip-based communcation, a focus of the first part of Zhifeng's proposal.