代价约束下基于随机游走的负影响力传播抑制方法

陈伯伦，朱国畅，纪敏，朱鸿飞，韦晨

（淮阴工学院 计算机与软件工程学院，江苏 淮安 223003）

近年来，随着在线社交网络的蓬勃发展，成千上万的人通过形式多样的媒介产生前所未有的海量数据，并且数据呈现出多源化、异构化的趋势。其中，影响力最大化是社交网络分析中的一项重要的研究课题，主要是通过网络中的病毒式营销来驱动，目的是找到在特定传播模型下最大化影响力传播的关键用户子集[1-2]。

Morone 和Makse 在Nature上发表论文，对影响力最大化问题进行了深入探讨[3]。影响力最大化的目标就是在群体中寻找一些关键的种子节点集合用于去最大化其余节点。例如：在病毒式营销的情况下，公司希望依靠口碑推荐来增加其产品的销售，通过挖掘网络中的重要客户的影响力去最大化宣传效果[4]。2020 年新型冠状病毒肺炎的爆发，牛津大学、哈佛大学医学院、波士顿儿童医院等团队在Science上发表论文，他们基于中国百度地图迁徙大数据平台的数据，分析了研究人员的迁徙与疫情之间的相关关系，为研究病毒传播提供了强有力的数据支撑[5]。另外，影响力最大化的研究对病毒传播、政府部门进行舆情管控、虚假信息控制以及这些信息的发布源追踪等提供了理论上的支撑，为社会的安全保障活动起到了应有的保障作用[6-7]。

影响力在传播的过程中，存在着正影响力，例如同意、支持、好评等，也存在着诸如差评、谣言等负影响力，很多负面消息都在网络中迅猛肆意地扩散，复杂网络中影响力最大化问题目标是希望能够最大程度地限制网络中负影响力的扩散，切断传播途径。新冠肺炎的爆发，网上出现了大量的谣言，这些谣言经过用户的转发大规模地扩散。例如，网络中曾传白岩松主持一场邀请钟南山院士介绍疫情的活动新闻。一时间，各微信群、朋友圈、论坛，甚至一些大V 的博主都转发了该新闻，后来经证实这条新闻是谣言。可以看出负面影响力传播时间短，但是传播速度快，影响范围广。因此，如何对负影响力进行抑制，通过一些措施来制止谣言的传播显得格外重要[8]。

负影响力传播抑制最大化问题其实就是通过选择一些种子节点来尽可能地阻止其竞争实体的影响传播，He 等[9]称此问题为影响阻塞最大化(influence blocking maximization，IBM)问题，同时证明了在竞争性线性阈值模型中IBM 的目标函数是亚模的，贪婪算法可以达到最优解。当社交网络中出现负面信息并且部分用户已经受其影响时，Arazkhani 等[10]提出了基于中心度测量的算法，以寻找适当的正影响种子节点进行扩散以最小化IBM 问题。谭振华等[11]结合引力学思想，对负面信息的传播过程进行刻画，并充分考虑用户的个性化特征，对谣言的传播进行抑制。Tong 等[12]发现经典的贪心算法与蒙特卡洛模拟相结合的算法运行时间过长，提出了一种随机近似算法，在保证性能的同时提升了运行效率。刘亚州等[13]考虑到不同节点在受到负影响力影响时的差异性以及影响力在网络上传播的特性，进行负影响力传播的研究。Lee 等[14]通过分析在影响扩散过程中节点的潜在影响趋势，提出了影响分布重定向算法，通过重定向节点的影响分布，以最大化目标函数来定义影响扩散的初始种子节点。曹玖新等[15]通过K-核和节点的度，提出了基于核数层次特征和影响半径的核覆盖启发式算法。Peng 等[16]通过引入社会关系图评估节点影响力，然后使用选举制查找最有影响力的节点，最后通过对前k个有影响力的节点采取免疫措施来阻止负影响力的传播。陈晋音等[17]对网络拓扑结构进行了修改，提出了基于信息级联预测模型的抑制虚假消息传播的算法。江成等[18]从负影响力传播的广度和深度两个维度，对负面信息传播影响力进行测度分析，从而设计出抑制负影响力传播的启发式策略。

