Dominated competitive influence maximization with time-critical and time-delayed diffusion in social networks

摘要

Online social networks (OSNs) have become important platforms for information dissemination. The competitive diffusions of multiple information are very common in online social networks, thus how to restrain the influence of other information and enhance the influence of desired information at the same time is a critical problem for practical applications, such as viral marketing and advertising pricing. In order to develop an optimal strategy to the competitive diffusions of information, a problem named dominated competitive influence maximization (DCIM) is proposed in this paper, which researches how to maximize the difference value between the influence of desired information and its competitors. Due to the complexity of the diffusion environment, both time limitation and time delay in the propagation process need to be taken into consideration, which have been included in the independent cascade model with meeting events (lC-M) model. However, IC-M model can only deal with single information diffusion. Based on the IC-M model, the competitive independent cascade model with meeting events (CIC-M) model is proposed to be applicable to competitive information diffusion. Then DCIM problem under CIC-M model is proved to be NP-hard, but with the properties of monotonicity and submodularity. According to these properties, 1 - 1/e approximation precision is guaranteed to be achieved with greedy algorithm. In order to improve the efficiency of greedy algorithm to be applicable to large-scale network, an algorithm named DCIM_CELF is put forward to solve the DCIM problem under CIC-M model. Extensive experiments are conducted on four real-world datasets, proving that the DCIM problem under CIC-M model is solvable. In addition, comparative experimental results show that DCIM_CELF algorithm achieves better performance than two basic heuristic algorithms. (C) 2017 Elsevier B.V. All rights reserved.