Competitive Influence Maximization within Time and Budget Constraints in Online Social Networks: An Algorithmic Approach

Abstract

Competitive Influence Maximization ( CIM ) problem, which seeks a seed set nodes of a player or a company to propagate their product’s information while at the same time their competitors are conducting similar strategies, has been paid much attention recently due to its application in viral marketing. However, existing works neglect the fact that the limited budget and time constraints can play an important role in competitive influence strategy of each company. In addition, based on the the assumption that one of the competitors dominates in the competitive influence process, the majority of prior studies indicate that the competitive influence function (objective function) is monotone and submodular.This led to the fact that CIM can be approximated within a factor of 1 − 1 / e − ϵ by a Greedy algorithm combined with Monte Carlo simulation method. Unfortunately, in a more realistic scenario where there is fair competition among competitors, the objective function is no longer submodular. In this paper, we study a general case of CIM problem, named Budgeted Competitive Influence Maximization ( BCIM ) problem, which considers CIM with budget and time constraints under condition of fair competition. We found that the objective function is neither submodular nor suppermodular. Therefore, it cannot admit Greedy algorithm with approximation ratio of 1 − 1 / e . We propose Sandwich Approximation based on Polling-Based Approximation ( SPBA ), an approximation algorithm based on Sandwich framework and polling-based method. Our experiments on real social network datasets showed the effectiveness and scalability of our algorithm that outperformed other state-of-the-art methods. Specifically, our algorithm is scalable with million-scale networks in only 1.5 min.

Keywords

• social networks
• competitive influence maximization
• optimization
• approximation algorithm