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

社交网络影响力最大化研究综述摘要近年来，随着互联网的发展，社交网络得到飞速的发展并且得到人们越来越多的关注。许多研究工作致力于社交网络的分析，社交网络中的影响力传播问题的研究具有很实际的现实意义，它在市场营销、广告发布、舆情预警以及社会安定等方面有十分重要的应用。因此，本文对社交网络影响力最大化问题的定义、传播模型和算法的研究现状进行了调研分析，希望对社交网络影响力最大化问题有一个整体的认识。关键词社交网络；影响力；传播模型；病毒式营销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{(),||,}AAkAV其中，()A为集合A最终影响的节点数目。从影响力最大化的问题定义中可以看出，影响力最大化算法首先要保证受影响的节点数目尽可能的多，其次是在尽可能短的时间内找到k个初始的节点。如果受影响的节点数目比较少，即使时间再短也没多大的意义，相反，如果受影响的节点比较多但是找到k个初始的节点的效率非常低，这种情况下也没有多大的意义。所以，影响力最大化问题的目标是在尽可能短的时间内找出k个初始的节点并使最终受影响的节点数目达到最大。影响力最大化问题被Domingos和Richardson引入到社交网络领域后，已成为社交网络领域的一个研究热点，如今，已有各种算法用于求解社交网络上的影响力最大化问题，如贪心算法、OASNET算法、CGA算法、HPG算法等。当然信息扩散有其本身的规则或者模型，当前所有社交网络影响力最大化问题的研究都是基于影响力传播模型的，目前，影响力传播模型主要有两种：线性阈值模型和独立级联模型，本文在第2节详细介绍这两种模型；在第3节介绍基于这两种传播模型的影响力最大化算法，并对这些算法进行分析；最后总结全文。2影响力传播模型社交网络上的影响力最大化问题需要借助于相应的影响力传播模型，在研究中一般将社交网络抽象成一个图G(V,E)，其中V为网络中个体的集合，E为网络中个体之间交互和关系的集合；网络G上的每个节点初始时刻有两种状态，即激活和未激活，只有处于激活状态的节点且对它指向的节点才具有影响力，未激活的节点则对它指向的节点没有影响力，当一个节点被其它节点成功影响时，称此节点被激活；当一个节点被激活的邻居节点越来越多，该节点被激活的概率则越来越大，直到某一时刻该节点被激活，被激活的节点又可以影响它指向的节点，每个节点只能由未激活状态转化为激活状态，不能反向转化。社交网络影响力最大化要解决的问题是如何选取k个种子节点进行信息的传播和扩散，使得最终被激活的节点个数最多。社交网络中的传播过程是：当一个节点被激活时，它会尝试激活与它连接的每一个未被激活的邻居节点，当邻居节点被激活时，它又会尝试激活它自己的邻居节点，这种过程会一直持续，直至没有新的节点被激活为止。目前，社交网络影响力传播中最常见的主要有两种传播模型：独立级联模型和线性阈值模型，下面进行详细的描述[1,11]。2.1独立级联模型独立级联模型(IndependentCascadeModel，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](DescreasingCascadeModel)。2.2线性阈值模型线性阈值模型(LinearThresholdModel，LT模型)是一种价值积累模型，它对每个节点v都有一个激活阈值[0,1]v。线性阈值模型的信息传播过程如下：(1)给定集合中的任意节点v随机分配阈值[0,1]v，该阈值表示这个节点受影响的难易程度，v越小，表示节点v越容易被影响，v越大，表示该节点v越难被影响。只有当节点v的新处于激活状态的邻居节点对它的影响力大于该阈值时，节点v才能被激活；(2)用权值bwv表示节点v被它的邻居节点w的影响，()1wvwinvb表示节点v的处于活跃状态的邻居节点对它的影响力之和。这里in(v)是v的入边邻居节点集合。(3)给定初始的活跃节点集合A（网络中其余所有节点均处于非活跃状态），给网络中每个节点任意分配一个阈值，在t时刻，所有在t-1时刻处于活跃状态的节点仍保持活跃，并且当这一时刻节点v的邻居节点的影响力之和大于节点v的阈值时，节点v被激活，即节点v被激活的条件是v已激活的入边邻居对v的积累影响大于v的激活阈值，如下式所述：(),()0wvvwinvactivewb(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的概率为：||()(,)()||vvvkSpupuSpuV其中{1,0,1}k；|V|是V的基数；()SNv；|S|是S的基数，pv(u)是节点u影响节点v的初始概率。因为缺乏节点间影响何时该增强、何时该减弱的相关知识，所以用随机选择方法模拟这种情况。该模型不仅表示了每个节点如何影响其他节点，而且表示了节点的影响力如何受节点之前的交互所影响。具有影响力的节点是以动态变化的概率激活其邻居节点的，更加接近于现实情况。Kempe[12]等人也提出了其它传播模型，如普通阈值模型(generalthresholdmodel)和普通级联模型(generalcascademodel)。当然还有其他的传播模型：巴斯模型[6]、投票模型[14]、SIR模型(传染病传播模型)[15]等。总之在做影响力最大化的传播过程中都需要使用相应的传播模型来定义相应社交网络上的传播机制。3影响力最大化算法3.1贪心算法为了找到模型中要求的初始扩散集合Sk，一个简单有效的策略是每一步根据算法的标准确定初始集合中的一个节点，直到找到k个节点。为了便于介绍算法，令：(1)0S；(2)()iIS：集合Si扩散后已激活节点的集合；(3)(|)|({})||()|iiimuSISuIS：节点u相对于集合Si的边际影响范围。Kempe和Kleinberg等[12]证明了影响力最大化问题是一个NP完全问题，并提出了一个贪心算法(简称KK算法)，它能保证在1-1/e的范围内接近最优解：算法每一步都选择当前最具影响力的节点。从S0开始，在第i步，根据局部最优策略选择节点u，argmax(|1)ivumvS，并令1{}iiSSu，重复上述步骤，直至|S|=k为止。算法终止，这样就可以得到初始的k个平均影响力最大的激活节点。贪心算法求解影响力最大化问题结构简单，易于理解，Kemple和Kleinberg指出贪心算法最大的优点就是能够得到稳定的解，算法的结果至少能保证得到最优解的63%，但是其缺点非常明显，每一步都要计算所有未激活节点u的边际影响(|)imuS，时间复杂度非常高。对于一般上百个节点的网络，都需要较长的时间来完成搜索初始节点的工作，更别说上千上万以上的大型网络，因此，贪心算法只适合于小型网络。Leskovec等[16]利用IC模型的子模特性给出了KK算法的改进方法CELF算法。CELF优化方案运用了影响力最大化目标的子模特性[12]，子模函数是一个“收益递减”的函数，即添加一个节点v到种子集合S中所获得的边际收益(marginalgain)，不能小于添加相同的元素v到S的父集合所获得边际效益，用公式({})()({})()fSvfSfTvfT来表示。利用子模函数的性质可以大大降低评价节点影响力传