社交网络影响力最大化研究综述

社交网络影响力最大化研究综述

摘 要

近年来，随着互联网的发展，社交网络得到飞速的发展并且得到人们越来越多的关注。许多研究工作致

力于社交网络的分析，社交网络中的影响力传播问题的研究具有很实际的现实意义，它在市场营销、广告发布、舆情预警以及社会安定等方面有十分重要的应用。因此，本文对社交网络影响力最大化问题的定义、传播模型和算法的研究现状进行了调研分析，希望对社交网络影响力最大化问题有一个整体的认识。 关键词

社交网络；影响力；传播模型；病毒式营销

1引言

近年来，随着互联网和个人电脑的普及，Facebook、Flikr、Twitter、人人网、新浪微博等社交网络得到迅速发展，社交网络也成为研究的热点。社交网络分析从19世纪20年代早期开始发展，主要研究社会实体之间的关系，经过几十年多个学科领域的许多学者的努力，社交网络的相关研究也随着可获取的数据量的飞速增长及计算能力的大幅度提高取得了显著的成果，社交网络已经形成了比较完善的研究体系。社交网络中的网络社区结构问题、重叠社区发现问题、影响力最大化问题、节点聚类问题等。但社交网络中丰富的数据也给知识发现和数据挖掘领域带来前所未有的挑战和机会。

社交网络[1]是通过网络这一载体把人们连接起来，从而形成具有某一特点的团体，是指由个体及个体之间的关系所组成的一个复杂网络，这种复杂的社会结构对信息的传播和扩散起着至关重要的作用，当一个人采纳一个新的思想或接受一种产品时，他会向他的朋友或同事推荐，某些人可能会接受或采纳他的推荐，并进一步向他们自己的朋友或同事推荐，这个过程称为传播或扩散。一个人的行为在很大程度上取决于周边的朋友或同事的决定。社交网络是复杂网络的一种类型，文献[2]中详尽的介绍了复杂网络的相关理论和知识。

社交网络中的影响力最大化问题的研究有着十分重要的现实意义，它在市场营销、广告发布、舆情预警以及社会安定等方面有十分重要的应用。影响力最大化问题[3, 4]的提出要追溯到对于 “病毒式营销”[5-7]和“口碑效应”[8-10]的研究，社交网络影响力最大化问题首次由Domingos和Richardson提出的[3, 4]，影响力最大化问题可概括为：给定一个社交网络图和一种特定的影响力传播模型，给定初始的传播节点个数，如何在网络上确定这些初始的节点集合(这些集合中的节点初始时是被激活的)，然后遵循影响力节点的传播机制，从这些集合中的节点开始传播，使最终被影响的节点数目达到最多，其形式化的表述如下：

给定一个社交网络G(V, E)，V为节点集合，E为边的集合，对于给定参数k，k是一个正整数，如何从网络G中选择k个初始节点结合A，满足|A|=k且A?V，按照某种传播策略，由这k个初始的节点开始影响其它节点，并使最终被影响的节点数目达到最大，用如下形式表示：

max{?(A),|A|?k,A?V}

其中，?(A)为集合A最终影响的节点数目。

从影响力最大化的问题定义中可以看出，影响力最大化算法首先要保证受影响的节点数目尽可能的多，其次是在尽可能短的时间内找到k个初始的节点。如果受影响的节点数目比较少，即使时间再短也没多大的意义，相反，如果受影响的节点比较多但是找到k个初始的节点的效率非常低，这种情况下也没有多大的意义。所以，影响力最大化问题的目标是在尽可能短的时间内找出k个初始的节点并使最终受影响的节点数目达到最大。

影响力最大化问题被Domingos和Richardson引入到社交网络领域后，已成为社交网络领域的一个研究热点，如今，已有各种算法用于求解社交网络上的影响力最大化问题，如贪心算法、OASNET算法、CGA算法、HPG算法等。当然信息扩散有其本身的规则或者模型，当前所有社交网络影响力最大化问题的研究都是基于影响力传播模型的，目前，影响力传播模型主要有两种：线性阈值模型和独立级联模型，本文在第2节详细介绍这两种模型；在第3节介绍基于这两种传播模型的影响力最大化算法，并对这些算法进行分析；最后总结全文。

2影响力传播模型

