考虑用户意愿的符号网络净积极影响力最大化问题

宗金醒, 帅天平

(北京邮电大学 理学院,北京100876)

随着电子设备的快速扩张和社交媒体的增长,人们通过社交网络联系得更加紧密, 社交网络的发展对人与人之间的信息交流和传递有着至关重要的影响,人与人之间的关系可以是合作者、朋友、敌人等.近年来,最大化社交网络影响力的问题引起了研究人员的注意,因为许多主要的社交网络,如Twitter,微信和谷歌,已经变得普遍,这些在线社交网络提供的大规模和多样化的数据促进了社会计算的研究,其中影响力最大化是一个根本性和关键性的问题[1-9],这个问题的目的是选择k个潜在用户,影响并说服他们采用产品,即信息的传播利用的是口碑效应.并在网络中成功地创造更多的采用.潜在的社会网络通常被表示为有向图,并且描述传播过程的扩散模型已经被广泛研究.

由于无符号网络默认的是社交网络用户之间的关系都是信任友好的关系,但在实际情形中,人与人之间的关系还可能会有敌对的关系,因此,越来越多的研究人员开始关注符号网络中影响力最大化的研究.在符号网络中,已经有一些研究[10-13]提出了积极影响力最大化(PIM)的问题,并提出了几种解决方案.PIM问题的目标是在符号网络中选择具有最大积极影响的种子节点集.然而仅仅最大化积极影响有时并不是最好的,因为在现实情境中,负面影响的作用不容小觑,例如我们在淘宝购物时,若看到某个商品的好评很多但同时差评量也很多时,我们可能不会购买这个商品,这对商家来说是不利的.再比如一个商家想要推广自己的某个产品,如果选择的种子用户积极影响力很大,但负面影响力也很大,虽然会有很多用户认可该产品,但也会造成很多用户不喜欢这个产品的情况,这种结果肯定不是商家想要的,因此如何选择种子节点,使得它们具有尽可能多的积极影响和尽可能少的负面影响是一个有实际意义的优化问题.

为了解决上述问题,Li Dong等人[14]针对符号网络首次提出了净积极影响的概念,并提出了净积极影响力最大化问题.净积极影响既考虑了积极影响,也考虑了消极影响,净积极影响最大化是指在最小化消极影响的同时最大化积极影响.但是他们在研究该问题时,并没有将用户自身的传播意愿考虑进来,由于用户在传播信息时,会考虑到自身的某些原因比如性格等,导致他们并不愿意去影响自己的邻居.本文在研究最大化种子节点净积极影响力的同时,将用户的传播意愿考虑在内,以更贴近实际情景.

本文创新点:1)提出了在符号网络中,考虑用户传播意愿的净积极影响力最大化问题,并且证明了在考虑用户传播意愿的极性相关的独立级联模型下,目标函数既不是单调的也不是次模的;2)基于Gong等人[15]提出的概率驱动的结构感知(PDSA)算法,提出了A-PDSA算法来解决该问题;3)给出了在三个符号网络常用的数据集上的实验结果.

1 相关工作

Kempe等[1]将IM问题建模为离散优化问题,并引入了两种传播模型:IC和LT.在这两种情况下,IM问题都是NP-hard的,并提出了贪婪算法.但是,计算影响函数本身就是NP-hard,所以寻找边际增益最大的节点也是NP-hard.由于蒙特卡罗模拟用于计算影响函数,他们的最终算法被称为蒙特卡罗贪婪,然而基于模拟的方法非常复杂,为了缓解这一问题,Lescovec等[16]注意到,节点在当前迭代中的边际收益不会超过其在前几次迭代中的边际收益.通过这种技术,大大减少了对传播估计过程的调用次数,这种方法称为CELF算法.Tang等[3]提出了具有跳数限制的贪婪算法,但该算法的效率仍然很低.由于贪心算法的低效性,Chen等提出了两种启发式算法:DegreeDiscount[4]和PMIA[5].在每一步中,DegreeDiscount将度最大的节点添加到种子集,然后对所选节点的邻接度进行相应的折扣.PMIA通过使用局部影响树来计算影响传播,该树基于两个节点之间最可能的影响路径,但该算法仍然无法扩展到大型社交网络图.

