基于最小点覆盖和反馈点集的社交网络影响最大化算法

许宇光 潘惊治 谢惠扬



基于最小点覆盖和反馈点集的社交网络影响最大化算法

许宇光①潘惊治①谢惠扬*②

①(北京大学信息科学技术学院 北京 100871)②(北京林业大学理学院 北京 100083)

社交网络中的影响最大化问题是指在特定的传播模型下，如何寻找个最具影响力的节点使得在该模型下社交网络中被影响的节点最多，信息传播的范围最广。该问题是一个优化问题，并且已经被证明是NP-难的。考虑到图的最小点覆盖和反馈点集中的顶点对图的连通性影响较大，该文提出一种基于最小点覆盖和反馈点集的社交网络影响最大化算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS)，并给出了具体的仿真实验和分析。实验结果表明，与最新的算法比较，该算法得到的节点集在多种模型下都具有优异的传播效果，例如在独立级联模型和加权级联模型中超过当前最好的算法，并且还具有更快的收敛速度。

社交网络；影响最大化；传播模型；最小点覆盖；反馈点集

1 引言

社交网络是指由个体及个体之间的关系所组成的一个复杂网络，它与交通网络，通讯网络和生物网络等其他复杂网络相比，包含了更加海量和多元化的信息。自从社交网络出现以来[1,2]，它便在社会个体的信息传播、思想引导和相互影响中发挥着重大作用。近年来，随着大规模在线社交网络(如人人，Facebook, Twitter和微博等)的迅速发展，从个人到个人和从个人到群体的相互作用中探索社会影响引起了人们的广泛兴趣，这是因为社会影响可以作为一种微妙的力量控制社交网络的动态性。为此，关于在大规模社会网络中挖掘对信息和思想的传播有影响的个体集的研究受到了大量学者的青睐。其中，一个关键问题是影响最大化问题，即如何选择个初始节点，使得它们在社交网络中的影响最大化。

关于影响力最大化算法的研究，目前主要有基于贪心思想的方法和启发式方法。其中，基于贪心思想的方法选出的节点传播效果较好，但是选择节点时算法效率较低，因此这类方法目前主要的研究方向是如何降低算法的运行时间，提高算法效率。文献[7,8]首次将影响最大化问题引入到社交网络中，他们考虑了个体之间的社会关系并提出了一种概率信息传播模型。随后，文献[9,10]首次将影响最大化问题描述成离散优化问题，并在两个不同的模型下，即线性值模型和独立级联模型，研究了此问题。他们证明了影响最大化问题在上述两个模型下是NP-难的。同时，他们提出了一种贪心算法，并证明了所提算法在这两种模型下的性能比为。 考虑到贪心算法效率不高的问题，文献[11]提出了“Lazy-forward”的优化策略来选择初始节点。2014年，文献[12]在研究基于线性阈值模型下的影响最大化问题时，为线性阈值的传播方程推导出了理论上界[13]。2014年，文献[14]提出贪心算法本质上是一种自一致性排序，即自身的排序和影响范围的增益相一致。

通常启发式方法选出的节点传播效果不如基于贪心思想的方法，但启发式方法算法效率较高，因此这类方法目前主要的研究方向是如何在保持其效率较高优势的前提下，改善选出节点的传播效果。文献[15]基于度提出了“Degree Discount”方法。文献[16]根据模拟退火法启发式求解影响最大化问题。文献[16-18]首次将潜伏限制加到线型阙值模型下的影响最大化问题中，并称其为快速信息传播问题(fast information propagation problem)。他们证明了该问题是NP-难的，并给出了两个启发式的算法来求解该问题。近年来，文献[19]提出了概括影响力公式的问题。文献[20]研究了社区结构和影响最大化问题的关系。文献[21]提出一种基于-核的社会网络影响最大化算法。文献[22]提出一种在独立级联模型下估计节点级联影响力的方法。

基于上述考虑以及图最小点覆盖和反馈点集中顶点的重要性，本文提出了一种基于最小覆盖集和反馈点集的近似求解影响最大化的算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS)。该算法同时考虑了最小点覆盖和反馈点集中顶点的影响力，具有很好的效果。实验结果表明，所提算法可以较快地找到具有较好影响范围的节点集。本文第2节介绍3种常用的传播模型；第3节介绍与本算法相关的概念，详细描述本文的算法，并对本算法的时间复杂度进行分析；第4节介绍实验设计及实验结果分析；第5节对本文成果进行了概括并探讨未来的工作。

