复杂网络中影响力最大化问题的现状综述时浩东摘要:影响力最大化问题通常是指在社会网络或一些其它的网络中，选出一个K个节点的集合，以此来实现在该网络中的影响力最大化。一方面，由于影响力最大化是一个NP-hard[1]问题，另一方面由于网络中的节点数量庞大，而且我们往往又需要在最快的时间内发现这K个节点，因此现在的大多数算法都采用贪心策略来解决这一问题。而且随着多核CPU的兴起，能否通过并行设计来达到更快的速度也成为了人们研究的方向。本文便是对当前存在的一些方法的分析，介绍，并阐述了自己对当前情形的理解以及对未来研究方向的展望。说明文章的研究目的、方法和主要结果。关键词:复杂网络影响力最大化1背景介绍自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体之间的关系，通常是当两个节点之间具有某种特定的关系时连一条边，反之则不连边。有边相连的两个节点在网络中被看作是相邻的。这些从现实网络中抽象出来的真实网络体现了不同于其他网络的统计结构特征，由于节点数目众多，因此称其为复杂网络。而影响力最大化问题就是基于这种网络而提出的。例如，神经系统可以看作是大量神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络，类似的还有电力网络、社会关系网络、交通网络等。而社会网络则是指由社会个体来作为节点，个体间的关联关系作为边所形成的具有复杂链接关系的网络。它的意义在于为各种关系提供了精确的量化分析，从而为构建理论模型和检验实证命题提供了一种可行的模型。由于社会网络的无标性，因此它存在一些可以影响整个网络的关键节点。而影响力最大化问题则就是研究如何找出这些关键节点，以此来达到对整个网络的监视和分析，获取一些有用的信息。在基于社会网络的影响力模型及其算法的研究领域，影响力最大化问题可以简单的概括为：给定一个网络和一种特定的影响力传播模型，如何在网络中确定一个给定大小的初始节点集合，当集合里面的节点在初始时刻被激活时，遵循传播模型的传播机制，最终能在网络上激活最多的节点。在应用方面，随着冷战的结束，而恐怖主义却严重威胁到了人类的生存，并且严重的阻碍了人类文明的发张。对于恐怖组织，如何我们能根据社会网络节点影响力，迅...