无符号社交网络中影响力最大化问题的研究取得了丰富的成果,这些现有的成果也启发了学者们对符号网络中对该问题的研究.Li等[17]提出了符号网络中与极性相关的影响力最大化(PRIM)问题,包含了积极影响和消极影响,将经典的独立级联(Independent Cascade)模型推广到符号网络,提出了极性相关的独立级联模型(Polarity-related Independent Cascade),并证明了在该模型下PRIM问题的影响函数是单调的和次模的,然后使用贪婪算法来求解该问题,该算法得到的近似解可以逼近最优解的1-1/e.Ju等[18]在计算符号网络中节点间的正激活概率时采用了独立路径的方法,并且提出了用来估计种子节点集积极影响传播的影响函数,该方法避免了采用蒙特卡洛模拟来估计影响传播.Li等[14]首次提出了符号网络中净积极影响的概念,并利用改进的R-Greedy算法来解决该问题,该方法虽然准确度较高但时间复杂度也很高.谢等[19]在影响传播过程中将用户传播意愿考虑进来,在IC-P模型的基础上提出了AIC-P传播模型,并采用基于用户传播意愿的节点搜索策略的差分进化算法(PWDE).

2 模型和问题描述

给定一个符号网络G=(V,E,P,S),其中V为用户的节点集,E为用户之间关系的有向边的集合,每条边e=(u,v)有一个对应的激活概率pu,v,为节点u成功激活节点v的概率.su,v为节点u和节点v之间的极性关系,即su,v=+1表示节点u与节点v之间的关系是正的,su,v=-1表示节点u与节点v之间的关系是负的.如图1是一个代表符号网络的有向图,每条边上的权重即为pu,v·su,v的结果.

图1 符号网络

2.1 影响传播模型

Li等[11]针对符号网络提出了极性相关的独立级联(IC-P)模型,在IC-P模型中,节点的活跃状态有两种:积极(正)状态和消极(负)状态.因此,IC-P模型中每个节点的状态分为3种:积极(正)状态、消极(负)状态或不活跃状态.对于节点u来说,积极状态意味着在社交网络中,相应的用户采用并进而支持或信任传播信息.u的消极状态意味着相应的用户采纳了信息,但随后又反对或不信任该信息.u的不活跃状态意味着相应的用户不采用该信息.

该模型的传播过程如下:在IC-P模型中,扩散过程从初始的一组活跃节点S开始,S中节点的状态有积极状态和消极状态,不在S中的节点都是不活跃的.该过程根据以下随机规则以离散的步骤展开:对于在(t-1)时刻被激活的节点u,它将在t时刻变成积极或消极状态.然后这个节点u在t时刻有且只有一次机会去尝试激活每个当前不活跃的邻居节点.一旦其邻居节点v被节点u成功激活,节点v的其他活跃的邻居将不能再去激活它.对于新激活的节点v,它的状态s(v)与节点u的状态s(u)以及su,v有关,即s(v)=s(u)·su,v.一旦节点变为积极(正)或消极(负)状态,它的状态将不再发生改变.该过程一直进行下去,直到没有新的节点被激活.

由于在实际情境中,用户的传播意愿在信息扩散过程中也扮演了很重要的角色,而IC-P模型并没有考虑用户在影响传播过程中的个人意愿,对此谢等[19]提出了考虑用户传播意愿的AIC-P模型,将用户的传播意愿用w表示,且w∈(0,1).此模型中节点状态的确定与IC-P模型相同,两个模型的差异如下:AIC-P模型中每个节点的状态分为:活跃并表现为积极(正)状态,活跃并表现为消极(负)状态,激活但不活跃状态或未被激活状态.扩散过程从初始种子集合S开始,S包含的是活跃并表现为积极状态的节点,不在S中的节点表示未被激活.其次,在激活过程中,如果节点u在(t-1)时刻被激活,它将在t时刻根据自身的传播意愿值w(u),判断自身是否会处于活跃状态,如果激活的节点u处于活跃状态,那么会在(t+1)时刻变为积极或消极状态.而后在(t+1)时刻才有一次机会去激活当前未被激活的邻居v.其中激活且处于活跃状态的节点u改变其对应状态的过程与IC-P模型一样.

2.2 符号网络中考虑用户传播意愿的净积极影响力最大化

令f±(·)表示积极影响函数,给定一个节点集S,f+(S)即为在AIC-P模型下,被S激活为积极状态的期望节点数,被认为是S的积极影响.同样,f-(·)表示消极影响函数,给定一个节点集S,f-(S)即为被S激活为消极状态的期望节点数,被认为是S的消极影响.我们定义f±(·)为净积极影响函数,对于节点集S,净积极影响函数的计算方法如下:

f±(S)=f+(S)-f-(S)

