PPRank Economically selecting initial users for influence maximization in social networks




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). 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.





PR Discount was proposed to alleviate the “overlapping effect” existing in reverse Page Rank-like schemes. Interestingly, greedy-based algorithm and Page Rank-inspired heuristic are integrated by , which conducted the greedy algorithm on a small set of nodes, consisting of the top nodes ranked by Page Rank algorithm on social networks. As emphasized previously, all aforementioned existing works ignore one key aspect of influence propagation that we usually experience in the real social life: The cost used to persuade individuals might vary highly (due to their different susceptibility of being influenced).

Assuming a new behavior has occurred, then we focus on its spreading in social networks. Each user, classified as either an “active” or a “potential” consumer, is represented by a node in the social network structure. An active consumer is a user who has already adopted the behavior and so can influence her neighbors in favor of obtaining it. A potential consumer is an individual who does not adopt the behavior yet but is susceptible of obtaining it if exposed to someone who does.




We argue that fine-tuned heuristics may provide truly scalable solutions to the influence maximization problem with satisfying influence spread and blazingly fast running time.

However, considering that those improved algorithms are essentially greedy based, their running times are still long

By overlapping effect, it means that a given group of connected nodes may have a high degree, but if their adjacent nodes are overlapped, then behavior may not be widely propagated into the rest of the social networks


To complement the existing works on influence maximization, 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. As described previously, due to the huge computational overhead in greedy-based schemes, we seek to propose a new heuristic method that could be cost-effective and achieve influential range as large as possible. There exist many heuristic schemes to solve the problem of seed selection. A degree discount heuristic algorithm called Degree Discount was proposed , in which the IC diffusion model is used.

PP Rank, Reverse Page Rank-like, Weighted degree discount and Greedy-based schemes under two real-world data sets: political blogs and neural network. Obviously, under same budgets, PP Rank achieves better performance than other heuristic schemes and greedy-based algorithm in both real social network data traces. Interestingly, due to the fact that our scheme considers both price (PC)-performance (IP) ratio and IP as an integrated selection criterion, within same budgets, PP Rank selects more seeds than other schemes, and simultaneously, takes into account those seeds’ influence power, which, in turn, leads to the better performance of PP Rank than other schemes .



The first is to improve those greedy algorithms to further reduce their running time

The second is to propose new heuristics that utilize some structural properties of social networks to directly select seeds at one time without running tremendous enumerations to infer each user’s influence power.

The CELF strategy can greatly reduce the number of evaluations on the influence spread of nodes

Simultaneously fulfills both goals: cost-effective and performance-preference





System:Pentium IV 2.4 GHz.

Hard Disk:40 GB.

Floppy Drive:1.44 Mb.

Monitor:15 VGA Colour.

Mouse: Logitech.




Operating system: Windows XP/7.

Coding Language:ASP.net, C#.net

Tool:Visual Studio 2010

Database:SQL SERVER 2008




The literature has greatly studied the mentioned problem from two directions: the enhanced greedy algorithms and various heuristic schemes. However, all existing works ignore one key aspect of influence propagation that we usually experience in real social life: The cost used to persuade individuals to adopt a new behavior might vary highly (due to their different susceptibilities of being influenced). Thus, instead of being given a static number of initial seeds, the main motivation of our paper is to investigate how to economically select initial seeds within a given budget to maximize influence. To solve the aforementioned issue, this paper proposes a new heuristic algorithm, PPRank, based on the integration of price-performance ratio and influence power. First, we explicitly characterize each user with two distinct factors: susceptibility of being influenced (SI) and Influential Power (IP); then, inspired by special properties of price-demand function in economic field, our scheme properly converts SI into PC; and then PPRank utilizes both price-performance ratio (PC − IP ratio) and IP as an integrated selection criterion, and explicitly deals with the overlapping effect.

Leave a comment