文摘

最具影响力的个人影响力最大化问题的目标是识别,以便在发展中有效的病毒式营销策略在社交网络。先前的研究主要集中在设计有效的算法或启发式在一个静态的社交网络。事实上,现实世界的社交网络不断随着时间的发展,在改变和重新计算网络就不可避免地导致长时间运行的时间。在本文中,我们提出一种增量式方法,IncInf,这可以有效地定位——顶部根据以往的信息影响个人发展的社交网络而不是从头计算。特别是IncInf定量分析了影响传播变化的节点通过本地化拓扑演化的影响只有当地的地区,和修剪策略进一步提出缩小搜索空间为节点经历主要增加或高度。评估效率和效果,我们进行了大量的实验实际动态社会网络:Facebook, NetHEPT和Flickr。实验结果表明,与先进的静态算法相比,IncInf达到显著加速执行时间,同时保持匹配性能的影响蔓延。

1。介绍

在线社交网络的日益普及促进了信息的扩散,意见,采用新产品等等,为智能病毒式营销提供了巨大的机遇。效益最好的口碑效应,影响力最大化(IM)是一个基本的和重要的问题,旨在确定一组小的个人影响力,开发有效的病毒式营销策略对一个给定的社交网络的影响力最大化(1]。事实上,现实世界的社交网络随着时间不断的演变。例如,在Facebook,新人们会加入,虽然旧的可能撤离,人们可能相互结交新朋友。此外,现实世界的社交网络发展在一个相当惊人的速度;据报道,多达100万每天在Twitter创建新帐户2]。这样的大规模网络拓扑结构的演化,相反,可能会导致一个重要的网络结构的转换,从而提高reidentification自然需要高效。

现有研究和解决方案影响最大化主要关注发展中有效和高效的算法在给定的静态的社交网络。尽管人们可能运行的任何静态影响最大化方法,如(3- - - - - -6),找到新的最高有影响力的个人网络更新时,这种方法有一些固有的缺点不容忽视:()一个特定的静态方法的运行时间非常漫长而不可接受的,尤其是在大型社交网络,和()网络拓扑发生变化时,我们需要重新计算所有节点的传播影响,导致很高的成本。我们能快速有效地识别发展的社交网络的影响力的节点?我们可以逐步更新影响力节点基于之前所知信息而不是从头开始频繁地重新计算?

不幸的是,迅速和不可预知的改变动态社会网络的拓扑结构提出了一些挑战reidentification的有影响力的用户,我们列表如下。一方面,边在现实社会之间的联系图相当复杂;拓扑结果,连一个小变化可能影响的影响传播大量的节点,更不用说在大规模社交网络的巨大变化。很难有效地计算影响价差的变化,进化后的所有节点。另一方面,因为有大量的节点在大型社交网络,如何有效地限制范围的潜在影响力的节点和减少计算量最大的是一个非常具有挑战性的问题。

要应对这些挑战,我们调查动态特性表现出在真实的社会网络的演化过程。通过测试三个真实数据集的痕迹,Facebook, NetHEPT,和Flickr,我们观察到,首先,社交网络的增长主要是基于优惠附件原理(7];即新边喜欢附着程度较高的节点,这自然导致了“rich-get-richer”现象;其次,顶部-有影响力的节点主要从那些高度选择节点。受这样的观察,我们知道,某些节点的影响变化没有影响——顶部选择可以修剪,从而减少计算。出于这一点,我们提出IncInf,增量识别方法——顶部有影响力的节点发展的社交网络,而不是从头开始重新计算,从而大大促进了效率和可伸缩性来处理非常大规模的网络。总之,IncInf的主要贡献如下。

首先,我们设计一个有效的方法来定量分析网络拓扑演化的影响传播的变化采用本地化的想法。提供了一个可调参数之间的权衡效率和有效性。

其次,我们提出一个修剪策略,可以有效地缩小搜索空间为节点只有经历主要高度变化的基础上增加或影响传播和前前信息。

第三,我们进行广泛的实验在三个动态真实的社交网络。与最先进的静态算法相比,IncInf达到显著加速执行时间,同时提供匹配的影响蔓延。此外,IncInf提供了更好的可伸缩性非常大规模的网络规模。

