开放科学（资源服务）标志码（OSID）：

0 概述

随着社交网络的快速发展，用户数量和信息传播规模不断扩大，影响力最大化问题受到越来越多的关注，广泛应用于病毒营销^[1-2]、舆情预警、疾病控制等任务中。病毒营销是一种通过用户之间的口碑效应，最大限度扩大品牌知名度的方式，在有限的资源下选择合适的初始传播用户以最大化最终传播效果，成为解决影响力最大化问题的关键。RICHARDSON等^[1]将影响力最大化问题归纳为算法问题，即在某一信息传播模型下，从一个社交网络中选取k个初始种子节点集合，使最终影响传播范围最大化。KEMPE等^[3]基于独立级联（Independed Cascade，IC）^[4]模型和线性阈值（Linear Threshold，LT）^[5]模型，证明了影响力最大化问题是一个NP-hard问题，并提出一种贪心算法（Greedy Algorithm，GA）。该算法通过迭代的选择边际效应最大的节点加入种子集保证了在$ \left( {1 - \frac{1}{e} - \varepsilon } \right) $范围内接近最优解，但时间复杂度太高，不适用于大规模社交网络。很多研究人员针对贪心算法的低效率问题提出了一些优化算法。LESKOVEC等^[6]提出CELF（Cost-Effective Lazy Forwards）算法，利用节点间影响传播函数满足子模性的特征将贪心算法的运行速度提高了700倍。GOYAL等^[7]提出CELF++算法，进一步降低了CELF算法的时间复杂度。这些算法在一定程度上提升了运行速度，但每次选取节点加入种子集时均要计算节点的影响增加量，运行效率依然很低，难以扩展到大规模社交网络中。

目前，多数研究人员采用启发式算法提高运行效率。CHEN等^[8]在度中心性的基础上提出影响力^[9]最大化算法。CHEN等^[10]基于节点间最大影响传播路径提出PMIA算法。JUNG等^[11]针对IC模型提出IRIE启发式算法。WANG等^[12-14]提出基于网络拓扑结构的启发式影响力最大化算法。谢胜男等^[15]提出新的启发式算法提高运行效率。曹玖新等^[16]提出基于k-核的CCA算法。但是，这些启发式算法仅重点考虑了网络的拓扑结构特性而缺少一定的理论依据，导致算法得不到最优解。基于以上算法存在的问题，BROGS等^[17]提出一种将理论与实际效率相结合的反向影响抽样（Reverse Influence Sampling，RIS）算法，通过生成一定数量的反向可达（Reverse Reachable，RR）集来选择节点，进而多次计算节点影响力，使得到的时间复杂度接近线性，并具有一定的理论依据。虽然RIS算法有很多优点，但在选取反向可达集的数量上不够准确稳定，导致算法在实际应用中会产生大量的计算开销。本文提出一种基于反向可达集采样的影响力最大化算法D-RIS，无须提前预设反向可达集生成数量的理论阈值，根据影响力传播函数的单调性和子模性，自动调试生成一定数量的反向可达集。

1 基于反向可达集的社交网络影响力最大化算法

将社会网络抽象为一个具有节点集$ V $（用户）和有向边集$ E $（用户间的关系）的网络图$ G $，其中$ G=(V, P, E) $，$ \left|V\right|=n $，$ P\in \left(\mathrm{0, 1}\right) $，$ \left|E\right|=m $。假设$ G $中每条边$ e $都有传播概率$ P\left(E\right)\in \left(\mathrm{0, 1}\right) $，那么$ P(u, v)\in P(u, v\in V) $代表节点$ u $激活节点$ v $的概率。为了表述方便，表 1给出了本文常用的符号表示。

1.1 传播模型和问题描述

在社交网络中寻找一组特定的影响力最大的种子节点集时，需要运用一定的传播模型来模拟信息在网络上的传播规律。目前，经典的信息传播模型有IC模型和LT模型。

