Noncooperative information diffusion in online social networks

Abstract

Information diffusion in online social networks has received attention in both research and actual applications. The prevalence of online social networking sites offers the possibility of mining for necessary information. However, existing influence maximization algorithms and newly proposed influence diffusion models do not distinguish between seed nodes (or pilot users) and nonseed nodes and assume all nodes are cooperative in propagating influence. This thesis investigates models and heuristics for noncooperative information diffusion in online social networks. It consists of three parts: tragedy of the commons in online social search (OSS), influence maximization in noncooperative social networks under the linear threshold model (LTM), and influence maximization in noncooperative social networks under the independent cascade model (ICM). Firstly, the tragedy of the commons problem in OSS is considered. I propose an analytical model that captures the behavior of OSS nodes, and, from a gaming-strategy point of view, analyze various strategies an individual node can utilize to allocate its awareness capacity. Based on this I derive the Pareto inefficiency in terms of the system cost. An incentive scheme which can lead selfish nodes to the “social optimal” state of the whole system is also proposed. Extensive simulations show that the strategy with our proposed incentive mechanism outperforms other strategies in terms of the system cost and the search success rate. The second part of the thesis presents the first detailed analysis of influence maximization in noncooperative social networks under the LTM. The influence propagation process is structured into two stages, namely, seed node selection and influence diffusion. In the former, I introduce a generalized maximum-flow-based analytical framework to model the noncooperative behavior of individual users and develop a new seed node selection strategy. In the latter, I propose a game-theoretic model to characterize the behavior of noncooperative nodes and design a Vickrey-Clarke-Groves-like (VCG-like) scheme to incentivise cooperation. Then I study the budget allocation problem between the two stages, and show that a marketer can utilize the two proposed strategies to tackle noncooperation intelligently. The proposed schemes are evaluated on large coauthorship networks, and the results show that the proposed seed node selection scheme is very robust to noncooperation and the VCG-like scheme can effectively stimulate a node to become cooperative. Finally, I study the influence maximization problem in noncooperative social networks under the ICM using the same two-stage framework originally proposed for LTM. For the seed selection stage, a modified hierarchy-based seed node selection strategy which can take node noncooperation into consideration is introduced. The VCG-like incentive scheme designed for the influence diffusion stage under LTM can also be utilized for ICM in a similar manner. Then I also study the budget allocation problem between the two stages. The evaluation results show that the performance of the hierarchy-based seed node selection scheme is satisfactory in a noncooperative social network and the VCG-like scheme can effectively encourage node cooperation.