Title: STIM: Scalable Time-Sensitive Influence Maximization in Large Social Networks
Authors: Yuanyuan Zhu, Kailin Ding, Ming Zhong and Lijia Wei
Abstract: Influence maximization, aiming to select k seed users to influence the rest of users maximally, is a fundamental problem in social networks. Due to its well-known NP-hardness, great efforts have been devoted to developing scalable algorithms in the literature. However, the scalability issue is still not well solved in the time-sensitive influence maximization problem when propagation incurs a certain amount of time delay and only be valid before a deadline constraint, because all possible time delays need to be enumerated along each edge in a path to calculate the influence probability. Existing approaches usually adopt a pathbased search strategy to enumerate all the possible influence spreading paths for a single path, which are computationally expensive for large social networks. In this paper, we propose a novel scalable time-sensitive influence maximization method, STIM, based on time-based search that can avoid a large number of repeated visits of the same subpaths and compute the influence probability more efficiently. Furthermore, based on time-based search, we also derive a new upper bound to estimate the marginal influence spread efficiently. Extensive experiments on real-world networks show that STIM is more space and time-efficient compared with existing state-of-the-art methods while still preserving the influence spread quality in real-world large social networks.