本文实验使用IC模型模拟用户影响力最大化传播。在该模型中给出一个具有$ n $个节点和$ m $条边的有向加权图$ G $来表示底层网络。边$ e=(v, u) $的权值表示节点$ v $沿着边$ e $传播到节点$ u $的概率$ P $。IC模型中节点被分为已激活、新激活和未激活3种状态。每个新激活节点有且仅有一次机会以概率$ P $对未激活的邻居节点尝试激活。$ P $值越高，激活的可能性越大。当$ G $中不存在有影响力的活跃节点时，传播过程结束。在IC模型上影响力传播模拟是通过从一组种子节点的随机传播开始的。设$ I\left(S\right) $为种子节点集$ S $中所有节点的最终影响传播范围，即种子节点集S传播模拟激活的节点个数。期望$ E\left[I\right(S\left)\right] $是选取的$ I\left(S\right) $最优值。该模型模拟传染病模型^[18-19]的传播过程，种子节点集$ S $类似于一组受感染的个体，激活其邻居节点的传播模拟过程类似于疾病从一个个体传播到另一个个体。

图 1是由4个节点组成的一个社交网络初始图，每条边上的权值代表出边节点到入边节点的传播概率$ {P}_{ij} $。设此社交网络中所有节点的激活概率为0.5，模拟社交网络的信息传播过程。$ S=\left\{a\right\} $为初始种子节点集，在$ {T}_{1} $时刻激活节点$ a $，在$ {T}_{2} $时刻节点$ a $具有0.2的概率激活节点$ c $以及0.8的概率激活节点$ d $，由于$ {P}_{ac}=0.5 > P=0.2 $，因此在$ {T}_{2} $时刻，节点$ d $被激活，$ S=\{a, d\} $。在$ {T}_{3} $时刻节点$ c $和节点$ b $都具有1的概率被节点$ d $激活。假设节点$ d $激活节点$ c $而不激活节点$ b $，影响传播过程结束。网络上没有新的节点可以被激活，该传播过程中激活的节点总数为3，即$ I\left(S\right)=3 $，$ S=\{a, d, c\} $。若在$ {T}_{3} $时刻节点$ b $被激活，则$ I\left(S\right)=4 $，$ S=\{a, b, c, d\} $。由于IC模型是一种概率模型^[20]，因此传播过程及最终传播结果都是不一定的。在实验过程中经常采用蒙特卡洛方法^[21]来多次运行取平均值，以确保结果具有较高的准确率。

在给定社交网络$ G $和常数$ k $的前提下，影响力最大化问题要求在$ G $中寻找一组种子节点集$ S $，使其在IC传播模型下传播影响范围最大，即找到种子节点集$ S\in V $且$ \left|S\right|=k $使得$ E\left[I\right(S\left)\right] $最大。

1.2 RIS算法

RIS算法引入反向可达集采样方法替代蒙特卡洛方法计算节点预期传播的影响力，主要思想是生成尽可能少的反向可达集样本，最终在$ \left( {1 - \frac{1}{e} - \varepsilon } \right) $的范围内获得一个近似最优解。RIS算法证明了对于任何$ \varepsilon > 0 $，都可以在$ O\left(\beta \right(m+n\left)k\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right) $的时间下运行，时间复杂度是近似线性时间的，其中$ \beta $为选取反向可达集中运行的步数。

RIS算法避免了贪心算法产生高时间复杂度的问题，同时解决了启发式算法缺少理论保障，得不到最优解的问题。但是，RIS算法不能有效控制随机RR集的数量。BORGS等^[17]提出一种基于阈值的方法生成随机RR集，当生成的节点和边的总数达到预定的理论阈值时停止生成随机RR集。尽管该方法具有近似线性的时间复杂度，但是与生成固定理论阈值的反向可达集之间具有很大的相关性，在实际应用中隐藏的常数较大，导致RIS算法存在以下问题：1）生成的实际RR集样本数量大于理论阈值；2）不能保证理论阈值是生成RR集样本数量的最小值。因此，RIS算法选取RR集的样本数量并不准确，不能较好地适用于大规模社交网络。

1.3 基于反向可达集的D-RIS算法

针对大多数经典影响力最大化算法存在时间复杂度高或得不到最优解的问题，本文基于IC模型提出D-RIS算法。D-RIS算法主要包括以下步骤：

1）生成反向可达集。随机且有放回地选择$ n $个节点，通过在随机图$ g $上进行传播模拟生成$ \theta $个节点RR集的集合R。