社交网络上的影响力最大化问题需要借助于相应的影响力传播模型，在研究中一般将社交网络抽象成一个图G(V, E)，其中V为网络中个体的集合，E为网络中个体之间交互和关系的集合；网络G上的每个节点初始时刻有两种状态，即激活和未激活，只有处于激活状态的节点且对它指向的节点才具有影响力，未激活的节点则对它指向的节点没有影响力，当一个节点被其它节点成功影响时，称此节点被激活；当一个节点被激活的邻居节点越来越多，该节点被激活的概率则越来越大，直到某一时刻该节点被激活，被激活的节点又可以影响它指向的节点，每个节点只能由未激活状态转化为激活状态，不能反向转化。

社交网络影响力最大化要解决的问题是如何选取k个种子节点进行信息的传播和扩散，使得最终被激活的节点个数最多。社交网络中的传播过程是：当一个节点被激活时，它会尝试激活与它连接的每一个未被激活的邻居节点，当邻居节点被激活时，它又会尝试激活它自己的邻居节点，这种过程会一直持续，直至没有新的节点被激活为止。目前，社交网络影响力传播中最常见的主要有两种传播模型：独立级联模型和线性阈值模型，下面进行详细的描述[1, 11]。 2.1 独立级联模型

独立级联模型(Independent Cascade Model，IC模型)是一种概率模型，当一个节点v被激活时，它会以概率pvw对它未激活的出边邻居节点w尝试激活，这种尝试仅仅进行一次，而且这些尝试之间是相互独立的，即v对w的激活不会受到其它节点的影响。独立级联模型的信息传播过程为：

(1) 给定初始的活跃节点集合S，当在时刻t节点v被激活后，它就获得了一次对它的邻居节

点w产生影响的机会，成功的概率为pvw，是随机赋予的系统参数，其自身独立不受其它节点的影响，该值越大，节点w越有可能被影响。

(2) 若w有多个邻居节点都是新近被激活的节点，那么这些节点将以任意顺序尝试激活节点w。

如果节点v成功激活节点w，那么在t+1时刻，节点w转为活跃状态。

(3) 在t+1时刻，节点w将对其它节点产生影响，重复上述过程。

需要注意的是，在上述传播过程中，在t时刻无论节点v是否能成功激活它的邻居节点，在以后的时刻中，v本身虽然仍保持活跃状态，但它已经不再具备影响力，即在t时刻被激活的节点，已经尝试激活它自身的邻居节点后，在t+1时刻仍然处于活跃状态，但它本身已经不能去激活其它任何节点，这一类节点成为无影响力的活跃节点。当网络中不存在有影响力的活跃节点时，传播过程结束。

目前关于独立级联模型的影响力最大化研究很多，IC模型的特点是它仅仅考虑v与出边邻居w之间的激活关系，完全不考虑w的其它入边邻居对w的影响。但是由于是概率模型，它的激活过程是不确定的，对于同一个网络，同样的种子节点进行激活得到的最后结果可能会差异较大。Kemple和Kleinberg认为pvw并不是独立的，随着时间的推移会变的越来越小。也就是说w已经被其它很多节点尝试激活过多次都没有成功，新激活的邻居节点v对w的影响力就会被削弱，由此提出了一个新的模型叫做递减级联模型[12](Descreasing Cascade Model)。 2.2 线性阈值模型

线性阈值模型(Linear Threshold Model，LT模型)是一种价值积累模型，它对每个节点v都有一个激活阈值?v?[0,1]。线性阈值模型的信息传播过程如下：

(1) 给定集合中的任意节点v随机分配阈值?v?[0,1]，该阈值表示这个节点受影响的难易程度，

?v越小，表示节点v越容易被影响，?v越大，表示该节点v越难被影响。只有当节点v的

新处于激活状态的邻居节点对它的影响力大于该阈值时，节点v才能被激活； (2) 用权值bwv表示节点v被它的邻居节点w的影响，

w?in(v)?bwv?1表示节点v的处于活跃状态

的邻居节点对它的影响力之和。这里in(v)是v的入边邻居节点集合。

(3) 给定初始的活跃节点集合A（网络中其余所有节点均处于非活跃状态），给网络中每个节点

任意分配一个阈值，在t时刻，所有在t-1时刻处于活跃状态的节点仍保持活跃，并且当这一时刻节点v的邻居节点的影响力之和大于节点v的阈值时，节点v被激活，即节点v被激活的条件是v已激活的入边邻居对v的积累影响大于v的激活阈值，如下式所述：

w?in(v),active(w)?0?bwv??v

(4) 节点v被激活后，下一时刻将对它的邻居节点产生影响，重复上述过程。

在LT传播模型中，当网络中已存在的所有活跃节点中任意活跃节点的影响力之和都不能激活他们的处于非活跃状态的邻居节点时，传播过程结束。