目前还有一部分工作是基于网络的社区结构的。Arazkhani 等[19]提出了一种使用模糊聚类和集中度度量来找到用于扩散正信息的节点的良好候选子集的方法。Lv 等[20]根据影响力的种子节点在社区中的分布，首先确定种子节点的数量，然后，选择影响力最大的前k个节点，提出了一种网络社区结构的模型，从而解决社交网络中影响力扩散的局部性的问题。除此之外，Wang 等[21]提出了一种具有用户体验的动态谣言影响最小化模型，该模型同时考虑了谣言的全球知名度和吸引力以及用户体验效用的约束，为每个节点分配一个容忍时间阈值，如果用户的阻止时间超过该阈值，则用户对该网络的满意度将会降低。Zhu 等[22]发现位置信息可以在影响力传播中发挥重要作用，针对位置感知影响块最大化问题，通过寻找一个正种子集，以阻止负面影响在给定区域中的传播，提出了基于四叉树索引和最大影响树状结构的两种启发式算法。

从国内外研究现状可以看出，在负影响力抑制研究方面，传统的方法将正负影响力传播特征同等地看待，然而在真实环境中，相比于正影响力的传播，负影响力的传播速度更快，传播范围更广。因此在负影响力传播抑制的过程中，如何对负影响力的传播范围以及抑制节点的抑制范围进行合理的度量显得格外重要，本文利用叠加的随机游走策略对网络的影响力传播进行度量，将影响力传播的范围控制在某一子图中，设计出抑制负影响力传播的有效方法。

1 问题的描述

本文将社交网络影响力传播问题用图的结构来进行模拟，首先用G=(V,E)来定义该网络，其中V代表网络中节点的集合，节点可以被正影响力激活也可以被负影响力激活。E代表节点之间边的集合。如果社交网络G 中存在两个节点u和v，且u和v不是同一个节点，那么 (u,v)∈E表示u和v之间存在一条连边，它们之间可以进行影响力的直接传播，该传播概率用p来表示。其中，n表示网络G 中节点的总个数，即n=|V|，用m表示网络G 中的总边数，即m=|E|。那么影响力最大化问题即转化成在图G 中寻找k个种子节点使其能够阻止节点的负影响力在网络中的传播。

在网络G 中，如果想要选择一些节点来抑制网络中节点负影响力的传播，则需要付出相应的代价。例如：某企业想通过明星代言来扩大自己的影响力，而每一位明星的出场费是不同的，并且企业的广告宣传费用是有限的，那么成本限制下影响力最大化就转化成如何在有限的成本下，邀请到的明星能够使得企业的影响力最大。因此，本文设 c ost(v)为节点v的代价，成本的总代价为Q。设I(SN,SP)为被负种子集合激活的顶点个数的期望值。 (SN为负种子集合，SP为正种子集合)因此，成本限制下的负影响力抑制问题的目的是在顶点集合VSN中选择一个最优的正种子集合S∗，使得I(SN,S∗)最小：

2 算法的主要思想与步骤

对网络中负节点影响力传播的范围进行模拟，使用抽样子图的方法对抑制节点的综合影响力进行精确地度量，设计出抑制负影响力传播的有效方法，算法步骤如下所示：

算法基于随机游走的负影响力传播抑制方法(SRW-IBM)

6) 根据渗流理论计算最优抑制节点个数k=λNp|S|pm，其中pm为相变值；

7)选取综合影响力排名靠前的k个节点作为负影响力抑制节点集合S∗。

算法的流程图如图1 所示。

图1 算法流程Fig.1 Flow diagram of algorithm

2.1 两点之间影响力权值计算