2）节点选择。使用最大覆盖方法寻找$ k $个覆盖最多RR集的节点并返回种子节点集$ S $。

对RIS算法理论进行分析可以得出：若随机RR集采样数量过少，则会因选取节点不足导致算法得不到最优解；若随机RR集采样数量过多，则虽然误差减小，但会造成时间复杂度太高。因此，根据种子节点集的准确率判定最终的影响力传播范围和时间效率。D-RIS算法的研究重点是选取尽可能少的RR集样本数量，使算法在影响力传播范围和运行效率之间取得较好平衡。借鉴文献[17]中采样方法定义统一的反向可达集采样框架，在此基础上提出新的临界值判断方法，能够动态选取尽可能少的RR集样本数量，并使用最大覆盖方法选取种子节点集。给定网络$ G=(V, E, P) $，D-RIS算法通过生成随机RR集的集合R来捕捉G中节点的影响传播过程，设$ {R}_{z} $为节点$ v $的RR集的子集，即节点的随机RR集，图$ g $是在$ G $中以$ 1-P\left(E\right) $的概率去掉边$ e $后得到的随机图。

定义1（反向可达集）   随机图$ g $中可以到达$ v $的节点集，对于RR集中的节点$ u $，$ g $中都有一条从$ u $到$ v $的有向路径。

采样过程为：1）随机选择一个节点$ v\in V $；2）在网络G上生成样本随机图$ g $；3）返回$ g $中节点v的反向可达集$ {R}_{z} $。将采样过程中的节点v称为$ {R}_{z} $中的源节点，则$ {R}_{z} $中的所有节点都存在一定的概率能够激活源节点v。因此，某一节点出现在更多的RR集中就意味着能够激活更多的节点，同时该节点具有较大的影响力传播范围。基于同样的推断，如果具有$ k $个节点的节点集S覆盖大量的RR集，则在网络$ G $中的这$ k $个节点具有很强的传播能力传播至最大范围，即$ I\left(S\right)=nP\left[S\mathrm{C}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}{R}_{z}\right] $。由于节点集S的影响与S和RR集相交的概率成正比，因此解决影响力最大化问题就是确定R集的下界。基于反向可达集采样框架，设置一种动态调试方法确定最小R集数量。

通过实例说明在IC模型下对图 1社交网络$ G $生成反向可达集的过程，设置$ k=1 $。图 2是在G上生成的3个随机图$ {g}_{1} $，$ {g}_{2} $，$ {g}_{3} $。对于3个随机选取的源节点$ c $，$ b $，$ d $生成的3个随机RR集$ {R}_{1}=\{c, a\} $、$ {R}_{2}=\{d, a\} $、$ {R}_{3}=\{b, c, a\} $，因为节点a出现在3个随机RR集中，所以节点$ a $是影响力最大的节点，最终返回结果为$ S=\left\{a\right\} $。

1.3.1 反向可达集数量确定

通过对RIS算法中随机RR集的数量选取分析可知，$ {R}_{z} $数量越多（R集越大），选取的种子节点集越准确，但会增加时间成本。因此，本文提出一种在不影响最终影响力传播范围的同时使得生成的R集数量尽可能少的方法。随着随机RR集数量的增多，影响力传播范围的上升并不是线性的，而是效用递减的。因此，RR集的数量与影响力传播范围函数的关系同时满足单调性和子模性（边际效用递减），具体定义如下：

1）单调性。设影响力传播范围函数$ f $，对于任意反向可达集的数量$ {q}_{1} < {q}_{2} $，都有$ f\left({q}_{1}\right)\le f\left({q}_{2}\right) $。

2）子模性。对于图的节点总数$ t $，设影响力传播范围函数$ f $，反向可达集数量$ {q}_{1} < {q}_{2} $以及所有$ a > 0 $，若$ {q}_{1} < {q}_{2} < t $，则有$ f({q}_{1}+a)\ge f({q}_{2}+a) $。

