成本控制下的快速影响最大化算法

刘院英，郭景峰，魏立东，胡心专

(1.燕山大学 信息科学与工程学院，河北 秦皇岛 066004； 2.河北经贸大学 信息技术学院，石家庄 050061)

(*通信作者电子邮箱slt115@126.com)

成本控制下的快速影响最大化算法

刘院英1,2*，郭景峰1，魏立东2，胡心专1

(1.燕山大学 信息科学与工程学院，河北 秦皇岛 066004； 2.河北经贸大学 信息技术学院，石家庄 050061)

(*通信作者电子邮箱slt115@126.com)

针对成本控制下影响最大化时间复杂度高的问题，提出一种快速的最大化算法BCIM。首先提出对初始节点进行多次传播的传播模型；其次选择高影响力节点作为备用种子，并基于近距离影响减少计算节点影响范围的工作量；最后利用动态规划方法在每组备用种子中最多选择一个种子。仿真实验表明，与随机算法Random、每轮取影响力增量最大的节点的贪心算法Greedy_MII、每轮取影响力增量与成本比值最大的节点的贪心算法Greedy_MICR相比，在影响范围上，BICM接近或优于Greedy_MICR及Greedy_MII，远次于Random；在种子集合的质量上，BCIM、Greedy_MICR、Greedy_MII三者差距较小，但都远远好于Random；在运行时间上，BCIM是Random的几倍，而两个贪心算法都是BCIM的几百倍。BCIM算法能在较短时间内找到更有效的种子集合。

影响最大化；在线社会网络；成本控制；动态规划；多次传播模型

0 引言

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

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

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

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

为解决基于成本的影响最大化问题，本文给出了综合考虑成本预算和节点初始激活费用的最大化算法BCIM(InfluenceMaximizationwithBudgetandnodeCost)。此算法的基本思路是把节点分为若干组，按照动态分配的思路在每一组中选择一个种子。为了提高程序的运行速度，从以下两个方面进行优化：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，当S1⊆S2⊆V，且v∉S2时，有σ(S1∪{v})-σ(S1)≥σ(S2∪{v})-σ(S2)。

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

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

下面形成G1、G2中进行信息传播的样本空间。

对于G1中的任意边(u1，v1)，u1将以概率p激活v1。在每一次可能的结果中，若v1被激活，则在u1和v1之间保留一条边；否则，u1和v1之间没有边。每一个可能的结果就是一个样本点，也是G1的一个子图G1i。子图中包含G1的所有节点和某些边。所有的样本点组成样本空间X1：{G11,G12,G13，…}。

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

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

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

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

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

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

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

2 问题定义

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

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

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

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

Num(u)=γ·Cost(u)/Degree(u)

(1)

其中γ是比例系数。

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

inf(a)=

(2)

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

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

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

图1 节点A以及A的邻居

定义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}

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

3 影响最大化算法

3.1 贪心算法

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

算法1Greedy_MII。

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

输出 种子集合S。

1)

S=∅

2)

WhileB≥0

3)

V′={v|v∈V-SandCost(v)≤B}

4)

for each nodewinV′ do

5)

sw=0

6)

fori=1 toRdo

7)

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

8)

sw=sw/R

9)

10)

S=S ∪{u}

11)

B=B-Cost(u)

12)

OutputS

算法2Greedy_MICR

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

输出 种子集合S。

1)

S=∅

2)

WhileB≥0

3)

V′={v|v∈V-SandCost(v)≤B}

4)

foreachnodewinV′do

5)

sw=0

6)

fori=1toRdo

7)

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

8)

sw=sw/R

9)

10)

S=S∪ {u}

11)

B=B-Cost(u)

12)

OutputS

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

3.2 BCIM算法

3.2.1 减少搜索范围

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

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

3.2.2 减少计算工作量

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

3.2.3BCIM算法实现

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

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

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

f[k][b]=max{f[k-1][b],

f[k-1][b-Cost(v)]+σ(v)|v∈group(k)}

