0 引言

社会网络上的信息传播大都基于“病毒式营销”。“病毒式营销”指的是当一个人接受了某种思想或购买了某种产品后，他会把这种信息传播给他的朋友，他的朋友亦会再告诉自己的朋友，这种信息传播方式能够影响用户的决策、购买等行为。

影响最大化问题是Domingos等^[1]最先提出的，它定义为如何寻找K个初始节点，使得信息的最终传播范围最广。Kempe等^[2-3]第一次将最大化问题归纳为离散最优化问题，并且证明了求最优解是一个NP难问题，他们提出采用贪心算法求解，即每一步采用当前最优解作为种子。针对贪心算法的时间复杂度非常高这一问题，后来的研究者又提出若干改进算法，如CELF(Cost-Effective Lazy Forward)算法^[4]、新贪心算法NewGreedyIC^[5]、混合贪心算法MixGreedyIC^[5]等。虽然这些算法较贪心算法有所改进，但时间复杂度依然很高，无法适用于大型网络。Chen等^[6]提出了信息沿着最大生成树传播的MIA(Maximum Influence Arborescence)算法，并将节点的影响范围局限在以节点为根的局部树状结构中。本文在计算节点的影响力时认为影响只沿最短路径传播。

以前的研究没有考虑营销活动中的费用问题。实际上，在营销活动中，商家往往采用支付广告费用、赠送产品、打折等形式来激励客户的传播积极性，这个过程需要一定的成本，所以商家会有意识地选择某些“性价比”高的客户进行广告投放，以期通过用户的影响力达到广泛扩散信息的目的。针对这一目标，Zhan等^[7]采用CELF算法思路，每次将影响增量与节点费用比值最大的节点纳入种子集合。Wang等^[8]采用贪心算法思路，选取四种不同类型的种子集合，分别是成本最低的、影响范围最大的、影响范围与成本比值最大的，以及成本与传播增量比值最大的。上述算法都基于贪心算法来解决问题，时间复杂度高。为了降低时间复杂度，本文采用动态规划的思路来解决问题。

在影响最大化领域，经常采用的信息传播模型是独立级联(Independent Cascade，IC)模型，该模型中假设种子节点和非种子节点都只能进行一次信息传播。而在市场营销活动中，得到一定经济利益的初始用户会进行多次信息传播，非初始用户则只进行一次信息传播。另外，Alon等^[9]也提出，当初始用户得到k份费用时，他就会向他的邻居进行k次信息传播。显然，IC模型不适用于成本控制下的信息传播情况，所以本文在IC模型的基础上提出了初始节点进行多次传播的MTIC(Multiple Transmission model based on IC)模型，并证明了该模型具有单调性和子模性。Kempe等^[2-3]已经证明了具有子模性的影响范围函数使用贪心算法求解，能取得最优解的63%。

为解决基于成本的影响最大化问题，本文给出了综合考虑成本预算和节点初始激活费用的最大化算法BCIM(Influence Maximization with Budget and node Cost)。此算法的基本思路是把节点分为若干组，按照动态分配的思路在每一组中选择一个种子。为了提高程序的运行速度，从以下两个方面进行优化：1) 将PageRank^[10]排名靠前的节点选作备用种子节点，减少种子节点的搜索范围；2) 在计算节点的影响范围时，只考虑此节点对它近距离邻居的影响值，减少计算工作量。

1 传播模型

  定义1  设图G=(V,E)表示一个社会网络，其中：V表示节点集合，∀v∈V表示节点；E表示边集，∀e(u,v)∈E表示节点u和v之间的关系。如果e(u,v)∈E，则u试图激活v的概率用p(u,v)表示。

  定义2  给定图G=(V,E)，种子集合S⊆V，初始节点进行多次信息传播的模型MTIC的工作过程如下：在t=0时，∀s∈S会激活它的邻居节点Num(s)次，每一次激活都是独立的；当t≥1时，在t-1时刻被激活的节点会激活它的非活跃邻居节点一次，此过程会级联下去，直到没有新节点被激活为止。整个激活过程中，节点u对节点v的激活概率为p(u,v)。节点一旦被激活，就会一直保持活跃状态。

  定理1  在社会网络中采用MTIC模型进行信息传播时，信息传播影响范围函数σ(·)具有单调性和子模性。

