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

0 概述

随着微信、Facebook和Twitter等在线社交网络的兴起，越来越多的人们使用不同的社交网络进行交流和分享，使得网络中信息扩散研究成为社交网络分析的热点。影响最大化（Influence Maximization，IM）作为信息扩散研究中的关键问题，具有较广泛的应用场景。文献[1-3]分别把IM问题应用于病毒式营销、谣言控制和社会计算领域，将社交网络建模为一个图G，并给图G的每条边分配一个传播概率。IM问题是给定一个传播模型及正整数k，从节点集V中选择一个不多于k个节点的种子集合S，使得S的影响范围$ \sigma \left(S\right) $达到最大。

文献[4]证明IM问题也是NP-hard问题，表明IM问题在多项式时间内不可能得到最优解的精确算法，其求解方法主要是近似算法和启发式算法。文献[5-6]针对IM问题，提出基于次模函数的贪心近似算法，具有较大的时间复杂度，因此，该算法在规模较大的图上难以得到实际有效的应用。以上贪心近似算法均具有较大的时间复杂度，其原因为在节点选择过程中，每个种子节点的选择均使用大量的Monte-Carlo模拟来计算节点集的影响范围。为了更快地求解IM问题，启发式算法利用不同的策略来代替模拟过程。此类算法分为基于中心性的算法、基于社区的算法和基于排序的算法。启发式算法与近似算法相比具有较低的时间复杂度，但是在具有不同拓扑结构的图上，启发式算法和近似算法都缺乏稳定性。文献[7]提出基于VoteRank的投票算法，在求解IM问题时具有较强的稳定性。在该类算法中，节点v具有投票能力va_v和得票分数vs_v两种属性，其中va_v表示节点v能够给邻居节点投票的票数，vs_v表示节点v的邻居给其投票的票数总和。此外，在每轮投票中得票分数最高的节点将不参与后续的投票，即投票能力为0，其邻居节点的投票能力也会随之得到一定程度的弱化。投票算法通常定义一个衰减因子f来表示投票能力的弱化程度。然而该算法并未有效地区分节点对其不同邻居的投票能力，种子节点所有的邻居均使用相同的衰减因子，不能有效地表示出它们投票能力的弱化程度。

本文基于K-truss提出一种改进的投票算法TrussVote，用于求解IM问题。基于边的truss值设计节点有效投票能力的计算方法，该方法不仅考虑网络拓扑结构对投票能力的影响，同时也有效地区分节点对其不同邻居的投票能力。基于节点的相似性提出动态的衰减因子，表示节点邻居的投票能力具有不同程度的弱化。此外，本文结合IC模型下的原始传播结果提出影响范围的等价分析指标——传播差异（Diffusion Difference，DD），以直观地区分各个算法的实验效果。

1 相关工作

为了表述方便，表 1所示为本文所需主要变量的说明。

网络中节点的中心性是衡量节点重要性的关键指标，中心性较高的节点在网络中通常占据着信息传播的关键位置。节点的中心性分为局部中心性和全局中心性。文献[8-10]和文献[11-12]分别基于局部中心性和全局中心性提出不同的启发式算法，以求解IM问题。此类算法的主要原理是在计算每个节点的中心性之后，选择中心性最高的前k个节点作为种子节点集。相比基于局部中心性的启发式算法，基于全局中心性的启发式算法在获得较优实验效果的同时提高了算法的时间复杂度。

影响力的扩散与社区结构有着密切关联，并且在社区内节点之间联系紧密，更容易传播影响力。文献[13-14]基于图的社区提出用于求解IM问题的方法，其原理是将网络中的节点划分为不同的社区，并在每个社区中选取影响力较大的节点作为种子节点。文献[15-16]提出基于排序的算法，采用不同方式定义节点的影响力，通过迭代方式使节点按照影响力的排序达到一个稳定状态。该类算法与基于中心性的算法相比能够获得更广泛的影响力覆盖范围，但迭代次数的增加也提升了算法的时间复杂度。

