  Influence maximization, fundamental for word-of-mouth marketing and viral
marketing, aims to find a set of seed nodes maximizing influence spread on
social network. Early methods mainly fall into two paradigms with certain
benefits and drawbacks: (1)Greedy algorithms, selecting seed nodes one by one,
give a guaranteed accuracy relying on the accurate approximation of influence
spread with high computational cost; (2)Heuristic algorithms, estimating
influence spread using efficient heuristics, have low computational cost but
unstable accuracy.
  We first point out that greedy algorithms are essentially finding a
self-consistent ranking, where nodes' ranks are consistent with their
ranking-based marginal influence spread. This insight motivates us to develop
an iterative ranking framework, i.e., IMRank, to efficiently solve influence
maximization problem under independent cascade model. Starting from an initial
ranking, e.g., one obtained from efficient heuristic algorithm, IMRank finds a
self-consistent ranking by reordering nodes iteratively in terms of their
ranking-based marginal influence spread computed according to current ranking.
We also prove that IMRank definitely converges to a self-consistent ranking
starting from any initial ranking. Furthermore, within this framework, a
last-to-first allocating strategy and a generalization of this strategy are
proposed to improve the efficiency of estimating ranking-based marginal
influence spread for a given ranking. In this way, IMRank achieves both
remarkable efficiency and high accuracy by leveraging simultaneously the
benefits of greedy algorithms and heuristic algorithms. As demonstrated by
extensive experiments on large scale real-world social networks, IMRank always
achieves high accuracy comparable to greedy algorithms, with computational cost
reduced dramatically, even about $10-100$ times faster than other scalable
heuristics.