本文首先设置节点被负影响力影响的阈值θv，如果两点之间的相似性大于该权值，那么该节点将被负激活。接下来对负节点的传播范围进行估计，设N(SN,G)为在网络G中被负种子节点集合SN激活的顶点集合。我们将有叠加的局部随机游走(superposed random walk，SRW)的相关思想与影响力传播模型相结合，对负节点的传播范围进行度量。假设负影响力节点u从t时刻传播，定义πt(u,v)为t+1 时刻负影响力正好传播到节点v的概率，那么可以得到系统演化方程：

式中：π0(u)为一个N×1的向量，只有第u个元素为1，其他元素为0。其中矩阵P=[p(u,v)]。p(u,v)=a(u,v)/k(u)。a(u,v)为邻接矩阵A中的元素，k(u)为节点u的度。设定各个节点的初始资源分布为q(u)，那么基于t步随机游走的两点之间影响力权值为

在这基础上，将t步及以前的结果加起来便得到SRW 的影响力权值，即

对式（4）的计算，关键在于对 πl(u,v)的计算。设Hl(x)为由x出发所有长度不超过l 的路径的集合。设路径h∈Hl(x)，定义d(h)为h中顶点u到v的距离。则 πl(u,v)可以写成：

在得出两个节点之间的影响力权值后，接下来可以求出每一个节点被负影响力节点激活的概率，如果节点的激活概率大于负影响力影响的阈值 θv，那么该节点将被负激活。

2.2 抑制节点的影响力子图计算

确定了负激活顶点的集合后，接下来需要对网络中的每一个可能被负种子集合激活的节点v进行抑制，抑制其被负激活。如果v在被负激活之前能被正种子u激活，则称u为v的抑制顶点。其中顶点v的抑制顶点集合，称之为反向被抑制，用 RI(v,G)来表示。顶点u可以抑制被负激活的顶点集合，称之为节点u的正向抑制，用PI(u,G)来表示。为阻止节点v在被激活成负节点之前被正激活，需要设计抑制顶点被负激活的规则，即求每个顶点v∈N(SN,G)的 RI(v,G)的集合S。本文首先设最大的抑制节点集合S=V−SN，在计算S中每个节点u的抑制集合 PI(u,G)过程中，对每一节点在整个网络中进行遍历是一项巨大的耗时工程，因此本文拟对S中节点影响力的传播用抽样子图方法进行模拟，使得节点的正影响力在某一范围内进行传播，降低算法的搜索时间复杂度。

首先，文中定义Gu(r)是以u为中心，r为半径的子图。给定一个 ε>0，即可以求出一个关于目标节点u的子图Gu(r)，使得Gu(r)中的顶点v与u的影响力不小于 ε，而Gu(r)外的顶点与u的影响力小于ε。这样，可不必考虑Gu(r)以外的顶点，只需考虑Gu(r)中的节点与u的影响力。

接下来，在给定 ε 的情况下，关键是要计算节点u的子图半径r。记 πt(u,v)为 πt(u)的第v个分量，为影响力由顶点u出发，t时刻到达顶点v的概率。设G的子图Gu(r)满足：对所有的节点y∈G−Gu(r)，有wt(u,v)≤ε。因为y∈G−Gu(r)，那么节点v到节点u的最短路径大于r，即影响力从u出发到v最快在r时间到达，即 π1(u,v)，π2(u,v)，…，πr−1(u,v)，全为0。对于t≥r，设k(u)=h，k(u)为节点u的度。则从u到v的路径最大可能的概率是由图2 所示的路径l构成。路径l满足如下条件：起点u和终点v的度分别为k(u)和k(v)，路径l中其余节点的度皆为2。

图2 节点u 与v 之间最大可能概率的路径lFig.2 Pathlof the maximum possible probability between nodesuandv

因此，粒子选择此路径的概率为

根据粒子选择路径的概率优化问题，本文使用牛顿法来进行求解。因此得出 πt(u,v)和πt(v,u)的取值范围是和搜索半径r相关的某一函数，记为

根据式(4)可知如果使得子图外的节点和目标节点的影响力权值满足w(u,v)≤ε，即要求其满足：