2 传播模型

在研究社交网络时，社交网络通常被抽象成一个有向(无向)图，图中的节点代表参与社会活动的人，边代表人与人之间的联系。对于给定的社会网络，在网络中寻找影响力节点集，需要借助于相应的传播模型。线性阈值模型、独立级联模型和加权级联模型是3个常用的传播模型。在这些模型中，节点有活跃和不活跃两种状态可以选择。其中个体处于活跃状态时，表示该个体接受了这个信息；处于不活跃状态时，表示该个体没有接受这个信息。随着不活跃节点的活跃邻居数目的增加，节点也越倾向于变为活跃状态。

线性阈值模型(Linear Threshold Model, LTM)在线性阈值模型中，一个节点是否受到影响从不活跃状态变为活跃状态是由其邻居的共同影响力决定的。对于节点的邻居节点，将对的影响记为，则有。在该模型中，如果节点受活跃邻居的影响总和超过某个阈值，则由不活跃状态变为活跃状态。即满足公式时，节点被激活(即由不活跃状态变为活跃状态)，其中()表示的活跃邻居节点集。可以看出，越大，则节点越不容易被激活。因此可以反映出节点被激活的倾向性[23]。

独立级联模型(Independent Cascade Model, ICM) 在独立级联模型中，节点只有在刚被激活时才可以尝试去激活其邻居。假设是一个在时刻刚被激活的节点，则对于的每个不活跃邻居,可以以概率激活。若激活成功，则节点在时刻变为活跃节点；若不成功，仍然保持不活跃状态。无论是否成功激活其邻居，在以后的时刻都不能再尝试激活其他节点。如果在时刻不活跃节点有多个邻居都刚被激活，则其邻居节点对其的激活顺序对于最后结果没有影响。概率不依赖于之前所有对的激活尝试。传播过程以这种方式不断进行直到没有刚被激活的节点时停止[10]。

加权级联模型(Weighted Cascade Model, WCM) 加权级联模型可以看作是独立级联模型的一个特例。在该模型中，节点激活其不活跃邻居节点的概率与节点的度有关，。故当一个节点有很多邻居时，每个邻居对其的影响就会被平均到一个非常小的值，这在某种程度上可以反映出真实世界中的人际关系。例如，如果一个人只有一个朋友，那么这个朋友对他的建议就非常具有影响力，而如果他有很多朋友，那么其中一个朋友的建议对他作何决定的影响并不大[10]。

3 MVCFVS算法

由于社交网络通常被抽象成图来研究，所以本文的算法在理论上把图作为研究对象，最后在真实的社交网络数据集上进行实验来验证。

本文所言之图皆指无向有限连通简单图(无环无重边)。对于任意图，用()和()分别表示图的顶点集和边集。图的一个点覆盖是指()的一个顶点子集，使得()中的每条边至少有一个端点在中。如果不存在任何覆盖满足，那么称是的最小点覆盖。求一个图的最小点覆盖并非易事，该问题是NP-完全的[24]。

对于一个图，令是中的一个顶点。我们用N()表示中与相邻的所有顶点构成的集合。顶点的度，记作，定义成N()含有顶点的个数，即=|N()|。若=，那么称是的一个-点。和分别表示图的最大度和最小度。若中任意两个顶点之间都存在一条路，那么称为是连通的；否则，称为不连通。如果是不连通的，那么至少含有两个连通分支，用表示的连通分支的个数。不含圈的图称为无圈图，连通的无圈图称为树。

树最小点覆盖算法如表1所示。

表1 树最小点覆盖算法

定理1 对于任意树，算法1都得到的最小覆盖集。

证明 首先，我们证明存在一个最小点覆盖不含1-点。否则若的某个最小点覆盖含有1-点，那么将1-点从中删去，然后将与其相邻的顶点加入中，从而得到一个新的最小点覆盖。令是的一个不含1-点的最小点覆盖，那么即是按算法1得到的。因为，每个1-点关联的边如要被覆盖，那么与该1-点相邻的顶点必定在最小覆盖中。故包含算法1所选出的所有的顶点。另一方面，容易验证算法1选出的顶点集是的一个覆盖，所以，结论成立。 证毕