本文的初步版本出现在[8),我们提出了IncInf算法的基本思想。在本文中,我们提出以下额外的贡献。首先,我们添加相应的实验来比较IncInf与IMM (9)的影响传播和运行时间。第二,我们测试我们的剪枝策略的效果来证明其有效性。第三,我们添加一个新的实验来评估定位参数的敏感性和修剪阈值传播和运行时间的影响。

本文的其余部分组织如下。节2,我们展示了相关工作。部分3提出了相关的预赛和问题定义。部分4显示动态社会网络的结构演化特征,我们观察从三个数据集:Facebook, NetHEPT和Flickr。部分5细节的设计我们IncInf增量算法。IncInf的性能评估的综合实验部分6。我们在部分总结本文7。

2。相关工作

对静态网络的影响力最大化吸引了大量的关注。陈等人提出的爬山贪婪算法效率低,最近提出了许多有效的算法来解决这个问题。Leskovec et al。5]利用submodularity影响力的传播功能和开发一个优化的贪婪算法,CELF,比基本的贪婪算法快得多。陈等人。3提出MixGreedy,计算每个种子的传播影响设置在一个单一的模拟和包含CELF优化。MIA (4)使用当地的每个节点的树状结构近似的影响蔓延,从而获得效率通过限制计算,只更新到本地区域。然而,米娅只考虑静态网络,而在本文中,我们专门设计一个增量算法发展的社交网络。最近,王et al。10)提出一个社区贪婪算法(CGA)考虑到夫妻共同财产。Goyal等人提出CELF + + (11],进一步利用的性质submodularity扩散函数,以避免不必要的重新计算的边际收益和大大提高CELF算法的效率。老大(12荣格提出的)也是一个启发式et al .,包含影响有影响力的排名算法估计方法实现可伸缩性。刘等人。13)设计一个新的框架来加速的影响最大化利用GPU的并行处理能力。陈等人。14)开发一个以社区为基础的框架来解决影响最大化问题重点是效率问题。唐et al。9)设计一个鞅方法,试图找到顶部在近似线性时间节点。,在(15王),提出了一种方法来获得每个节点边际贡献的欧文价值并部署在网络恐怖主义网络分析。陆等人研究的复杂性影响最大化问题的确定性线性阈值模型(16]。在[17),陆等人展示如何有效地估计线性阈值下的影响力传播的影响力最大化模型。在[18),阮和郑关注预算影响最大化(BIM)问题,旨在选择种子节点的总成本不超过固定预算。汉et al。19]研究及时性的影响最大化网络,设计一种新颖的算法,包括延时时间和机会选择承兑比率。刘等人。20.]提出的时间限制的影响最大化问题,发展一套并行算法实现节省更多的时间。裴et al。21)利用亚临界路径的概念,提出CI-TM,集体影响最佳渗透二阶转换算法。

在动态社会网络影响力最大化问题仍然很大程度上是未知的。因此et al。22)和Michalski et al。23提出一个动态社会网络模型,和我们是不同的。在他们的建议,网络传播过程中不断演变影响,和他们的目标是找到——顶部在这样一个动态的网络影响力的节点。(相比22,23),我们的工作是基于快照图模型和我们的目标是逐步确定最高有影响力的节点拓扑结构变化的基础上两个相邻快照。陈等人。24]扩展集成电路模型将影响扩散的时间延迟方面个体在社会网络和考虑时效性的影响最大化,一个想要最大化传播的影响力在给定的期限。与此同时,在[25),作者考虑一个连续时间制定的影响力最大化问题可以传播信息或影响以不同的速率在不同的边缘。Aggarwal et al。26]试图发现影响节点动态社会网络和他们设计一个随机的方法来确定全球信息流当局使用方法和一个本地落后的方法。他们的影响模式和目标不同于我们的。壮族et al。27)认为,在线社交网络的发展不能完全观察和探索战略设计的实际影响扩散过程可以最好的发现与探索节点。通等。28)主要关注这一事实真实的动态社会网络的扩散过程的许多方面uncertainness和提出一个方法,选择种子用户以自适应的方式。

3所示。预赛和问题陈述

在本节中,我们说明了社交网络的定义和影响扩散模型,我们将使用在纸上,然后给影响力最大化问题定义的不断发展的网络。

3.1。预赛上影响最大化