单调性指的是对于图G=(V,E)，当A⊂V，v∈G且v∉A时，有σ(A+v)≥σ(A)。

子模性指的是对于图G，当S₁⊆S₂⊆V，且v∉S₂时，有σ(S₁∪{v})-σ(S₁)≥σ(S₂∪{v})-σ(S₂)。

Kempe等^[2-3]已经证明了IC模型上的信息传播范围函数σ(·)具有子模性。

证明 在任意图G=(V,E)上用MTIC模型进行信息传播是一个随机事件。在实验之前，将G分为两部分G₁和G₂。其中：G₁是图G删除节点集T及其所在边形成的子图；G₂是节点集合T及其直接邻居形成的子图。

下面形成G₁、G₂中进行信息传播的样本空间。

对于G₁中的任意边(u₁，v₁)，u₁将以概率p激活v₁。在每一次可能的结果中，若v₁被激活，则在u₁和v₁之间保留一条边；否则，u₁和v₁之间没有边。每一个可能的结果就是一个样本点，也是G₁的一个子图G_1i。子图中包含G₁的所有节点和某些边。所有的样本点组成样本空间X₁：{G₁₁,G₁₂,G₁₃，…}。

令T为初始节点集合，由于T中节点对其邻居的影响次数为多次，所以在G₂中求样本点时都按如下方法设置：T中的某个节点u₂对其邻居v₂进行多次激活时，只要有一次成功了，就认为在u₂和v₂之间存在一条边。这些样本点是G₂的子图G_2i。所有的样本点组成样本空间X₂：{G₂₁,G₂₂,G₂₃，…}。

令X₁和X₂进行笛卡尔乘积，得到总的样本空间X₃={(G_1i,G_2j)|G_1i∈X₁,G_2j∈X₂}。对X₃中的每个样本点，把图G_1i和G_2j合并成一个图：把编号相同的节点看成是一个节点，把所有的边都保留下来。这样形成了样本空间X。

现在取样本空间X的一个样本点x，令：σ_x(U)表示从节点集合U出发，能到达的节点集合的大小；R(v,x)表示从节点v出发能够达到的节点集合，所以有:

${{\sigma }_{x}}(U)=|\underset{u\in U}{\mathop{\bigcup }}\,R(u,x)|$

1) 证明在样本点x上的单调性。

当A⊂T，v∈T且v∉A时，用Rx₁表示在样本x上集合A影响到的节点集合，Rx₂表示在样本x上节点v影响到的节点集合。若Rx₁∩Rx₂=∅，则σ_x(A+{v})=σ_x(A)+σ_x(v)，所以σ_x(A+{v})≥σ_x(A)；若Rx₁∩Rx₂≠∅，则显然σ_x(A+{v})≥σ_x(A)，得证。

2) 证明在样本点x上的子模性。

当S₁⊆S₂⊆T，v∉S₂时，σ_x(S₁∪{v})-σ_x(S₁)的值就是在R(v,x)中却不在$\bigcup\limits_{_{u\in {{S}_{1}}}}{R(u,x)}$中的节点数目，很显然这个值不小于在R(v,x)而不在$\bigcup\limits_{_{u\in {{S}_{_{2}}}}}{R(u,x)}$中的节点数目。所以σ_x(S₁∪{v})-σ_x(S₁)≥σ_x(S₂∪{v})-σ_x(S₂)，得证。

σ(S)是在整个样本空间上求得，是所有样本点上取值σ_x(S)的非负线性组合，所以σ(S)具有单调性和子模性。

2 问题定义

