DIMACS TR: 2007-20
Maximizing the Extent of Spread in a Dynamic Network
Authors: Habiba and Tanya Y. Berger-Wolf
ABSTRACT
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