社交网络。一个社交网络正式定义为一个有向图 ,节点集 表示实体的社交网络。每个节点可以是活动或活动,将开关从非活动变成活跃的如果是受其他节点的影响。边集 是一组定向边缘代表不同的用户之间的关系。将Twitter作为一个例子。一个有向边 从节点将成立吗来如果紧随其后的是 ,这表明可能是受到 。 表示边缘的影响概率;每条边 概率与影响 定义的函数 。如果 ,然后 。

独立级联(IC)模型。集成电路模型是一个受欢迎的扩散模型,深入研究[3,6,10,29日]。给定一组初始 ,集成电路模型的扩散过程如下。步骤0,只有节点是活跃的,而其他节点在不活跃的状态。在步骤 ,为每个节点刚刚从思想活跃不活跃的,它有一个机会来激活每一个目前不活跃的邻居和成功的概率 。如果成功,将成为活跃在一步 。如果有多个新激活的邻居,他们在激活吗以任意顺序排序。这样的流程运行,直到没有更多的激活是可能的(29日]。我们使用表示初始传播的影响 ,被定义为预期数量的活跃节点的传播影响。

基本的贪婪算法。多明戈和理查德森(1,30.)首次于2001年在静态网络影响力最大化问题。在[29日),肯普等人提出一个基本的爬山贪婪算法如算法所示1。提出了贪婪算法迭代,从一个空集((行))。在每个迭代中,一个节点带来最大的边际影响传播 选择要包括在吗((行)和())。这个过程结束时的大小到达((行))。然而,该算法有一个严重的缺点由于计算密集型影响传播的计算效率。最近的一些研究[3- - - - - -6,10,12,31日- - - - - -35为了解决效率问题。

3.2。IM问题发展网络的正式定义

本文从以前作品的不同之处就在于考虑在线社交网络的动态特性。事实上,现实世界的社交网络并不完全静态但将会逐渐进化的时间。大型社交网络的发展提出了新设置的问题;其中一个有趣而富有挑战性的问题是如何快速识别——顶部有影响力的用户当网络的拓扑结构发生了变化。

为了解决这样的问题,我们定义了一个不断发展的网络 一系列网络快照发展随着时间的推移, 是网络快照时间 。 表示网络图的结构变化 。显然,我们有 。和影响力最大化问题定义如下:

鉴于。《社交网络》在时间 ,——顶部有影响力的节点在 ,和构造演化的图 。

客观的。目的是识别影响力的节点 的大小在在时间 ,这样传播的影响扩散是最大化的影响。

4所示。社交网络进化的观察

在本节中,我们研究社会网络演化的一些模式。节点和边的数目是首先调查部分4.1检查用户的增长和互联。然后,我们考虑节点的度分布和优惠附件规则新的边缘部分4.2。我们进一步研究之间的关系的影响,在部分节点的程度4.3。我们研究三个网络痕迹,即Facebook, NetHEPT,和Flickr的详细描述可以在部分6。这里我们只显示结果在Facebook上,因为其他数据集上的进化趋势定性相似,因此被省略了。

4.1。网络发展有多快?

节点和边的基本元素是社交网络拓扑。在本节中,我们使用节点和边的数量来检查用户的增长和互联。图1说明了节点和边的数量在整个跟踪期在Facebook数据集;我们将每个月一个快照。从图1,我们观察一个线性节点数量的增加,这表明有稳定数量的新用户加入网络每月。同时,在边缘上,数量上升几乎成倍增长。边的数量后14个月的25.6 x初始图而上升到112.9 x 28个月。节点和边的快速成长提出了一个自然需要有效地找到之后最具影响力的节点拓扑演化。

4.2。网络拓扑演化的模式是什么?

了解网络拓扑演化的模式是最重要的设计有效的影响最大化算法发展的社交网络。在本节中,我们进一步研究节点的度分布和附件优惠规则(7,36,37新到来的边缘)。图2(一个)显示了度分布的Facebook最终在双对数图的规模。正如所料,主要遵循众所周知的幂律分布。大量用户的百分比只有一小部分与其他用户的链接,虽然存在一些“集线器”节点以极大量的连接。这是符合现实世界的网络。

我们也研究附件优惠规则或者,换句话说,“rich-get-richer”规则(38),假设,当一个新节点加入网络时,它会创建一个边数,每条边的目的节点选择与目的地的程度成正比。这意味着新边更有可能连接到节点高度较低的比学位。这是合理的在现实中;Lady Gaga收益平均每天新增30000追随者(39),没有任何常见的个人形象。Facebook的数据集的结果显示在图2 (b),在那里设在节点和程度不同设在新边连接到节点的平均数量不同的程度。请注意,这两个设在和设在在对数尺度。从图2 (b),我们可以看到用户在Facebook是线性的程度与新创建的链接的数量。这表明,高度节点获得超级优惠待遇。因此,影响传播改变应该相当大影响力的节点,虽然可能只是普通人小,甚至没有变化。

4.3。影响和程度之间的关系是什么?

研究影响和节点的程度之间的关系可以帮助我们理解的影响程度改变的影响传播节点上。出于这个原因,我们运行静态MixGreedy算法(3)在最后一个图和标识位有影响力的节点。Facebook的数据集的结果见图3,在那里设在是程度的不同节点的等级(我们只显示前150名)。显然,所有选中的有影响力的节点有一个很大程度上。特别是,在50个节点,48个节点排在前100名的61096个节点的度,和其他两个节点等级102年和111年,分别。同时,NetHEPT和Flickr上的数据集,一位有影响力的节点被选中节点度从1.79%和0.84%,分别。这表明,顶部有影响力的节点主要从那些有大量选择度。然而,值得注意的是,顶部影响力的节点影响力最大化通常不是最高节点在程度排名,因为不同节点的影响力传播可能互相重叠。

5。IncInf设计

在本节中,我们提出IncInf的详细设计,增量的方法来解决在动态社会网络影响力最大化问题。IncInf的主要思想是充分利用的有价值的信息网络中固有的构造演化和之前的有影响力的节点,大大缩小搜索空间有影响力的节点。这样,IncInf可以显著降低计算复杂性,提高效率。图4简要说明了的总体想法IncInf在动态社会网络。——顶部有影响力的节点的在时间 逐渐的确定是基于前面的有影响力的节点在时间和结构变化从来 。特别是,我们设计一个有效的方法来定量分析不同结构变化的影响的影响传播节点采用本地化的概念(部分5.2),提出一个修剪策略来减少潜在的影响力节点(部分5.3)。我们首先描述了六种基本操作动态网络拓扑演化的部分5.1。

5.1。拓扑演化的基本操作

社交网络的演变,反映到它的基本图,可以概括为六大类,插入或删除一个节点,引入或删除一条边,增加或减少的影响概率优势。我们表示六个类型的拓扑变化 , , , , ,和 。详细的描述和对影响传播的影响如表所示1。

应该注意的是,只有在操作节点建立链接(一个 )或切断链接( )与其他节点,节点只能删除所有相关的边被删除。此外,体重操作可以等同于分解成两个边操作。例如, 可分为 和 ,假设以前的重量的优势是 。

5.2。影响传播的变化

正如上面所讨论的,当一个优势从社交网络,引入或删除所有节点的影响力传播可达节点可能会改变。然而,事实上,现实世界的社交网络具有小世界网络特征和节点之间的联系是非常复杂的。结果,甚至一个小拓扑的变化,比如添加或删除,可能影响的影响传播大量的节点,因此引入大量的重算。为了减少计算量,我们设计一个有效的计算方法上的变化影响的传播节点,采用本地化的想法(4)并试图限制影响扩散到当地区域的节点。

本地化的主要思想是利用每个节点的局部区域近似其整体影响传播。特别是,我们使用的最大影响路径近似从节点传播的影响来 。这里最大的影响路径从节点来在图被定义为最大影响的路径概率在所有从节点的路径吗来并且可以正式描述如下: 在哪里表示传播路径的概率和 表示节点的所有路径来在图 。对于一个给定的路径 传播路径的概率定义如下: 此外,阈值产生影响精度和效率之间的权衡。在传播过程中,我们只考虑路径的影响概率大于而忽略那些概率小于 。通过这样做,影响有效地限制在每个节点的局部区域。

同样,在我们的提议,我们本地化拓扑变化的影响在影响扩散到当地的区域,从而减少计算量。在六种拓扑变化,(或)是最简单的,因为它只是影响的传播节点设置为1或0);和以及必须方法类似于 。因此,在接下来,我们将作为一个例子展示哪些节点的影响传播需要更新,如何确定这些变化当一个新的边缘添加到图。

