《On the Shoulders of Giants: Incremental InfluenceMaximization in Evolving Social Networks》——解析

中文翻译——动态社会网络的增量式影响最大化算法

1.什么是影响力最大化

        在2003年Kempe 等人就给出了准确的影响力最大化的定义，同时也证明了影响力最大化问题是一个NP难问题。影响力最大化问题可以定义如下:给定一个G=(V，E)的网络图，其中V表示图中的节点，E表示图中的边，同时给定一个正整数k，影响力最大化问题就是要在给定的传播模型下，找到一组数量为k的种子节点集，使得在网络中的影响力传播规模最大化。用数学语言来描述也就是:找到一个集合满足如下这些条件的集合，S∈V同时丨S'丨=k,使Φ(S') = max(Φ(S))。     

        上面所描述的影响力最大化问题其实就是在给定节点数量k的前提下，去寻找相应数量的节点使得所找到的给定数量的节点集合能影响最多的节点。而对影响力最大化问题的描述除此之外，还有一种，那就是给定所要达到的影响力大小，以此为前提，去寻找能够产生相应影响力的最小的节点集合。

2.文章背景

         社交网站规模的飞速发展导致大规模社会网络的底层拓扑结构不断变化。当社会网络结构变化时，其中用户的影响力和影响范围也会随之改变，从而导致最有影响力用户发生变化。然而，已有影响最大化问题研究大多针对静态社会网络。当社会网络结构改变时，现有算法仅能在变化后的网络图中重新计算来定位新的最有影响力节点。        

         社会网络会不断有新用户加入，另外旧用户可能放弃使用。同时，社交网络中每个用户的好友关系也在通过认识新朋友或者放弃对别人的关注等方式不断发生改变。而且，真实社会网络的变化速度十分惊人；据报道目前世界最大的社交网站Facebook 的用户数量正在以每天 60 万的速度不断增长；同样国外知名微博网站Twitter 平均每秒钟有 11 个新用户注册使用。社会网络拓扑结构如此大量的变化必然会导致网络结构重组，节点影响范围变化。原来的最有影响力用户影响值可能下降，而之前并非最有影响力的用户可能影响力迅速增长，成为有力的竞争者。因此，当社会网络结构发变化时，最有影响力用户也会随之发生变化，所以有必要对最有影响用户进行重新选择，才能保证最大的影响范围。

3.主要工作和创新

（1）社会网络的增长基本上满足优先连接原则（Preferential Attachment，PA），即新增加的边更加趋向于同网络中度数大的节点连接，这会导致著名的“富者更富”现象。

（2）社会网络中最有影响力节点基本上是从度数大的节点中选出。

（3）设计了一种增量式影响最大化算法 IncInf。IncInf 算法的增量式设计不需要在变化后的网络图中重新计算所有节点的影响值，从而大大提高了计算效率和可扩展性，因此可以处理大规模的动态社会网络。

4.什么是动态社交网络

    动态社会网络被定义为随着时间推移的一组社会网络图快照ζ=(G0,G1, · · · ,Gt)，其中 Gt = (Vt, Et, Pt) 是社会网络 ζ 在时间 t 时的网络结构快照。本算法使用∆Gt = (∆Vt, ∆Et, ∆Pt) 来代表网络图 Gt 从时间 t 到 t + 1 发生的拓扑结构变化。很明显，等式 Gt+1 = Gt ∪∆Gt 成立。     

给定： 时间为 t 时的社会网络 Gt，社会网络 Gt 所对应的大小为 K 的最有影响力节点集合 St，社会网络 Gt 所对应的拓扑结构变化 ∆Gt。     

目标： 高效选择出时间 t + 1 时社会网络图 Gt+1 所对应的大小为 K 的最有影响力节点集合 St+1 ⊂ Vt+1，从而使得集合 St+1 的最终影响范围最大。

5.社会网络增长速度分析

        节点和边是社会网络拓扑的基本组成元素和重要组成部分。通过分析社会网络中节点和边的数量随时间的变化情况来挖掘社会网络的增长速度。

6.优先连接规则 

 7.节点影响力同度数关系

8.设计IncInf算法 

9.所提公式

        使用最大影响路径来近似从节点u到v的影响扩散。在这里，将图G中从节点u到v的最大影响路径MIP（u，v，G）定义为具有最大影响路径影响从节点u到v的所有路径之间的概率，可以正式描述如下

        其中prob（p）表示路径p的传播概率，P（u，v，G）表示图G中从节点u到v的所有路径。对于给定路径p = {u1，u2，...，um }，路径p的传播概率定义如下：

 10.addNode伪代码

11.剪枝策略设计 

         （1）在第 i 轮迭代中，如果图 Gt 中的最有影响力节点集合 Sti 的影响值变化量 deltaInf[Sti] 为正（即 Sti 的影响值增加），则选择影响值变化量大于deltaInf[Sti] 的节点作为备选节点。这种剪枝方式可以剪枝大量节点，有效减少计算量。

        （2）在第 i 轮迭代中，如果图 Gt 中的最有影响力节点集合 Sti 的影响值变化量 deltaInf[Sti] 为负，则除了条件1之外，备选节点还需要在度数排名或者影响值增加量方面具备显著优势。上述条件可以形式化描述为满足下面两个条件之一：（1）节点的度数排名在图 Gt+1 所有节点中位于前 5%。（2）节点的度数增长率在图 Gt+1 所有节点中排名前 5%。节点 vj 的度数增长率被定义为degreet+1（j）/degreet（j）

 12.IncInf算法设计

 13.本文数据集

 14.实验结果

 文章引用：[1] X  Liu,  X  Liao,  Li S , et al. On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks[J].  2015.