PPRank: Economically selecting initial users for influence maximization in social networks

This paper focuses on seeking a new heuristic schem for an influence maximization problem in social networks: ho to economically select a subset of individuals (so-called seeds) t trigger a large cascade of further adoptions of a new behavio based on a contagion process. Most existing works on selectio of seeds assumed that the constant number k seeds could b selected, irrespective of the intrinsic property of each individual' different susceptibility of being influenced (e.g., it may be costl to persuade some seeds to adopt a new behavior). In this paper a price-performance-ratio inspired heuristic scheme, PPRank, i proposed, which investigates how to economically select seed within a given budget and meanwhile try to maximize the diffusio process. Our paper's contributions are threefold. First, w explicitly characterize each user with two distinct factors: Th susceptibility of being influenced (SI) and influential power (IP representing the ability to actively influence others and formulat users' SIs and IPs according to their social relations, and then a convex price-demand curve-based model is utilized to properl convert each user's SI into persuasion cost (PC) representing th cost used to successfullymake 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 meanwhil explicitly takes into account the overlapping effect; finally, simulation using both artificially generated and real-Trace networ data illustrate that, under the same budgets, PPRank can achiev larger diffusion range than other heuristic and brute-force greed schemes without taking users' persuasion costs into account.