基于以上理论，对于给定的$ G $，算法设置一个随机RR集数量的临界值$ \theta $，其中$ \theta =n\times \alpha ，\alpha $为随机RR集选取比例。当随机RR集的数量小于$ \theta $时，会导致选取随机RR集的数量不足而不能取得最大影响力传播范围。当随机RR集的数量大于$ \theta $时，边际效益递减，影响力传播范围的上升幅度过于缓慢或不再上升，会导致时间成本增加。因此，基于网络中节点当前的传播情况，算法每轮自动加倍生成反向可达集，直至满足算法1中设置的临界值判断条件3次，认为算法生成的RR集数量无限逼近临界值。设本轮次影响力传播范围为$ {f}_{\mathrm{c}} $，上轮次影响力传播范围为$ {f}_{\mathrm{p}} $。算法1给出了D-RIS算法反向可达集生成过程的伪代码，主要过程如下：

1）设置初始的反向可达集生成比例为一个极小的值$ \alpha $，例如算法1将$ \alpha $值取0.001，此时$ \theta =0.001n $，从种子节点集$ S $中随机选取节点生成比例为$ \alpha $的随机RR集并计算影响力传播范围$ {f}_{\mathrm{c}} $（算法1中的第4~6行）。

2）每轮将$ \alpha $的值加倍并计算本轮影响力传播范围增加量$ {I}_{\mathrm{c}} $，即$ {I}_{\mathrm{c}}={f}_{\mathrm{c}}-{f}_{\mathrm{p}} $，下面对本轮影响力传播范围增加量进行判断（算法1中的第7行），若满足条件，则认定本轮$ \alpha $加倍对影响力增长不起作用，影响力可能已经接近临界值。判断条件为：若$ {I}_{C}\le 0 $或I_c＜math.log_a（I_p，2），则本轮影响力范围增加量小于等于0或小于上轮影响力范围增加量开根号的结果。

3）迭代上述步骤，直到连续3次的$ \alpha $加倍无效，或$ \alpha $的值大于等于1时停止继续生成反向可达集，此时算法生成的随机RR集数量逼近临界值。设最终的反向可达集生成比例为$ {\alpha }_{1} $，此时得到了相对稳定且有效的反向可达集的临界值$ \theta $，即$ \theta =n\times {\alpha }_{1} $。

算法1  反向可达集生成算法

输入  社会网络$ G=(V, P, E), k $

输出  种子节点集$ S $，临界值$ \alpha $

1.$ \mathrm{R}=\mathrm{\varnothing }, \mathrm{\alpha }=0.001, {\mathrm{I}}_{\mathrm{p}}=0, {\mathrm{f}}_{\mathrm{p}}=0 $

2.$ \mathrm{W}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{e}(\mathrm{\alpha } < 1\&\&\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g} < 3) $

3.生成$ \mathrm{\alpha } $值的种子节点集合

4.$ {\rm{z}} \leftarrow {\rm{Simulate}}\_{\rm{influence}}\_{\rm{propagation}}\left( {} \right) $

5.generate $ \mathrm{\theta } $ random RR Sets and add all $ {\mathrm{R}}_{\mathrm{z}} $ to $ \mathrm{R} $

6.$ {\mathrm{f}}_{\mathrm{c}}=\mathrm{C}\mathrm{n}\mathrm{t}\_{\mathrm{f}}_{\mathrm{c}}\left(\right), {\mathrm{I}}_{\mathrm{c}}={\mathrm{f}}_{\mathrm{c}} $-$ {\mathrm{f}}_{\mathrm{p}} $

7.if $ {\mathrm{I}}_{\mathrm{c}}\le 0 $ or（$ {\mathrm{I}}_{\mathrm{p}} > 0 $and I_c＜math.log_a（I_p，2））

8.$ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}=\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}+1 $

9.else $ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}=0, {\mathrm{f}}_{\mathrm{p}}={\mathrm{f}}_{\mathrm{c}} $

10.if $ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}=2 $

11.break

12.$ \mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}=\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\times 2 $

13.return $ \mathrm{S}, \mathrm{\alpha } $

在动态调试确定α值的过程中，α值是跳跃式逐渐上升，直至接近临界值。除了第一轮以外，每轮迭代并不是生成α个反向可达集，而是生成$ \frac{\alpha }{2} $个反向可达集，存储上一轮$ \frac{\alpha }{2} $个反向可达集，从而组合成本轮的α个反向可达集，即在原有反向可达集的基础上生成同样数量的反向可达集，达到加倍的作用。因此，本文算法极大地提升了算法的时间效率。