在LT模型中，它的激活过程是确定的，当我们对一个图用同样的种子节点来激活时，最后的传播范围是完全一样的。当一个激活节点w尝试去激活它的未激活邻居节点v而没有成功时，节点w对节点v的影响力bwv会被“积累”下来，而不是被抛弃，这种积累对后面节点v的其它邻居对v的激活时有贡献的，直到节点v被激活或传播过程结束，这表明LT模型的激活工程是一种合作激活的过程，每次的激活尝试都会被累积下来，这就是LT模型的影响积累特性，这和IC模型是不同的。

2.3 其他传播模型

完全级联传播模型[13]用一个可增减的函数来表示活跃节点u影响节点v的概率，该模型表示每个节点如何影响其他节点，如果用S表示v的邻居中已经尝试激活v但未激活成功的节点集，则活跃结点u影响不活跃的邻居节点v的概率为：

pv(u,S)?pv(u)?k?|S|?pv(u)

|V|其中k?{?1,0,1}；|V|是V的基数；S?N(v)；|S|是S的基数，pv(u)是节点u影响节点v的初始概率。因为缺乏节点间影响何时该增强、何时该减弱的相关知识，所以用随机选择方法模拟这种情况。该模型不仅表示了每个节点如何影响其他节点，而且表示了节点的影响力如何受节点之前的交互所影响。具有影响力的节点是以动态变化的概率激活其邻居节点的，更加接近于现实情况。

Kempe[12]等人也提出了其它传播模型，如普通阈值模型(general threshold model)和普通级联模型(general cascade model)。当然还有其他的传播模型：巴斯模型[6]、投票模型[14]、SIR模型(传染病传播模型)[15]等。总之在做影响力最大化的传播过程中都需要使用相应的传播模型来定义相应社交网络上的传播机制。

3影响力最大化算法

3.1 贪心算法

为了找到模型中要求的初始扩散集合Sk，一个简单有效的策略是每一步根据算法的标准确定初始集合中的一个节点，直到找到k个节点。为了便于介绍算法，令：

(1)S0??；

(2)I(Si)：集合Si扩散后已激活节点的集合；

(3)m(u|Si)?|I(Si?{u})|?|I(Si)|：节点u相对于集合Si的边际影响范围。

Kempe和Kleinberg等[12]证明了影响力最大化问题是一个NP完全问题，并提出了一个贪心算法(简称KK算法)，它能保证在1-1/e的范围内接近最优解：算法每一步都选择当前最具影响力的节点。从S0开始，在第i步，根据局部最优策略选择节点u，并令Si?Si?1?{u}，u?argmaxm(v|Si?1)，

v重复上述步骤，直至|S|=k为止。算法终止，这样就可以得到初始的k个平均影响力最大的激活节点。

贪心算法求解影响力最大化问题结构简单，易于理解，Kemple和Kleinberg指出贪心算法最大的优点就是能够得到稳定的解，算法的结果至少能保证得到最优解的63%，但是其缺点非常明显，每一步都要计算所有未激活节点u的边际影响m(u|Si)，时间复杂度非常高。对于一般上百个节点的网络，都需要较长的时间来完成搜索初始节点的工作，更别说上千上万以上的大型网络，因此，贪心算法只适合于小型网络。

Leskovec等[16]利用IC模型的子模特性给出了KK算法的改进方法CELF算法。CELF优化方案运用了影响力最大化目标的子模特性[12]，子模函数是一个“收益递减”的函数，即添加一个节点v到种子集合S中所获得的边际收益(marginal gain)，不能小于添加相同的元素v到S的父集合所获得边际效益，用公式f(S?{v})?f(S)?f(T?{v})?f(T)来表示。利用子模函数的性质可以大

大降低评价节点影响力传播工作的次数，从而降低影响力节点的增加度，减少每次选择初始节点的计算量。CELF利用子模特性，在每一步选择初始种子节点时，大量节点的增量影响不需要被重新计算，这是因为它们在之前步骤中的值已经小于其它节点在当前步骤中的值，它缩短了KK算法的时间，但在影响范围上没有提高。

Chen等[17]在[12, 16]的基础上继续改进贪心算法的时间复杂度并且提出了新的降低度数的启发式算法(degree discount algorithm)改进影响力传播，Chen基于独立级联模型(Independent Cascade Model, IC模型)和权重级联模型(Weighted Cascade Model, WC模型)提出了改进的贪心算法NewGreedyIC、MixedGreedyIC、NewGreedyWC以及MixedGreedyWC和一种改进的度数最大化算法DegreeDiscountIC算法。NewGreedy算法是从原始网络中去掉对传播没有影响的边，得到一个小网络，然后从小网络中去做影响传播，这样可不需要每次都在整个网络上去考虑。MixGreedy算法是先用NewGreedy算法计算第一步，第二步到最后用CELF算法[16]，把两者结合起来使用，实验结果表明，这两个改进的算法都比贪心算法的时间复杂度低，但是相比度数最大算法，时间复杂度还是很高。