符号网络中考虑用户意愿的净积极影响力最大化问题的定义如下:给定一个符号的网络G=(V,E,P,S,w),一个信息扩散模型(AIC-P)以及一个非负整数k,目标是寻找一个包含k个种子节点的集合S,使得净积极影响函数f±(S)最大化.这个问题可以形式化为:

S=arg maxS⊆V,|S|=kf±(S)

其中:集合S包含的种子节点都设置为活跃状态并表现为积极状态,有些节点虽然被激活,但未处于活跃状态,视为影响力不会继续传播下去.f±(S)表示的是在AIC-P模型下,由种子节点集S激活并处于活跃状态的净积极节点数量的期望值.

2.3 影响函数的性质

定理:在AIC-P模型下,净积极影响函数f±(S)既不是单调的也不是次模的.

证明:由于在IC-P模型下,净积极影响函数f±(S)既不是单调的也不是次模的[14],而IC-P模型是AIC-P模型当用户传播意愿为1时的特殊情况,因此,在AIC-P模型下,净积极影响函数f±(S)既不是单调的也不是次模的.

2.4 影响函数的计算

由于在AIC-P模型中,激活节点前要先看节点的意愿,如果节点愿意才执行激活. 因此在AIC-P模型中,对于活跃边图g,其发生的概率为Pr[g]=Πpe·wuΠ(1-pe·wu),其中:pe表示边e上的激活概率,wu表示节点u的传播意愿值.

f±(S,g)=f+(S,g)-f-(S,g)=

3 求解算法

Gong等人[15]针对无符号网络中的影响力最大化问题,提出了概率驱动结构感知(PDSA)算法.该算法的主要思想是,生成一定数量的活跃边图,找出每个节点在这些活跃边图中可以激活的节点数量的总和,再求出平均值即作为每个节点的扩散得分,最后根据每个结点的扩散得分来对节点进行排序.由于该算法可以基于网络结构的变化自适应地寻找有影响力的节点,在效率和准确性方面取得了良好的性能.因此,本文将该算法的思想推广到符号网络中,用来求解符号网络中考虑用户传播意愿的净积极影响力最大化问题.

定义3(可达集):设g为图G的一个活跃边图,图g中的节点v沿着图中的路径可以到达的所有节点的集合称为v的可达集.在v的可达集中表现为积极状态的节点的集合称为v的积极可达集,表现为消极状态的节点的集合称为v的消极可达集.

定义4(净扩散得分):给定一个图G=(V,E),则节点v∈V的净扩散得分定义为:NSS(v)=f±(v).其中f±(v)表示在图G中被节点v激活且处于活跃状态的净积极节点的预期数量.

对节点v,它的净扩散得分的精确计算方法如下:

其中:X为图G的所有活跃边图的集合,NNSg(v)为节点v在图g中的净积极扩散得分.然而由于活跃边图的数量很多,所以给定一个节点v后,利用上述方法很难精确计算NNS(v),因此可利用蒙特卡洛模拟的方法来估计NNS(v).

由于添加了用户的意愿值,因此,可将提出的算法命名为A-PDSA算法.我们将节点的积极可达集记为PR,消极可达集记为NR,算法具体描述如下:

A-PDSA算法输入:符号网络G=(V,E,P,S,w),种子集大小k,蒙特卡洛模拟次数Mc输出:种子集S1.生成节点的传播意愿值,并计算每条边添加意愿后的激活概率,得到Ep2.对图G中的每个节点v,NSS[v]=03.for i=1,...,Mc, do4. g=copy(G)5. while e∈E do6. if c>Ep(e) do7. 将边e从图g中删除8. end if9. end while10. while v∈V do11. 在g中计算节点v的净积极可达集NPRS[v]=PR[v]-NR[v]12. NSS[v]=NSS[v]+NPRS[v]13. for v∈V do14. NSS[v]=NSS[v]/Mc15. 将节点按净扩散得分降序排列得到Rank16. 返回Rank[:k]

在该算法中,首先生成节点的传播意愿值,Ep为边的参数空间,即若边e=(u,v),则Ep(e)=wu·pu,v.第4～9行是生成图G的活跃边图g的过程,其中c为在[0,1]之间随机生成的一个均匀分布的随机数.第10～14行计算每个节点的净扩散得分,在g中通过广度优先搜索算法(BFS)来获得每个节点的积极可达集PR和消极可达集NR,从而得到该节点的净积极可达集NPRS.然后将每个节点在生成的所有活跃边图中得到的NPRS作和并求出平均值作为每个节点的净扩散得分(NSS),最后按照该得分进行排序得到排名列表Rank,从而得到种子集S.