基于影响力传播函数满足单调性和子模性的特点，根据网络中节点实时传播情况，提出一种确定随机RR集临界值$ \theta $的方法，并遵循反向可达集采样框架，生成$ \theta $个反向可达集。

1.3.2 种子节点选择

D-RIS算法使用最大覆盖方法进行种子节点选择。给定$ G $、$ k $和反向可达集的数量$ \theta $。将算法1中生成的$ \theta $个随机RR集插入到集合R中。若$ S\bigcap {R}_{j}\ne \mathrm{\varnothing } $，则种子集S覆盖一个随机RR集$ {R}_{j} $，即$ {\rm{Cove}}{{\rm{r}}_R}\left( S \right) = \sum\limits_{{R_j} \in R} {\rm{m}} {\rm{in}}\left\{ {\left| {S\bigcap {{R_j}} } \right|, 1} \right\} $，将$ I\left(S\right) $的近似值定义为$ I\left(S\right)={I}_{R}\left(S\right)=\frac{\mathrm{C}\mathrm{o}\mathrm{v}\mathrm{e}{\mathrm{r}}_{R}\left(S\right)}{\left|R\right|} $。算法2给出了D-RIS算法的节点选择过程的伪代码，$ k $次迭代过程如下：

1）每次算法在R集中选择一个覆盖最多RR集数量的节点$ v $。

2）删除R集中节点$ v $所在的所有反向可达集，被删除的反向可达集中的节点都有一条通过节点$ v $能到达的路径。

3）将节点$ v $加入到$ S $集中，更新R集进行下一次迭代。

4）选出节点集$ S=k $，迭代结束。

由于在使用最大覆盖方法选择$ k $个节点集的过程中，利用贪心算法反复选择覆盖最大边际收益的节点加入种子节点集S中，因此可以返回$ \left(1-\frac{1}{e}-\epsilon \right) $的近似解，并且能得到近似线性的时间复杂度。

算法2  节点选择算法

输入  社会网络$ G=(V, P, E), k, \theta $

输出  种子节点集$ S $

1.S←Ø

2.for $ \mathrm{i}=1 $to $ \mathrm{k} $ do

3.$ \mathrm{v}=\mathrm{m}\mathrm{a}\mathrm{x}\_\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{g}\mathrm{e}\left(\right) $

4.add $ \mathrm{v} $ to $ \mathrm{S} $

5.for RR Sets contain $ \mathrm{v} $

6.remove all RR Sets from R

7.return $ \mathrm{S} $

由上文分析可知，D-RIS算法主要包括两个阶段。在第一阶段中，随机选取$ n $个节点生成$ \theta $个反向可达集，其中$ \theta =n\times \alpha (\alpha < 1) $，时间复杂度为$ O\left(\theta \right) $。对于任意随机选取的节点$ {v}_{j} $，如果基于一定传播模型进行传播模拟生成的反向可达集的时间复杂度为$ O\left({E}_{\mathrm{E}\mathrm{P}\mathrm{V}}\right) $，其中E_EPV是随机RR集的宽度（即随机图$ g $中指向节点$ {v}_{j} $的有向边数），则D-RIS算法的第一阶段的时间复杂度为O（θ×$ {E}_{\mathrm{E}\mathrm{P}\mathrm{V}} $）。在第二阶段中，使用最大覆盖方法选择$ k $个节点运用了贪心算法，可以得到线性的时间复杂度为O（θ×E_EPV）。贪心算法的时间复杂度$ O\left(kmnr\right) $，其中，$ r $代表使用蒙特卡洛采样次数，$ n $和$ m $分别代表网络$ G $中全部的节点个数和边数，在通常情况下$ n $、$ m $、$ r $的数值都很大。D-RIS算法相比贪心算法时间复杂度更低，相比同样能达到线性时间复杂度的RIS算法，在反向可达集数量的选取上更加准确合理。根据上述时间复杂度的分析结果可以得出，D-RIS算法更适用于大规模社交网络。

2 实验与结果分析 2.1 实验数据集

