Influence Maximization

开山之作

Maximizing the spread of influence through a social network

这篇文章是IM领域的开山之作，其基于子模函数的框架考虑IM问题，证明了Influence function在IC和LT以及满足特定条件下的扩散模型中是子模的，从而通过子模函数算法的近似度得到IM问题贪心算法的近似度。也就是说，把IM问题转化为子模函数的优化问题。在证明影响函数是子模的时候，用到了一种方法，就是先将边的分布确定下来（hard-wired），考虑在确定性边的情况下，影响函数的子模性，然后总的Influence function就等于hard-wired边的情况下得到的influence乘和边的分布的线性求和。因为子模函数的线性结合仍为子模，得到Influence function是子模的结论。这样，通过解决目标函数为子模函数的优化问题也就解决了IM问题，进而得到了IM问题的近似度。前半部分的讨论是基于LT模型和IC模型，后半部分讨论general的LT和IC模型，并且证明了二者之间的等价性。但是在这样的情况下得到的影响函数就不再是子模了。怎么办呢，作者又引入了一个新的影响模型，就是trigger模型，由这个模型出发，猜想什么扩散模型下影响函数才是子模的。然后又考虑了non-progressive以及多种市场行为的情形。实验部分，是看在三种概率模型下，随着seed nodes数量的增加，active nodes数量的变化。

IM中的scalability问题

Sketch-based influence maximization and computation

这篇解决的是IM和influence computation的scalability问题。解决IM问题主要用到的就是贪心算法嘛，但是目前的贪心算法扩展性都很差，其他的目前一些算法如果扩展性好了，一般就没有质量的保证，或者不能算到底（得到所有节点影响力的序列），因此我们就是要在保证算法质量的情况下，进行scalability问题。同时，能够进行影响力的oracle，能够做到查询时间快，所需的存储空间小，以及估计的相对误差小。 Combined reachability sketches的主要思想就是从一个节点的小的结构来预测它在全局的影响力，这个小的结构就生成这个节点的一个sketch，combined的意思就是考虑多个instances。Sketch构造的方法就是为每个节点对应一个rank值，这个值服从[0,1]上的均匀分布，对于某个节点，把它的rank以及它所能到达的节点的rank进行排序，选择k个最小的rank，就构成了这个节点的sketch。然后reachable sets的大小就可以由sketch里最大的那个值估计。感觉整体的思想就是用子结构来估计整体结构。具体k和l的选择是通过实验来保证的。根据sketch框架来解决IM问题，设计了SKIM算法，主要思想就是先把所有节点的rank按照递增的顺序进行排序，然后通过前面的节点来填后面节点的草图，后面节点的草图大小最先达到k的加入seed nodes。再去除这个节点的影响，进行Residual problem。具体的k以及Instance数量l的选择由实验进行保证。然后就是影响力计算，可以继续用sketch估计的方法，也可以采取另一种方法，利用sketch里所有的节点，而不是那个最小的节点来进行影响力计算。实验部分，比较固定数据集的条件下，不同的算法随着seed nodes数量的增加，误差以及运行时间的变化；固定数据集，两种算法在不同（uc和wc）概率模型下，随着seed nodes数量的增加，影响以及运行时间的变化；使用SKIM算法，在不同数据集上，随着seed nodes数量的增加，影响以及运行时间的变化。以及在不同数据集上，随着种子节点数量的增加，预测误差的变化。