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.

提出一种基于迭代排序的算法 IMRank，通过同时利用贪心算法和启发式算法，以节点排序的感染影响力边际作为参考，高效地解决了社交网络中的最大影响力问题。经过对大规模真实社交网络的广泛实验，IMRank 总是以极高的准确性实现的同时，计算成本大大降低。