在营销活动中，商家需要支付一定的成本费用；另外，向不同的客户投放信息时，由于客户的社会地位、知名度等原因的不同，所需费用也会不同。

  定义3  在图G=(V,E)中，假设B是给定的成本预算，Cost(u)表示商家为了使u接受某种产品或观念所需付出的费用，S是种子集合，σ(S)是S的最终影响范围，成本B控制下的影响最大化(Influence Maximization with Budget,BIM)定义为：

$\begin{align} & \underset{S\subset V}{\mathop{\text{arg}\ \text{max}}}\,\ \{\sigma (S)\} \\ & \text{s}\text{.t}\text{.}\ \ \ \ \sum\limits_{u\in S}{Cost(u)\le B} \\ \end{align}$

当每个节点的成本为1时，BIM问题就是传统的社会网络影响最大化问题。由于传统的社会网络影响最大化是NP难问题^[2-3]，所以BIM也是NP难问题。

  定义4  当以Cost(u)表示节点的费用，Degree(u)表示u的邻居数时，u进行信息传播的次数Num(u)定义为：

$Num(u)=\gamma \cdot Cost(u)/Degree(u)$

(1)

其中γ是比例系数。

  定理2  设w的入边邻居集合为N_in(v)，u的活跃概率为p(u)，从节点a出发经过l步可达的节点集合为T^l(a)，则节点a对所有可达节点的预期影响值之和为:

$\begin{align} & \inf (a)= \\ & \sum\limits_{l=1}^{\max }{\sum\limits_{v\in T_{^{{}}}^{l}(a)}{(1-\prod\limits_{u\in {{N}_{in}}(v)\cap {{T}^{l-1}}(a)}{{{(1-p(u)p(u,v))}^{Num(u)}}})}} \\ \end{align}$

(2)

当u=a时，p(u)=1；T⁰(a)=a。

证明 对于T^l(a)中的任意节点v，当它的入边邻居节点u激活它一次时，它的活跃概率为p(u)p(u,v)，非活跃概率为1-p(u)p(u,v)。当u影响v的次数为Num(u)时，v的不活跃概率为(1-p(u)p(u,v))^Num(u)。所以v不被所有入边邻居激活的概率为$\prod\limits_{u\in {{N}_{in}}(v)\cap {{T}^{l-1}}(a)}{{{(1-p(u)p(u,v))}^{Num(u)}}}$，v的活跃概率为($(1-\prod\limits_{u\in {{N}_{in}}(v)\cap {{T}^{l-1}}(a)}{{{(1-p(u)p(u,v))}^{Num(u)}}}$。集合T^l(a)中所有节点的活跃概率和为：

$\sum\limits_{v\in {{T}^{l}}(a)}{\left( 1-\prod\limits_{u\in {{N}_{in}}(v)\cap {{T}^{l-1}}(a)}{{{(1-p(u)p(u,v))}^{Num(u)}}} \right)}$

因此，节点a对所有可达节点的影响值之和为：

$\sum\limits_{l=1}^{max}{\sum\limits_{v\in T_{^{{}}}^{l}(a)}{(1-\prod\limits_{u\in {{N}_{in}}(v)\cap {{T}^{l-1}}(a)}{{{(1-p(u)p(u,v))}^{Num(u)}}})}}$

图 1给出的是节点A以及它的邻居节点，当计算A的影响力时，节点B和C属于T¹(a)，节点D、E、F属于T²(a)。基于后面提到的近距离影响法，忽略边(B,C)和(D,E)的影响。

  定义5  对于图G=(V,E)，假设G′=(CS,E′)，其中CS⊂V，E′⊆E。对于∀u∈CS，group′(u)={u}∪{v|(u,v)∈E′}，则group(w)定义为：

group(w)∈{group′(u)|u∈CS}

s.t. ∪w∈CS group(w)=CS且group(u)∩group(v)=∅

根据定义5可以得出，分组group(w)中任意两个节点u和v之间的距离不大于2。

3 影响最大化算法 3.1 贪心算法

本文给出了两种贪心算法：1) 在成本允许的情况下，每一步选取当前最具影响力的节点加入种子集合，称为Greedy_MII，如算法1所示；2) 在成本允许的前提下，每一步选取影响力与节点费用比值最大的节点加入种子集合，称为Greedy_MICR，如算法2所示。