(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所示。

算法3BCIM。

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

输出 种子集合S。

1)

computePageRankofeverynode

2)

computespreadtimesofeverynode

3)

selecthighPageRankvaluenodesintothecandidatesetCS

4)

fori=0 to len(CS) do

5)

select a nodevand its direct neighbors intogroup(v)

6)

CS=CS-group(v)

7)

ifCS==null then

8)

break

9)

m=i

10)

fori=0 tom+1do

11)

forj=0 toB+1 do

12)

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

13)

fork=1 tom+1 do

14)

forb=Bto 0 do

15)

for each node ingroup[k]do

16)

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

17)

ifb-w<0 then

18)

continue

19)

iff[k-1][b]

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)

fori=1 tom+1 do

26)

ifg[i][j]!=0 do

27)

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

28)

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

29)

OutputS

第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所示。

表1 数据集的统计特性

4.2 实验设置

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

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

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

4.3 实验结果

4.3.1 信息传播范围和种子质量

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

图2 NetHEPT数据集上的传播范围

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

图3 NetHEPT数据集上的种子数

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

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

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

图4 NetHEPT数据集上种子传播范围增加值

图5 NetPHY数据集上的传播范围

图6 NetPHY数据集上的种子数

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

通过对图2～7的综合分析可以得出如下结论：1)Random算法所选种子对网络中其他节点产生的影响最小，所以质量最差。有研究表明，在“病毒式营销”方式中，公司倾向于寻找某个领域中的专家或最具影响力的人物进行推销。这些人接受新产品后会以自身的影响力为公司带来更大的客户群体。如果选择的初始用户过多且没有什么影响力，不仅会让客户产生厌烦情绪，不利于产品的推广，而且也不利于对种子节点的管理。2)采用贪心算法进行种子选择，每轮选择传播范围增量与费用比值最高的节点的效果要好于选择传播范围增量最大的节点，所以选择“性价比”高的节点作为种子是一个很好的策略。3)BCIM算法所选种子的影响范围接近或优于两个贪心算法，并且种子数量适中，利于产品的推广。

图7 NetPHY数据集上种子传播范围增加值

4.3.2 运行时间

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

表2 各算法在两个数据集上的运行时间 s

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

5 结语

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

)

[1]DOMINGOSP,RICHARDSONM.Miningthenetworkvalueofcustomers[C]//KDD2001:Proceedingsofthe7thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDatamining.NewYork:ACM, 2001: 57-66.

[2]KEMPED,KLEINBERGJ,TARDOSÉ.Maximizingthespreadofinfluencethroughasocialnetwork[C]//KDD2003:Proceedingsofthe9thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2003: 137-146.

[3]KEMPED,KLEINBERGJ,TARDOSÉ.Influentialnodesinadiffusionmodelforsocialnetworks[C]//ICALP2005:Proceedingsofthe32ndInternationalColloquiumonAutomata,LanguagesandProgramming,LNCS3580.Berlin:Springer-Verlag, 2005: 1127-1138.

[4]LESKOVECJ,KRAUSEA,GUESTC,etal.Cost-effectiveoutbreakdetectioninnetworks[C]//KDD2007:Proceedingsofthe13thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2007: 420-429.

[5]CHENW,WANGY,YANGS.Efficientinfluencemaximizationinsocialnetworks[C]//KDD2009:Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2009: 199-208.

[6]CHENW,WANGC,WANGY.Scalableinfluencemaximizationforprevalentviralmarketinginlarge-scalesocialnetworks[C]//KDD2010:Proceedingsofthe16thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2010: 1029-1038.

[7]ZHANQ,YANGH,WANGC,etal.CPP-SNS:asolutiontoinfluencemaximizationproblemundercostcontrol[C]//ICTAI2013:Proceedingsof25thInternationalConferenceonToolswithArtificialIntelligence.Piscataway,NJ:IEEE, 2013: 849-856.