考虑当一个新的优势 介绍了现有的两个节点之间和 。我们之前和之后表示图这样的拓扑变化和 ,和当前种子集 。详细算法描述的算法2。根据定位的原则4),如果传播概率小于指定阈值比的概率 ,边缘可以简单地忽视和不需要更新任何节点的影响力传播((行)- ())。否则,新添加的边缘将成为 。因此,每个节点最大的影响路径有一个影响概率大于可能会经历一个上升的影响力传播(线()因为节点可能会影响更多的节点通过新优势 。所以,我们然后检查的概率最大的影响路径来及其继任者和 。基于这两个概率,我们将问题划分为两个小的情况。

第一种情况下,最大的影响路径的概率来在小于 ,同时,在大于((行)- ())。在这里表示节点的概率大于 。在这种情况下,节点构建一个新的路径通过新的边缘 ,这就增加了影响的传播通过 ((行))。在这里事实上,节点的概率是受到当前种子准备好了吗 ,这是定义如下: 在这里表示in-neighbour组 。

第二种情况是当最大影响路径的概率来大于在这两个和((行)- ())。在这种情况下,节点的影响力增加是 。

我们对待网络动力学来作为一个有限改变流 ,每个变化是六个我们前面描述的拓扑变化。当所有的变化改变流处理,我们可以得到所有节点的影响传播改变。接下来,我们将展示如何有效地找到最高有影响力的节点在新的图基于这些影响传播变化和之前的有影响力的节点信息。

5.3。潜在的前有影响力的用户识别

灵感来自于观察的部分4,我们设计一个修剪策略减少搜索空间的潜在影响力的节点在本节。假设我们只知道——顶部有影响力的节点图 ,但是他们详细的影响的扩大,超出了我们的知识。原因主要是两个方面。首先,一些影响最大化算法,如DegreeDiscount [3),不计算影响传播信息识别有影响力的用户,这样这些信息不可用。第二,即使这些信息是准备好,储存成本一样内存空间,节点的数量在吗 。大规模真实社交网络通常以来,这将引入严重的存储开销和直接影响到可伸缩性。

优惠附件的规则,我们知道这些高度的影响传播变化节点应该远远大于普通节点。此外,根据幂律分布,这种高度节点只占一小部分的节点。因此,我们只能挑选节点经历主要增加或度高,因为这些节点成为顶级——巨大的潜力有影响力的节点 。然后我们只计算这些所选节点的实际影响的扩大,而忽略了他人。通过这种方式,一个大比例的节点修剪和搜索空间在很大程度上是狭窄的。应该注意的是,一个聪明的修剪策略是至关重要的,因为一个可怜的选择可能影响效率或减少疾病传播方面的精度影响。我们描述的细节我们的剪枝策略如下:(1)在th迭代,如果前面的影响传播影响力的节点增加 ,所选节点传播变化比那些更大的影响 。在大多数情况下,有影响力的节点将会吸引大量的新节点和建立新的连接。因此,他们的影响力传播将大幅增加。在这种情况下,不可能影响传播的节点变化小于影响力节点成为最具影响力的节点 。因此,当之前的影响传播影响力节点增加时,我们只选择那些影响变化大于传播影响力的节点 。根据附件优惠规则,这样的修剪方法可以大大缩小搜索空间,减少计算量。(2)在th迭代,如果前面的影响传播影响力的节点减少 ,除了资格1、节点进一步选择举行一个足够大的学位或经验足够大的增加。为了正式定义“很大程度上”和“增加”,在这里我们设定一个阈值运行时间和影响传播之间的权衡。足够大的节点度(或增加)被定义为节点的集合的程度(或学位比例增加)在前吗所有节点的百分比 。程度增加的比例被定义为 ,在那里表示节点的程度在图 。在部分实验结果6将演示,5%可能是良好的运行时间和影响传播之间的权衡。应该注意的是,尽管先前的情况下,影响传播影响力节点减少进化中很少发生,我们认为这里的完整性。在这种情况下,除了资格1、因为我们进一步选择节点的节点数量满足条件1是相对较大,从而导致大规模计算。与此同时,在现实中,一个节点小程度上只有很低的概率成为一个有影响力的节点。为了只选择最具潜力的节点,我们细化要求,另外选择节点很大程度上和大幅增加。因此,严格限制搜索空间和计算复杂度大大降低。

潜在的节点被选中后,我们计算的实际影响传播这些节点并选择最大的影响在每个迭代中传播。算法3概述了我们的算法IncInf的设计。IncInf迭代的轮(线(),在每一轮选择一个节点,提供最大的边际影响传播。行()- ()计算每个节点的影响传播改变引起的拓扑演化。节点与巨大的潜力成为最高有影响力的选择(线())和他们的影响力扩散计算((行)- ())。然后提供最大的节点边际收益将选择并添加到集合中((行)- ())。

6。实验

在本节中,我们提出我们的算法的实验结果确定前在动态社会网络影响力的节点。我们检查两个指标,运行时间和影响扩散,评估效果以及不同算法的执行效率。详细的实验结果部分6.2,6.3,6.4。

6.1。实验装置

我们选择三个真实的社交网络,Facebook的社交网络,NetHEPT引文网络,社交网络和Flickr(表2总结了数据集的统计信息):(我)Facebook:这个数据集是友谊关系网络在新奥尔良地区网络在Facebook上,从2006年9月到2009年1月(40]。有超过60 K用户连接在一起的1.5链接的社交网络。41.4%的边缘不包含时间信息,因此丢弃。在我们的实验中,节点和链接从2006年9月到2007年4月被用作第一个快照,然后网络快照记录每3个月(2)NetHEPT:这是一个学术引用网络(41)提取arXiv的“高能物理理论”部分在此期间从1992年到2003年,覆盖28 K论文的引文数据集内与352 K边缘。在我们的实验中,前三年(即引文链接。,从1992来1994)are considered as the basic graph and the network snapshots are recorded once a year(3)Flickr:这个数据集42]包含Flickr的社交网络的用户链接爬每日在此期间从2006年11月2日到2006年12月3日再一次从2007年2月3日到2007年5月18日,代表共计104天的增长。有完全2.5 Flickr用户和33 M链接。在这段时间的观察,在970万个新链接形成和超过950000个新用户加入网络。在我们的实验中,我们使用2006年11月2日之前网络作为基本图形和另外五个快照记录12月3日,2月3日,3月3日,4月3日、5月18日

我们比较我们的算法和五个静态算法:MixGreedy,ESMCE,米娅,IMM,随机。MixGreedy改进贪婪算法在IC陈等人提出的模型在3]。ESMCE是一个幂律指数监督评估方法由刘等人在[设计6]。米娅是一个启发式,使用当地的每个节点的树状结构近似的影响传播(4]。唐等人设计的IMM算法是一种基于鞅估计技术和能够运行在近似线性时间9]。随机是一个基本的启发式随机选择节点在整个数据集。