文献[7]提出一种新的解决方案用来求解IM问题，它最早基于投票机制提出VoteRank算法。在初始化阶段，每个节点的投票能力均被设置为1，在投票过程中，每轮选出一个得票分数最高的节点作为种子节点，在此基础上，使用固定的衰减因子弱化该种子节点一跳邻居的投票能力。当权重表示节点间联系紧密性的加权网络时，文献[17]基于VoteRank提出WVoteRank算法，在计算节点的得票分数时，权重的差异使得节点对其不同邻居的投票能力产生差异。文献[18]设计的NCVoteRank算法认为节点的投票能力取决于其在网络中的拓扑结构，并提出邻居核心值（Neighborhood Coreness，NC）的概念，当计算节点的得票分数时，综合考虑了邻居节点的NC值及投票能力。文献[19]提出EnRenew算法，采用信息熵的方式来表示节点的重要性及投票能力。文献[20]不仅引入投票比例的概念以区分节点对其不同邻居的投票能力，而且在更新种子节点邻居的投票能力时，采用不同程度的衰减因子分别弱化其一跳和二跳邻居的投票能力。

2 本文算法

本文基于第1节中的投票机制提出TrussVote算法，该算法在投票阶段使用K-truss的相关理论及算法区分节点对其不同邻居的投票能力，在更新阶段通过节点相似性指标定义一个动态的衰减因子，用于表示种子节点邻居的投票能力具有不同程度的衰减。

2.1 K-truss分解

K-core^[21]揭示了网络的结构性质和层次性质，而K-truss则是K-core基于三角形的一种扩展，它所推导的子图在结构上更接近一个团^[22]。

定义1（边的支持度sup（e，G））   边的支持度等于图G =（V，E）中边e∈E所在三角形的个数。

定义2（K-truss子图T_K）   若$ {T}_{K}=\left({V}_{{T}_{K}}, {E}_{{T}_{K}}\right) $满足K ≥ 2，$ \forall e\in {E}_{{T}_{K}} $且sup（e，G）≥ K-2，则称T_K为G的K-truss子图。

定义3（边e=（v，u）的truss值t_vu）   t_vu= max{K：$ e\in {E}_{{T}_{K}} $，T_K为图G的K-truss子图}。

定义4（边集K-class，记为$ {{\mathit{\Phi}} }_{K} $）   图G =（V，E）的$ {{\mathit{\Phi}} }_{K}=\{e=(v, u\left)\right|e\in E, {t}_{vu}=K\} $。

本文的投票算法通过引入K-truss相关理论，不仅考虑网络的拓扑结构对投票能力产生的影响，同时有效地区分节点对其不同邻居拥有不同的投票倾向。对于边e=（v，u），t_vu的计算与v和u的公共邻居相关，因此边的truss值在一定程度上反映了节点间联系的紧密程度。对于同一节点的不同邻居，邻边的truss值越大，其两端节点的联系越紧密。无向图示例如图 1所示。

在节点3的邻边中，边（3，4）具有最大的truss值，它们的联系也更加紧密。基于网络的核分解理论^[23]，K-truss分解与K-core分解相似，K值越大的子图在网络中的相对位置越趋于核心。对于网络中不同位置的节点，truss值可以对节点的投票能力进行有针对性和不同程度的放大。从图 1可以看出，$ {{\mathit{\Phi}} }_{3} $和$ {{\mathit{\Phi}} }_{1} $中的边对它们两端节点投票能力的放大程度不同，在同一轮投票中趋于中心位置的节点将会获得更高的得票分数。

2.2 有效投票能力

节点间相似性差异会导致节点对其邻居的投票能力不同。为了更准确地表示这种差异，本文基于边的truss值提出有效投票能力$ {e}_{v}^{\mathrm{e}\mathrm{v}\mathrm{a}}\left(u\right) $，用于计算节点v对其邻居节点u$ \in $N_v的投票能力。当不考虑节点间的相似性时，节点v给其每个邻居投票的概率均为1/d_v；当考虑节点间的相似性时，本文基于边的truss值定义了节点v对其邻居节点u$ \in $N_v的有效投票能力，其计算过程如式（1）所示：

$ {e}_{v}^{\mathrm{e}\mathrm{v}\mathrm{a}}\left(u\right)=\frac{{v}_{v}^{\mathrm{v}\mathrm{a}}\cdot {t}_{vu}}{{d}_{v}} $

(1)

2.3 得票分数

本文在计算节点的得票分数时，利用有效投票能力来表示节点对其邻居拥有不同的投票票数，而这种有效的投票能力也会受到边的传播概率的影响。在实际传播过程中，节点v通过边（v，u）将u激活，其激活概率大于该边的传播概率。因此，基于传播模型的随机性特点，本文将投票算法中能够得到的有效投票能力乘以传播概率，用来表示u能够获得v投票的票数期望值。对于节点v，$ {e}_{v}^{\mathrm{e}\mathrm{v}\mathrm{a}}\left(u\right) $∙p_uv表示能够得到其邻居节点u$ \in $N_v的实际票数，其中p_uv为边（u，v）的传播概率。与其他投票算法相似，本文节点v的得票分数来源于邻居节点的投票，其计算过程如式（2）所示：