本文为给出MVCFVS算法，需要先找到图的反馈点集，于是本文提出了一个简单的图的反馈点集算法：

图反馈点集算法如表2所示。

表2 图反馈点集算法

定理2 对于任意图，算法2都得到的一个反馈点集。

证明 首先，对于任意连通图，经过步骤1后所得之图都是连通图，因为每次删去的都是1-点。其次，若一个图含有圈，那么经过步骤1后一定不是空图。所以，当算法结束时，即对应的是空图，所以对应的的每个分支都是树，从而，结论成立。 证毕

下面将应用上述两个算法给出本文求解影响最大化的算法MVCFVS。我们的思想是：对于一个图，首先利用算法2求出的一个反馈点集；其次，对于的每个树分支T，利用算法1求出树分支的最小点覆盖集C。第三，令含有个树分支，对于中的顶点，我们将按下述定义的影响力函数()，从大到小选出最有影响力的个顶点。

MVCFVS算法如表3所示。

表3　MVCFVS算法

因为反馈点集中的每个顶点都属于一个圈中，故有理由认为他们的全局影响力比较大。另外，最小点覆盖中的顶点的局部影响力比较大，从而可以认为由此算法筛选出来的个顶点的影响力比较大。下一节将给出具体的实验。

4 实验

为了验证算法的有效性，我们在真实的社交网络数据上进行了实验，用基于最小点覆盖和反馈点集的影响最大化算法(MVCFVS)在这些真实社交网络数据上选出种子节点，并通过不同的传播模型模拟他们的实际影响传播效果，然后和其他几种节点选择方法的影响传播效果比较，评价各自的优缺点，最后分析有这样的表现的原因，总结本算法的使用条件。

本节主要分为两个部分：第1部分简要介绍实验中用到的数据集和用于作对比的其他节点选择算法；第2部分从不同的方面来分析实验结果，得出结论。

4.1 数据集和算法介绍

为了显示算法的实验效果，实验中用到的来自真实社交网络中的数据集有如下3个：

CA-HepTh[26]该数据来自于arXiv，涵盖了提交到该网站的高能物理(High Energy Physics- Theory)分类下的作者之间的科学合作。如果作者和作者合作了一篇文章，那么节点和节点之间存在一条无向边；如果一篇文章是由个作者共同合作完成的，那么这个节点之间构成了一个个节点的完全图。该数据涵盖了从1993年1月至2003年4月期间(124个月)的论文，共包含9877个节点，25998条边。

Email-Enron[27]该数据是美国联邦能源监管委员会在调查安然公司破产案的过程中发布到网上的安然公司的邮件通信网络。其中，节点代表电子邮件的地址，边代表邮件地址之间的通信，如果两个地址之间至少发过一封邮件，那么这两个地址之间存在一条边。该网络是一个无向简单网络，覆盖约五十万封电子邮件数据集内的所有电子邮件通信，共包含36692个节点，183831条边。

Facebook-Combined(FC)[28]该数据来自Facebook的“社交圈”(或“朋友列表”)，是一个ego网络(所谓ego网络，指的是网络的节点是由唯一的一个中心节点(ego)，以及这个节点的邻居(alters)组成的，它的边只包括了ego和alter之间，以及alter与alter之间的边)。共包含4039个节点，88234条边。

为了和其他节点选择算法作对比，选择了如下几个节点选择方法：

随机选择(Random) 一种简单的节点选择方法，这种方法完全随机地选出个初始节点。

局部中心度算法(Local Centrality, LC) 节点的邻居节点集为out1(), out1()中所有节点的邻居节点集的总集合为out2(), out2()中所有节点的邻居节点集的总集合为out3()；设,,分别为的相应层次邻居节点集out1(), out2(), out3()的影响度。对于无符号网络，影响度定义为邻居节点集的元素个数。节点的潜在影响力值PI定义为：，其中定义为对所有未激活邻居节点的影响力之和：