由此可得节点搜索半径的取值范围：

图3 抑制节点的影响力子图Fig.3 Influence sub-graph of restraining nodes

2.3 抑制节点集合大小的计算

当完成节点影响力的模拟后，本文通过渗流来模拟网络传播影响力的固有能力，进行最优抑制节点个数的选取。在网络G 中，本文通过改变传播概率p的值，并在网络G 上对节点进行随机选择，通过这种模拟方式模拟了影响力扩散的动态演化。其中被选中节点所形成的最大连通子图大小s与概率p之间就发生了幂律行为，在相变值pm处，s变化速率最快，意味着此时影响力传播速度最快，因此本文取pm作为影响力传播速度的上界，即当网络中传播概率p>pm时，网络传播的能力变化已经不明显了，所以本文将pm作为网络G 传播概率的临界概率，即渗流值，并作为网络传播影响力的固有能力的度量标准。因此本文抑制节点的个数定为k=λ×Np×|S|×pm，此数值为抑制节点个数的上界，如果超过此数值，那么其余的抑制节点的抑制效果是不明显的。

最后在确定完抑制种子节点的个数以后，需要从S集合中挑选出最优的抑制节点。算法首先计算每一个节点u的影响力子图，然后计算抑制集合中节点的个数 |PI(u,G′)|，然后，结合节点的度k(u)计算出每一个节点的综合抑制力：

并对其进行排序，其中 α 为调节节点的影响力子图和节点度的参数。本文将其设置成0.5。最后根据综合抑制力选取前k个抑制节点作为负影响力抑制节点集合。

3 实验结果及分析

3.1 数据集介绍

在实验模拟中，本文通过4个真实数据集来对算法进行测试与分析，4个真实数据集分别是：email[23]、socfbBowdoin47[24]、hamsterster[25]和socfb-Smith60[26]。其中，email 由欧洲大型研究机构的电子邮件数据组成，数据由发送与接收的邮件信息组成，如果节点u和v之间至少收发过一次邮件，那么u和v之间存在一条边。socfbBowdoin47和socfbSmith60 是从FaceBook 数据中提取出来的，代表着用户之间是否是好朋友。如果节点之间是好友关系，那么节点之间存在一条边。Hamsterster 是从hamsterster.com 网站上提取的朋友与亲人信息。所有数据集的拓扑属性如表1 所示，其中n、m分别为网络中节点和边的总数，网络中最大节点的度用dmax表示，平均度用d¯ 表示。网络的同配系数、聚集系数以及网络的密度分别用r、C、D来表示。

表1 4个不同数据集的拓扑属性Table1 Topological properties of four different datasets

4个不同的数据集具有不同的网络特性，例如email 数据集的同配系数r<0，表示度大的节点倾向性和度小的节点相连接；而其余3个数据集的r>0,表示度大的节点更倾向性和度大的节点相连接。hamsterster 数据集聚集系数C更高，因此相比于其余3个数据集而言节点之间的连接更加紧密。

3.2 最优种子节点数量的选取

为了计算网络G的相变值pm，首先需要计算函数F(x)的变化速率。图4 中，p为传播概率，纵坐标为函数F(x)的变化速率rate，即函数dF(x)的值。图4 中绿色的点用pm来表示，也是函数F(x)变化最快的时候。当网络的传播概率p小于相变值pm时，变化率r还处于较低水平，渗流后的网络由零散的小团块组成，当传播概率p大于pm时，渗流后的网络趋向由主团块组成，逐渐呈现出以最大连通子图为主的图结构。本文相变值pm反应了网络G传播影响力的固有能力，也就是相变值反应网络G中边被激活的能力，即在影响力传播模型下，被激活边占总边数的比例。

因此最终可以通过相变值计算出最优种子节点的个数。如图4 所示，本文4个数据集的相变值pm分别为0.020、0.009、0.034、0.008。

图4 不同数据集拟合函数变化速率Fig.4 Changing rate of fitting function in different datasets

3.3 影响力范围的比较与分析