DegreeDiscount算法[17]是选取度数最大节点的探索式算法[12]的一种改进。该算法的思想是当一个节点v的邻居节点中有一些节点已经被选作为初始的节点，在选取下一个度数最大的节点时，对于节点v，不能仅仅考虑v的度数，应该对节点v的度数做一个折扣，然后再选出折扣之后度数最大的若干节点。实验结果表明DegreeDiscount算法的效果相比直接选取度数最大的探索式算法有改进。虽然这些算法改进了贪心算法的时间复杂度，但是时间复杂度仍然很高，不适合于大型的网络。

3.2 基于度数的节点选择策略

节点的中心度常用来衡量一个节点在网络中的作用和重要程度，也是判断网络中关键节点的重要指标。在影响力最大化问题提出之后，刚开始只是使用一些探索式的方法来求解影响力最大化问题，如随机算法，度中心算法和MaxDegree等探索式算法[18]，它们的最大优点是时间复杂度小，可以处理任意大的网络，因为它们在选取初始的激活节点只需要统计一些节点的网络性质，如度中心性、度数等，然后利用这些性质直接选择k个初始的激活节点如最大的k个度中心性最大的几点等，最后去统计它们的影响力。这些启发式算法最大的缺点是不能得到稳定的解，效果会随网络的变化在变化，其中度中心性算法和MaxDegree算法又比随机算法的结果要好。在这些启发式的算法中MaxDegree算法是比较简单有效的一种探索式算法，其思想是在网络中直接选取前k个度数最大的节点作为初始的激活节点。因此，在某些情况下使用MaxDegree算法求解影响力最大化问题是可行的，一方面其时间复杂度低，另一方面它的效果是比较好的。虽然MaxDegree算法能够快速的选取初始最具影响力节点，但是在选取节点的时候可能会出现邻居重叠的缺点。为避免这种情况，可以在每个社区中选取一个节点作为初始的最具影响力的节点，这样就可以将初始节点分散到各个社区中，这样能够促进信息更快更好的传播。

选取度数最大的算法是求解影响力最大化问题比较好的探索式算法，Pablo等人[19]提出了一种基于探索式算法的改进算法SCG算法。SCG算法的思想是为了避免选取的度数最大的节点有邻

居重叠的情况，尽可能将这些初始的节点分散。SCG算法中定义每个节点的邻居节点为与它的最短路径?m（m可以自己设定）的节点集合，这样在选择第一个度数最大的节点之后，将这个节点的邻居节点排除，然后从剩余的节点中选择度数第二大的节点。依次下去，这样保证选取的初始度数最大的节点不会出现邻居重叠的情况，有效的提高了节点的传播。实验结果表明它的时间复杂度比贪心算法要低很多，效果比简单的选择前k个度数最大算法要好。

中心度是分析社会网络的一个最重要的和常用的概念工具之一。它是关于行动者在社会网络中的中心性位置的测量概念，反映的是行动者在社会网络结构中的位置或优势的差异。在一个社会网络中，某节点度数最高，该点就居于中心位置，这表明该点所对应的行动者为此网络中的中心人物即最具影响力的人物[20]。在社会网络和其它网络中，以度数递减的顺序选择k个最大度数节点的启发式节点选择策略，是长期以来的一个标准方法，在社会科学中被称为“度中心性”。此方法的一个缺点就是静态选择初始节点，没有考虑影响的扩散过程，不能保证最终影响范围最优。 3.3 基于社区的影响力最大化算法

基于社区的影响力最大化算法主要利用现有的社区发现算法，将网络分成若干个社区，然后在每个独立的社区上应用已有的影响力最大化算法求解，Galstyan等[21]第一次提出了利用网络的社区性质来求解影响力最大化问题。Galstyan虽然使用了社区性质来求解问题，但是方法只是局限在由两个松散社区组成的随机网络，这种选取方法有很多局限性，因为很多的社交网络都不止两个社区。OASNET算法和CGA算法是目前两种应用社区发现算法来求解影响力最大化问题的算法。 3.3.1 OASNET算法