混合度分解算法(MDD) 在计算k-核的过程中考虑了剩余度(residual degree)和排出度(exhausted degree)，该算法中的可调参数在实验中被设置为0.7。

基于度的启发式算法(DegreeDiscountIC, DDIC) 该算法是在传统基于度的启发式算法基础上改进后适用于独立级联模型的算法。在Degree Discount 中，如果某个节点已经被选入种子集合中，则该节点的邻居节点(不在种子集合中的节点)的度相应地减1。而DegreeDiscountIC算法使用了不同的折扣方法，当节点的邻居节点已经被选入种子节点中，那么将以概率被影响，这样的话就没必要将选入种子节点中。当比较小的时候，忽略的多跳邻居节点对其的间接影响，只关注直接影响。，其中，表示节点的度，初始为0，对于的邻居节点中未加入种子节点集合的节点每加1,也加1。

基于最小点覆盖和反馈点集的影响最大化算法(MVCFVS) 使用第3节中介绍的算法3选择初始活跃节点集合，该算法先找到网络的反馈点集，再在的每个分支上找最小点覆盖集合，最后在候选集根据影响力函数选出个节点。

4.2 实验结果

将以上6种节点选择方法选出的节点作为初始的活跃节点，分别按照线性阈值模型、独立级联模型、加权级联模型的传播方式进行影响力传播，对最终的传播效果进行比较。由于基于度的启发式算法(DegreeDiscountIC)是适用于独立级联模型的节点选择算法，所以我们只在独立级联模型下加入了这种算法(DDIC)作比较。为了保证算法的有效性，在初始活跃节点集上进行10000次模拟，取这10000次结果的平均值作为传播模型的最终结果。其结果如下：

图1比较了在CA-HepTh网络上4.1节中的6个节点选择方法在各个传播模型上的表现。其中，横坐标表示初始活跃节点(种子节点)集合的大小，即参数的大小，的取值范围从0到50，纵坐标表示最终的影响效果，即最终活跃节点数目。

图1(a)是5个不同算法选出的种子节点在线性阈值模型下的传播效果()，可以看出，本文算法(MVCFVS)虽不如Degree方法和LC方法，但和他们接近，且比Rand方法和MDD方法好得多。

图1(b)是6个不同算法(包括DDIC算法)选出的种子节点在独立级联模型下的传播效果()，可以看出，本算法(MVCFVS)是表现最好的。

图1(c)是5个不同算法选出的种子节点在加权级联模型下的传播效果(,是节点的度)，本算法(MVCFVS)和按照度选择方法(Degree)结果相似。

总的来说，MVCFVS算法在CA-HepTh网络上表现不错，特别是对于独立级联模型和加权级联模型，它能够通过较小的种子节点集合去影响更多的节点，和按照度选择方法(Degree)效果相似是因为本算法在进行节点选择时用到了最大度的思想，且由于CA-HepTh网络本身的局部中心性，导致本算法和Degree方法选出的种子节点有较大的重合。

图2比较了在Email-Enron网络上6个节点选择方法在各个传播模型上的表现。图2(a)是5个不同算法选出的种子节点在线性阈值模型下的传播效果()，可以看出，本文算法(MVCFVS)在时不如Degree方法和MDD方法，但是在时和他们接近，且比Rand方法和MDD方法好得多。通过仔细比较这些方法选出的不同节点，发现造成这种结果是因为Degree方法和MDD方法一开始就将度最大的节点选入了种子节点集合，使得他们能够在早期快速影响较多的节点，而本算法是在稍晚些时候才将这些度居榜首的节点选入种子节点集合；后期随着Degree方法和MDD方法的缺陷逐渐显现，本算法的表现越来越好，开始追上Degree方法，赶超MDD方法。

图2(b)是6个不同算法选出的种子节点在独立级联模型下的传播效果()，可以看出，本算法(MVCFVS)是最先收敛的，即在较小时比起Degree方法和MDD方法本算法能影响更多的节点。

图2(c)是5个不同算法选出的种子节点在加权级联模型下的传播效果(,是节点的度)，可以看出，本文算法(MVCFVS)也是最先收敛的，即在较小时比起Degree方法和MDD方法本文算法能影响更多的节点。

