编者按：在IEEEFellow评选中，微软亚洲研究院高级研究员陈卫因在社交网络影响力最大化算法研究方面的贡献成功入选。在这篇文章中，陈卫为我们细致地梳理了计算机科学视角中的影响力最大化问题，包括影响力传播的建模、算法优化、多种变体问题以及现实应用。你也可以在陈卫刚刚出版的新书《大数据网络传播模型和算法》中深入了解他对这一研究领域进行的详尽概总结和论述。文末有福利哦~

那些对餐馆的目标消费者具有影响力、能带来巨大传播效应的社交网络意见领袖（keyopinionleader）将是非常好的选择。你可以通过社交网络用户行为分析，或者借助一些营销分析平台的相关服务，一定程度上筛选出位合适的推广用户，与他们进行沟通合作，为你的餐馆完成一次病毒式营销（viralmarketing），来成功打入竞争激烈的餐饮市场。

这仅仅是社交网络影响力最大化问题在现实世界中的广泛应用的一隅。

任何社会性动物在个体与个体、群体与个体之间都存在着相互影响关系。人类作为具有复杂交流手段的高级社会性动物，人际和社会影响力在我们的社会生活中更是无处不在。小到听一首歌曲、看一部电影、读一部新书、选一个餐馆，大到买一处房产、选择职业方向、选择生活城市、确定我们的政治观点等，我们的各种选择和决定常常受我们的家人、同事、朋友以及更广泛的大众倾向的影响。

深入认识影响力的产生和传播模式有助于我们理解人类群体和个体的行为，从而能够对人们的行为作出预测，为政府、机构、企业等各部门的决策提供可靠的依据和建议。比如企业在做新产品推广时，可以利用对用户影响力及其传播的了解选择有影响力的用户和传播渠道帮助产品推广，公益机构可以通过影响力传播推动公益事业的发展，比如增强全民健康意识，推动扶助贫困地区等。影响力传播建模和影响力最大化的研究就是基于这一背景，利用数学、算法和博弈论等工具对影响力传播及其优化问题进行的研究。

广义的影响力传播研究可以涉及社会学、心理学、经济学、复杂网络、计算机科学等多个方面，而各方面研究的侧重点有所不同。在此我们重点介绍由计算机科学出发对影响力传播的研究，包括影响力传播建模、影响力传播优化和影响力传播学习推断等方面。

它最初由Kempe、Kleinberg和Tardos在年的数据挖掘会议KDD上给出了完整的优化形式刻画及一系列的研究结果[1]。它的基本形式一般如下表述：首先，我们将一个社交网络建模为一个有向图G=(V,E)，其中V表示结点集合，E表示有向边的集合。图G中的每个结点（vertex或node）代表社交网络中的一个个体或一个用户，而G中的每一条边代表它所连结的两个个体的影响关系。边是带方向的，从结点u指向结点v的有向边(u,v)表示个体u可以对个体v施加影响。施加影响力的强弱由模型给出的参数决定。比如在最基本也是研究最广泛的独立级联模型（independentcascademodel）中，每个有向边(u,v)上带了一个影响概率参数p(u,v)，表示u影响v的成功概率。独立级联模型的动态传播发生在离散时刻点t=0,1,2,…：在0时刻，若干结点被选为种子结点（seednode）并被激活，这就相当于前面例子中被选中给予免费餐券的顾客；在时刻t≥1，如果一个结点u在时刻t-1被激活，那么u会沿着每一条出边(u,v)尝试一次激活v（如果v还没有被激活），而其成功激活v的概率就是该有向边的影响概率p(u,v)。每条边最多尝试一次影响力传播，且不同尝试之间相互独立。如果一个结点被激活，就一直保持活跃状态。这个传播过程直到某一时刻没有新的结点被激活为止。

这样的随机传播模型（stochasticdiffusionmodel）中很重要的一个度量参数就是影响力扩展度（influencespread），被定义为给定种子集合S时传播最终激活结点个数的期望值，记为σ(S)。在餐馆的例子中，S为选定的个接受免费餐券的“种子”顾客集合，σ(S)就代表由于这些种子顾客在社交网络中的影响力传播所带来的餐馆顾客数，即客流的期望值。影响力最大化问题就是在给定的预算条件k下，选择网络中的k个结点，使得这k个结点的影响力扩展度最大。在餐馆的例子中，就是要找到个种子顾客使其带来的客流量最大。

上面给出了影响力最大化的基本定义以及在社交网络病毒式营销中的例子。影响力最大化当然还有很多变种，其应用也包括更广泛的领域。下面我们先简要介绍一下解决影响力最大化问题涉及的一些主要技术。

首先，影响力最大化是个典型的随机优化问题：输入包括有向图G及其上决定动态传播的参数，要求找到一个集合使得传播的随机动态过程的影响力扩展度最大。对于独立级联模型等基本的传播模型，容易论证影响力最大化属于优化问题中常见的难解问题，被称为NP-难（NP-hard）的问题，就是说无法找到有效的算法得到问题的最优解。那么解决影响力最大化问题，现在主要依靠寻求近似解的方法，也即设计问题的近似算法。这就需要用到近似算法设计中一个十分重要的技术——次模函数最大化（submodularfunctionmaximization）及其贪心算法（greedyalgorithm）。