为更好地验证D-RIS算法的合理性和时效性，采用两个真实数据集进行实验，如表 2所示。Slashdot数据集是分享科技资讯网站的朋友数据集，此网站允许用户将彼此标记为朋友或敌人，其中76.7%是朋友关系。为方便不同算法之间的比较，对Slashdot数据集进行处理，在朋友关系中随机选取10 000个节点，预处理后的这些节点间存在36 338条边，代表 10 000个用户之间存在的社交关系。Epinions数据集是一种基于信任的在线社交网络数据集。若节点$ v $到节点$ u $存在一条有向边，则节点$ v $信任节点$ u $，即节点$ u $可以影响节点$ v $，对Epinions数据集进行了相同的预处理后，保留了信任关系中的10 000个节点和67 059条边。Slashdot和Epinions数据集^[22]均可在斯坦福大学大型网络数据集网站上下载得到。

2.2 结果分析

实验中使用的信息传播模型为IC模型，传播概率为0.08，运行10 000次蒙特卡洛^[18]模拟信息传播过程，并取平均值作为最终的影响力传播范围。为验证D-RIS算法的合理性和时效性，选取的对比算法为当前具有代表性的5种算法，具体如下：

1）CELF算法。该算法是贪心算法的改进算法，核心思想与贪婪算法基本一致且效率提升明显。

2）HighDegree算法。该算法是基于节点中心性的经典启发式算法，选择k个度最大的节点作为种子节点集。

3）LIR^[13]算法。该算法是基于拓扑结构的启发式算法，选取并排序局部度最大的节点进而选取种子节点集。

4）pBmH^[14]算法。该算法是基于拓扑结构的启发式算法，考虑了节点受多重邻居节点的影响，避免了富人俱乐部现象。

5）RIS^[17]算法。该算法是反向影响抽样算法，通过生成一定理论阈值数量的反向可达集进而选取种子节点集。

设置以下3种仿真实验：

1）D-RIS算法传播规律合理性验证。使用Slashdot数据集对RIS算法中影响力传播函数满足单调性和子模性进行分析与验证。

2）D-RIS算法与RIS算法的性能比较。在Slashdot和Epinions数据集上，设置不同的反向可达集生成比例的RIS算法的反向可达集数量，与D-RIS算法分别进行影响力传播范围和运行时间比较。

3）D-RIS算法与经典算法的性能比较。对D-RIS算法与CELF算法、HighDegree算法、LIR算法和pBmH算法在两个真实数据集上进行影响力传播范围和运行时间比较，以验证D-RIS算法的时效性更优。

2.2.1 D-RIS算法传播规律合理性验证

设置$ k=5 $，RIS算法从$ \alpha =0.001 $开始迭代，每轮加倍反向可达集生成比例直到连续3次加倍无效或$ \alpha \ge 1 $时停止。

由图 3可知，随着反向可达集生成比例的增加，曲线呈上升趋势，即影响力传播范围不断增大，表明算法影响力传播范围函数具有单调性。RIS算法的反向可达集生成比例大于0.01后，随着反向可达集生成比例的上升，影响力传播范围曲线趋于平缓，这是由于影响力传播范围函数满足子模性导致边际效益递减，从而呈现影响力传播范围曲线扩大趋势逐渐减缓。当反向可达集生成比例为0.03时，曲线有稍微下降的趋势，符合实际情况。理论上，算法的影响力传播范围具有单调性，但由于采用的传播模型为概率模型，因此在实验中具有一定的波动性。

由图 3中RIS算法的曲线趋势可以看出，影响力传播函数由于满足单调性和子模性，因此出现递增后逐渐减缓的情况。同时，对D-RIS算法进行验证，结果表明随着反向可达集数量的增加曲线上升趋势先增大后趋于平缓。RIS算法需要提前预设反向可达集生成比例，若选取不合理则导致算法达不到最优影响传播范围或增加时间成本。D-RIS算法只需给定一个较小的反向可达集生成比例，就可自动加倍调试反向可达集生成比例直到满足条件时停止。因此，该实验证明了D-RIS算法传播规律的合理性和实用性。

2.2.2 D-RIS算法与RIS算法的性能比较

将RIS算法反向可达集生成比例分别设置为0.001、0.2、0.5，在两个数据集上与D-RIS算法进行影响力传播范围和运行时间的比较。