OASNET算法[22]利用网络的社区性质把影响力最大化问题看成一种最优的资源动态分配问题而提出的一种算法，利用社区发现算法[23]将网络划分为各个独立的社区，然后利用动态规划的方法将初始的节点最优的分配到各个社区，然后将各个社区中被影响的节点累加得到最终被影响的节点数目。

利用社区发现算法找到社区之后，OASNET算法求解影响力最大化问题的公式如下：

d??Fi(ki,Gi,Mi,Γi)i?1n?k?kii?1n

其中，n为社区的个数；k为给定的初始的激活节点个数；Fi(ki,Gi,Mi,Γi)是求可达节点的函数；ki代表给第i个社区分配的节点的个数；Gi代表第i个社区，即第i个网络；Mi代表给第i个网络使用的传播模型为LT模型或IC模型；Γi为给第i个社区所使用的传播算法。该问题的目标是如何将k个初始的激活节点分配到各个社区，使各个社区的影响力之和达到最大。OASNET算法使用动态分配的方法：

OPT(k,n)?MAX{F(i,Gn,Mn,Γn)}?OPT(k?i,n?1),0?i?k

其中，OPT(k, n)代表分配给前n个社区k个节点所获得影响力最大值。对于第i个社区，可以给这个社区分配0到k个节点，求出Fi(ki,Gi,Mi,Γi)，从而可以得到OPT(k, 1)，利用上述公式可以

计算出OPT(k, 2),…., OPT(k, n)，从而得到将k个节点最佳的分配到n个社区，使获得的影响力最大。

OASNET算法分为三部分，第一部分是使用Newman等人提出的社区发现算法[23]来对网络进行社区发现，这部分的时间复杂度为O(n(log2n)2)；第二部分是对每个社区分配1到k个节点求其影响力的值，这部分时间复杂度为O(kmM)，其中k为初始分配的节点个数，M为模拟传播的次数，m为网络的边数；第三部分求最佳分配的时间复杂度为O(Nk2)，N为社区的个数。OASNET算法的时间复杂度主要由第二部分决定，因此，算法的时间复杂度为O(kmM)，相比贪心算法的时间复杂度有不少的提高。

OASNET算法首次提出把影响力最大化算法看成是资源的动态分配问题，而且证明了这种资源分配方法求解影响力最大化也是一个NP难问题，OASNET算法的特点是利用动态分配方法求解初始节点分配问题，虽然OASNET算法与均等分配算法、比例分配算法、随机分配算法和全局网络上的度数最大化算法相比有改进，但是OASNET算法有一个缺点是它假设全局网络通过社区发现后被分成各个独立的社区，然而实际社交网络中的各个社区之间还是有很多联系，将全局网络划分为独立社区之后会导致边的损失而影响最终被影响的节点数。 3.3.2 CGA算法

CGA[24]算法的总体思想和OASNET算法类似，也是根据社区发现算法将网络划分成各个独立的社区，然后把问题转化为将初始激活节点个数最佳的分配到各个社区，最后将各个社区影响力值求和得到最大的影响力值。

CGA算法针对从通话日志中提取的移动通话社交网络进行研究，将移动通话社交网络抽象为有向带权图G(V, E, W)，网络中的手机用户抽象为节点V，用u到v的有向边E表示用户u向用户v拨通电话，边上的权值W表示通话时长。CGA算法使用独立级联模型进行信息传播，但在独立级联模型中边上不存在权值，而在移动社交网络中，边上的权值是一个很重要的参数，权值越大表明节点间的联系越密切，节点越有可能被激活。因此，CGA算法将边上的权值和独立级联模型中的传播概率联系起来，构成独立级联模型的一个特例：带权独立级联模型。该模型中，边上权值越大则该边的传播概率越大。

CGA算法首先进行社区划分，在社区划分完成后，需要解决的问题主要是从哪些社区中选择影响力最大的节点，最简单的方法是从每个社区中平均选择，但这会带来不必要的计算量，在这里CGA算法中提出了一个动态规划算法用来确定选择影响力最大节点的社区。令Zk-1表示在第k-1步已经选择出的影响力最大节点的集合，用?Rm表示影响度的最大增量。公式1定义当第k个影响力最大节点在社区Cm中选择时基于社区Cm算出的影响度最大增量。

?Rm?max{Rm(Zk?1?vj)?Rm(Zk?1)|vj?Cm} (1)

为找到第k个影响力最大的节点，首先要找到所有社区中会产生影响度增量的社区。令

R[m,k](m?[1,M],k?[1,K])表示在前面m个社区中找到第k个最大影响力节点后得到的影响度。

R[m,k]?max{R[m?1,k],R[m,k]??Rm}R[m,0]?0,R[0,k]?0