$ {v}_{v}^{\mathrm{v}\mathrm{s}}=\sum \limits_{u\in {N}_{v}}{e}_{v}^{\mathrm{e}\mathrm{v}\mathrm{a}}\left(u\right)\cdot {p}_{uv} $

(2)

2.4 衰减因子

本文基于ra指标^[24]提出一种动态的衰减因子，以区分种子节点不同邻居的衰减情况。ra指标是一种基于资源分配策略的节点相似性指标，ra（v，u）表示节点v、u之间的相似度，也表示v接收到u资源的能力。其计算过程如式（3）所示：

$ {r}_{\mathrm{r}\mathrm{a}}(v, u)=\sum\limits _{w\in {N}_{v}\bigcap {N}_{u}}\frac{1}{{d}_{w}} $

(3)

当节点v被选为种子节点后，其邻居节点u$ \in $N_v需去除来自v的资源，本文将减去的这部分视为节点u投票能力的衰减程度f_u，其计算过程如式（4）所示：

$ {f}_{u}=1-{r}_{\mathrm{r}\mathrm{a}}(v, u) $

(4)

当节点v被选为种子节点后，其邻居节点u$ \in $N_v的投票能力可根据式（5）计算：

$ {v}_{v}^{\mathrm{v}\mathrm{a}}={f}_{u}\cdot {v}_{v}^{\mathrm{v}\mathrm{a}} $

(5)

2.5 复杂度分析

TrussVote的算法过程：首先，在初始化阶段，计算所有边的truss值，并且给每个节点都赋予相同的初始投票能力；然后，重复k轮投票，每次均将投票分数最高的节点选为种子节点，并使用动态的衰减因子更新其邻居节点的投票能力。TrussVote如算法1所示。

算法1    TrussVote算法

输入   图G（V，E），初始集合大小k

输出    初始传播集合S

1. $ \mathrm{S}\leftarrow \mathrm{\varnothing } $

2. 计算边的truss值

3. for $ \mathrm{v}\in \mathrm{V} $ do

4.    va_v$ \leftarrow $1

5. end for

6. for $ \mathrm{v}\in \mathrm{V} $ do

7.    vs_v$ \leftarrow $0

8.   for $ \mathrm{u}\in {\mathrm{N}}_{\mathrm{v}} $ do

9.     vs_v$ \leftarrow $vs_v + eva_v（u）·p_uv

10. end for

11. end for

12. 将得票分数最高的节点v加入到S

13. while |S| < k do

14.   移除节点v的得票分数

15.   $ \mathrm{H}\leftarrow \mathrm{H}\bigcup {\mathrm{N}}_{\mathrm{v}} $

16.   for $ \mathrm{u}\in {\mathrm{N}}_{\mathrm{v}} $ do

17.      va_u$ \leftarrow $va_u·f_u

18.      $ \mathrm{H}\leftarrow \mathrm{H}\bigcup {\mathrm{N}}_{\mathrm{u}} $

19.   end for

20.   va_v$ \leftarrow $0

21.   for $ \mathrm{u}\in \mathrm{H} $ do

22.     vs_u$ \leftarrow $0

23.      for $ \mathrm{w}\in {\mathrm{N}}_{\mathrm{u}} $ do

24.         vs_u$ \leftarrow $vs_u + eva_w（u）·p_wu

25.     end for

26.   end for

27.   将得票分数最高的节点v加入到S

28. end while

29. return S

在算法1中，步骤2是边truss值的计算阶段，计算每个节点邻边truss值的时间复杂度为O（$ {\stackrel{-}{d}}^{2} $），因此本阶段的时间复杂度为O（n$ {\stackrel{-}{d}}^{2} $）。步骤3~步骤11是投票能力与得票分数的初始化阶段，投票能力初始化的时间复杂度为O（n），得票分数初始化的时间复杂度为O（n$ {\stackrel{-}{d}}^{2} $），因此，该阶段的时间复杂度为O（n$ {\stackrel{-}{d}}^{2} $）。步骤12~步骤28是投票能力与得票分数的更新阶段：首先，选出得票分数最高的节点v，并更新N_v的投票能力，时间复杂度为O（$ \stackrel{-}{d} $）；其次，更新N_v及其邻居的得票分数，时间复杂度为O（$ {\stackrel{-}{d}}^{2} $）。因此，投票能力与得票分数更新阶段的时间复杂度为O（k$ {\stackrel{-}{d}}^{2} $）。由此可得，算法总的时间复杂度为O（n$ {\stackrel{-}{d}}^{2} $+ n$ {\stackrel{-}{d}}^{2} $+ k$ {\stackrel{-}{d}}^{2} $）= O（n$ {\stackrel{-}{d}}^{2} $）。