传播的概率随机选择的集成电路模型0.1,0.01和0.001为每个网络快照。评估算法的参数设置为作者建议。IMM的参数和分别设置为0.5和1的实验。的设置在米娅,如上所述6.4的膝盖点影响扩散曲线可以作为很好的调优点效率和有效性之间的权衡。例如,Facebook的膝盖点的影响力扩散曲线和NetHEPT 1/180和1/200,分别。的价值为特定的数据集在实验中选择根据曲线拐点得到最好的权衡。ESMCE,置信水平设置为95%,最大蒙特卡罗误差阈值设置为5%。IncInf的价值设置类似于米娅,也就是说,膝盖的影响力扩散曲线,而的价值在部分设置为5%,建议吗6.4运行时间和影响传播之间的权衡。

6.2。效率研究

在本节,我们的算法的效率进行了研究并与相应的静态算法,MixGreedy MIA,通过实验在Facebook, NetHEPT和Flickr的数据集。实验是在PC与英特尔酷睿i7 920 @2.67 GHz CPU和6 GB RAM。四种算法的运行时间是衡量选择50种子从整个数据集。

不同的算法的时间成本是如图5,我们记录每个快照的时间总成本的三个数据集。自增量和静态算法有相同的时间成本在初始快照,图中省略了。实验结果表明,我们的算法在每个快照的时间成本明显低于静态的算法。显然,MixGreedy需要最长的时间在四种影响最大化算法。需要MixGreedy超过6小时确定位有影响力的节点最后NetHEPT数据集,而更大的数据集Facebook上的时间更长。此外,MixGreedy不是可行的最大的数据集上运行Flickr由于运行时间久。ESMCE,得益于其抽样估计的方法,比MixGreedy跑得快,但它仍然需要平均高达3511秒的五个快照Flickr上运行。与两个贪心算法相比,启发式米娅和鞅方法IMM执行得更好。只需要米娅23.8秒(IMM 8.2秒,职责。)最后的脸谱图上运行。在Flickr上运行数据集时多达2.5节点和边缘33米,然而,IMA的加速还远非令人满意,因为它仍然需要超过45分钟完成。 Comparatively, IMM performs better than MIA and it takes IMM nearly 10 minutes to locate the influential nodes. Meanwhile our proposed algorithm, IncInf, outperforms all the static algorithms in terms of efficiency. In particular, IncInf is almost four orders of magnitude faster than the MixGreedy algorithm on the Facebook dataset. Compared with the MIA heuristic, the speedup of IncInf is 8.41x and 6.94x on the Facebook and NetHEPT datasets, respectively. What is more, when applied on the largest dataset Flickr, IncInf can achieve as much as 20.65x speedup on average. The efficiency of IncInf is only slightly better than IMM on our small dataset NetHEPT, but it performs considerably better than IMM on Flickr dataset: the running time of IncInf is only 40% on average of IMM on each snapshot. This is because IncInf only computes the incremental influence spread changes and adaptively identifies the influential nodes based on the previous influential nodes and the current influence spread changes. The experimental results clearly validate the efficiency advantage of our incremental algorithm IncInf. We can also observe that the running time of IncInf is not monotone like other algorithms as the time evolves. This is because the running time of IncInf is closely related to the topology change between two graph snapshots. An evident change in topology will usually lead to a relatively long running time and vice versa. Without doubt, Random runs the fast among all the algorithms. However, as we will show in Section6.3,其准确性是更糟,不能接受在开发实际的病毒式营销策略。