算法1 Greedy_MII。

输入 G=(V,E)，成本B，节点费用C={Cost(i)|i∈V}；

  输出  种子集合S。

  1)  S=∅

  2)  While B≥0

  3)  V′={v|v∈V-S and Cost(v)≤B}

  4)  for each node w in V′ do

  5)  sw=0

  6)  for i=1 to R do

  7)  sw+=σ(S ∪{w})-σ(S)

  8)  sw=sw/R

  9)  u=arg maxw∈V′{sw}

  10)  S=S ∪{u}

  11)  B=B-Cost(u)

  12)  Output S

  算法2  Greedy_MICR

  输入  G=(V,E)，成本B，节点费用C={Cost(i)|i∈V}；

  输出  种子集合S。

  1)  S=∅

  2)  While B≥0

  3)  V′={v|v∈V-S and Cost(v)≤B}

  4)  for each node w in V′ do

  5)  sw=0

  6)  for i=1 to R do

  7)  sw+=σ(S ∪{w})-σ(S)

  8)  sw=sw/R

  9)  u=arg maxw∈V′{sw /Cost(w)}

  10)  S=S ∪ {u}

  11)  B=B-Cost(u)

  12)  Output S

以上两个算法的最大缺点是效率低，原因主要有两点：1) 每一步都要搜索V-S中的每个满足成本要求的节点；2) 求每个节点的边际收益时，采用蒙特卡罗模拟法计算σ(·)需要重复计算R次，而R取值一般是10000。

3.2 BCIM算法 3.2.1 减少搜索范围

社会网络中，有影响力的用户或者意见领袖的言论更能影响他人。微博环境下，新用户加入网络时，也往往选择大V进行关注。在线社会网络通常采用PageRank值表示用户的影响力排名，一般认为该值越大，用户的影响力就越强^[11]。

网络中除了一部分有影响力的用户之外，还存在大量的低影响力甚至没什么影响力的用户。在进行信息传播时，这部分用户几乎没有什么贡献，所以不能作为种子。为了缩小种子的搜索范围，选择有影响力的用户加入备用种子集合。

3.2.2 减少计算工作量

式(2) 计算的是任意节点a对所有可达节点的影响力之和，在计算时需要遍历整个网络，计算量很大。为了减少计算工作量，提出近距离影响思路。

假设存在路径P=〈a₁,a₂,…，a_m〉，不考虑节点的激活次数，则节点a_m被a₁激活的概率为$p'({{a}_{m}})=\prod\limits_{i=2}^{m}{p({{a}_{i-1}},{{a}_{i}})}$。通过上式可以看出，随着距离的增加，节点a_m被a₁激活的概率急速下降。所以在利用式(2) 计算节点a₁的影响力时，用对近距离节点的影响力之和来近似代替对整个网络产生的影响力，不再遍历整个网络。文献[12]中的实证研究表明，当计算节点的影响力时，取节点对两步之内的邻居的影响力之和作为节点对整个网络的影响力，其效果是最好的。

3.2.3 BCIM算法实现

步骤1 计算每个节点的PageRank排名，然后按比例选取排名靠前的节点加入备用种子集合。

步骤2 按照定义5，把备用种子集合划分为若干组。由于同一组内的节点之间距离不超过2，所以组内节点之间的相互影响力很强。

步骤3 在每组中最多选取一个节点作为种子。由于组内用户相互影响力很强，且种子节点能进行多次传播，所以组内其他节点被激活的概率会很高。被选作种子的节点必须满足两个条件：1) 所有种子节点的费用之和不能超过成本预算B；2) 种子集合的信息传播范围最广。选择种子的策略可以用以下表达式来描述：

$\begin{align} & f[k][b]=\max \{f[k-1][b], \\ & f[k-1][b-Cost(v)]+\sigma (v)|v\in group(k)\} \\ \end{align}$