3 实验设计

本文所有的算法均使用Python语言来实现。运行环境为Windows10操作系统，内存8 GB，处理器Intel^® Core^TM i7-7700 CPU @3.60 GHz。

3.1 数据集

本文实验选用4个不同规模的真实网络数据集，数据集的统计特征如表 2所示，其中p_c表示网络的传播阈值^[25]。

3.2 对比算法

为验证本文算法的性能，本文将其与当前具有代表性的启发式算法进行对比。不同算法的时间复杂度对比如表 3所示。

3.3 实验设置与评价指标

本文在4个不同规模的真实网络数据集上，使用IC模型^[4]和SIR模型^[26]对不同算法进行对比实验。

3.3.1 IC模型

在IM问题中，IC模型是一种应用最为广泛的影响力传播模型。在IC模拟传播过程中，每个数据集使用p_c作为传播概率，并且每次选择50个节点作为初始传播源的种子集合。在IC模型下的影响范围即种子节点影响扩散的个数，并将其作为算法的主要评价指标。由于IC模型的传播具有随机性，因此本文使用10 000次的Monte-Carlo模拟来保证实验能够得到较为精确的影响范围。但是多数算法在IC模型下的影响范围比较接近，并且当k值不同时，不同算法的表现也会上下浮动。为了便于分析，本文给出一个等价的分析指标——传播差异。算法a₁和a₂在$ k=x $时的传播差异如式（6）所示：

$ {{D}_{\mathrm{D}\mathrm{D}}}_{x}({a}_{1}, {a}_{1})={\sigma }_{{a}_{1}}\left({S}_{x}\right)-{\sigma }_{{a}_{2}}\left({S}_{x}\right) $

(6)

其中：$ {\sigma }_{a}\left({S}_{k}\right) $表示算法a选取大小为k的种子集S_k所达到的影响范围。

3.3.2 SIR模型

SIR模型是一种经典的病毒传播模型，近年来在IM问题中得到了广泛的应用。在SIR模型中，每个节点具有易感S、感染I和治愈R这3种状态。节点由易感S到感染I的状态转换称为感染，感染率为μ；节点由感染I到治愈R的状态转换称为治愈，治愈率为β。该模型下算法的评价指标有2个，第1个是当给定初始感染比例时对比算法在t时的感染规模F（t），计算过程如式（7）所示：

$ F\left(t\right)=\frac{{n}_{I\left(t\right)}+{n}_{R\left(t\right)}}{n} $

(7)

其中：n_I（t）表示t时感染状态的节点个数；n_R（t）表示t时恢复状态的节点个数。第2个评价指标是当初始感染比例不同时，对比算法的最终感染规模F（t_c ），计算过程如式（8）所示：

$ F\left({t}_{c}\right)=\frac{{n}_{R\left({t}_{c}\right)}}{n} $

(8)

其中：$ {n}_{R\left({t}_{c}\right)} $表示当传播过程达到稳定时处于恢复状态的总节点数。以下实验均采用100次的传播来得到F（t）及F（t_c ）。因为在本文实验中，F（t）在t = 20之前均已达到峰值，所以在实验中只展示了t ≤ 20的感染规模。另外，网络初始感染比例ρ根据网络规模及传播阈值来选取，本文在Email、Hamster、CacondMat、Brightkite数据集上最大感染比例下的感染个数分别为50、50、150、200。

在SIR模型中，感染比例$ \lambda =\mu /\beta $对模型的传播速度具有至关重要的作用，本文将其设置为1.5。感染率的选择没有固定标准^[19]，一些算法根据边的传播概率来选取种子节点，而本文为了保证算法的有效性及统一性，将每个数据集的传播阈值p_c设置为感染率。

4 实验结果分析

