Noncooperative Information Diffusion in Online Social Networks Under the Independent Cascade Model

摘要

In this paper, we present the first detailed analysis of influence maximization in noncooperative social networks under the Independent Cascade Model (ICM). We propose a new influence model based on the ICM and prove the approximation guarantees for influence maximization in noncooperative settings. We structure the influence diffusion into two stages, namely, seed node selection and influence diffusion. In the former, we introduce a modified hierarchy-based seed node selection strategy, which can take node noncooperation into consideration. In the latter, we propose a game-theoretic model to characterize the behavior of noncooperative nodes and design a Vickrey- Clarke-Groves (VCG)-like scheme to incentivise cooperation. Then, we study the budget allocation problem between the two stages, and show that a marketer can utilize the two proposed strategies to tackle noncooperation intelligently. We evaluate our proposed schemes on large coauthorship networks, and the results show that our seed node selection scheme is very robust to noncooperation and the VCG-like scheme can effectively stimulate a node to become cooperative.