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 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 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.
PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):
- Chen et al. have proposed several influence maximization algorithms in social networks. In particular, based on an independent cascade (IC) diffusion model, a heuristic algorithm called Degree Discount was proposed to alleviate the effect of overlapping, which intentionally discounts the degree of each node by removing the neighbors that are already in seed set. The aforementioned authors extended the Degree Discount algorithm to make it fit the weighted cascade (WC) diffusion model.
- PRDiscount was proposed to alleviate the “overlapping effect” existing in reverse PageRank-like schemes. Interestingly, greedy-based algorithm and PageRank-inspired heuristic are integrated, which conducted the greedy algorithm on a small set of nodes, consisting of the top nodes ranked by PageRank algorithm on social networks.
DISADVANTAGES OF EXISTING SYSTEM:
- Their running times are still long.
- All aforementioned works ignore one key aspect of influence propagation that we have usually experienced in real life. That is, users have intrinsically different susceptibility of being persuaded to adopt a specific behavior that system designer advertises.
- This paper proposes a new heuristic algorithm, PPRank, for economically selecting seeds to maximize influence. In detail, our main contributions are threefold.
- First, we explicitly characterize each user with two distinct factors: susceptibility of being influenced (SI) and influential power (IP), and formulate users’ SIs and IPs according to their social relationships.
- Second, we argue that each user’s SI is an implicit measurement of persuasion cost (PC): Qualitatively the less a user’s SI is, the more cost would be used to persuade the user. Therefore, inspired by the properties of price-demand function in economic field, our paper properly converts individual’s SI into PC, and then, a novel seed selection algorithm is proposed, which utilizes both the price-performance ratio (PC-IP ratio) and IP as an integrated selection criterion, and explicitly takes into account the overlapping effect.
- Finally, simulations using real social network data traces and artificially generated network graphs illustrate that, under the same budget constraints, our scheme, PPRank, can achieve better performance than other heuristic and greedybased schemes, in terms of maximal diffusion range.
ADVANTAGES OF PROPOSED SYSTEM:
- Our paper deeply investigates how to economically select seeds, within a specific marketing budget, so as to trigger a large cascade of further adoptions based on contagion process.
- In our paper, we utilize WC diffusion model for the problem of influence maximization
- Unlike the aforementioned works, our paper investigates how to select the initial seeds from cost-effective viewpoint and designs a new heuristic scheme.
- System : Pentium Dual Core.
- Hard Disk : 120 GB.
- Monitor : 15’’ LED
- Input Devices : Keyboard, Mouse
- Ram : 1 GB
- Operating system : Windows 7.
- Coding Language : JAVA/J2EE
- Tool : Netbeans 7.2.1
- Database : MYSQL
Yufeng Wang, Athanasios V. Vasilakos, Qun Jin, and Jianhua Ma, “PPRank: Economically Selecting Initial Users for Influence Maximization in Social Networks”, IEEE SYSTEMS JOURNAL, 2017.