2.2 近几年研究进展及算法讲解
2.2.1 RIS(Reverse Influence Sampling)
2014年的Maximizing Social Influence in Nearly Optimal Time
2014年的Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
2015年的Influence Maximization in Near-Linear Time: A Martingale Approach
2016年的Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks
以上我列出了四篇采用反向影响力采样方法的论文，该方法大幅度改善了影响力最大化的速度，并使得影响力最大化算法在大型（上百万甚至上亿个节点）社交网络上得以运行。接下来我具体介绍它们的基本思路。
首先是一些定义：
DEFINITION 1 (REVERSE REACHABLE SET). Let v be a node in G, and g be a graph obtained by removing each edge e in G with 1−p(e) probability. The reverse reachable (RR) set for v in g is the set of nodes in g that can reach v. (That is, for each node u in the RR set, there is a directed path from u to v in g.)
反向可达集：节点v是图G中的一个节点，将G中所有边以1-p(e)的概率删去得到图g。在图g中能够到达节点v的节点集合就是节点v的反向可达集。
DEFINITION 2 (RANDOM RR SET). Let G be the distribution of g induced by the randomness in edge removals from G. A random RR set is an RR set generated on an instance of g randomly sampled fromG, for a node selected uniformly at random from g.
随机反向可达集：图g是从图G中随机采样生成的，节点也是随机均匀地选择的。
通过以上定义可知，如果节点u出现在节点v的反向可达集中，那么从u到v一定存在一条路径，也就是u有一定概率能够影响v。那么覆盖更多RR set就意味着能影响更多的节点，基于以上的思想算法如下：
- （采样过程）生成一定数量的RR set；
- （节点选择过程）贪婪地选择节点。每次选出一个覆盖RR集合最多的节点，选中后对整体数据结构进行更新（遍历该节点所覆盖的RR集，对每一个覆盖相同RR集的节点覆盖数减一），然后继续选择下一个节点。
当然该选择生成多少RR set才能满足理论上的近似保证是这几篇文章最关键的地方。生成RR set越少，时间性能就越好。当然实验的评估标准除了时间还有内存消耗以及影响力大小。
这几篇文章有的是直接生成指定数量的RR set，有的是不断生成测试满足条件就不再生成。具体数学细节有兴趣的同学可以去下载这四篇文章去看下。