[8]WANGY,HUANGW,ZONGL,etal.Influencemaximizationwithlimitcostinsocialnetwork[J].ScienceChinaInformationSciences, 2013, 56(7): 1-14.

[9]ALONN,GAMZUI,TENNENHOLTZM.Optimizingbudgetallocationamongchannelsandinfluencers[C]//WWW2012:Proceedingsofthe21stAnnualConferenceonWorldWideWeb.NewYork:ACM, 2012: 381-388.

[10]BRINS,PAGEL.Theanatomyofalarge-scalehypertextualWebsearchengine[J].ComputerNetworksandISDNSystems, 1998, 30(1/2/3/4/5/6/7): 107-117.

[11]WENGJ,LIME-P,JIANGJ,etal.TwitterRank:findingtopic-sensitiveinfluentialtwitterers[C]//WSDM2010:Proceedingsofthe3rdACMInternationalConferenceonWebSearchandDataMining.NewYork:ACM, 2010: 261-270.

[12]LIUY,GUOJ,SHENJ.Influencemaximizationalgorithmbasedongeneticalgorithm[J].JournalofComputationalInformationSystems, 2014, 10(21): 9255-9262.

ThisworkispartiallysupportedbytheNationalNatureScienceFoundationofChina(61472340),theTechnologyPlanProjectsofHebeiProvince(15210913).

LIU Yuanying, born in 1977, Ph.D.candidate, lecturer.Her research interests include online social network.

GUO Jingfeng, born in 1962, Ph.D., professor.His research interests include data mining, online social network.

WEI Lidong, born in 1962, M.S., associate professor.His research interests include data mining.

HU Xinzhuan, born in 1978, Ph.D.candidate, associate professor.Her research interests include online social network.

Fast influence maximization algorithm in social network under budget control

LIU Yuanying1,2*, GUO Jingfeng1, WEI Lidong2, HU Xinzhuan1

(1.SchoolofInformationScienceandEngineering,YanshanUniversity,QinhuangdaoHebei066004,China;2.CollegeofInformationTechnology,HebeiUniversityofEconomicsandBusiness,ShijiazhuangHebei, 050061,China)

Concerning the high time complexity in influence maximization under budget control, a fast influence maximization algorithm, namely BCIM, was proposed.Firstly, a new information dissemination model which propagates the initial nodes for many times was proposed.Secondly, the nodes with high influence ranking value were selected as candidate seeds, and the calculation of node’s influence scope was decreased based on the short distance influence.Lastly, only one seed was selected at most in each set of candidate seeds by using the dynamic programming method.The experimental results show that, compared with Random (random algorithm), Greedy_MII (greedy algorithm based on the maximum influence increment) and Greedy_MICR (greedy algorithm based on the maximum of influence increment over cost ratio), the influence scope of BCIM is near to or a bit better than that of Greedy_MICR and Greedy_MII, but much worse than that of Random; the quality of seeds set of BCIM, Greedy_MICR and Greedy_MII is similar, but much better than that of Random; the running time of BCIM is several times of Random, while the running time of the both greedy algorithms are hundreds times of BCIM.In summary, BCIM algorithm can find a more effective seeds set in a short time.

influence maximization; online social network; budget control; dynamic programming; multi-propagation model

2016- 08- 12;

2016- 09- 08。 基金项目:国家自然科学基金资助项目(61472340);河北省科技计划项目(15210913)。

刘院英(1977—),女,河北石家庄人,讲师,博士研究生,CCF会员,主要研究方向:在线社会网络; 郭景峰(1962—),男,河北秦皇岛人,教授,博士,CCF会员,主要研究方向:数据挖掘、在线社会网络; 魏立东(1962—),男,河北石家庄人,副教授,硕士,主要研究方向:数据挖掘; 胡心专(1978—),女,河北石家庄人,副教授,博士研究生,主要研究方向:在线社会网络。

1001- 9081(2017)02- 0367- 06

10.11772/j.issn.1001- 9081.2017.02.0367

TP312

A