influence maximization

Robust Influence Maximization

首先简要介绍一下这个问题:在一个社交网络图中寻找固定数量的节点,使得这些节点对所有节点的影响值尽可能的大。这个问题由于在病毒式营销,谣言监控,舆情分析等活动之中有巨大的应用,所以在过去的几十年,已经被广泛的研究过了。举个例子:一家化妆品公司想要通过送给一些用户免费产品的形式来推广产品,这些用户如何选择就可以采用解决Influence maximization问题的思路来进行。这个问题首先是被Kempe首先提出来的,他提出了两种模型来解决这个问题,第一个是independent cascade model (独立级联模型),第二个是 linear threshold model(线性阈值模型),直到现在为止,解决这个问题的很多方法都是在这两种模型上来进行优化,也有很多人是通过提出新的模型来模拟现实世界之中的信息传过程。

首先对这个问题给出形式化的定义:给一个有向图G = (V,E) ,V代表节点,E代表有向边,每一条边有一个权值  ∈ [0,1],代表源点对终点的影响因子(源点有多大的几率对终点产生影响)。

定义参数向量θ=( ) e∈E 代表每一条边上的影响因子。我们定义 (S)为影响传播函数,( (S)代表从S出发能传播到的所有节点数目的期望值) 其中L代表图G的子图, [L]代表在参数向量θ下子图L出现的概率。(每一条边出现的概率就是传播因子)RL(S)代表在子图L中从S节点能到达所有节点的个数。

Influence maxization问题就是要找到使得  (S)取得最大值得集合S。

已经被证明: (S)具有三个性质:(1)(∀S ⊆ V, (S)≥0);(2)单调递增(∀S⊆T⊆V, (S)≤ (T));(3)(∀S ⊆ T⊆V,∀v∈V (S∪{v})− (S)≥ (T∪{v})− (T))

根据 (S)具有的三个性质Influence maxization问题就存在一个贪心的解法。下面是伪代码:

这个算法的思想就是每一次找到使得 (S)增长幅度最大的节点,加入结果集合中,循环k次,便得到我们想要的集合了。

这个算法 并不是一个好的算法,时间复杂性太高。而时间复杂度高的原因是 (S)函数的计算并不存在多项式时间的算法。精确计算 (S)函数本身就是一件很困难的事情,但是我们有一些别的方法来近似的计算 (S),比如我们可以运行一次信息级联模型,首先将S集合设置为种子节点,然后根据边上的影响因子来确定种子节点旁边的节点是否受到影响,这样算法运行结束之后便可以得到最终有多少节点受到影响,如果对数据的精确度要求比较高的话,我们可以多次运行这个信息级联模型,然后对最后的结果取平均值,这样的话,我们就能够算出一个比较好的结果,我在真正运行程序查看结果的时候,发现每一次运行信息级联模型的结果差距比较小,所以这个方法我个人觉得还是可行的。

所以如果要优化的话,可以从这个算法入手。Influence maxization问题是一个已经被广泛研究过的问题,但是对于一个社交网络图,我们不能得到真正的影响因子,我们能得到的是一个影响因子的置信区间,使得影响因子落在这个区间中的可能性非常大。由于影响因子的不确定性,传统的解法寻找到的k个种子节点已经不够好了。

这篇论文中,首先形式化的定义了一个问题robust influence maxization(RIM)

给一个有向图G = (V,E) ,V代表节点,E代表有向边,每一条边有一个权值区间[le,re],代表源点对终点的影响因子。定义参数空间Θ =  [le,re],我们希望能找到一个大小为k的集合,使得目标函数g(Θ,S)取得最大值。也就是找公式中的集合 (定义如下)

作者在提出这个问题之后,证明这个问题是NP-hard的,并且提供了一个LUGreedy算法给出 一个近似的解法。下面是伪代码:

这个算法的思想就是取每一条边上影响因子为区间上界re运行一次算法1,得到一个集合1,取每一条边上影响因子为区间上界le跑一遍算法,又得到一个集合2,最后看这两个集合在影响因子为le构成的参数向量上得到的影响值,取表现好的那个结果。接着作者证明这个算法的结果存在一个依赖于解的下界:

作者接下来证明了,当图的规模很大的时候, RIM问题不存在令人满意的解,直观上也很容易想出来,当每一条边上的影响因子都不确定的时候,目标函数 的最大值也不会很大。

这个时候作者就另辟蹊径地解决这个问题,我们可以通过采样的方式来减小边上的影响因子的不确定度,作者提出了两种算法,一种是uniform sampling另一种是 adaptive  sampling。

对于第一种算法,我们对于每一条边采样次数都是一样的,并且作者给出了一个采样次数与最终解的好坏之间的一个函数关系。对于第二种算法,是一个启发式的算法,这个算法对于一些重要的边进行了多次的采样,对于其他的边采样次数就明显减少。从结果上来看,第二种算法能明显提升解的正确性。

下面是uniform sampling算法的伪代码:

uniform sampling算法的正确性由下面这个定理来证明:

下面是adaptive  sampling算法的伪代码,这个算法是一个启发式的算法,作者并没有证明此算法的优点。Lemma7给出了此算法中第三行的具体操作。虽然这个算法是 启发式算法,但是这个算法在数据集中的表现是相当不错的。

由于例子并不是 特别好举,所以我就举一个简单的好了。

下面就是运行线性级联模型的例子。

选取第七个和第三个节点为集合s,然后运行线性级联模型,第五个第四个节点被第七个节点影响,第三个节点影响了第一个和第二个节点。所以运行这个算法就能够得到 (S)。

所以第一个算法就是这个算法运行k次,依次寻找使得 (S)增长幅度最大的节点,就得到了结果。

第二个算法就是第一个算法运行两边,每次参数不相同,具体的解释可以参考前面的关于LUgreedy算法的 解释部分。

第三个算法就是运行t次的线性级联模型,最后运行一遍第二个算法。

最后一个算法采用类似的思想,但是在求取置信区间的时候,很巧妙,采用了lemma7来获得区间,保证了算法的运行结果比较好。

最后分析一下这些算法,假设输入的图形有n个节点,m条 边。第一个贪心算法的时间复杂度不是多项式的,但是经过优化之后可以发现,可以优化到k*m(每一次循环计算 (S)是O(m)的,循环k次,所以是k*m)第二个算法是运行两边第一个算法所以也是k*m,最后两个算法和抽样次数有很大的关系,第三个算法是O(min(k*m,t))这个t可能会 很大。至于第四个算法的话,由于循环的次数并不确定,算法一直运行到得到一个满足条件的结果,我们只能分析每一次的时间复杂度O(min(k*m,t*m))。

上一篇:android开发支付宝接口开发流程(密钥篇)


下一篇:Weighted Visibility Graph With Complex Network Features in the Detection of Epilepsy