社交媒体的不断发展使得信息在社交网络上广泛传播．传播的信息主要包括正面信息和负面信息两种．正面信息如官方发布的新闻、科学知识等，它们的有效传播能够促进社会的和谐发展；负面信息有伪造的谣言、诽谤等，这些负面信息的传播会对社会产生危害．因此研究在社交网络中如何有效地阻塞负面信息的传播有着重要意义．影响阻塞最大化(influence blocking maximization，IBM)问题是影响最大化[1]问题的拓展与延伸．最早由Budak等[2]定义为如何选择k个节点进行正面信息传播来有效地阻塞社交网络中负面信息的传播，并基于次模性质提出了一个基本的贪心近似算法．该近似算法复杂度较高，为了降低其时间复杂度，近年来研究者们又提出了若干改进算法[3]，如基于中心性的Proximity算法[4]和Degree算法[5]、基于采样的IBMM算法[6]、基于影响路径的CMIA-O算法[7]和BIOG算法[8]等．目前的影响阻塞最大化算法往往只考虑了节点的扩散能力和网络的拓扑结构，没有深入挖掘节点本身的综合属性．本研究在COICM模型[2]下提出了基于节点混合阻塞力的影响阻塞最大化算法(IBM algorithm based on node mixed blocking ability，IBM-MBA)．该算法综合考虑了节点对负面信息的阻塞能力和对正面信息的扩散能力，更全面地刻画了每个节点在信息传播中的作用．在典型社交网络实例上的实验表明，与现有的算法相比，该算法所选出的阻塞节点对负面信息有着更好的阻塞效果．1 背景知识1.1　问题描述将社交网络建模成一个图〈G=V,E〉，给定一个传播负面信息的节点集R⊂V和正整数k．IBM问题就是从节点集V-R中找出k个节点组成的集合S来传播正面信息，使得负面信息的传播范围最小．设IS(R)表示传播正面信息的点集S存在的情况下负面信息的影响范围，IBM问题的目标是找到点集S⊂V-R使得负面信息的影响范围IS(R)最小．IBM的形式化表示为S=argminS⊆V-R{IS(R)||S|=k}. (1)1.2　节点影响概率在社交网络中，节点的影响概率决定了信息的传播范围．Wu等[7]在CMIA-O算法中提出了一种局部范围内计算节点影响概率的方法．通过动态规划的思想计算每个时刻节点的影响概率，从而累加得到总的影响概率．为方便描述，用R表示传播负面信息的节点集，用S表示传播正面信息的阻塞点集，用N-(v)表示节点v出邻居节点的集合．设ps(v,t)为t时刻节点v被正面信息所影响的概率(简称为正影响概率)，pr(v,t)为t时刻节点v被负面信息所影响的概率(简称为负影响概率)，s(v,t)为t时刻后节点v的正影响概率，r(v,t)为t时刻后节点v的负影响概率，qw,v为节点w到节点v的传播概率．根据COICM模型的传播特点，CMIA-O算法中提出了以下公式：    ps(v,t)=1-∏w∈N-(v)1-ps(w,t-1qw,v)∙(1-r(v,t-1))(1-s(v,t-1)); (2)    pr(v,t)=1-∏w∈N-(v)1-pr(w,t-1qw,v)∙∏w∈N-(v)1-ps(w,t-1qw,v)(1-r(v,t-1)∙(1-s(v,t-1)); (3)s(v,t)=∑0≤t'≤tps(v,t'); (4)r(v,t)=∑0≤t'≤tpr(v,t'). (5)正影响概率的计算方法如式(2)所示，它表明一个节点v在t时刻被正面信息影响当且仅当至少一个入邻居节点在t-1时刻成为阻塞节点并成功传播正面信息给节点v，同时节点v在t时刻前一直保持在未被影响状态．同理，负影响概率的计算方法如式(3)所示．式(4)和(5)表示t时刻后节点的影响概率等于0~t时刻的影响概率之和．2 IBM-MBA算法为了求解影响阻塞最大化问题，从两个方面考虑传播正面信息的节点所带来的阻塞增益：一方面这些节点可以阻塞掉传播到该节点的负面信息和通过该节点传播到其他节点的负面信息，本研究用节点对负面信息的阻塞能力来刻画这一部分的阻塞增益；另一方面当这些节点传播正面信息给邻居节点后，这些邻居节点也会对负面信息形成阻塞，同理，用节点对正面信息的扩散能力来刻画这一部分的阻塞增益．节点对负面信息的阻塞能力和对正面信息的扩散能力构成了节点的混合阻塞力，用来衡量节点对负面信息的阻塞增益．本文算法是一个基于节点混合阻塞力的贪心算法．首先估算出每个节点的影响概率，由此得到节点的扩散能力和阻塞能力，从而可计算出节点的混合阻塞力；然后进行k轮贪心选择，每轮中优先选出混合阻塞力最大的节点作为传播正面信息的阻塞节点，最终形成阻塞点集S．2.1　估算节点影响概率的扩展方法局部范围内节点影响概率的计算方法只考虑了最大影响路径对节点的影响，且须要构建大量的局部影响树来估算节点影响概率．对该方法进行扩展，综合考虑所有的入邻居节点的传播概率，借助于已有的节点影响概率的计算公式(2)~(5)，从全局的角度提出一种基于时间动态计算节点影响概率的方法．同时引入时间阈值T0，将信息的传播时间限制在T0内，这样不仅可以计算出节点的影响概率，同时也降低了时间复杂度．估算节点影响概率的扩展方法如算法1所示．算法1 CPM(估算节点影响概率)输入 G=〈V，E〉，R，S，T0输出 r，s，pr初始化阶段：ps(v,0)←1，pr(v,0)←0 ∀v∈Spr(v,0)←1，ps(v,0)←0 ∀v∈Rpr(v,0)←0，ps(v,0)←0 ∀v∈V-(R⋃S)r(v,0)←pr(v,0)， s(v,0)←ps(v,0) ∀v∈V计算阶段：for t=1 to T0 doNext S←∅，Next R←∅Next S←Next S⋃N+(v) ∀v∈Scompute ps(v,t) ∀v∈Next Scompute s(v,t) ∀v∈Next SNext R←Next R⋃N+(v) ∀v∈Rcompute pr(v,t) ∀v∈Next Rcompute r(v,t) ∀v∈Next RS←Next S，R←Next Rend forreturn r，s，pr．在算法1中的初始化阶段，计算t=0时刻节点的影响概率；在计算阶段，首先根据式(2)计算节点的正影响概率，随后根据式(3)计算节点的负影响概率．根据IBM问题的次模性[2]，随着时间t的增加，节点影响概率的增量会减小，当tT0时，可以忽略不计．2.2　节点对负面信息的阻塞能力节点对负面信息的阻塞能力，简单来说可以理解为该节点存在和不存在的情况下负面信息传播范围的差值，即S集中节点的阻塞能力越大，负面信息的传播范围就越小．以图1为例，初始状态下节点2为传播负面信息的节点，节点之间的传播概率均为0.5．根据COICM模型的传播特点，节点5的负影响概率为0.5，节点6和7的负影响概率均为0.25．当节点5作为阻塞节点时，节点5的负影响概率减小为0，节点6和7的负影响概率也减小为0．10.13245/j.hust.240211.F001图1节点对负面信息的阻塞实例由此可见，节点5作为阻塞节点对传播到节点5和节点6和7的负面信息都起到了抑制作用．也就是说节点对负面信息的阻塞能力包含两个部分：a．对传播到该节点负面信息的阻塞，即节点5的负影响概率的减小；b．对该节点传播到邻居节点负面信息的阻塞，即节点6和7的负影响概率的减小．将对负面信息阻塞能力大的节点作为阻塞节点能够较好地抑制负面信息的传播．因此，基于节点的影响概率，本研究提出了一种度量节点对负面信息的阻塞能力的计算方法，即b(u)=r(u,T0)+∑0tT0∑  v∈N+(u)w(u,v,t)，(6)式中w(u,v,t)为t时刻节点u传播负面信息给邻居节点v的概率，可以用局部范围内节点间传播负面信息的概率来计算，即    w(u,v,t)=pr(u,t-1)qu,v(1-s(v,t))(1-r(v,t-1)). (7)2.3　节点对正面信息的扩散能力节点对正面信息的扩散能力表示阻塞节点对正面信息的扩散范围．根据COICM模型的传播特点可知：阻塞节点对正面信息的扩散能力越大，被正面信息影响的邻居节点就越多，负面信息的可传播范围就越小．以图2为例，初始状态下节点2为传播负面信息的节点，节点之间的传播概率均为0.5，当节点3作为阻塞节点时，节点5的负影响概率由0.5减小为0.25，节点6和7的负影响概率也由0.25减小为0.125．10.13245/j.hust.240211.F002图2节点对正面信息的扩散实例由此可见，节点3作为阻塞节点对传播到节点5和节点6和7的负面信息都起到了抑制作用．节点3的扩散能力越大，阻塞效果就越好．在传统的影响最大化问题中，节点对信息的扩散能力通常用该节点对邻居节点的传播概率之和来表示[9]，即f(v)=∑u∈N+(v)qv,u．(8)在影响阻塞最大化问题中，由于正面信息的扩散要尽可能阻塞负面信息的传播，因此当计算正面信息的扩散能力时须要考虑该节点的负影响概率．当一个节点的负影响概率为0时，正面信息影响该节点对负面信息的扩散没有阻塞作用．当一个节点负影响概率越大时，正面信息扩散到该节点所获得的阻塞增益就越大，因此，基于节点的负影响概率提出了一种新的度量节点对正面信息扩散能力的计算方法，f'(v)=∑u∈N+(v)(qv,ur(u,T0)). (9)2.4　混合阻塞力基于上述节点对负面信息的阻塞能力和对正面信息的扩散能力来计算节点混合阻塞力，同时将此作为贪心算法选择阻塞节点的依据．节点的混合阻塞力是节点对负面信息的阻塞能力和对正面信息的扩散能力之和，计算公式为z(v)=b(v)+f'(v)．(10)2.5　算法及复杂度分析IBM-MBA算法主要思想是通过k轮迭代来选取阻塞节点集，每轮迭代中，首先，根据当前选取的部分阻塞节点集S和负面信息传播点集R计算出节点的影响概率(见算法1)；然后，基于影响概率计算节点对负面信息的阻塞能力和对正面信息的扩散能力进而更新节点的混合阻塞力(见式(6)、(9)、(10))；最后，选择混合阻塞力最大的节点添加到S集中．算法IBM-MBA的非形式化描述如算法2所示．算法2 IBM-MBA输入 G=〈V，E〉，R，k输出 SS←∅compute CPM(R，S)compute b(v)，f'(v)，z(v) ∀v∈Vv*←arg max{z(v)}S={v*}while |S| k do:compute Q //Q表示节点v*在T0时间内可以到达的点集compute CPM(R，S)compute b(v)，f'(v)，z(v) ∀v∈Qv*←arg max{z(v)}S←S∪{v*}return S算法2首先根据算法1计算节点的影响概率，其时间复杂度为O(T0nd¯)，其中d¯为社交网络的平均度，n为社交网络的节点数；然后根据式(10)计算节点的混合阻塞力，其中计算节点对负面信息的阻塞能力的时间复杂度为O(T0nd¯)，计算节点对正面信息的扩散能力的时间复杂度为O(nd¯)，因此算法2中计算节点混合阻塞力的时间复杂度为O(T0nd¯)．在第一轮迭代中须计算所有节点的影响概率和混合阻塞力，但在第(2-k)轮迭代中，只须更新S集中新增的节点v所影响到的节点集的影响概率和混合阻塞力．那么第(2-k)轮迭代的时间复杂度为O(T0d¯2)，即算法总的时间复杂度为O(T0nd¯+T0nd¯+(k-1)(T0d¯2))=O(T0nd¯)．考虑到T0是一个常数，所以算法IBM-MBA的时间复杂度可以看作O(nd¯)．3 实验分析实验中所有的算法均使用Python语言来实现．运行环境为Windows10操作系统，内存8.00 GiB，处理器Intel(R) Core(TM) i7-7700 CPU @3.60 GHz．3.1　数据集和对比算法实验中选用5个不同规模的真实网络数据集，网络基本信息如表1所示．10.13245/j.hust.240211.T001表1数据集网络基本信息数据集节点数/103边数/103Email1.1335.451Blogs1.22419.025Maayan-figeys2.2396.452Wiki-vote7.115103.689Epinions75.879508.837为了验证本文算法性能，将算法IBM-MBA与当前具有代表性的算法进行比较．实验对比的算法及时间复杂度如表2所示，表中m为数据集的边数；t¯c为构建最大影响树[7]的平均时间；t¯i为生成反向可达集[6]的平均时间．由于构建最大影响树和生成反向可达集的过程须考虑多步可达点集，因此t¯c和t¯i都要远远大于平均度d¯．随机采样算法IBMM的时间复杂度中N表示生成反向可达集的个数，为了要保证解的质量，N通常要比n大．由此可看出，IBM-MBA在时间复杂度上有一定优势．10.13245/j.hust.240211.T002表2对比算法算法年份时间复杂度Proximity[4]2012O(|R|d¯)CMIA-O[7]2017O(nt¯c3+kt¯c2(t¯c+log n))Degree[5]2019O(n+m)BIOG[8]2019O(knd¯3)MSN[6]2020O(nd¯)IBMM[6]2020O(Nt¯i)IBM-MBA2022O(nd¯)3.2　实验方法为验证算法的有效性，实验中利用5个真实网络数据集在COICM模型上的传播进行比较．鉴于加权级联模型是确定权重最常用的方法之一[10]，因此对于边e=〈u,v〉，设置传播概率qu,v=1/|N-(v)|，其中|N-(v)|为节点v的入邻居的个数．为了验证算法IBM-MBA在不同初始状态下的阻塞效果，对每个网络使用两组不同的负面信息节点集R1和R2，其中：R1是随机选择50个节点组成的点集；R2是度最高的50个节点组成的点集．社交网络中影响阻塞最大化算法的评价通常从负面信息的影响范围来衡量．为了更好地对比阻塞前后负面信息的影响范围，采用一种称为拯救比率(SR，ξ)[11-12]的评价指标，它表示阻塞活动前后受负面信息影响的节点数目减少的百分比，计算方法为ξ=I(R)-IS(R)I(R)，(11)式中：I(R)为传播正面信息的点集S不存在的情况下负面信息的影响范围；IS(R)为传播正面信息的点集S存在的情况下负面信息的影响范围．为计算负面信息的传播范围，使用1 000次的蒙特卡罗模拟．3.3　实验结果与分析本研究中影响阻塞最大化算法的评价指标采用拯救比率．即相同规模的S集和相同的传播模型下，SR越大，负面信息的传播范围越小．图3~7比较了5个真实数据集在两种不同的初始状态下的传播结果，图中k为初始状态下传播正面信息节点集的节点个数，即S集的规模．10.13245/j.hust.240211.F003图3Email数据集在不同的R集下的运行结果10.13245/j.hust.240211.F004图4BLOG数据集在不同的R集下的运行结果10.13245/j.hust.240211.F005图5Maayan-figeys数据集在不同的R集下的运行结果10.13245/j.hust.240211.F006图6Wiki-Vote数据集在不同的R集下的运行结果10.13245/j.hust.240211.F007图7Epinions数据集在不同的R集下的运行结果从图3~7中可以看出：SR与点集S的节点个数k呈正相关的态势，这说明传播正面信息的节点越多，对负面信息的阻塞效果越好．虽然算法Degree和算法Proximity在时间效率上有优势，但从图4~7可看出，它们难以有效阻塞负面信息的传播．在Email数据集和BIOG数据集中，当S集规模较小时，算法Degree有着较好的阻塞效果，但随着S集规模增大，阻塞效果趋于稳定，这主要是因为基于中心性算法的存在节点聚集的特点，会导致节点对负面信息的阻塞存在交叉的情况．而算法IBM-MBA在多数情况下都能获得较好的阻塞效果．算法CMIA-O和算法BIOG在Email数据集和Maayan-figeys数据集有着相似的阻塞效果，这是因为两种算法都是基于最大影响路径实现的，S集中的节点也相近．算法IBMM在Epinions数据集中的R1初始状态下有着较好的阻塞效果，但在BIOG数据集中的R2初始状态下有着较差的阻塞效果，表明算法IBMM的稳定性差，这是由其采样的随机性所决定的．而算法IBM-MBA从正面信息的扩散和负面信息的阻塞两个角度考虑节点的阻塞增益，在两种不同的初始状态对应的五个真实数据集上均能有较好的阻塞效果和较高的时间效率，这说明了算法IBM-MBA的稳定性．4 结语本研究基于节点的阻塞能力和扩散能力提出了启发式算法IBM-MBA来求解社交网络中的影响阻塞最大化问题．该算法首先基于COICM模型引入了节点影响概率的计算方法，然后依据节点的影响概率计算节点对负面信息的阻塞能力和对正面信息的扩散能力，并将节点阻塞能力和扩散能力之和最大的节点加入到传播正面信息的S集中．与其他算法相比，该算法有更好的阻塞效果和更快的时间效率．