基于社交网络的影响力最大化算法
2022-09-03王璿张瑜周军锋陈子阳
王璿，张瑜，周军锋，陈子阳,2
（1.东华大学计算机科学与技术学院，上海 201620；2.上海立信会计金融学院信息管理学院，上海 201620）
0 引言
影响力最大化（IM,influence maximization）[1-2]研究如何从社交网络中选择一组最具影响力的种子节点，基于这些节点发起信息传播，使最终的传播范围最大化。该问题广泛应用在产品营销[3]、疾病控制[4]和个性化推荐[5]等方面。例如，商家会从社交网络中选择最具影响力的部分用户，基于这些用户对产品进行推广和营销，使更多的用户了解并最终转化为潜在顾客。
影响力最大化问题需要基于特定传播模型来描述信息在网络中的传播过程。目前使用最为广泛的是独立级联（IC,independent cascade）模型[6]和线性阈值（LT,linear threshold）模型[7]。不同的传播模型适用于不同类型的社交网络。社交网络可以分为个体网络和群体网络[8]。个体网络主要考虑单个节点和单个节点之间的影响关系，适用于独立级联模型。群体网络主要考虑单个节点和多个节点之间、多个节点和多个节点之间的影响关系，适用于线性阈值模型。基于选定的传播模型，影响力最大化问题等价于选择影响力尽可能大的种子集。
为了得到合适的种子集，Kempe 等[1]首先基于IC模型和LT 模型提出了一个贪心算法。该算法可以同时在这2 个模型上提供近似保证（ε为误差参数），但是时间复杂度过高，难以适用于大规模社交网络。后续的研究者陆续提出基于某种特定传播模型的高效算法[10-12]。这些算法虽然在大规模社交网络上的运行效率得到提升，但是仅局限于特定传播模型中，只能解决单一类型社交网络下的影响力最大化问题，当使用在不同类型社交网络上时效果较差[13]。为解决该问题，本文提出一种可以同时支持IC 模型和LT 模型的高效种子集求解算法，该算法包括3 个阶段。1)预处理阶段，基于节点度筛选策略，筛选出有效节点集；2)采样阶段，基于边界约束策略，确定采样次数并从有效节点集中采样；3)种子选择阶段，应用贪心策略选择种子节点，并基于影响力增量剪枝策略，剪枝种子选择时的部分无效排序。具体来说，本文的贡献如下。
1)提出边界约束策略，以快速确定估计最优采样次数。提出基于节点度筛选策略，以提升种子集质量。提出基于影响力增量剪枝策略，以提高算法运行效率。
2)结合这3 个策略，提出一种三阶段的影响力最大化（MTIM,mixed three-stage influence maximization）算法，该算法不但能够同时支持IC 模型和LT 模型，而且具备优越的近似保证和期望时间复杂度。
3)将MTIM 与IMM、TIM、PMC 等贪心算法，以及OneHop、DegreeDiscount 等启发式算法在4 个真实社交网络上对比实验。结果表明，MTIM 算法能够适用于大规模社交网络，提供近似保证，并有效提升影响范围和效率。
1 背景知识和相关工作
1.1 背景知识
本文使用加权有向图G=(V,E,W)表示社交网络，其中，V表示节点集（用户），E表示有向边集（用户间关系），W表示每条有向边对应权值的集合。W(u,v)∈[0,1]表示有向边(u,v)的权值，代表传播过程中节点u把信息传递给节点v的概率，即u激活v的概率。为表述方便，使用n和m分别表示节点集V和有向边集E的大小，In(v)和Out(v)分别表示节点v的入邻居集合和出邻居集合。
影响力最大化问题旨在通过种子集（信息传播的源头节点）进行信息传播，实现传播范围的最大化。而信息如何在网络中传播是由传播模型确定的。在信息传播过程中，如果节点v接受某种信息，则称该节点为激活节点，否则称其为未激活节点。目前主流的2 种影响力传播模型的主要区别在于节点的激活方式。
1)IC 模型。假设节点u在i时刻被激活，则节点u在i+1 时刻只有一次机会以传播概率W(u,v)激活其尚未被激活的出邻居v∈Out(u)。
2)LT 模型。每个节点有概率阈值φ∈[0,1]，该阈值表示节点被激活的难易程度。如果节点v在i时刻未被激活，且满足，则节点v在i+1 时刻被激活，其中A是节点v在前i时刻被激活的入邻居集合。
给定社交网络G、种子集S⊆V以及传播模型M，传播过程如下。1)在第0 时刻，S中的所有节点被激活，其他节点未被激活。2)如果一个节点在i时刻被激活，则该节点在i+1 时刻只有一次机会激活其尚未被激活的出邻居（激活方式取决于传播模型M），之后它就不能再激活任何节点。3)重复步骤2)，直至不再有节点被激活，传播结束。种子集S在传播模型M下激活节点的总数表示为σ(S)，代表种子集S的预期影响范围。表1 给出了本文的常用符号。
表1 常用符号设置
问题定义（影响力最大化问题）给定社交网络G、参数k以及传播模型M，影响力最大化问题旨在找出种子集S⊆V且=k，使种子集预期影响范围σ(S)最大化。
1.2 相关工作
现有影响力最大化算法大多基于反向影响采样（RIS,reverse influence sampling）技术[9]选取种子节点。反向影响采样就是先随机选一个节点，从该节点出发，沿着该节点所有入边的相反方向模拟传播，这样反向可达的节点集合就称为反向可达集（RR set,reverse reachable set）；再生成足够多的反向可达集，从中找出影响力最大的种子集（即能够覆盖最多反向可达集的节点集合）。这里，如果节点v在集合R中出现，则称节点v覆盖集合R；如果集合S中至少有一个节点在集合R中出现，则称集合S覆盖集合R。根据文献[9]可知，对于从节点v反向采样得到的反向可达集R，节点u∈V{v}覆盖集合R的概率等于节点u激活节点v的概率。利用RIS 技术，可以使反向可达集更容易包含极具影响力的节点，从而提高算法效率。
例1（反向可达集构建示例）以IC 模型为例，反向可达集构造如下。首先在图1(a)所示的社交网络g中随机选择节点b，此时反向可达集R={b}。接着沿节点b的所有入边反向执行广度优先遍历，对入边(c,b)生成随机数r1=0.3。由于r1≤0.6，节点c被节点b激活，将节点c加入R中，即R={b,c}。同理，为节点c的入边(a,c)生成随机数r2=0.9。由于r2＞0.8，节点a没有被节点c激活，不将节点a加入R中，图1(b)中的虚线表示遍历失败，灰线表示遍历成功，黑线表示社交网络g中的有向边。此时不再有节点能被激活，最终反向可达集R={b,c}。
图1 反向可达集构建示例
Borgs 等[9]在种子集预期影响范围与反向可达集之间建立了以下联系。
引理1设S⊆V为种子集，R为传播模型M下生成的反向可达集，则
引理1 表明，可以使用反向可达集来估计任意种子集的预期影响范围。假设生成一个反向可达集集合 R={R1,R2,…}，令ΛR(S)表示种子集S覆盖的反向可达集数量，代表种子集S在集合R 中的覆盖范围，则是对种子集预期影响范围的无偏估计，即E[σ(S)]=。
Borgs 等的解决方案。利用引理1，Borgs 等[9]提出一种影响力最大化算法，该算法分为两步：1)采样，即生成足够多的反向可达集；2)种子选择，即贪心地选择对反向可达集覆盖率最大的种子集。Borgs 等证明，如果检验了条边，则该算法可以提供近似保证。
TIM 和IMM。Tang 等[14-15]基于RIS 技术提出了TIM 算法和IMM 算法，这些算法的时间复杂度均为，明显优于Borgs 等的算法，但是仍存在大量冗余的计算开销。TIM 算法利用切尔诺夫边界（Chernoff bound）来确定采样次数，而不再通过检验遍历的边数来判断是否满足近似保证，该算法适用于LT 模型。而IMM 算法利用鞅技术改进，进一步减少采样次数，能够同时适用IC模型和LT 模型，算法性能稳定高效。
其他基于特定传播模型的解决方案。Sun 等[10]基于多轮扩散（MRT,multi-round triggering）模型提出的MRIM 算法，解决了多轮扩散下的影响力最大化问题。Guo 等[11]基于触发（TR,triggering）模型提出的IMCB 算法，从社区结构角度解决了影响分布不平衡的问题。Guo 等[12]基于加权级联（WC,weighted cascade）模型提出SUBSIM 算法，对反向可达集生成过程进行了优化。
2 MTIM 算法
本文针对现有算法效率低、适用传播模型单一的问题，提出一种三阶段影响力最大化算法——MTIM 算法。MTIM 算法包括3 个阶段。
1)预处理阶段。基于节点度筛选策略，根据节点的出度和被链接程度，筛选出有效节点集C。
2)采样阶段。基于边界约束策略，先迭代地确定近似最优采样次数θ*，再从C 中随机选点采样θ*次，得到反向可达集集合 R={R1,R2,…,Rθ*}。
3)种子选择阶段。应用贪心策略找出对集合R 覆盖率最大的种子集；同时，基于影响力增量剪枝策略，剪枝部分种子选择时的无效排序。
MTIM 算法的具体流程如算法1 所示。
2.1 基于节点度筛选策略的预处理
RIS 方法每次从整个社交网络中随机选点采样，由于所选节点质量参差不齐，导致求解出的种子集对反向可达集的覆盖率偏低，使种子集影响范围有限。针对该问题，本文提出基于节点度筛选策略。该策略的基本思想为根据节点的出度和被链接程度（lv,linked value）[16]，筛选出潜在影响力较大的节点集合（即有效节点集）。利用该策略，不仅可以缩小采样时的选点范围，而且可以提高种子集对反向可达集的覆盖率，从而有效改善种子质量。
预处理阶段的主要工作如下。1)根据节点的出度和被链接程度，从社交网络G中筛选出节点集合A 和集合B，且；2)取这2 个集合的并集作为有效节点集C。算法2 为预处理阶段的伪代码。
对于有向图中的节点，其度包含出度和入度这2 个含义，因而从这2 个方面考虑。1)出度大的节点，影响其出邻居的潜在可能性较大，则其影响力往往较大。因而，可以根据节点的出度降序排序，获得出度前r% 大的节点集合A（算法2 的步骤2)～步骤5)）。2)由于传播在多个节点间进行，考虑单个节点的入度并无意义，可求单个节点被其入邻居链接的程度。被链接程度大的节点，其被入邻居影响的潜在可能性大，则影响力大的节点往往存在于被链接程度大的节点的反向可达集中。因而，可以先根据式(2)迭代地计算节点的被链接程度（d为平衡因子），再根据节点的被链接程度降序排序，获得被链接程度前r% 大的节点集合B（算法2 的步骤6)～步骤9)）。
此时，潜在影响力大的节点多在集合A 和集合B 中，因而，可以取两集合的并集作为有效节点集C 输出（算法2 的步骤10)～步骤11)）。
例2（预处理示例）对图1(a)社交网络g预处理流程如下。假设筛选比例为70%。首先，计算每个节点的出度，并根据出度降序排序，取出度前70%大的节点集 A={a,c,d,e}；然后，计算每个节点的被链接程度，并根据被链接程度降序排序，取被链接程度前70%大的节点集 B={b,c,d,e}；最后，取A 和B 的并集 C={a,b,c,d,e}作为有效节点集。
2.2 基于边界约束策略的采样
针对RIS 方法难以确定采样次数的问题，提出边界约束策略。该策略的基本思想如下，首先估计出近似最优采样次数的取值区间；然后根据该区间依次计算不同采样次数下影响范围近似解下界和最优解上界之比，不断计算直至该比值达到给定要求时停止。利用该策略，可以快速确定近似最优采样次数。
采样阶段的主要工作如下，首先估计出近似最优采样次数θ*；然后从预处理阶段获得的有效节点集C中随机选点采样θ*次，从而得到反向可达集集合R={R1,R2,…,Rθ*}。
2.2.1 最优采样次数的估计
为估计采样次数θ，需进一步分析。假设是期望影响力最大的k大种子集，即OPT=，根据引理1，如果θ大小适当，则≈OPT。给定ε∈[0,1]，根据文献[15]可推导出近似最优采样次数θ*，如式(3)所示。
根据式(3)，如果OPT 已知，则可以计算出近似最优采样次数。但是OPT 实际未知，因而考虑根据OPT 的取值范围估计出θ*的取值区间。
已知OPT∈[1,n]，由于中包含k个节点，至少能够影响到这k个节点，则可知OPT∈[k,n]。为估计出θ*的取值区间，给出引理2[15]与定理1。
引理2给定ε∈(0,1)，ℓ≥1，令θO表示理论最优采样次数，θ*表示根据式(3)计算出的近似最优采样次数，则满足
定理1给定x∈[k,n]，令θmax=2λ*ε−2k−1，θmin=λ*n−1，根据引理2，可知
证明构造函数θ(x)=λ*ε−2x−1，可知该函数随着x的增大而单调递减。已知x∈[k,n]，则函数值域为[θ(n),θ(k)]。根据引理2，θmin≤θ(n)≤θ(x)；同时根据式(3)计算的近似最优值恰在θ(x)的值域内，则必然满足
证毕。
根据定理1，可以估计出近似最优采样次数的取值区间为[θmin,θmax]。
2.2.2 影响范围边界的估计
为了从取值区间[θmin,θmax]中找出近似最优采样次数θ*，可以根据该区间依次计算出不同采样次数θ下影响范围的近似比，即当前解下界和最优解上界之比，如果该比值大于或等于，则立刻停止并返回当前采样次数θ，否则将当前采样次数θ乘以2 并重复上述步骤。为估计影响范围的边界，给出引理3[17]。
引理3给定种子集S和由θ个反向可达集构成的集合 R={R1,R2,…,Rθ}，则对于∀λ＞0，满足
根据引理3，当前种子集S影响范围的近似比可以用表示。
2.2.3 算法描述
根据2.2.1 节估计出的近似最优采样次数θ*的取值区间[θmin,θmax]，以及2.2.2 节判断是否为近似最优采样次数的边界约束条件，将其组合，即可构成基于边界约束策略的采样阶段。
算法3 为采样阶段的伪代码。具体地，首先，根据式(5)初始化θmin和θmax（算法3 的步骤1)）；接着，至多执行imax次for 循环（算法3 的步骤3)～步骤13)），在第i次时，先从有效节点集C 中随机选择节点采样，生成θi个反向可达集，再根据式(7)和式(8)计算出当前采样次数下种子集Si影响范围下界与上界之比，如果该比值大于或等于或者当前执行第imax次循环，则停止并返回当前种子集，否则将θmin乘以2 并重复计算。组合后算法的近似比为，原因在于：1)如果循环次数少于imax时就停止，则必能够提供近似保证；2)如果循环次数为imax时才停止，此时的采样次数必大于或等于θ*，则必能采样足够多的反向可达集，即必能提供近似保证。
算法4 为生成反向可达集集合的伪代码。具体流程如下。首先，将集合H 初始化为空集（算法4的步骤1)）；接着，执行θ次for 循环（算法4 的步骤2)～步骤6)），每次随机选择节点v∈C，沿该节点所有入边的相反方向进行广度优先遍历（即基于传播模型发起信息传播），将激活的节点依次插入反向可达集Ri，并将Ri插入H；最后，输出H（算法4 的步骤7)）。
例3（采样示例）IC 模型下采样阶段流程如下。假设采样次数θ=3，参数k=1。预处理阶段从图1(a)中筛选出有效节点集 C={a,b,c,d,e}（详见例2）。如图2 所示，从C 中随机选点b、c、e，生成反向可达集集合 R={R1,R2,R3}，其中R1={b,c}，R2={a,c}，R3={b,c,d,e}。图2 中的虚线表示遍历失败，灰线表示遍历成功，黑线表示社交网络g中的有向边。因为节点c对R 覆盖率最大，即节点c的影响力最大，所以将其加入种子集。最后，返回种子集{c}。
图2 采样示例
2.3 基于影响力增量剪枝策略的种子选择
由于RIS 方法每次找出对反向可达集集合R覆盖率最高的种子节点后，需要更新其他节点对R的覆盖率，并根据各节点对R 的覆盖率重新排序，导致存在节点对R 的覆盖率更新后相对排名不变时的无效排序，影响算法运行效率。针对该问题，本文提出基于影响力增量的剪枝策略。该策略的基本思想为保存前一轮排序后的数据，在删除该节点及其覆盖的反向可达集后，比较前一轮中原次大节点更新后和第三大节点更新前对R 的覆盖率，若前者大于等于后者，则直接选择原次大节点作为新一轮中的种子，而无须重新排序。利用该策略，可以剪枝部分种子选择时的无效排序，从而降低算法时耗。
种子选择阶段的主要工作如下。应用贪心策略找出对R 覆盖率最高的种子集S；同时，剪枝节点对R 的覆盖率更新后相对排名不变时的无效排序。
算法5 为种子选择阶段的伪代码。具体地，首先，初始化种子集为空集（算法5 的步骤1)），计算出每个节点v∈V对集合R 的覆盖率FR({v})，保存至pairs
例4（种子选择示例）令表示第i轮中节点v对集合R 的覆盖率。如图3 所示，第1 轮已计算出每个节点对R 的覆盖率，降序排序后选择当前对R 覆盖率最大的节点b作为种子，并更新其他节点影响力。进入第2 轮，先比较前一轮中原次大节点c更新后和原第三大节点a更新前对R 的覆盖率，发现，则节点c必为新一轮的最优种子，直接选择节点c而无须重新排序。
图3 种子选择示例
2.4 MTIM 算法时间复杂度分析
预处理阶段（算法2）主要用于筛选有效节点，其时间复杂度为O(n(ncnt+logn))，其中cnt 为迭代次数。采样阶段（算法3）主要用于生成反向可达集，其时间复杂度为。种子选择阶段（算法5），所花时间主要与反向可达集集合R和采样次数θ相关，其时间复杂度为。组合3 个阶段后得到的MTIM 算法（算法1），其时间复杂度为。
3 实验与分析
3.1 实验设置
实验的硬件配置Intel(R)Xeon(R)Silver 4208 CPU @ 2.10 GHz，运行内存64 GB，操作系统Ubuntu 20.04（64 位），所有算法均采用C++实现并使用G++4.8.5 编译。
实验采用4 个真实的社交网络数据集。其中，Slashdot 是提供技术资讯服务的社交网络；soc-LiveMocha 是提供外语学习服务的社交网络；Web-BerkStan 是BerkStan 的社交网络；soc-pokec是斯洛伐克的社交网络。
表2 给出了数据集的统计信息。其中，|V|表示图中的节点个数，|E|表示图中的边个数，Avg.deg表示图的平均度。
表2 数据集的统计信息
3.2 算法性能比较分析
算法评价标准包括：①运行时间，即求解出种子集的时间；②预期影响范围，即求解出的种子集能够影响到的节点个数。
实验使用IC 模型和LT 模型，基于4 个社交网络数据集分别在k∈{1,10,20,50,100}5 种规模下实验。根据之前的工作[10-15,17]，设置误差参数ε=0.5。根据表3，不同数据集单位时间筛选节点总数在r=70时最大，因而预处理阶段的筛选比例r%设置为70%。为避免误差，本文所涉及的算法都运行30 次，各算法评价指标取其均值。
表3 不同筛选比例r%下的筛选节点个数和筛选时间比较
为验证算法高效性，设置对比算法，具体如下。
1)TIM 算法[14]，为贪心算法。TIM 算法基于反向影响采样技术，利用切尔诺夫边界确定采样次数，支持LT 模型，可应用于大规模社交网络。本文将该算法用于LT 模型下对比实验。
2)IMM 算法[15]，为贪心算法。IMM 算法是TIM算法的改进算法，利用鞅技术确定采样次数，同时支持IC 模型和LT 模型。本文以IMM 算法为基准，并同时用于IC 模型和LT 模型下对比实验。
3)OneHop 算法[18]，为启发式算法。OneHop算法基于跳步思想选取种子，支持IC 模型，是目前精确度最高的启发式算法。本文将该算法用于IC模型下对比实验。
4)PMC 算法[19]，为贪心算法。PMC 算法基于蒙特卡罗模拟技术，支持IC 模型。该算法将原图随机切割为τ个子图，在子图中进行T 次传播模拟来估计节点影响力，选择前k大的节点作为种子。本文设置τ=200，T=10 000，并将该算法用于IC模型下对比实验。
5)DegreeDiscount 算法[20]，为经典启发式算法。DegreeDiscount 算法基于折扣度思想选取种子，支持LT 模型。本文将该算法用于LT 模型下对比实验。
6)MTIM 算法，为本文算法。
3.2.1 IC 模型下的结果
第一组实验。基于IC 模型比较了MTIM、IMM、OneHop、PMC 这4 种算法在不同数据集上的预期影响范围，结果如图4 所示。根据图4 可以发现，1)随着种子集规模k的增大，4 种算法的预期影响范围总体均呈上升趋势，并且种子集预期影响范围的增幅随种子个数的增加而递减。2)MTIM 的预期影响范围最广，IMM 和PMC 次之，而OneHop 表现最差。具体而言，MTIM 算法的预期影响范围较IMM 算法提高了约20%，IMM 算法的预期影响范围较PMC 算法提高了10%～20%，而OneHop 算法的预期影响范围为IMM 算法的50%左右。
图4 IC 模型下的预期影响范围比较
其原因主要是节点度筛选策略的应用。该策略通过约束采样范围，提高种子集S对反向可达集集合R 的覆盖率FR(S)，从而扩大影响范围。根据式(1)，，即种子集预期影响范围E[σ(S)]与覆盖率FR(S)正相关。图5 统计了k=100时IMM算法和MTIM 算法在各数据集上的覆盖率，可以发现MTIM 算法较IMM 算法覆盖率提高约20%。因而，MTIM 算法较IMM 算法预期影响范围提高约20%。而PMC 算法由于需要对网络中的所有节点进行多次传播模拟，取预期影响范围平均值来估计节点影响力，导致实际结果不够精确。OneHop 启发式算法基于跳步思想选择种子，并未考虑复杂网络结构，导致所选节点质量不高。因而，IMM 算法、PMC 算法和OneHop 算法的预期影响范围均不如MTIM 算法。
图5 覆盖率统计信息
第二组实验。基于IC 模型比较了MTIM、IMM、OneHop、PMC 这4 种算法在不同数据集上的运行时间，结果如图6 所示。根据图6 可以发现，1)随着种子集规模k的增大，MTIM 算法、IMM 算法和PMC 算法的运行时间及其差距倍增，而OneHop 算法运行时间趋于平稳。2)OneHop 的运行时间最短，MTIM 次之，PMC 和IMM 的运行时间较长。具体而言，当k＜20 时，MTIM 算法与OneHop 算法的性能差异不大；当k＞20 时，MTIM 算法略慢于OneHop 算法。MTIM 算法较IMM 算法快了4～9 倍，且数据集规模越大，提升效果越明显。PMC 算法较IMM 算法减少运行时间约50%。
图6 IC 模型下的运行时间比较
其原因主要有两点。1)边界约束策略的应用。该策略利用更高精度的边界约束来估计最优采样次数，降低确定采样次数时间，从而提升算法的运行效率。图7(a)统计了k=100时IMM 算法和MTIM 算法在各数据集上的确定采样次数时间，由于各数据集的运行时间相差较大，因此将时间设置为T=lgy，其中y表示实际运行时间，可以发现：MTIM 算法较IMM 算法减少确定采样次数时间40%～50%。图7(b)统计了k=100时IMM算法和MTIM算法生成的反向可达集个数（即采样次数），可以发现，MTIM 算法所确定的采样次数约为IMM 算法的70%。2)影响力增量剪枝策略的应用。该策略避免了部分种子选择时的无效排序。图7(c)统计了k=100时IMM 算法和MTIM 算法在各数据集上种子选择时的有效排序次数，可以发现：MTIM 算法较之IMM 算法剪枝了约15%的无效排序。因而，MTIM 算法较之IMM 算法快了4～9 倍。而PMC 算法将原社交网络随机分割为多个较小规模的子图网络，从子图中选择种子。因而，PMC 算法快于IMM 算法。OneHop 算法基于启发式规则粗略估计节点影响力，直接选择前k大的节点作为种子。因而，OneHop 算法的运行速度总体优于MTIM 算法、IMM 算法和PMC 算法。
图7 统计信息
3.2.2 LT 模型下的结果
第一组实验。基于LT 模型比较了MTIM、IMM、TIM、DegreeDiscount 这4 种算法在不同数据集上的预期影响范围，结果如图8 所示。根据图8 可以发现，1)随着种子集规模k的增大，4 种算法的预期影响范围总体呈上升趋势，且预期影响范围的增幅随种子个数的增加而递减。2)MTIM 的预期影响范围最广，IMM 和TIM 次之，而DegreeDiscount 表现最差。具体而言，MTIM 算法较IMM 算法扩大预期影响范围约30%，且数据集规模越大，提升效果越明显；IMM 算法和TIM 算法折线几乎重合，性能差异不大；而DegreeDiscount 算法的预期影响范围约为IMM 算法的50%。
图8 LT 模型下的预期影响范围比较
其原因与IC 模型类似，主要是节点度筛选策略的应用。利用该策略，可以提高种子集对反向可达集的覆盖率，从而扩大种子集预期影响范围。因而，MTIM 算法较IMM 算法扩大预期影响范围约30%。IMM 算法是TIM 算法的改进算法，在确保获得相同近似保证的同时，主要研究如何提升算法的运行速度。因而，IMM 算法和TIM 算法的预期影响范围极为接近。DegreeDiscount 算法是经典启发式算法，基于折扣度思想来选择种子节点，并未考虑网络结构的复杂性。因而，该算法的预期影响范围远不如MTIM算法、IMM 算法和TIM 算法。
第二组实验。基于LT 模型比较了MTIM、IMM、TIM、DegreeDiscount 这4 种算法在不同数据集下的运行时间，结果如图9 所示。根据图9 可以发现，1)随着种子集规模k的增大，DegreeDiscount、MTIM 和IMM 的运行时间递增，并且增幅逐渐减小；而TIM 在k＜10 时运行时间递减，在k≥10 时运行时间递增，并且增幅逐渐减小。2)MTIM 运行时间最短，DegreeDiscount 和IMM 次之，TIM 运行时间最长。具体而言，MTIM 算法略快于DegreeDiscount 算法，MTIM 算法较IMM 算法快了1.5～2.3 倍，而TIM 算法的运行时间为IMM 算法的2 倍多。
图9 LT 模型下的运行时间比较
其原因与IC 模型类似，是因为边界约束策略和影响力增量剪枝策略的应用。利用这2 个策略，不仅可以快速确定近似最优采样次数，提升算法效率，而且可以避免部分种子选择时的无效排序，降低算法时耗。因而，MTIM 算法优于TIM 算法和IMM 算法，略快于DegreeDiscount 启发式算法。但是，相比于IC模型，LT 模型下的优化效果并不显著，主要是因为节点信息的传播方式不同，IC 模型下反映的是单个用户与单个用户之间的影响关系，而LT 模型下反映的是多个用户与单个用户之间的影响关系。
综合2 个传播模型下的实验结果可知，1)相比于IMM、TIM 和PMC 等贪心算法，以及OneHop和DegreeDiscount 等启发式算法，MTIM 算法均获得最大预期影响范围，提供近似保证，且种子集规模越大，优势越明显。2)与IMM、TIM和PMC 等贪心算法相比，MTIM 算法运行时间最短。而与启发式算法相比，在IC 模型上，MTIM 算法略慢于OneHop 算法；在LT 模型上，MTIM 算法运行速度与DegreeDiscount 算法极为接近，总体略快于DegreeDiscount 算法。3)MTIM 算法不仅预期影响范围更优、精确度更高，而且运行速度优于大多贪心算法，略快于部分启发式算法。因而，MTIM 算法能够更好地适用于大规模社交网络。
4 结束语
针对现有影响力最大化算法效率低、适用模型单一的问题，本文基于2 个基础影响力传播模型，结合反向影响采样技术，提出了MTIM 算法，该算法包括3 个阶段。1)预处理阶段：基于节点度筛选策略，筛选出有效节点集。2)采样阶段：基于边界约束策略，确定近似最优采样次数并从有效节点集中选点采样。3)种子选择阶段：应用贪心策略选择种子节点，并基于影响力增量剪枝策略，剪枝种子选择时的无效排序。基于4 个真实社交网络的实验结果表明，MTIM 算法不仅可以提供近似保证，而且其预期影响范围远高于DegreeDiscount和OneHop 等启发式算法，优于IMM、TIM、PMC等贪心算法；在运行时间方面，MTIM 算法显著快于IMM、TIM、PMC 等贪心算法，总体上略慢于OneHop，略快于DegreeDiscount。因而，MTIM 算法在拥有较快运行速度的同时，保证了较大预期影响范围、较高近似保证，能够更好地适用于大规模社交网络。
后续工作中将会进行如下深入研究。1)影响力传播模型的扩展。进一步考虑特定的、复杂多变的应用场景下，如何解决影响力最大化问题。2)动态图下的研究。实际情况下，社交网络的结构以及用户间的关系往往会随着消息的传播而发生一定变化，未来可以尝试在动态图上进行研究。
