Ph.D. Theses

Optimizing Diffusion and Pricing in Networks of Independent Agents

By Ameya Hate
Advisor: Elliot Anshelevich
March 20, 2012

Diffusion is a process through which contagious entities (such as ideas, viruses etc.) spread through a population of objects over links between them. An important area for the study of diffusive process is social networks, where objects are individuals and they are linked if they "know" or can "influence" each other. Because social networks play an important role in the spread of ideas, influence, and information among individuals of the network, study of diffusive processes in such settings is of interest to many. The entities that have an ability to spread through a network may not always be benign. A malicious meme or a contagious disease can also diffuse over a social network. In such cases it becomes important to study methods and techniques to limit the spread of such diffusive processes.

In this thesis we try and address some of these problems. We first look at the scenario where a malevolent entity is diffusing through a network and there are limited resources available to curb its spread. The goal here is provide rigorous theoretical analysis and come up with provably efficient algorithms. The model used for this analysis is simple but it does capture the essence of hardness of these problems. On the other hand, we also study diffusion in a more general scenario which takes into consideration many of the complexities encountered in real situations. Specifically, we develop heuristics for maximizing diffusion of evacuation and warning messages in real life scenarios taking into consideration the complex social interactions that drive the diffusion.

We also study a somewhat different topic that deals with efficiency of the Internet. One of the principal factors behind phenomenal growth of the Internet has been decentralization of control, which also allows it to be modeled naturally as a system of interacting but independent, self-interested agents. The Internet can be viewed as a collection of ISPs or ASes (Autonomous Systems) that are interested in routing and pricing traffic to maximize their individual revenues. While the study of efficiency of the Internet seems to be unrelated to diffusive processes, many of the analytical tools required to examine both scenarios are the same. Both contain networks of agents behaving independently of each other. In fact, as we show in our work, efficiency of the Internet depends on optimal allocation of resources which can be achieved by diffusion of "prices" through the network. As ISPs are generally interested in maximizing their individual profits, this question is naturally studied in the framework of non-cooperative game theory.

Return to main PhD Theses page