Influence maximization by leveraging the crowdsensing data in information diffusion network

Abstract The algorithm of influence maximization aims at detecting the top- k influential users (seed set) in the network, which has been proved that finding an optimal solution is NP hard. To address this challenge, finding the trade-off between the effectiveness and efficiency may be a more realistic approach. How to accurately calculate the influence probability is a fundamental and open problem in influence maximization. The existing researches mainly adopted the pair-wise parameters to denote the influence spread probability. These approaches suffer severe over-representing and overfitting problems, and thus perform poorly for the influence maximization problem. In this paper, we calculate the influence probability by learning low-dimensional vectors (i.e., influence vector and susceptibility vector) based on the crowdsensing data in the information diffusion network. With much fewer parameters and opposed to the pair-wise manner, our approach can overcome the overfitting problem, and provide a foundation for solving the problem effectively. Moreover, we propose the DiffusionDiscount algorithm based on the novel method of influence probability calculation and heuristic pruning approach, which can achieve high time efficiency. The experimental results show that our algorithm outperforms other five typical algorithms over the real-world datasets, and can be more practical in large-scale data sets.