Location driven influence maximization: Online spread via offline deployment

摘要

Existing works on influence maximization (IM) aim at finding influential online users as seed nodes. Originated from these seed nodes, large online influence spread can be triggered. However, such user-driven perspective limits the IM problem within the purely online environment. Due to the increasing interactions between the cyber world and the physical world, offline events in real world are showing more impact on online information spread. Most IM methods are totally unaware of the cyber–physical interactions and thus their effectiveness is limited when offline events are taken into account. To address this issue, in this paper we consider influence maximization from an online–offline interactive setting and propose the location-driven influence maximization (LDIM) problem. The LDIM problem aims to find the optimal offline deployment of locations and durations to hold events, so as to maximize the online influence spread. We propose a location-driven propagation (LDP) model to describe the online influence spread process triggered by offline events. Under the LDP model, we prove the LDIM problem is NP-hard and computing the objective function is #P-hard. Thus we develop a greedy algorithm over integer lattice and prove its 1−1∕e approximation. To overcome the expensive time complexity, we further develop two algorithms with time complexity reduced successively while ensuring provable approximation ratios of 1−1∕e−ε and 1−1∕e−ε−ε′ respectively. Experimental results on real datasets show the effectiveness of the proposed algorithms and the significant improvement on scalability.