4 实验与结果分析

4.1 用户传播意愿的生成

对于符号网络中用户的传播意愿,谢等人[19]通过对微博数据集进行分析,模拟生成了一组用户的传播意愿值,并对于每个节点分析了其分享程度和度值的关系,并采用了生成用户意愿的方法:将节点度值升序排列,若数据集节点总数用M表示,则前r*M个节点的传播意愿要和自身度值成线性关系,剩下的(1-r)*M个节点的传播意愿要满足幂律分布和部分节点度值很大但传播意愿较小的情况.本文采用同样的方法来模拟生成一组用户的传播意愿值.为了确定r值,本文采用A-PDSA算法在三个真实数据集Bitcoinotc、Bitcoinalpha和Slashdot上进行了实验,实验结果如图2所示.

图2 对不同r值求得的净积极影响力随种子节点的变化情况

通过对比发现,r=0.9时,A-PDSA算法的效果最好.所以在模拟生成用户传播意愿值时,均采用r=0.9.

4.2 实验数据集

本文测试了三个不同大小的真实网络的数据集:Bitcoinotc、Bitcoinalpha和Slashdot,并与其他三个启发式算法在性能和时间上进行了比较.Bitcoinotc是在称为比特币OTC的平台上使用比特币进行交易的人的谁信任谁网络;Bitcoinalpha是在一个名为比特币Alpha的平台上使用比特币进行交易的人的谁信任谁网络.Slashdot是一个受欢迎的技术新闻网站.Slashdot中的用户可以将其他用户标记为朋友(正面)或敌人(负面).由于该数据集太大,因此我们从Slashdot中选择度最高的10 900个节点以及所选节点之间的边.表1统计了三个数据集的信息,实验所用数据集可以从斯坦福大型网络数据集网站(http://snap.stanford.edu/data)中下载.

表1 数据集

4.3 参数设置

对于这三个网络,边上的激活概率p=0.1,在模拟信息传播阶段,蒙特卡洛模拟的次数设置为1 000.考虑到贪心算法时间复杂度较高,因此本文不考虑贪心算法作为对比算法,将所提出的算法(A-PDSA)与K-shell算法[20],MaxShare算法[19]和Iv-greedy算法[21]进行对比.

K-shell算法递归地剥离网络中度小于或等于k的节点,直到网络中所有的节点都被赋予ks值,选择前k个ks值最高的节点做为种子节点.

MaxShare算法是选择前k个分享意愿最大的节点作为种子节点.

Iv-greedy算法为图中的每个节点建立一个影响向量,节点的影响向量体现了该节点对其邻居的影响程度,本文中要同时考虑该节点的传播意愿和对邻居节点的影响概率.

4.4 实验结果与分析

图3为数值实验的结果,图(A)～(C)是分别在三个不同数据集上当k分别取10、20、30、40、50时,四个算法求得的净积极影响力范围.其中:横轴表示种子集的大小,纵轴表示种子节点的净积极影响力.

图3 不同数据集上求得的净积极影响力随种子

从图3中可以看出,在这三个数据集上,本算法找到的种子集产生的净积极影响均明显大于其他三个算法的结果.

表2为在三个不同数据集上,当种子集中节点个数取50时四个算法的运行时间.结合表2和图3,可以看出虽然在数据集Bitcoinalpha和Bitcoinotc中三个对比算法比本文算法要快一些,但是产生的净积极影响却比本文算法小很多,在数据集Slashdot(subgraph)中,本文算法不仅比Iv-greedy快,求得的结果也是最好的.

表2 k=50时的运行时间(s)

5 结 语

符号网络中的净积极影响力最大化问题是一个具有实际意义的问题,但由于用户在传播信息时会考虑自身的原因,因此,本文引入了用户的传播意愿来使得这个问题更符合实际场景.其次,证明了在AIC-P模型中,目标函数既不是单调的也不是次模的,另外提出了改进的PDSA算法,即A-PDSA算法来解决考虑用户意愿的净积极影响力最大化问题.并且在三个真实数据集上进行大量的实验表明,利用本文算法得到的种子集,具有更大的净积极影响力.对于本文提出的算法,在寻找种子节点时仍会花费大量时间,因此未来应该考虑其他更优的算法;在模拟生成节点的传播意愿值时,是通过微博数据集进行分析的,有一定的缺陷,将来还要研究更合适的方法来生成用户的传播意愿值.