基于拓扑势的影响力最大化算法

王秀芳，牛炜南，孙承爱，仇丽青

(山东科技大学 计算机科学与工程学院，山东 青岛 266510)

0 引 言

近年来，很多大型社交网络不断涌现，人们可以通过微信，qq和微博等社交网络获取有价值的信息。于是，商家趋向于在社交网络上发布广告信息，让信息通过社交网络传播的更广。例如，商家在想要推销一款产品时，首先选择一些有影响力的人来接受它们，让他们推荐给自己的朋友，朋友的朋友，依次影响更多的人购买这款产品，这就是“口碑效应”。最近比较流行一种职业-美妆博主，他们通过在线试妆，根据用户的要求试该产品，然后分析其产品的优点，推荐该产品，使得很多人对此产品满意，主动去抢购该产品，最终使得产品库存不足，那么，这些商家如何选择合适的美妆博主为他们试妆，使得产品推广的更好，这就是“影响力最大化问题”。当然，社交网络中的影响力最大化问题还有很多其余的应用。比如，职业路径的预测。用户根据自己的基本信息，提取到人生的各个阶段中最具影响力的因素和特征，从而预测未来可能从事的职业。这样对自己的人生规划有着重要的意义。

IMP(influence maximization problem)作为数学优化问题解决的第一个模型是由Kempe等建立的，验证了影响力最大化问题是一个NP问题，提出运用贪心算法和Monte Carlo模拟解决该问题，然而贪心算法的时间复杂度高，不适合大型社交网络。为了提高算法的运行时间，一系列启发式算法被研究者们相继提出。然而，启发式算法在准确率方面还有待提高。研究发现，贪心阶段和启发阶段相结合的综合型算法可以适当均衡影响力和运行时间，这是最近的研究热点。拓扑势理论[1]首次在物理学中提出，近年来被应用到社交网络中用来衡量节点重要性，并取得了一定的效果。

因此，为了均衡运行时间和影响力，从而更有效解决影响力最大化问题，本文提出了一种基于拓扑势的影响力最大化算法，TSH(topology-stage-heuristic)算法。首先，启发式阶段：基于拓扑势理论，识别“山峰”，“山谷”和“斜坡”节点，选择“山峰”和“斜坡”节点作为候选种子集。然后，贪心阶段：使用CELF算法[2]从候选种子集中选择最优种子集。

1 相关研究

影响力最大化问题被Kempe等提出后，因为其广泛的应用，得到了研究者们极大的关注。目前，研究者对此问题的解决方法可以归纳为两类：贪心算法和启发式算法。

自从Richardson和Domingos等[1]将影响力最大化问题归纳为算法问题后，Kempe等[2]提出了贪心算法来解决此问题。贪心算法需要重复计算节点的影响增益，然后选择影响力增益最大的节点作为种子节点，导致了其在大规模社交网络上运行时间慢，不适合大规模社交网络。为了解决贪心算法时间效率低的问题，一些优化算法被提出，比如经典的CELF算法[3]，它利用子模性来减少计算的时间，从而提高运行时间。然而，这些优化算法虽然提高了运行时间，但是在面对大规模社交网络时仍存在时间效率问题。因此，一系列启发式算法被研究者们提出[4-20]。Nguyen等[5]提出了一种基于概率的多跳扩散方法来解决影响力最大化问题，该算法考虑了多跳邻居节点的影响，从而提高算法的准确性。Han Meng等[6]将时间延迟，接受率和传播宽度这3个因素相结合，研究了一个新的模型，其运行结果优于传统的算法。另外，Kyomin Jung等[7]提出了包括信息排序和信息评估两个方面的IRIE(influence ranking influence estimation)算法，此算法在运行时间和影响范围上有了明显的提高。与上述研究方向不同，Cao等[8]结合度和核提出了CCA(core covering algorithm)算法，首先从核心开始选择度比较大的节点作为种子节点，一旦某个节点被选为种子节点，其邻居节点将会被覆盖。该算法可能覆盖部分影响力较高的节点，使得影响范围不太准确。为了解决重叠社区的影响力问题，Qiu等[20]提出了IM-BOC(influence maximization algorithm based on overlapping community)算法。该算法分为3个阶段：划分社区，启发阶段和贪心阶段。