总的来说，MVCFVS算法在Email-Enron网络上3种模型下的表现比其他算法都好，特别是对于独立级联模型和加权级联模型，它收敛的速度最快，和Degree算法和MDD算法比较起来，本算法能够通过较小的种子节点集合去影响更多的节点。

图3比较了在Facebook-Combined网络上6个节点选择方法在各个传播模型上的表现。

图3(a)是5个不同算法选出的种子节点在线性阈值模型下的传播效果()，可以看出，本文算法(MVCFVS), Degree方法和MDD方法接近。

图3(b)是6个不同算法选出的种子节点在独立级联模型下的传播效果()，可以看出，本文算法(MVCFVS)和Degree方法、MDD方法接近。

图3(c)是5个不同算法选出的种子节点在加权级联模型下的传播效果(,是节点的度)，可以看出，本文算法(MVCFVS)和Degree方

图1 CA-HepTh网络上各个算法在3个模型下的实验对比

图2 Email-Enron网络上各个算法在3个模型下的实验对比

图3 Facebook-Combined网络上各个算法在3个模型下的实验对比

法、MDD方法接近。

总的来说，在这3种模型下，MVCFVS算法在Facebook-Combined网络上表现和Degree算法、MDD算法相似，但比其他文献的算法好。这是因为Facebook-Combined网络是一个ego网络，大多数节点会团结在某个节点周围，使得本文算法的影响力函数和Degree算法、MDD算法效果相似，选出的节点集合也相似，最终的传播效果也相似。

5 结束语

本文提出了一种求解社交网络影响最大化的算法MVCFVS。通过和不同的节点选择算法在不同的数据集上实验比较发现，算法MVCFVS比较适用于独立级联模型和加权级联模型，并且收敛速度很快，在取较小值时，就能影响非常多的节点。在规模较大且不是那么集中的网络中采用本算法选取种子节点，效果会更好。当然，阈值越大，最终活跃节点数越少；影响概率越大，最终活跃节点数越多。并且概率对于传播模型的影响非常显著。

另一方面，FC算法在求解反馈点集时只考虑了顶点度的影响，并没有考虑图的整体结构，故得到的反馈点集可能会有一定的局限性，即反馈点集中包含的顶点可能会多一些，从而影响了算法FC选出的个顶点的传播效果。为此，我们需要对FC算法在求解反馈点集这一步进行更深入的研究，这将是我们后续探索的工作。

[1] WATTS D J and STROGATZ S H. Collective dynamics of 'small-world' networks[J]., 1998, 393(6684): 440-442.

[2] BARABASI A L and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512.

[3] SAITO K, NAKANA R, and KIMURA M. Prediction of information diffusion probabilities for independent cascade model[J]., 2008, 5179: 67-75.

[4] TANG J, SUN J, and YANG Z. Social influence analysis in large-scale networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2009: 807-816.

[5] GOYAL A, BONCHI F, and LASKHMANAN L. Learning influence probabilities in social networks[C]. Proceedings of the Third ACM International Conference on Web Search & Data Mining, New York, USA, 2010: 241-250.

[6] WANG C, TANG J, SUN J,. Dynamic social influence analysis through time-dependent factor graphs[C]. Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and Mining, Washington, DC, USA, 2011: 239-246.

[7] DOMIGOS P and RICHARDSON M. Mining the network value of customers[C]. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, USA, 2001: 57-66.

[8] RICHARDSON M and DOMINGOS P. Mining knowledge- sharing sites for viral marketing[C]. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Alberta, Canada, 2002: 61-70.

[9] KEMPE D, KLEINBERG J, and TARDOS E. Influential nodes in a diffusion model for social networks[J].,, 2005, 32: 1127-1138.

[10] KEMPE D, KLEINBERG J, and TARDOS E. Maximizing the spread of influence in a social network[C]. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, 2003: 137-146.

[11] LESKOVEC J, KRAUSE A, GUESTRIN C,. Cost- effective outbreak detection in networks[C]. Proceedings of the Kdd 07 ACM SIGKDD International Conference on Knowledge Discovery and Data, Pittsburgh, PA, USA, 2007: 420-429.

[12] ZHOU C and GUO L. A note on influence maximization in social networks from local to global and beyond[C]. Proceedings of the 1th International Conference on Data Science (ICDS), Beijing, China, 2014: 27-28.