我们也测试我们的剪枝策略的影响。这里我们以Facebook的数据为例;结果在其他数据集相似,从而省略了。不同于其他的实验中,我们记录了Facebook图表从2006年9月到2007年10月(14个月)快照在这个实验中。之后,我们将每月快照作为快照 。我们使用IncInf找到最高快照中有影响力的节点基于的快照 。结果如图7。之间的时间间隔是设在快照和 ,和设在修剪后的节点数量的比例在快照的节点总数 。最小和最大修剪比率分别为3.90%和5.86%,分别平均比率为4.72%在所有14个快照之间的时间间隔和 。这表明我们的剪枝策略可以有效地限制搜索空间的一小部分节点。我们还可以看到在图7随着时间间隔的增加,比例,虽然不单调,通常变得更大。这主要是因为长时间间隔意味着更大数量的拓扑变化,基本上可以更多的节点成为有影响力的节点。

6.3。有效性研究

在本节中,我们研究的影响传播——顶部有影响力的节点选择算法以及其他静态算法。不同算法的影响的扩大,随着节点数量的测量受位有影响力的节点选择的影响。显然,传播影响力越高,效果越好。我们没有测试的性能MixGreedy Flickr数据集上运行时间过长。

图6给出了实验结果。MixGreedy优于其他算法的影响蔓延。然而,效率问题限制了其应用于大规模数据集,如Flickr。ESMCE的表演,米娅,IMM, IncInf几乎匹配MixGreedy Facebook的数据集,在NetHEPT差距变得更大,但仍可接受(只有3.4%,4.7%,4.5%,和5.1%低于MixGreedy平均)。当数据集应用到Flickr, ESMCE执行最好的,因为ESMCE严格控制误差阈值迭代采样。米娅几乎匹配IMM的影响力传播的三个数据集和略低于ESMCE。与米娅相比,IncInf显示非常接近平均性能和低只有2.87%的所有五个快照,这表明我们的建议的有效性。基线的启发式随机,显然所有图上表现最糟糕的。实际上,随机的影响传播仅为15.6%,12.1%,和10.9%的人在Facebook上IncInf NetHEPT,分别和Flickr。