近年来，很多研究者将拓扑势理论应用于社交网络[21-24]，并取得了很好效果。复杂网络中，每个节点并不是孤立存在的，而是通过边相互联系，从而可以使用拓扑势场来进行模拟。假设一个节点为一个场源，则它会作用于场中的其它节点，从而构成了拓扑势场。文献[21]基于拓扑势，提出了一种基于位置的重叠社区发现方法。文献[22]利用拓扑势来评估节点重要性。与上述不同的是，何婧等[23]利用拓扑势来进行动态社区挖掘。

综上所述，为了解决影响力最大化问题中效率和效益问题，本文首先使用拓扑势理论挖掘社交网络中的“山峰”，“山谷”和“斜坡”节点，选取“山峰”和“山谷”节点作为候选种子集。然后，采用CELF算法确定最优种子集。这样，在保证影响范围的情况下，有效提高了算法的运行时间，从而弥补传统算法的缺陷。

2 影响力最大化与传播模型

2.1 问题描述

用网络图G(V,E) 表示是社交网络，V表示节点，E表示边。按照某种指标(度指标，介数指标，最短路径等)，从所有节点中选取k个影响力最大的节点作为种子节点(激活状态)，按照规定的传播模型将其消息传播给其邻居节点，使得最终影响到的节点最多。其具体表示如下所示

σ(S*)=max{σ(S)|S⊆V,|S|=k}

(1)

2.2 传播模型

社交网络信息传播的模型中，有两种比较常用的传播模型：独立级联(independent cascade，IC)模型和线性阈值(linear threshold，LT)模型。在这两种模型中，节点只有一种状态，要么激活态，要么非激活态。一个节点只可从非激活态转换为激活态，反之，不成立。一旦节点被其它节点激活或者未被其它节点激活，这个节点将保持激活态或者未激活态，不会再改变。IC模型假设种子集处于激活态，其它节点为未激活态，种子节点有且仅有一次机会去激活其邻居节点，邻居节点要么被激活，要么未被激活。而LT模型是对节点的激活概率进行累计，当达到一定阈值时，节点则会被激活。否则，节点将不会再被激活，保持非激活态。因为IC模型容易理解，而且比较符合信息传播特征，大多数研究采用IC模型，因此，本文也选用IC模型。该模型的传播流程如下所示：

(1)设种子集S为激活状态，其余节点为未激活态；

(2)激活态节点S以概率p去尝试激活其每一个邻居节点v；

(3)若节点v被激活，则v为激活状态，v将会重复(2)。否则，v是为未激活状态，它将保持此状态，不会再改变状态；

(4)不断重复上述过程，直至所有的节点都保持一种状态。

3 算法实现

为了均衡影响力范围和运行时间，本文提出了一种基于拓扑势的影响力最大化算法。该算法主要由以下两个阶段组成：启发式阶段和贪心阶段。启发式阶段，运用拓扑势理论，鉴别“山峰”，“山谷”和“斜坡”节点。“山峰”节点为影响力较大的节点，而“斜坡”节点为连接节点，我们将“山峰”和“山谷”节点加入候选种子集中。贪心阶段，采用CELF算法从候选种子集中确定最优种子集。其结构框架如图1所示。

图1 算法框架

3.1 启发式阶段：选取候选种子集

拓扑势理论自从被提出后，很多研究者将其用于社交网络。本文中，我们将节点的拓扑势作为衡量节点影响力指标。拓扑势理论需要研究的重点是如何评估节点的质量，节点的影响力因子以及节点间的最短路径。因为节点之间距离越远，受到的影响可能越小。

3.1.1 拓扑势

定义1 拓扑势：节点v的拓扑势计算方法如下

(2)

其中，nn为节点v的二度邻居节点，u为节点v的邻居节点，m(u) 为节点u的质量(如式(4)所示)，σ为影响力因子(如式(3)所示)，dvu为节点v和节点u之间的距离，取值为1或2(若邻居节点，则取值为1；若二度邻居节点，则取值为2)。

