一种带时间约束的影响力最大化方法
时间：2022-12-03 10:55:03 来源：雅意学习网 本文已影响 人 
毋 东，何楠群，张霄宏
(河南理工大学 计算机科学与技术学院，河南 焦作 454000)
E-mail：xh.zhang@hpu.edu.cn
在线社交网络平台为数以亿计的用户提供了跨越时间和空间的信息交流服务，越来越多的人将社交平台视为主要的信息来源.社交平台中大V们的言论往往比普通人的言论传播得更广，产生的影响更大.而用户影响力最大化正是通过寻找最具影响力的若干个用户作为种子，以期信息从这些种子开始传播时其传播范围最大.如何在给定时间期限前使信息得到最大化传播则是一个更具有现实意义的问题，电商平台广泛推出的双11、双12促销活动就是此类问题的典型代表.
影响力最大化可应用于政治选举[1]、在线营销[2]、谣言控制[3]等多个领域.Kempe等[4]证明了影响力最大化问题是NP-hard问题.简单贪婪算法及其优化算法、启发式算法等被广泛用于筛选优质种子.随着研究工作的不断推进，影响力传播过程中的时间因素逐渐引起重视[5-7].Li等[8]基于社交网络中的时间限制和时间延迟扩散提出了竞争影响力最大化算法.Tong等[9]将时间约束分散到种子选择的每一步，通过使种子选择的每步操作都服从预算约束来达到在既定时间约束下影响力最大化的目标.Litou等[10]的工作旨在满足时间约束的前提下，寻找最佳传播路径以达到影响力最大化的目标.尽管围绕信息传播的时间属性已经开展了大量的研究，但是如何在给定时间期限内使信息得到最大化传播仍然是一个开放问题.
针对这一问题，本文提出了基于时间约束的影响力最大化算法.该方法首先根据网络拓扑结构和节点间的交互信息构建带时间约束的影响力计算模型，然后定义最早激活时间、累积传播延时等概念，以此控制影响力的传播过程以满足给定的时间约束条件；
最后，引入有效激活节点的概念并利用其描述影响力在给定时间约束下的传播范围，并据此选出种子节点.
Kempe[4]等证明了影响力最大化问题是NP-hard问题，并提出了线性阈值模型和独立级联模型模拟影响力的传播过程.Kempe等提出的简单贪婪算法可以筛选出接近最优的种子，但是时间复杂度过高.为了降低时间复杂度，开展了大量对简单贪婪算法进行了优化的工作，并提出了CELF算法[11，12]、混合贪婪算法[13，14]、约束贪婪算法[15]等.除了贪婪算法，启发式算法[16]也被用来筛选种子节点.
筛选种子节点时需要计算节点的影响力.现有的方法在计算影响力时除了考虑节点的拓扑属性[17，18]，还会考虑社交属性.曹等[19]根据用户交互的主题偏好计算不同类别信息下节点的影响力，Mhadhbi等[20]以节点周围存在的密集社区为派系，根据派系识别影响力最大的节点.
随着相关研究工作的不断深入，影响力传播中的时间因素逐渐引起重视[21，22].Pham等[23]认为错误信息传播时间越长受影响的用户越多，并根据时间约束和预算限制提出了最大化错误信息限制算法.Ali等[24]认为信息的时间紧迫性会加剧群体影响力的差异，提出了在规定期限内、在保证种群传播公平的前提下实现影响力最大化传播的方法.Li等[8]基于社交网络中的时间限制和时间延迟扩散提出了竞争影响力最大化算法.Tong等[9]将时间约束分散到种子选择的每一步，通过使种子选择的每步操作都服从预算约束来达到在既定时间约束下影响力最大化的目标.Litou等[10]的工作旨在满足时间约束的前提下，在位置感知的社交网络中寻找最佳传播路径，以达到影响力最大化的目标.
尽管围绕信息的时间属性已经开展了大量的研究，但是如何在特定时间约束下使信息得到最大化传播仍是一个开放问题.
本文用有向图表示社交网络.图中的节点表示社交网络中的用户，边表示用户之间的交互活动.记G=(V，E)表示有向图，V表示节点集合且V={v1，v2，v3，…，vn}，E表示边集合且E={(vi，vj)|vi∈V，vj∈V}.影响力最大化问题旨在选择一个节点集合S且S⊂V，以S中的节点为种子开始信息传播时其传播范围最大.影响力最大化问题可由式(1)描述，式中k表示种子节点的数量，δ表示种子节点影响力的传播范围.
S*=arg|S|≤kmax(δ)
(1)
S*=arg|S|≤k，te-tb≤Δtmax(δ)
(2)
本方法根据节点的影响力和节点在特定时间约束下传播信息的能力两个因素选择种子节点.本方法包含三部分内容，首先设计包含时间约束的影响力计算模型，然后在影响力传播过程中引入了最早激活时间和累计传播时延以控制影响力的传播过程符合时间约束条件，最后根据每个节点在给定时间约束下的影响力传播范围选出种子节点.
4.1 影响力计算
节点的影响力与该节点是否能够选为种子密切相关.本文主要从网络的拓扑结构和用户之间的社交活动两方面入手来计算节点的影响力.为便于计算节点影响力，定义了节点的重要性和亲密度两个概念.
定义1.(重要性)从拓扑结构的角度刻画节点在整个社交网络中的重要程度.
记Imp表示重要性，Imp(vi)表示节点vi的重要性，可根据文献[25]中的方法计算.
定义2.(亲密度)从社交活动的角度刻画节点之间联系的紧密程度.
记Inm表示亲密度，节点vi和节点vj之间的亲密度则由Inm(vi，vj)表示，根据式(3)计算.
Inm(vi，vj)=α·con(vi，vj)
(3)
给定有向图G′，α是由G′中的集合T决定的一个量，α=1/|T|，con(vi，vj)的值由vi和vj之间社交活动决定，con(vi，vj)=|Ti，j|，Ti，j⊂T且Ti，j={ti，j|∃(vi，vj)∈E且ti，j∈T}.vi和vj之间的社交活动越频繁，Inm(vi，vj)的值就越大.
(4)
式(4)从网络拓扑结构和总体社交活动的角度描述vi的影响力.现实世界中用户在不同时期参与社交活动的程度往往有差异.用户在某些时期参与社交活动的积极性会比较高，而在另外某个时期参与社交活动的积极性可能会明显降低.这种积极性的变化会影响其影响力的传播.正如参与竞选活动的候选人在退出竞选前后其影响力的传播截然不同.
为了体现用户影响力在不同时期的差异，在式(4)所定义的影响力模型的基础上引入了基于时间约束的变化因子，该因子由用户在给定的时间约束内的社交活跃度决定.引入该因子后，vi的影响力记为InfΔ(vi)，由式(5)计算.
InfΔ(vi)=Inf(vi)*(1+δ(tb，te，vi))
(5)
(6)
下面以图1所示网络中的节点v2为例说明影响力的计算过程.在图1中，边上的数字标识节点间发生社交活动的时刻.假设tb=3，Δt=4，则有Imp(v2)=1.44，α=1/9，con(v2，v3)=1，con(v2，v4)=2，con(v2，v5)=3，根据式(5)可计算InfΔ(v2)=1.44，根据式(6)可计算得InfΔ(v2，v3)=0.24，InfΔ(v2，v4)=0.48，InfΔ(v2，v5)=0.72.
图1 包含5个节点社交网络图Fig.1 Social network graph with five nodes
4.2 种子选择
本方法在选择种子节点时主要考虑两个因素：一是节点的影响力传播范围是否属于top k之列，二是影响力传播开始与结束的时间是否满足时间约束条件，即te-tb≤Δt.如果某个节点的影响力传播范围属于top k之列，但所需的传播时间超过了Δt，则该节点不能选作种子节点.如果传播过程满足时间约束条件，但是该节点影响力的传播范围不在top k之列，则该节点也不能选作种子节点.
为了识别能在给定时间约束下使影响力得到最大化传播的节点，定义了节点的最早激活时间、影响力传播累积时延以及有效激活节点等概念.
定义3.(最早激活时间)用于标记某节点被激活的最早时间.
(7)
定义4.(传播累积延时)描述某节点的影响力传播到另一节点的累积延时.
(8)
如果在某个时刻t′，节点的影响力传播累积延时突破了时间约束条件，即t′-tb≤Δt，则自此时刻起激活的节点不再计入影响力的传播范围.换而言之，节点的影响力传播范围根据该节点在影响力传播累积延时满足时间约束条件时激活的节点进行计算.为便于识别此类激活的节点，引入了有效激活节点的概念.
定义5.(有效激活节点)若某节点的最早激活时间满足时间约束条件的限制，则此节点是有效的激活节点.
以vi为例，若满足Tal(vi)≤tb+Δt，则vi是有效激活节点.
由定义3至定义5可知，在影响力传播过程中，如果遍历到某个节点时影响力的传播累积延时不再满足时间约束条件，则在该节点处停止传播，即不尝试激活该节点以及该节点指向的所有节点.最终，节点的影响力传播范围由有效激活节点的数量决定.影响力传播范围最大的k个节点将被选作种子节点.
4.3 算法描述
带时间约束的影响力最大化目标是找到有效激活节点最多的k个节点作为种子节点，当从这k个种子节点开始传播信息时，能在Δt时间内将信息在最大范围内传播.
算法1.基于时间约束的种子选择算法
输入：社交网络图G′=(V，E，T)；
输出：种子集seeds；
1. for eachvinV
2. 将节点v加入anodes
3. while(anodes≠Φ)do
4.curnode←取anodes中的一个节点
5. 计算curnode的所有出边邻居节点，存入变量negs
6. for eachneginnegsdo
7. if(InfΔ(curnode，neg)≥激活阈值)
8. 计算Tal(curnode，neg)
9. if(Tal(curnode，neg)满足时间约束条件)
10.v的有效激活节点数加一
11. 计算Ipt(v，neg)
12. If(Ipt(v，neg)≤Δt)
13. 将neg加入anodes
14. end if
15. end if
16. end if
17. end for
18. 从anodes中删除curnode
19. end while
20. end for
21. 按有效激活节点有大到小的顺序对所有节点排序
22.将前k个节点加入seeds，并返回seeds
本实验采用线性阈值模型模拟影响力的传播过程.为了体现时间约束，对该模型进行了修改.通过比较本文算法和多种不同算法在修改后的线性阈值模型上的执行结果来来评价本文方法的正确性和有效性.
5.1 实验设置
5.1.1 实验环境
本次实验在单台主机上运行，该主机采用2.4GHz双核处理器，12GB主存和Windows10操作系统.
5.1.2 数据集
所有实验选用了斯坦福大型网络数据集(1)https：//snap.stanford.edu/data/中带有时间属性的六个数据集，这些数据集的信息介绍如下：
· email-Eu-core-temporal数据集是根据欧洲大型研究机构在803天内的电子邮件数据生成的社交网络，该网络包含986个节点和332334条边，节点表示机构成员，边表示机构成员之间的通信.
· email-Eu-core-temporal-Dept1数据集是根据欧洲大型研究机构部门1的成员在803天内的电子邮件数据生成的社交网络，该网络包含309个节点和61046条边，节点表示机构成员，边表示机构成员之间的通信.
· CollegeMsg数据集来自加州大学欧文分校的在线社交网络应用.该数据集包含1899个节点和59835条边，节点表示用户，边表示用户之间的消息通信.该数据集的时间跨度为193天.
· sx-mathoverflow-a2q数据集是根据Math Overflow网站的问答信息生成的社交网络.该网络包含21688节点和107581条边.节点表示用户，边表示一个用户在时间t回答了另一个用户的提问.该数据集的时间跨度为2350天.
· sx-superuser-c2a数据集根据Super User网站上的问答信息生成的社交网络.该网络包含101052节点和430033条边.节点表示用户，边表示一个用户在时间t评论了另一个用户的答案.该数据集的时间跨度为2735天.
· sx-superuser-a2q数据集也来自Super User网站.该网络包含167981节点和534239条边.节点表示用户，边表示一个用户在时间t评论了另一个用户的提问.该数据集的时间跨度为2773天.
5.1.3 评价指标
本实验采用执行时间和影响力传播范围作为评价指标.执行时间指的是各算法选择种子节点所消耗的时间.影响力传播范围由各算法所选种子节点在线性阈值模型下能够激活的节点数表示.
在线性阈值模型中，一个节点能否被激活主要取决于该节点的激活阈值以及邻居节点对该节点的传播概率(影响力).在本次实验中，所有节点的激活阈值都取固定值0.2.节点间的传播概率根据式(9)描述的模型计算.在该式中，fp(vi，vj)根据式(10)计算，其中Imp()的值由PageRank算法获得.在计算Imp()时，每个节点的PageRank初始值为1/|V|，V为节点集合，抑制因子d=0.85.
(9)
(10)
5.1.4 对比算法
本实验采用了6个对比算法，分别是Degree算法、Random算法、IMIT算法[22]、SingleSingle算法[22]、TCIM算法[24]和PageRank算法[26].通过与这些算法对比执行时间和影响力传播范围两项指标验证本文方法的正确性和有效性.
5.2 实验结果及分析
本次实验展示的所有结果均为相关算法独立运行50次的平均结果.
图2和图3展示了在Δt取不同值时各算法所选种子的影响力传播范围.图2展示了5个种子的影响力传播范围，图3展示了10个种子的影响力传播范围.在这两幅图中，纵坐标表示种子节点激活的节点数，横坐标表示不同的Δt取值.当累积传播延时达到Δt所对应的值时，停止传播.
图2 种子数为5时的传播结果对比Fig.2 Comparison of spread results with 5 seeds
图3 种子数为10时传播结果对比Fig.3 Comparison of spread results with 10 seeds
当种子数为5时，在sx-mathoverflow-a2q数据集上，只有在Δt=100%*t总时本文算法所选种子的影响力传播范围比Degree算法所选种子的影响力传播范围稍小.在Δt取其它值时，本文算法都比Degree算法要好.在除了sx-mathoverflow-a2q数据集之外的其它5个数据集上，本文算法所选种子的影响力传播范围都是最大.
当种子数为10时，本文算法在sx-superuser-c2a数据集上，只有在Δt=40%*t总时本文算法所选种子的影响力传播范围比TCIM算法和IMIT所选种子的影响力传播范围稍小，在此数据集上Δt取其它值以及在另外5个数据集上，本文算法的结果均优于6个对比算法.
根据图2和图3的结果计算了在种子数分别是5和10两种情况下各算法的归一化平均传播范围，结果如表1和表2所示.在种子数分别是5和10的情况下，本文方法的归一化传播范围要优于6个对比算法.
表1 种子数为5时的归一化平均传播范围比较Table 1 Comparison of normalized average spread range with five seeds
表2 种子数为10的归一化平均传播范围比较Table 2 Comparison of normalized average spread range with 10 seeds
图4展示了各算法在不同数据集上执行时间的比较结果.由图可知，本文算法在6个数据集上的执行时间要小于PageRank算法和SingleSingle算法，与IMIT算法不相上下.虽然Random算法的执行时间比其它算法短，但是它的影响力传播范围没有其它算法的大.由于TCIM算法的执行时间过大，为了突出本文算法和其它5个算法的对比结果，未将TCIM的结果在图4中展示.
图4 各算法在不同数据集上执行时间对比Fig.4 Execution time comparison of various algorithms on different data sets
本文提出了一种基于时间限制的影响力最大化方法.该方法根据社交活动的时间属性、节点拓扑属性以及时间约束条件等因素计算节点的影响力，并引入最早激活时间和有效激活节点以识别满足给定时间约束的激活节点，引入累积传播延时以控制影响力的传播过程符合约束条件.在真实数据集上的实验结果验证了本文方法的正确性和有效性.下一步，将在本文方法的基础上进行传播模型的改进.
猜你喜欢 最大化约束影响力 论慈善组织的影响力投资及其立法完善社会科学战线(2022年9期)2022-10-25太极拳，风縻世界的影响力金桥(2021年3期)2021-05-21勉县：力求党建“引领力”的最大化当代陕西(2021年1期)2021-02-01Advantages and Disadvantages of Studying Abroad考试与评价·高二版(2020年3期)2020-09-10刘佳炎：回国创业让人生价值最大化华人时刊(2019年15期)2019-11-26My Hobby阅读（快乐英语高年级）(2019年8期)2019-09-10马和骑师小学阅读指南·低年级版(2017年1期)2017-03-133.15消协三十年十大影响力事件瞭望东方周刊(2015年12期)2015-04-14CAE软件操作小百科（11）计算机辅助工程(2012年5期)2012-11-21超级最大化软件有“面子”网友世界(2009年12期)2009-03-05