(3)

其中： f[k][b]表示当成本是b时，在前k个分组中寻找到的种子集合的信息传播范围；Cost(v)表示节点v的费用；σ(v)表示节点v的信息传播范围。

此问题可以转换为在成本为b时，是否在第k个分组中寻找种子节点。如果在成本b的控制下，在前k-1个分组中寻找的种子集合的影响范围大于在前k个分组中寻找的种子集合的影响范围，则在前k-1个分组中寻找，函数变为f[k-1][b]；否则，将在第k个分组中寻找一个种子v，然后在前k-1个分组中寻找剩余的种子节点，此时的成本预算值需要减去v的费用Cost(v)，整个种子集合的信息范围需要加上节点v的传播范围σ(v)。

BCIM算法如算法3所示。

算法3 BCIM。

输入 G=(V,E)，成本B，节点费用C={Cost(i)|i∈V}；

输出 种子集合S。

  1)  compute PageRank of every node

  2)  compute spread times of every node

  3)  select high PageRank value nodes into the candidate set CS

  4)  for i=0 to len(CS) do

  5)  select a node v and its direct neighbors into group(v)

  6)  CS=CS-group(v)

  7)  if CS==null then

  8)  break

  9)  m=i

  10)  for i=0 to m+1 do

  11)  for j=0 to B+1 do

  12)  f[i][j]=0,g[i][j]=0

  13)  for k=1 to m+1 do

  14)  for b=B to 0 do

  15)  for each node in group[k] do

  16)  w=Cost(node),v=inf(node)

  17)  if b-w＜0 then

  18)  continue

  19)  if f[k-1][b]＜f[k-1][b-w]+v then

  20)  f[k][b]=f[k-1][b-w]+v

  21)  g[k][b]=node

  22)  else

  23)  f[k][b]=f[k-1][b]

  24)  j=B

  25)   for i=1 to m+1 do

  26)  if g[i][j]!=0 do

  27)  S.add(g[i][j])

  28)  j=j-Cost(g[i][j])

  29)  Output S

第2) 行中，节点的传播次数可以根据式(1) 求得。第4) ~8) 行，算法将备用种子集合划分为m个分组。第10) ~12) 行，定义了两个二维数组，初始值均为0： f[i][j]用来保存当成本预算为j时，在前i个分组中寻找的种子集合的信息传播范围；g[i][j]用来保存当成本为j时，在第i个分组寻找到的种子。第13) ~23) 行通过三层循环，应用式(3) 在每个分组中寻找满足要求节点。其中，第14) 行表示剩余预算b是按照递减的顺序进行的；第16) 行中的inf(node)值是根据式(2) 计算的node节点的影响力，根据近距离影响思路，只计算node节点对两步之内邻居的影响力；17) 、18) 行用来排除费用大于剩余成本预算的节点；19) ~21) 行表示选择一个节点，并保存到二维数组g中。 第25) ~28) 行，在数组g中选择满足成本要求的节点，并且每个分组至多选择一个节点。

4 实验与分析

本次实验在两个真实的数据集上进行，并比较了BCIM算法和Random算法、Greedy_MII算法、Greedy_MICR算法在种子集的最终影响范围和种子质量，以及算法的运行时间等方面的性能。

4.1 数据集

实验用到的两个真实的数据集分别是NetHEPT和NetPHY。这两个数据集与文献[5]中用到的数据集一致。在这两个数据集中，节点代表作者，边表示作者之间的引用关系。这两个数据集的统计特性如表 1所示。

4.2 实验设置

在Random算法中，每次随机选择节点费用不超过剩余成本的节点。在BCIM算法中，当采用式(2) 计算节点的影响范围时，只考虑对两步之内邻居的影响力。所有的算法都采用MTIC传播模型并设置影响概率p=0.01。在求种子集合的传播范围时，采用蒙特卡罗模拟法，由于传播模型的随机性，每种方法都重复模拟10000次，然后求平均值。