3.1.2 影响力因子

影响力因子σ用来控制节点的影响范围。通常可根据网络中节点的势熵来筛选。势熵的大小与网络的不确定性有关。势熵越小，网络的不确定性越小，网络的分布越不均匀。

定义2 势熵：设节点v的拓扑势为φ(v)， 则势熵为

(3)

由式(2)可知，当σ=0时，φ(u→v)→0时，则说明u和v之间无作用力，即φ(v)=mv=M， 此时，势熵趋近于最大值logN。 当φ(u→v)→∞时，φ(u→v)→mu， 则说明u和v的影响力相同，此时，势熵趋近于最大值logN。 因此，σ∈[0,∞)，H∈[0,logN]。 它们的关系如图2所示。因为势熵越小，网络的分布越均匀，所以，取H=logN， 此时σ≈2。 因此，我们取节点的拓扑势的影响范围主要是由二度邻居决定。

图2 势熵与影响因子关系

3.1.3 节点质量

节点的度是指与该节点直接相连的边的数量，其在一定程度上能够反应节点影响力，节点的度越大，说明其影响力越高。然而，若一个度很大的节点，其却很少进行传播信息，即其传播概率很小，这样，其影响力整体上来说，应该相对较小。因此，本文中，我们将传播概率和度结合，提出了加权度，作为衡量节点质量的指标。

定义3 节点质量：节点u的质量m(u) 的计算方法如下所示

(4)

其中，du和dw为节点u和w的度，N(u) 为u的邻居节点，puw为节点u激活v的概率。

3.1.4 节点位置

我们根据相邻节点的拓扑势，将节点的位置分为以下3类：山峰，山谷和斜坡。山峰节点代表着影响力相对较大，为相邻节点间的代表。斜坡节点相当于边缘节点，与外界联系密切，其充当“中介”的作用。山谷节点是内部节点且其影响力较小。我们根据影响因子将影响范围考虑为二度邻居节点。

(1)山峰。对于社交网络中节点v满足∀φ(v)≥φ(u)， 其中u为v的二度邻居节点，则v为山峰节点。

(2)山谷。对于社交网络中节点v满足∀φ(v)≤φ(u), 其中u为v的二度邻居节点，则v为山谷节点。

(3)斜坡。对于社交网络中节点v满足∃φ(v)<φ(u) 或者∃φ(v)>φ(u)， 其中u为v的二度邻居节点，则v为斜坡节点。

为了更加清楚的解释山峰，山谷和斜坡节点，我们以一个包含10个节点的社交网络为例，其简易图如图3所示。根据拓扑势公式(式(2)和式(4))，社交网络中的10个节点的拓扑势及节点的位置，见表1。

3.1.5 候选种子集

根据以上小节，我们已确定节点的相对位置：山峰，山谷，斜坡。在影响力传播的过程中，我们不仅需要影响力大的节点，而且需要边缘节点与外界进行联系。因此，为了提高算法的准确性，我们按照节点质量大小选取k个山峰节点和k个山谷节点作为候选种子集。

图3 社交网络

表1 社交网络中节点拓扑势及位置

节点12345678910拓扑势16162423232120171710位置山谷山谷山峰斜坡斜坡斜坡斜坡斜坡斜坡山谷

3.2 贪心阶段：确定最终种子集

通过上一小节我们得到了由k个山峰节点和k个山谷节点组成的候选种子集，本小节的主要任务就是利用CELF算法从候选种子集中选出最优种子集，使得最终影响力最大。CELF算法主要是在贪心算法的基础上利用节点的影响力具有子模性进行优化，使得时间效率比原始的贪心算法快了近700倍。

定义4 CELF算法：对于节点A，B和C，在节点A加入种子节点后，在下一轮选择种子节点时，若B在此轮的影响力增益大于C在上一轮的影响力增益，利用子模性，C在此轮的影响力必定小于其在上一轮的影响力增益，因此，B在此轮的影响力增益大于C。所以，我们可以直接将节点B加入种子节点，不需要再额外计算C的影响力增益，从而提高时间效率。

