  Influence maximization is a problem of finding a small set of highly
influential users, also known as seeds, in a social network such that the
spread of influence under certain propagation models is maximized. In this
paper, we consider time-critical influence maximization, in which one wants to
maximize influence spread within a given deadline. Since timing is considered
in the optimization, we also extend the Independent Cascade (IC) model and the
Linear Threshold (LT) model to incorporate the time delay aspect of influence
diffusion among individuals in social networks. We show that time-critical
influence maximization under the time-delayed IC and LT models maintains
desired properties such as submodularity, which allows a greedy approximation
algorithm to achieve an approximation ratio of $1-1/e$. To overcome the
inefficiency of the greedy algorithm, we design two heuristic algorithms: the
first one is based on a dynamic programming procedure that computes exact
influence in tree structures and directed acyclic subgraphs, while the second
one converts the problem to one in the original models and then applies
existing fast heuristic algorithms to it. Our simulation results demonstrate
that our algorithms achieve the same level of influence spread as the greedy
algorithm while running a few orders of magnitude faster, and they also
outperform existing fast heuristics that disregard the deadline constraint and
delays in diffusion.