在解决IM问题的投票算法中，节点向其邻居的投票可以被看作是一个局部信息的扩散过程，当每轮投票结束后均选择信息量最高的节点作为种子节点。投票算法通过信息扩散最大化的方法来识别网络中最有影响力的节点。因此，IM问题作为信息扩散的核心及关键问题，使用投票机制获得较优的实验效果。

4.1 IC模型下的结果分析

本文将CCA算法作为基准算法来计算不同算法在各个数据集上的传播差异。当种子节点数k分别为10、20、30、40、50时，CCA算法在不同数据集上的传播差异如表 4所示。

在不同数据集上各个算法使用IC模型产生的传播差异如图 2所示。从图 2可以看出，大多数算法在开始时选择的节点拥有类似的影响范围，但随着种子节点数的增大，算法的表现呈现出不同的特点。

在Email数据集上，TrussVote和VoteRank++具有类似的传播特点，当种子节点数较小时影响的范围相较于其他算法小，但随着种子节点数增大，影响范围逐步增大并趋于稳定。相比VoteRank++，TrussVote在种子节点数较大时影响范围最大。这种变化趋势也说明了TrussVote在消除影响力重合时的作用更加显著。在Hamster和CacondMat数据集上，TrussVote与MCDE总体的变化趋势接近，但TrussVote的表现更好，在Email和Brightkite数据集上，TrussVote具有较优的实验结果。在CacondMat数据集上，除CCA算法以外，其他算法具有相似的传播特点，影响范围的变化情况都基本类似，而TrussVote算法在k$ \in $[1，50]的多数情况下能获得最广泛的影响范围。

在Brightkite数据集上，CCA与DegreeDistance算法的表现较差，在其他数据集中的表现也有波动。这说明基于中心性的算法，在网络特点不同的数据集中难以产生持续有效的实验效果。在Hamster数据集上RNR算法的表现说明它在度数较大的数据集中，也不能有效解决富人俱乐部效应。与投票类算法相似，随着种子节点数增大，IM-ELPR算法的影响范围逐渐优于其他算法，但TrussVote与其相比，不仅时间复杂度更低，而且传播效果也更好。在IC模型下不同算法的实验结果表明，TrussVote算法具有更广泛的影响范围。

4.2 SIR模型下的结果与分析

当给定初始感染比例时，SIR模型下不同算法的感染规模F（t）随迭代轮次变化的结果如图 3所示。当初始感染节点数相同时，TrussVote只在Hamster数据集上的峰值略低于MCDE，而在其他数据集上均达到峰值。TrussVote选取的种子集能够在最短的时间内感染更多的节点，说明TrussVote具有更快的感染速度与更大的感染规模。

各个算法的最终感染规模F（t_c ）随初始感染比例增大的变化曲线如图 4所示。在Email和CacondMat数据集上，TrussVote在初始感染比例较小的情况下最终感染规模略低于VoteRank++及IM-ELPR算法，但随着初始感染比例的增大，TrussVote拥有更大的感染规模。TrussVote在Hamster数据集上初始感染比例为2.65%时表现相对较差，但在Hamster和Brightkite数据集上，TrussVote的最终感染规模总体最优。这说明TrussVote选取节点的策略及算法更新的过程都较为合理，具有较优的稳定性。在SIR模型下不同算法的实验结果表明，TrussVote不仅具有更快的感染速度及更大的感染规模，在不同初始感染比例下也拥有最好的表现。

因此，相比基于中心的算法，TrussVote在不增大时间复杂度的同时取得了更稳定且有效的实验效果。当迭代轮次较多时，RNR和IM-ELPR在较大网络规模中的时间和影响范围相比TrussVote较差。另外，与VoteRank++更新节点两跳之内的邻居投票能力不同，TrussVote在更新阶段对节点一跳之内的邻居投票能力赋予了不同程度的更新，不仅具有更低的时间复杂度，同时也能够获得拥有更大影响范围的种子集合。以上实验结果也验证了TrussVote算法的正确性及有效性。

5 结束语

针对社交网络中的影响最大化问题，本文提出基于K-truss的投票改进算法。在投票阶段和更新阶段分别引入边的truss值及节点相似性指标对投票类算法进行改进，以区分更新节点邻居的投票能力。在不同规模的真实网络数据集上的实验结果表明，本文算法在具有较低时间复杂度的同时，给IM问题提供了较有效的解决方案。下一步考虑将本文TrussVote投票算法应用到IM的拓展问题中，如利润最大化问题，使其具有更优的鲁棒性。