在独立级联模型以及很多类似的传播模型中，我们能够论证影响力扩展度函数σ(S)满足如下的次模性质：对于任何一个种子集合S和包含S的一个更大的种子集合T（S?T），如果在T之外再找一个种子u，则总能满足u在T之上的边际影响力总小于或等于u在S之上的边际影响力，即σ(T∪{u})-σ(T)≤σ(S∪{u})-σ(S)。次模性表达了在经济学中常会提到的边际效用递减的性质：一个个体在更大群体之上的边际效用或边际影响力，小于该个体在较小群体之上的边际效用或边际影响力。这种边际效用递减的特性在网络传播中也可以直观理解，虽然并不是所有的传播模型都满足次模性。当传播过程满足次模性和另外一个简单的单调性（种子集合越大，影响力扩展度越大）时，我们就可以使用经典的贪心算法：如果要找到k个种子结点，那么我们进行k轮，每轮找到一个种子结点，满足第i轮找到的种子结点u_i是在前面i-1轮找到的种子集合{u_1,…,u_(i-1)}之上的边际影响力最大的结点。这样的贪心算法找到的种子集合{u_1,…,u_k}可以保证是所能找到的最优解的1-1/e≈0.63近似，意思是{u_1,…,u_k}的影响力扩展度至少是最优解的影响力扩展度的63%。

大多数的影响力最大化研究都基于上面的次模函数最大化和贪心算法。但这只是一个基础框架，要解决影响力最大化问题，还需要在深度和广度方面都进行很大的拓展，所以从年的第一篇经典论文至今，影响力最大化的研究一直在深度和广度方面不断拓展，至今仍很活跃。下面我们介绍几个主要的研究方向和成果。

首先，将上面的贪心算法运用到影响力最大化，要面对的第一个问题是计算一个给定集合S的影响力扩展度σ(S)。由于影响力传播是随机动态过程，要得到影响力扩展度的精确解并不容易。事实上，笔者与合作者指出这一计算即使在基本的独立级联模型上也属于一类难解问题[2]。绕过这一难解性的最初方法是直接模拟模型的传播过程很多次，得到每次的传播结果后再取平均数作为近似。这一随机模拟近似过程被称作蒙特卡洛模拟（MonteCarlosimulation）。但是蒙特卡洛模拟要达到合理的效果需要对贪心算法中涉及到的每一个种子集合各自做上万次模拟。这导致整体贪心算法的效率十分低下，在上万个结点的图中也要跑几天才能完成。针对这一问题，一系列研究提出了解决可扩展的影响力最大化（scalableinfluencemaximization）的各种方法。到目前为止，基于反向影响力采样思想[3]的算法能够同时满足理论保证并在实际的大规模网络中高效地实现，其一系列改进和优化算法已经成为实现可扩展影响力最大化的主流算法。

社交网络病毒式营销是一种影响力最大化的基本形式，但针对网络传播的不同场景，还可以定义不同形式的影响力最大化问题，从而扩展它的应用领域。

比如，仍然是餐馆推广的例子，如果同时还有另外一家或多家餐馆也在网络上作推广，那么这在网络传播中就形成了竞争性传播的例子。餐馆就需要考虑在其它竞争性实体也在网络中传播时，如何合理选择种子顾客以增加自己餐馆的影响力。这就是竞争环境下的影响力最大化问题。我们可以给出一个竞争环境下的传播模型，如竞争性独立级联模型，并研究该模型下的竞争性影响力最大化问题，设计对应的高效算法（参见[4]中的4.2节）。

在竞争性传播中，竞争的一方追求的并不一定是扩大自己的影响力，也可能是希望限制对方的传播。比如当有不利于餐馆经营的谣言在网上开始传播，餐馆会希望尽快找到一些网络上的种子结点发布和传播正面的辟谣的信息，以阻断谣言的传播。这就可以用影响力阻断最大化的模型来研究实现[5]。限制谣言的传播有很重要的现实意义。比如在新冠肺炎疫情的传播过程中，社交网络中不断混杂着各种谣言的传播，容易造成大众的过度恐慌情绪等负面的社会影响。网络平台就需要及时发布正确信息，并找到合适的传播渠道使得正面信息的传播能及时阻断谣言的传播。

网络中的多实体传播除了竞争性传播，也可以是互补互助的影响力传播。比如餐馆店主又开了一个咖啡厅，他可以将咖啡厅和餐馆的优惠相结合，使得咖啡厅的顾客也更想光顾他的餐馆。那么关于咖啡厅和餐馆的优惠信息的传播，就是互补互助的信息传播，这也可以用互补互助影响力传播模型来建模，并研究互补情形下的影响力最大化[6]。

影响力最大化的研究依赖于传播模型的建模和模型参数的获取。这需要在实际网络中获取大规模的传播数据并加以分析，得出结点间影响力传播的强弱程度分析，比如说分析出独立级联模型中边上的影响力概率p(u,v)。这类传播模型的分析也是网络数据挖掘的一个重要方面。对于影响力最大化来说，围绕传播数据的分析也会产生不同的研究课题，比如省略建模过程直接从数据到优化的基于数据的影响力最大化问题[7]，容忍数据分析结果不准确的鲁棒影响力最大化问题[8,9]等。另外，我们还可以考虑边学习边优化的迭代过程，即利用从种子选取、到实施传播、观察传播结果、修正传播模型参数、再次种子选取的多步迭代过程以达到最好的影响力最大化效果，这被称为在线影响力最大化（onlineinfluencemaximization）问题。这属于组合在线学习（