节点u的费用Cost(u)可以有多种设置方式，本文实验中为了简单，将其设置为PageRank排名值。所有的实验均设置成本预算值B从0递增到100，每次增加10，然后比较信息传播范围和种子质量。同时，实验也比较了当成本预算值为100时，选择种子所需要的时间。

所有的程序代码都采用Python语言编写，运行计算机的配置为：Pentium Dual-core CPU E6500 2.93 GHz，2 GB内存。

4.3 实验结果 4.3.1 信息传播范围和种子质量

图 2给出的是NetHEPT数据集上的信息传播范围。从图 2中可以看到，Random算法信息传播范围明显大于其他算法，BCIM算法与Greedy_MICR算法的差异不大，Greedy_MII算法的性能最差。

图 3给出的是在NetHEPT数据集上所选的种子个数。通过观察图 3可以发现，Random算法选择的种子个数明显多于其他算法，而BCIM算法与Greedy_MICR的差异同样很小，Greedy_MII算法选择的种子数最少。

图 4给出的是NetHEPT数据集上种子传播范围的增加值。从图 4中可以看到，两个贪心算法的传播范围的增加值几乎是一样的，BCIM算法的增加值略小于两个贪心算法，而Random算法的增加值非常小。

图 5给出的是NetPHY数据集上的信息传播范围。从图 5中可以看到，Random算法信息传播范围明显大于其他算法，BCIM算法优于Greedy_MICR和Greedy_MII算法。

图 6给出的是在NetPHY数据集上所选的种子个数。通过观察图 6可以发现，Random算法选择的种子个数明显多于其他算法，BCIM算法所选种子数略多于Greedy_MICR算法，Greedy_MII算法选择的种子数最少。

图 7给出的是NetPHY数据集上种子传播范围的增加值。从图 7中可以看到，BCIM算法与Greedy_MII算法传播范围的增加值接近，Greedy_MICR算法的增加值小于上述两个算法，而随机算法Random的增加值依然非常低。

通过对图 2~7的综合分析可以得出如下结论：1) Random算法所选种子对网络中其他节点产生的影响最小，所以质量最差。有研究表明，在“病毒式营销”方式中，公司倾向于寻找某个领域中的专家或最具影响力的人物进行推销。这些人接受新产品后会以自身的影响力为公司带来更大的客户群体。如果选择的初始用户过多且没有什么影响力，不仅会让客户产生厌烦情绪，不利于产品的推广，而且也不利于对种子节点的管理。

2) 采用贪心算法进行种子选择，每轮选择传播范围增量与费用比值最高的节点的效果要好于选择传播范围增量最大的节点，所以选择“性价比”高的节点作为种子是一个很好的策略。3) BCIM算法所选种子的影响范围接近或优于两个贪心算法，并且种子数量适中，利于产品的推广。

4.3.2 运行时间

表 2给出了当成本预算值为100时，各个算法在两个数据集上进行种子选择所需要的时间。从表 2中可以看到，Random算法的运行时间是最短的，BCIM算法也仅仅需要几十秒，但两个贪心算法在两个数据集中都需要几十分钟甚至几百分钟，这是不能忍受的。

通过对种子集的传播范围和程序运行时间的分析表明，Random算法虽然很快，但是由于选择的种子太多且传播范围增加值又太小，所以不适合解决成本控制下的影响最大化问题；两个贪心算法运行时间太长，同样不适合解决此问题；BCIM算法在传播范围方面不次于贪心算法，并且选择的种子个数适中，运行时间又很短，所以更适合解决成本控制下的影响最大化问题。

5 结语

针对成本控制环境下影响最大化问题，首先提出初始节点进行多次传播的信息传播模型，然后通过缩减种子搜索范围以及减少计算节点影响范围的工作量，提出了基于动态规划思路的最大化算法BCIM。仿真实验表明BCIM算法比贪心算法更适合解决成本控制下的影响最大化问题。下一步的研究方向可以考虑如何实现利润的最大化。