上述公式表示若用前m-1个社区中找到的第k个节点计算所得的影响度小于在第m个社区中找到的第k个节点计算所得的影响度，则第k个节点就从社区Cm中选择，否则从前Cm-1个社区中选择。从前m个社区中选择一个社区用来找出第k个最大影响力节点，若被选出的社区用函数s[m, k]表示，则：

?s[m?1,k]s[m,k]???ms[0,k]?0R[m?1,k]?R[m.k?1]??RmR[m?1,k]?R[m.k?1]??Rm

CGA算法用函数s[m, k]选择用来找出第k个最大影响力节点的社区Cm。与OASNET相比，CGA算法是使用贪心算法作为各个社区寻找初始的影响力节点的算法，而OASNET算法是使用度数最大的算法。由于贪心算法的时间复杂度比度数最大算法的时间复杂度高很多，因此CGA算法的时间复杂度也比OASNET算法高很多。CGA算法由于将网络划分成各个小的网络，因此它相比贪心算法时间复杂度有很大数量级的降低。但是CGA算法使用贪心算法作为社区的寻找算法，时间复杂度依然比较高，而且由于网络分成各个独立社区之后会导致边的减少而影响效果。 3.4 对网络进行稀疏化

Michael提出了一种对网络结构进行稀疏化的方法来大量减少网络中边的数量[25, 26]，从而达到在较少的损失影响范围的情况下大量减少算法运行时间。Michel考察了现实社交网络中一些行为

?的传播路径，基于这些行为对网络进行稀疏化，使得稀疏化以后的网络让?中每一个可达的点

仍然可达，而且计算了所有这些行为的总的概率：

??logL?(G)??(logP(v)?logP??(v))

v?V??这里P?(v)表示v在?行为中可达的概率，相对的P?(v)表示v在?行为中不可达的概率。

最后使得稀疏化后的图中logL?(G)能达到最大，而且logL?(G)???，最终图中的边能得到大量的削减。但是，该方法是基于IC模型的，利用了概率最大化来稀疏化最终图，所以对LT模型并不适用。

3.5 混合式影响力最大化算法HPG

参考文献[19]中提到度数大的节点往往都处在社会网络的中心位置，KK算法考虑影响的传播过程能够达到最优值的63%[12]，田佳堂等[1]综合度中心性和贪心算法的优势并结合LT模型“积累特性”，提出了一种利用节点的度数outDegree(u)和节点u的潜在影响力的启发式算法HPG算法，HPG算法混合了启发式算法和KK算法。HPG算法分两个部分：首先是启发阶段，选取最具潜在影响力的节点，这部分节点虽然在当前不能带来最大的影响力，但却蕴含着巨大的潜在影响力；然后是贪心阶段，选取最具影响力的节点。

为了找到潜在影响力最大的节点，通过网络结构分析和实验发现有两个因素影响最具潜在影响力节点的选择[1]：节点的度数(outDegree)和一个激活节点对其所有未激活节点邻居影响力之和(inf)。HPG算法选择以节点的度数作为最具潜在影响力节点的选择，并综合考虑inf因素。潜在影响力

PI(Potential Influence)定义如下：

inf(u)?v?N(u),v?A(u)?0?buv

PI(u)?outDegree(u)?(1?e?inf(u))其中，N(u)表示u的出边邻居节点集合，A(u)表示N(u)中已激活的节点，buv表示节点u对v的影响力。因此，inf(u)表示节点u施加于所有未激活邻居节点的影响力之和，我们称之为节点u的影响力，它由节点u未激活邻居的个数以及buv大小这两个因素决定。outDegree(u)表示节点u的出度，当节点的出度相同时，选择影响力较大的节点，而不是盲目随机的选择一个度数最大的节点作为当前潜在影响力最大的节点。因此，最具潜在影响力的节点就是PI值最大的节点。

HPG算法将k个初始节点的选择分为两个阶段：启发阶段和贪心阶段。首先利用启发式算法来选择k???ck??个种子节点来激活网络，启发阶段每一步选取PI值最大的节点u作为种子节点激活网络；贪心阶段利用KK算法选取剩余??ck??个种子节点，但是HPG算法的启发阶段并没有考虑每个节点阈值不同的情况，仅仅将buv进行相加，而且若buv??v，则buv表明v节点提供了超过一个节点的价值，这显然不太合理。但是HPG算法没有考虑在不同节点不同激活阈值的问题，而且无法在启动因此c较小的情况下得到较好的激活范围，即无法在较小的复杂度下得到好的激活范围。 3.6 基于节点激活阈值的启发式算法

