  The influence maximization (IM) problem as defined in the seminal paper by
Kempe et al. has received widespread attention from various research
communities, leading to the design of a wide variety of solutions.
Unfortunately, this classical IM problem ignores the fact that time taken for
influence propagation to reach the largest scope can be significant in
realworld social networks, during which the underlying network itself may have
evolved. This phenomenon may have considerable adverse impact on the quality of
selected seeds and as a result all existing techniques that use this classical
definition as their building block generate seeds with suboptimal influence
spread. In this paper, we revisit the classical IM problem and propose a more
realistic version called PROTEUS-IM (Propagation Time conscious Influence
Maximization) to replace it by addressing the aforementioned limitation.
Specifically, as influence propagation may take time, we assume that the
underlying social network may evolve during influence propagation.
Consequently, PROTEUSIM aims to select seeds in the current network to maximize
influence spread in the future instance of the network at the end of influence
propagation process without assuming complete topological knowledge of the
future network. We propose a greedy and a Reverse Reachable (RR) set-based
algorithms called PROTEUS-GENIE and PROTEUS-SEER, respectively, to address this
problem. Our algorithms utilize the state-of-the-art Forest Fire Model for
modeling network evolution during influence propagation to find superior
quality seeds. Experimental study on real and synthetic social networks shows
that our proposed algorithms consistently outperform state-of-the-art classical
IM algorithms with respect to seed set quality.