我们将注意IncInf略低影响传播的原因主要是双重的。首先,IncInf限制影响到当地地区加快计算的影响传播的变化,这将影响其有效性。第二,修剪策略旨在缩小搜索空间的基础上影响传播和前——变化信息。尽管轻微损失效率,IncInf收益显著提高效率,如前所述。

6.4。优化的参数和

首先,我们研究如何有效地定位参数IncInf代表效率和有效性之间的权衡。我们运行IncInf具有不同的值在最后一个Facebook和NetHEPT图表。运行时间和影响传播基于种子大小的测量 。

实验结果如图所示8。请注意,设在代表的倒数 。我们观察到作为一个权衡效率和有效性:减少 ,IncInf和米娅取得更好的传播影响。然而,这是获得更长的运行时间为代价的,也就是说,可怜的效率。例如,当我们减少从1/200到1/500的Facebook数据集,IncInf影响传播的增加15.4%,在运行时间1.12倍长。此外,我们可以观察到的影响传播IncInf几乎在所有的值匹配的米娅 。例如,IncInf只有1.87%低于米娅在影响传播将于1/200 NetHEPT数据集。但IncInf显示运行时间的压倒性优势。当设置为1/500在Facebook, IncInf只需要5秒来识别位有影响力的节点,而需要米娅超过150秒完成相同的工作。更重要的是减少的 ,影响传播开始大幅增加,但增加后不再是那么重要降低到一定的水平。相反,运行时间几乎是线性的 。这表明的膝盖点影响扩散曲线可以作为很好的调优点 ,在那里我们可以得到最好的收益影响传播和运行时间。