CELF算法利用子模型改进了贪心算法，在准确率上有了一定的保证，但是，其运行时间虽然比贪心算法快了700倍，仍然不适用于大型网络。所以，我们先根据拓扑势理论划分节点的位置，将山峰节点和斜坡节点作为候选集，再利用CELF算法从候选集中选择最优种子集，从而提高时间效率。该算法的伪代码如下。

算法1：TSH算法

输入：社交网络G=(V,E)， 种子数量k

输出:种子集S

(1)初始化: 种子集S←φ

(2)forv∈V：

(3) 计算节点v的拓扑势φ(v)

(4)判断节点的位置

(5)从山峰山谷节点中：

(6) 按照加权度选取k个山峰节点和k个斜坡节点组成候选种子集

(7)对候选种子集进行CELF算法，寻找最优k个种子

(8)返回种子集S

时间复杂度：假设社交网络G=(V,E) 有n个节点，m条边，TSH算法的时间复杂度分析如下：第(2)～(3)行，计算节点拓扑势的时间复杂度为O(nemax2)， 其中emax为最大连边数。第(4)行判断节点的位置的时间复杂度为O(n)。 第(5)～(6)行选取候选种子集的时间复杂度为O(2k)。 因此，该算法的总的时间复杂度为O(nemax2+n+2k)≈O(nemax2)。

4 实验与分析

4.1 实验数据集