本文将SRW 算法和经典的度中心性(degree centrality，DC)[27]、网页排序(pagerank，PR)[28]、随机算法(random，RD)[29]的抑制影响力范围变化随着负种子集合大小变化的结果进行比较，实验结果如图5 所示。

图5 4 种经典算法抑制影响力随着负节点集合变化曲线Fig.5 Inhibition effect curves of the four classical algorithms with respect to the change of the negative node set

在图5 中，横坐标为负种子节点占整个网络节点总数的百分比Np，纵轴上的IF 表示k个种子节点的综合影响力之和。

计算公式为

其中，α ∈(0,1)为控制抑制节点个数和节点度影响力的参数。由实验结果可以发现，在不同数据集中，无论负种子集合大小如何变化，SRW 算法在选取抑制节点集合所取得的效果几乎都是最优的。

另外本文还将SRW 算法和基于反向元组的随机化算法(reverse-tuple based randomized，RBR)[14]以及基于社区划分算法FC_IBM[19]的抑制影响力范围变化随着负种子集合大小变化的结果进行比较，如图6 所示。

图6 3 种算法抑制影响力随着负节点集合变化曲线Fig.6 Inhibition effect curves of the three algorithms with respect to the change of the negative node set

其中RBR 算法在Np值较小的时候基于反向元组通过抽样的方法对负节点进行抑制，准确率较高。而FC_IBM 算法首先通过模糊聚类对网络进行社区划分，虽然在社区结构比较明显的数据集上该算法的效果略优，但该方法在社区不明显的数据集中效果一般。因为在本文的4个数据集选取过程中，它们的社区结构不是太明显。并且真实数据集中存在着重叠社区的影响。因此本文提出的SRW 算法效果的鲁棒性更强。

3.4 影响力成本的比较与分析

负影响力在传播的过程中，需要选取性价比较高的节点作为抑制节点集合，这样可以在有限的成本下最大化完成影响力的抑制。本文中，节点v的成本定义如下:

其值正比于节点的度，节点的度越大，表明需要选取该节点作为抑制该节点所需要的成本就越高。图7 和图8 分别为SRW 算法与经典算法以及SRW 算法与RBR、FC_IBM 算法在选取抑制节点集合的成本代价总和随着负种子节点集合大小变化而变化的趋势。

图7 4 种经典算法抑制集合种子成本随着负节点集合变化曲线Fig.7 Seed cost curves of the inhibition set of the four classical algorithms with respect to the change of the negative node set

图8 3 种算法抑制集合种子成本随着负节点集合变化曲线Fig.8 Seed cost curves of the inhibition set of the three algorithms with respect to the change of the negative node set

从图7 中可以看出，随着负种子节点的增加，抑制节点集合的种子节点成本也逐渐增加，因为需要有更多的种子节点来进行负影响力的抑制。但是其中SRW 算法相对于Degree Centrality、PageRank、Random 算法，选取的抑制节点集合所需要的成本是最低的。从图8 中SRW 算法与RBR 算法的对比过程中发现，虽然在Np较小时候RBR 算法的抑制影响力范围较优，但是他们选择的种子的成本也较大。综上所述，SRW 算法在给定的抑制节点数量的前提下可以最大化地影响到其余节点，并且所取的代价也是较优的。

4 结束语

在社交网络的信息传播机制中，不同用户之间信息扩散往往会受到用户之间影响力的影响。本文主要对负影响力的传播进行抑制研究，在未知影响力传播模型的基础上，通过有叠加的随机游走策略对负影响力传播进行模拟。在抑制节点的影响力度量中，提出了节点的影响力传播子图的概念，使得抑制节点的影响力传播局限在以该节点为源点的某一子图中，有效地降低了影响力计算模拟的复杂度。在此基础上，引入渗流的思想来进行抑制节点集合大小的选取，构建了代价约束下的抑制节点的最优选择方法。实验结果表明，该方法对负影响力抑制中，抑制节点的选取起着重要的指导性作用。