然后,我们将评估修剪的敏感度阈值传播和运行时间的影响。结果见图9。从图9我们可以看到,增加的 ,运行时间增加轻轻一开始,然后变成了大幅提升。例如,当我们增加从1%提高到5%,IncInf的运行时间在Facebook数据集只会增加从2.13到8.47年代,虽然大幅增加从8.47到87.35从5%调到10%。这一现象密切相关学历,社交网络的幂律分布;当将大量相对大量的潜在的节点将被选中。

传播的影响,增加了 ,更多的节点选为潜在的节点,这将保证更好的传播影响。与运行时间不同,影响传播迅速增长,而开始,然后逐渐减慢。Facebook上的影响力传播数据集是7854年设置为1%,迅速增长到13967年的最大误差阈值是5%。之后,增长趋势减缓,影响传播大约是15091年增加到10%。解释这种现象的原因是——顶部有影响力的节点主要从高度选择节点。因此,当变得更大,尽管更多的节点将被选中,他们的贡献,以影响传播相对较小;因此,增长趋势减缓。基于以上观察,我们表明,5%可能站作为一个良好的运行时间和影响传播之间的权衡。

6.5。讨论

实验结果表明,我们建议的IncInf算法显著降低了先进的静态影响最大化算法的执行时间,同时保持令人满意的精度的影响蔓延。尽管IncInf性能更好,但它有一些局限性进行进一步的改进。

首先,IncInf直接取决于先前的信息前影响力的节点有效的修剪,而有时候这些信息是不完整的甚至是不可用。我们计划研究这个问题。其次,IncInf为IC设计的模式,这可能限制其应用。但我们相信,我们的想法增量计算的影响最大化可以适当扩展到其他影响扩散模型。

7所示。结论和未来的工作

在本文中,我们考虑发展的社交网络中的影响力最大化问题,提出一种增量式算法,IncInf,有效识别前在动态社会网络影响力的节点。利用网络的构造演化和以前的各个节点的信息,IncInf大大减少了搜索空间,自适应地选择有影响力的节点以增量的方式。大量实验证明IncInf显著减少先进的静态影响最大化算法的执行时间,同时保持令人满意的精度的影响蔓延。

有几本研究未来的发展方向。首先,IncInf巨大的潜在融入现代并行计算框架。这是因为IncInf限制计算变化影响扩散到当地的地区,这可以减轻社交图的分区并行计算。此外,该修剪策略可以有效地并行执行。其次,我们目前IncInf算法来源于基本集成电路模型。我们相信,增量的概念计算影响最大化可以适当扩展到其他影响扩散模型,如另一个经典肝移植模型。第三,虽然有一些研究[43)关于如何测量传播概率,这个问题还没有很好的解决,特别是大规模动态社会网络。

的利益冲突

作者宣称没有利益冲突。

确认

这项研究得到了国家自然科学基金委批准号下61402511。