[13] ZHOU C, ZHANG P, GUO J,. An upper bound based greedy algorithm for mining top-k influential nodes in social networks [C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data, Seoul, Korea, 2014: 421-422.

[14] CHENG S, SHEN H, HUANG J,. IMRank: influence maximization via finding self-consistent ranking[C]. Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR '14), New York, NY , USA, 2014: 475-484.

[15] CHEN W, WANG Y, and YANG S. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 199-208.

[16] JIANG Q, SONG G, CONG G,. Simulated annealing based influence maximization in social networks[C]. Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 2011: 127-132.

[17] ZOU F, ZHANG Z, and WU W. Latency-bounded minimum influential node selection in social networks[C]. Proceedings of the Wireless Algorithms, Systems, and Applications, 4th International Conference, Boston, MA, USA, 2009: 519-526.

[18] ZOU F, WILLSON J, ZHANG Z,. Fast information propagation in social networks[J].&, 2010, 2(1): 125-141.

[19] COHEN E, DELLING D, PAJOR T,. Sketch-based influence maximization and computation: scaling up with guarantees[C]. Proceedings of Conference on Information and Knowledge Management, CIKM, Shanghai, China, 2014: 629-638.

[20] JIANG F, JIN S, WU Y,. A uniform framework for community detection via influence maximization in social networks[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Beijing, China, 2014: 27-32.

[21] CAO J, DAN D, XU S,. A-core based algorithm for influence maximization in social networks[J]., 2015, 38(2): 238-248.

[22] LUCIER B, OREN J, and SINGER Y. Singer influence at scale: distributed computation of complex contagion in networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 2015: 735-744.

[23] GOLDENBERG J, LIBAI B, and MULLER E. Talk of the network: a complex systems look at the underlying process of word-of-mouth [J].2001, 12(3): 211-223.

[24] KARP R M. Reducibility among Combinatorial Problems, Complexity of Computer Computations[M]. New York, USA, Plenum Press, 1972: 85-103.

[25] SCHULZ A. Correctness-proof of a greedy-algorithm for minimum vertex cover of a tree[OL]. http.//cs.stakexchange. com, 2013.

[26] LESKOVEC J, KLEINBERG J, and FALOUTSOS C. Graph evolution: densification and shrink diameters[J]., 2007, 1(1): 1-41.

[27] LESKOVEC J, LANG K, DASGUPTA A,. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[J]., 2009, 6(1): 29-123.

[28] MCAULEY J and LESKOVEC J. Learning to discover social circles in ego networks[C]. Proceedings of the 26th Annal Conference on Information Processing Systems, Lake Tahoe, NeVada, USA, 2012: 539-547.

许宇光： 男，1984年生，博士生，研究方向为计算机软件与理论.

潘惊治： 女，1992年生，硕士生，研究方向为社交网络.

谢惠扬： 女，1963年生，教授，研究方向为应用数学.

Minimum Vertex Covering and Feedback Vertex Set-based Algorithmfor Influence Maximization in Social Network

XU Yuguang①PAN Jingzhi①XIE Huiyang②

①(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China)②(College of Science, Beijing Forestry University, Beijing 100083, China)

Influence maximization is an optimization issue of finding a subset of nodes under a given diffusion model, which can maximize the spread of influence. This optimization issue has been proved to be NP-hard. Leveraging the fact that vertices in minimum vertex covering and feedback vertex set are of great importance for the connectivity of a graph, a heuristic algorithm for influence maximization based on Minimum Vertex Covering and Feedback Vertex Set (MVCFVS). Extensive experiments on various diffusion models against state of the art algorithms are carried out. Specifically, the proposed algorithm performs excellent on Independent Cascade Model (ICM) and Weighted Cascade Model (WCM), which exhibits its great advantages in terms of influence range and convergent speed.

Social network; Influence maximization; Diffusion models; Minimum vertex covering; Feedback vertex set

The National Natural Science Foundation of China (61370193)

TP393

A

1009-5896(2016)04-0795-08

10.11999/JEIT160019

2016-01-15；改回日期：2016-02-26；网络出版：2016-03-09

谢惠扬 xhyang@bjfu.edu.cn

国家自然科学基金(61370193)