陈浩等利用线性阈值模型提出了一种基于节点激活阈值的启发式算法[11]，该算法分为两个阶段：第1个阶段为启发阶段，并不像KK算法那样寻求局部最优，而是通过LT模型的影响累积特性来启发式寻找那些能够提供最大潜在影响的节点作为种子节点；第2个阶段则是在第1个阶段激活的基础上，利用KK算法局部最优的特性来尽可能扩展影响范围。它综合考虑了节点之间的影响力和节点的激活阈值，根据每个节点在激活过程中动态变化的阈值来计算PIN值，启发过程中，每一次都选取PIN最大的节点作为种子节点进行激活，贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点，该算法的复杂度相对较小。 3.7 其他相关算法

集合覆盖贪心算法[19]每次选择最高“uncovered”度数的节点，一旦一个节点被选中，它的所有邻居节点被标记为“covered”，这个过程一直持续k步．它选择覆盖范围最大的节点，但是在影响最大化的约束下，覆盖并不等于激活，所以其实验结果并不好。文献[27, 28]中讨论了如何在作者合作网络中找到k个研究员，使得与他们合作的其他研究员人数最多，这是影响力最大化问题的一个特例。

Kimura等[29]提出了一种通过分解极大联通子图去寻找影响力最大的节点的算法，实验结果表明算法的时间复杂度相比贪心算法降低了很多，而且效果和贪心算法差不多，是处理影响力最大化比较好的一个方法，但是这个算法在处理大型网络的时间复杂度仍然非常高。

Eyal等[14]把投票模型(Voter Model)引进到影响力最大化中来，通过分析Voter模型把影响力最大化问题转化为一种求解概率的问题，因为选民的投票也是一种概率策略，很多选民投票时会受周

围人的影响。Eyal等借助Voter模型然后利用启发式的算法(包括随机算法、最小路径算法、度数最大化等算法)来选择初始节点去求影响力最大化问题。

4结论

社交网络中对于影响力最大化问题的研究是近年来的研究热点之一，本文详细介绍了基本的影响力传播模型和几个主要的影响力最大化算法。从调研中发现，针对具体的社交网络，影响力最大化算法需要更合适的传播模型。在通用的LT模型和IC模型中，激活率是通过系统去随机给定，一旦给定这个传播概率则在此次试验的传播过程中将不会改变。这里面有两个问题，一是在实际的社交网络中，这个传播概率很难去界定，更需要根据实际情况来处理网络的传播概率；二是由于社交网络是动态变化的，节点之间的影响也是动态的，节点之间的这种激活概率也是动态变化的，因此，在针对具体社交网络求解影响力最大化问题时需要考虑合适的传播模型。

5参考文献

1. Tian, J., Y. Wang and X. Feng, A new hybrid algorithm for influence maximization in social networks.

Jisuanji Xuebao(Chinese Journal of Computers), 2011. 34(10): p. 1956--1965.

2. Boccaletti, S., et al., Complex networks: Structure and dynamics. Physics reports, 2006. 424(4): p.

175--308.

3. Domingos, P. and M. Richardson. Mining the network value of customers. 2001.

4. Richardson, M. and P. Domingos. Mining knowledge-sharing sites for viral marketing. 2002.

5. Goldenberg, J., B. Libai and E. Muller, Using complex systems analysis to advance marketing theory

development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review, 2001. 9(3): p. 1--18.

6. Mahajan, V., E. Muller and F.M. Bass, New product diffusion models in marketing: A review and

directions for research. The Journal of Marketing, 1990: p. 1--26.

7. Bass, F.M., Comments on “A New Product Growth for Model Consumer Durables The Bass Model”.

Management science, 2004. 50(12 supplement): p. 1833--1840.

8. Brown, J.J. and P.H. Reingen, Social ties and word-of-mouth referral behavior. Journal of Consumer

Research, 1987: p. 350--362.

9. Goldenberg, J., B. Libai and E. Muller, Talk of the network: A complex systems look at the underlying

process of word-of-mouth. Marketing letters, 2001. 12(3): p. 211--223.

10. Ma, H., et al. Mining social networks using heat diffusion processes for marketing candidates selection.

2008.

11. Hao, C. and W. Yitong, Threshold-Based Heuristic Algorithm for Influence Maximization. Journal of

Computer Research and Development, 2012. 10: p. 019.

12. Kempe, D., J. Kleinberg and E.V. Tardos. Maximizing the spread of influence through a social network.

2003.

13. 冀进朝, 韩笑, 王喆, 基于完全级联传播模型的社区影响最大化. 吉林大学学报: 理学版, 2009.

