DIMACS TR: 2007-20

Maximizing the Extent of Spread in a Dynamic Network

Authors: Habiba and Tanya Y. Berger-Wolf


Dynamic population phenomena, such as the spread of diseases, opinions, and behavior, can be modeled as processes that propagate in a network of interacting individuals. In this paper, we focus on the problem of identifying a set of individuals to initiate this spread so that the resulting extent of the spread is maximized. Kempe et al.("Maximizing the Spread of Influence in a Social Network". KDD'03) have solved this problem for the aggregate representation of the population network. Yet,real populations are inherently dynamic. In this paper we extend the approach of Kempe et al. to explicitly dynamic networks. We show that, for two common models of spread, maximizing the extent of spread in a dynamic network is an NP-hard problem. We present an (1-1/e)-approximation algorithm, evaluate the performance of the algorithm experimentally on real datasets and show that it performs well in practice. In addition, we compare the dynamic and the aggregate network representations both in terms of the resulting extent of spread and the actual set of initiating individuals that maximize the spread. We show that there are significant differences in both cases. Thus, we demonstrate that ignoring the dynamic aspects of data may result in extremely inaccurate answers and explicitly dynamic analysis is necessary.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-20.ps.gz
DIMACS Home Page