NDFUSION

Network diffusion processes -- that is, the dynamics by which some information, behavior, or condition starting out with a single or a few individuals, propagates through the network to reach a potentially much larger number -- are ubiquitous in social, biological, and technological networks. The spread of rumors, trends and innovation in social networks, the spread of diseases and mutations in population networks, or viruses and worms in computer networks are just a few examples. In this project, we will study the effect of the network structure on diffusion processes, and in particular, the extent to which one can affect the outcome of the diffusion by controlling a small, possibly, carefully selected fraction of the network. For example, increase the spread or speed of diffusion by choosing an appropriate set of seed nodes (a standard goal in viral marketing by word-of-mouth), or achieve the opposite effect either by choosing a small set of nodes to remove (a goal in immunization against diseases), or by seeding a competing diffusion (e.g., to limit the spread of misinformation in a social network). Our goal is to provide a framework for a systematic and rigorous study of these problems. We will consider several standard diffusion models and extensions of them, including models from mathematical sociology, mathematical epidemiology, and interacting particle systems. We will consider existing and new variants of spread maximization/limitation problems, and will provide (approximation) algorithms or show negative (inapproximability) results. In case of negative results, we will investigate general conditions that make the problem tractable. We will consider both general network topologies and specific network models, and will relate the efficiency of solutions to structural properties of the topology. Finally, we will use these insights to engineer new network diffusion processes for efficient data dissemination.