Abstract
The influence maximization problem in social networks seeks out a set of nodes that allows spreading information to the greatest number of members. A greedy algorithm, proposed by Kempe et al. [12], finds a solution in which the spread of influence is at least 1 - 1/e of the optimum. However, some shortcomings of this approach negatively affect the run time of this algorithm. In this work, we propose a methodology to speedup the Kempe’s algorithm with focus on power law graphs. The improvement consists of choosing the most promising nodes in advance. To this end, we explore some properties of power law graphs and the relationship between social influence and degree distribution. We have verified by experimental analysis that this preselection reduces the run time while preserving the quality of the solution.
