PPRank: Economically Selecting Initial Users for Influence Maximization in Social Networks

摘要

This paper focuses on seeking a new heuristic scheme for an influence maximization problem in social networks: how to economically select a subset of individuals (so-called seeds) to trigger a large cascade of further adoptions of a new behavior based on a contagion process. Most existing works on selection of seeds assumed that the constant number k seeds could be selected, irrespective of the intrinsic property of each individual's different susceptibility of being influenced (e.g., it may be costly to persuade some seeds to adopt a new behavior). In this paper, a price-performance-ratio inspired heuristic scheme, PPRank, is proposed, which investigates how to economically select seeds within a given budget and meanwhile try to maximize the diffusion process. Our paper's contributions are threefold. First, we explicitly characterize each user with two distinct factors: the susceptibility of being influenced (SI) and influential power (IP) representing the ability to actively influence others and formulate users' SIs and IPs according to their social relations, and then, a convex price-demand curve-based model is utilized to properly convert each user's SI into persuasion cost (PC) representing the cost used to successfully make the individual adopt a new behavior. Furthermore, a novel cost-effective selection scheme is proposed, which adopts both the price performance ratio (PC-IP ratio) and user's IP as an integrated selection criterion and meanwhile explicitly takes into account the overlapping effect; finally, simulations using both artificially generated and real-trace network data illustrate that, under the same budgets, PPRank can achieve larger diffusion range than other heuristic and brute-force greedy schemes without taking users' persuasion costs into account.