1）设置RIS算法反向可达集生成比例为0.001。由图 4、图 5可知，当RIS算法的反向可达集生成比例为0.001时，相较D-RIS算法，RIS算法运行速度更快，但影响力传播范围过小。特别地，当种子节点数量$ k $较低时，两者的影响力传播范围存在成倍的差距。这是由于RIS算法中的反向可达集生成比例过小导致选取种子节点数量不够精准，影响算法的最终传播范围。

2）设置RIS算法反向可达集生成比例为0.2。如图 6、图 7可知，当RIS算法的反向可达集生成比例为0.2时，在Slashdot数据集中，两种算法的影响力传播范围接近，但D-RIS算法的运行效率高于RIS算法。在Epinions数据集中，D-RIS算法在获得较大影响力传播范围的情况下，大幅降低了运行时间，且选取的种子节点集个数越多，在运行效率方面优势越明显。

3）设置RIS算法反向可达集生成比例为0.5。由图 8、图 9可知，当RIS算法的反向可达集生成比例设置为0.5时，在两个数据集上，D-RIS算法有较大的影响力传播范围，且运行效率远高于RIS算法。由此可以看出，过大的反向可达集生成比例会增加算法最终的时间成本。对于Slashdot数据集，RIS算法的运行时间是D-RIS算法的2倍多。对于Epinions数据集，RIS算法的运行时间是D-RIS算法的7倍多，因此D-RIS算法具有更高的运行效率。

在两个真实数据集上的实验结果表明：1）当RIS算法的反向可达集生成比例的理论阈值设置太小时影响力传播范围较小，当理论阈值设置太大时运行效率太差，D-RIS算法在达到较优的影响力传播范围的同时运行效率更高；2）与RIS算法相比，D-RIS算法避免了反向可达集生成比例的理论阈值设置不准确，导致达不到最优影响力传播范围或增加时间成本的问题。对于目前复杂的社交网络，D-RIS算法无需重复计算，可自动调试生成一定比例的反向可达集，因此更适用于后续拓扑结构变化的社交网络。

2.2.3 D-RIS算法与经典算法的性能比较

在两个不同数据集上，将D-RIS算法与CELF、LIR、pBmH和HighDegree算法进行影响力传播范围和运行时间的比较，如图 10、图 11所示。

由于5种算法的运行时间相差较大，因此运行时间设置为T=$ {2}^{y} $，其中y表示纵坐标数值。根据图 10、图 11实验结果分析可知：

1）D-RIS算法的影响力传播范围基本接近于在$ \left(1-\frac{1}{e}-\varepsilon \right) $范围内取得最优解的CELF算法，但运行速度更快，且种子节点集越大优势越明显，相差接近上百倍。CELF算法的时间复杂度较高，是由于多次使用蒙特卡洛方法模拟计算导致，因此D-RIS算法能更好地适用于大规模社交网络。

2）相比LIR、pBmH和HighDegree启发式算法，D-RIS算法虽在运行速度方面表现较差，但影响力传播范围明显更优。在Epinions数据集中，启发式算法的影响力传播范围仅有D-RIS算法的50%左右。在Slashdot数据集中，D-RIS算法的影响力传播范围优势更为明显。可见，启发式算法虽有极高的运行效率，但未考虑到复杂网络后续结构变化导致选取的种子节点不够准确，影响力传播范围较小且得不到最优解，同时在不同数据集中启发式算法的稳定性不佳。

通过以上算法的对比实验分析可知：D-RIS算法在影响力传播范围和运行时间两方面取得了较好的平衡，且表现出较好的通用性和稳定性，更适用于拓扑结构变化和规模较大的社交网络。

3 结束语

本文基于独立级联模型，结合反向可达集采样提出一种改进的影响力最大化算法D-RIS，根据影响力传播函数的单调性和子模性，设置随机生成反向可达集数量临界值的判断条件，自动调试生成一定数量的反向可达集。实验结果表明，D-RIS算法可在获得较大影响力传播范围的同时避免增加时间成本，并且能较好地应用于拓扑结构变化和规模较大的社交网络。下一步可将D-RIS算法扩展到多关系社交网络的影响力传播模型中，解决社交网络中多条信息同时传播情况下的影响力最大化问题。