为了验证算法的合理性，本文从斯坦福网站(http://snap.Stanford.edu/data/)上选取了4种不同类型的数据集：Ca-AstroPh，As-Caida，Email-Enron和Amazon数据集。其中，Ca-AstroPh源自e-print Arxiv，是由提交文章的科学家之间的协作关系所构成的。As-Caida是从地理和拓扑上不同位置的几种不同类型的数据中收集的。Email-Enron数据集是由CALO项目得出，它是由大约150个员工进行交流沟通所构成的网络。最后，Amazon数据集是通过爬取Amazon网站的评论和链接等而收集的。这4种数据集的基本信息见表2。

表2 数据集基本信息

4.2 对比算法及参数设置

为了验证算法的有效性，我们将TSH算法在IC模型的基础上，与CELF，PMIA，IRIE，Degree Discount和CCA算法进行比较。这6种算法的简要介绍如下所示。

TSH：该算法分为启发式算法和贪心算法。启发式阶段根据拓扑势找出候选种子集；贪心阶段使用CELF算法求出最优种子集。

CELF：贪心算法的代表算法，使用子模性原理优化了贪心算法。

PMIA：基于最短传播路径的较为经典的启发式算法。

IRIE：由IR和IE两个阶段组成，在时间效率和影响力范围上表现较好。

Degree Discount：在度中心性的基础上，对种子节点的邻居节点进行打折，从而提高了算法的准确性。

CCA：基于核覆盖理论，为了减少影响力重叠，将种子的节点的邻居进行覆盖。本文设radius=2。

为了评估上述6种算法的优劣，我们在IC模型的基础上，用蒙特卡罗模拟了10 000次实验，并在4.3.1中给出了影响力扩散的平均值。

4.3 结果分析

影响范围和运行时间是衡量社交网络影响力最大化的两个标准。目前现存的大部分算法存在影响力计算的准确性或者运行时间的问题。本节中，我们从影响力和运行时间两方面对我们的TSH算法和5个对比算法在4种不同的数据集上进行评估。

4.3.1 影响范围

图4(a)～图4(d)分别描述TSH，CELF，PMIA，IRIE，Degree Discount，和CCA算法在Ca-AstroPh，As-Caida，Email_Enron和Amazon数据集上的传播范围。通过比较这4种数据集上表现，我们可以轻易地发现CCA算法的影响范围整体上来说相对较低，其影响力分别低于TSH算法54%，78%，74%和44%。这可能是由于CCA算法虽然考虑了节点的度和核，但是其为了减少影响力重叠，覆盖了种子的邻居节点，这可能覆盖了过多的影响力高的节点，导致其影响范围不准确。PMIA算法整体上影响力明显低于TSH，CELF，IRIE和Degree Discount。比如，在Amazon数据集上，当种子集为100时，PMIA低于TSH算法36%。这可能是因为PMIA仅考虑了最短路径这一个因素，导致其影响力存在一定的误差。另外，Degree Discount算法的表现相对较好，明显高于PMIA和CCA算法，而且跟IRIE的影响范围相差无几。值得注意的是，TSH算法在4个数据集上仍分别以4%，5%，4%和11% 高于Degree Discount算法。这可能是因为DegreeDiscount算法将度大的节点看作影响力大的节点，没有考虑网络的整体结构，可能导致其影响力存在一定的误差。除此之外，当种子集为100时，TSH在4种数据集上的影响范围分别以2%，6%，6%和1%高于IRIE算法，充分说明了TSH算法的优越性。在这4个数据集上，TSH算法影响力跟CELF算法差不多，但是，由图4可知，CELF算法在Ca-AstroPh，As-Caida，Email-Enron和Amazon这4个数据集上的运行时间分别是1090 s，1733 s，13 401 s和12 850 s，不适合大型网络。而TSH算法在262 111个节点，1 234 877 条边的Amazon算法上的运行时间仅需344 s。综合考虑，TSH算法有效均衡了影响力和运行时间，不仅其准确率较高，而且其运行时间较快，适合大规模的社交网络。

图4 影响范围

4.3.2 运行时间

TSH，CELF，PMIA，IRIE，Degree Discount和CCA算法的时间复杂度分别是O(nemax2)，O(knm)，O(ntiθ+knoθniθlogn)，O(∑v∈Vdout(v))，O(klongn+m) 和O(km)。 由于各种数据集的内部属性不同可能导致其运行时间存在差距，因此，我们从斯坦福网站上选择了4种不同类型的数据集进行比较，以增强说服性。图5描述了TSH，CELF，PMIA，IRIE，Degree Discount和CCA算法在Ca-AstroPh，As-Caida，Email-Enron和Amazon数据集上的运行时间。从图5中可以看出，CCA算法的运行时间最快，而TSH算法的运行时间仅次于CCA算法。但是由图4可知，当种子集为100时，CCA算法在4个数据集上的影响范围约占TSH算法的45%，20%，25%和56%，影响力较低。图4显示CELF算法影响力较大，但是从图5中可知，其运行时间最长，尤其在Email-Enron数据集上的运行时间高达12 850 s，约是TSH运行时间的两倍。Degree Discount算法的运行时间整体上来看运行效率较高，但是，Degree Discount未重复考虑网络的整体结构，仅从局部角度评估节点的影响力，所以，其运行结果可能不太准确。TSH算法的运行时间在4个数据集上比PMIA分别快了77%，66%，41%和96%。另外，TSH算法的运行时间在4个数据集上比IRIE分别快了57%，73%，42%和24%。虽然TSH算法在计算拓扑势时，需要考虑节点间的传播度，导致了其运行时间稍长。但是，TSH在中大型社交网络Amazon上仅用344 s，比CELF，PMIA，IRIE，Degree Discount快了97%，59%，90%和24%，说明了TSH算法在大规模社交网络的可行性。

图5 运行时间

5 结束语

本文基于拓扑势理论，提出了一种启发式和贪心算法相结合的启发式算法-TSH算法。该算法首先使用拓扑势理论判断节点的位置，鉴别节点为“山峰”“山谷”和“斜坡”节点。然后，将“山峰”和“斜坡”节点加入到候选种子集。最后，使用CELF算法从候选种子集中确定最优种子集。

实验结果表明，与传统的算法相比，该算法的影响力与贪心算法近似，而运行时间却是贪心算法的两倍，从而，有效均衡了运行时间和传播范围。然而，我们分别选取k个山峰节点和k个山谷节点来构成候选种子集可能存在误差，如何对“山谷节点”和“山峰节点”的数量进行合理分配是我们下一步研究的重点。