47(005): p. 1032--1034.

14. Even-Dar, E. and A. Shapira, A note on maximizing the spread of influence in social networks. Internet

and Network Economics, 2007: p. 281--286.

15. 汪小帆, 李翔, 陈关荣, 复杂网络理论及其应用. 2006: 清华大学出版社有限公司. 16. Leskovec, J., et al. Cost-effective outbreak detection in networks. 2007.

17. Chen, W., Y. Wang and S. Yang. Efficient influence maximization in social networks. 2009. 18. 兰如钦, 社会网络上的影响力最大化算法研究. 2011, 北京交通大学.

19. Estevez, P.A., P. Vera and K. Saito. Selecting the most influential nodes in social networks. 2007. 20. 景天魁, 林聚任, 社会网络分析: 理论, 方法与应用. 2009, 北京: 北京师范大学出版社.

21. Galstyan, A., V. Musoyan and P. Cohen, Maximizing influence propagation in networks with community

structure. Physical Review E, 2009. 79(5): p. 056102.

22. Cao, T., et al. OASNET: an optimal allocation approach to influence maximization in modular social

networks. 2010.

23. Clauset, A., M.E. Newman and C. Moore, Finding community structure in very large networks. Physical

review E, 2004. 70(6): p. 066111.

24. Wang, Y., et al. Community-based greedy algorithm for mining top-k influential nodes in mobile social

networks. 2010.

25. Mathioudakis, M., et al. Sparsification of influence networks. 2011.

26. Gomez-Rodriguez, M., J. Leskovec and A. Krause, Inferring networks of diffusion and influence. ACM

Transactions on Knowledge Discovery from Data (TKDD), 2012. 5(4): p. 21.

27. Suri, N.R. and Y. Narahari. Determining the top-k nodes in social networks using the shapley value. 2008. 28. Narayanam, R. and Y. Narahari, A shapley value-based approach to discover influential nodes in social

networks. IEEE Transactions on Automation Science and Engineering, 2010(99): p. 1--18.

29. Kimura, M., K. Saito and R. Nakano. Extracting influential nodes for information diffusion on a social

network. 2007.

12. Kempe, D., J. Kleinberg and E.V. Tardos. Maximizing the spread of influence through a social network.

2003.

13. 冀进朝, 韩笑, 王喆, 基于完全级联传播模型的社区影响最大化. 吉林大学学报: 理学版, 2009.

47(005): p. 1032--1034.

14. Even-Dar, E. and A. Shapira, A note on maximizing the spread of influence in social networks. Internet

and Network Economics, 2007: p. 281--286.

15. 汪小帆, 李翔, 陈关荣, 复杂网络理论及其应用. 2006: 清华大学出版社有限公司. 16. Leskovec, J., et al. Cost-effective outbreak detection in networks. 2007.

17. Chen, W., Y. Wang and S. Yang. Efficient influence maximization in social networks. 2009. 18. 兰如钦, 社会网络上的影响力最大化算法研究. 2011, 北京交通大学.

19. Estevez, P.A., P. Vera and K. Saito. Selecting the most influential nodes in social networks. 2007. 20. 景天魁, 林聚任, 社会网络分析: 理论, 方法与应用. 2009, 北京: 北京师范大学出版社.

21. Galstyan, A., V. Musoyan and P. Cohen, Maximizing influence propagation in networks with community

structure. Physical Review E, 2009. 79(5): p. 056102.

22. Cao, T., et al. OASNET: an optimal allocation approach to influence maximization in modular social

networks. 2010.

23. Clauset, A., M.E. Newman and C. Moore, Finding community structure in very large networks. Physical

review E, 2004. 70(6): p. 066111.

24. Wang, Y., et al. Community-based greedy algorithm for mining top-k influential nodes in mobile social

networks. 2010.

25. Mathioudakis, M., et al. Sparsification of influence networks. 2011.

26. Gomez-Rodriguez, M., J. Leskovec and A. Krause, Inferring networks of diffusion and influence. ACM

Transactions on Knowledge Discovery from Data (TKDD), 2012. 5(4): p. 21.

27. Suri, N.R. and Y. Narahari. Determining the top-k nodes in social networks using the shapley value. 2008. 28. Narayanam, R. and Y. Narahari, A shapley value-based approach to discover influential nodes in social

networks. IEEE Transactions on Automation Science and Engineering, 2010(99): p. 1--18.

29. Kimura, M., K. Saito and R. Nakano. Extracting influential nodes for information diffusion on a social

network. 2007.

本文来源：https://www.bwwdw.com/article/j916.html