如何从计算视角研究网络传播影响力最大化问题？

假设你要在中关村区域开一个餐馆，你准备了100张免费餐券打算发给顾客。怎样利用这100张免费餐券获得最大化的新店推广效果呢？你希望这100位顾客在用餐后，不仅自己会喜欢这个餐馆，还会向更多人推荐，为餐馆引来更多的客流。那么这100张免费餐券，应该赠送给谁呢？

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

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

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

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

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

计算视角下的社交网络

影响力最大化问题

回顾文章开头的社交网络营销传播的例子，计算机科学中研究的社交网络影响力最大化问题就是将这些案例抽象整理后得到的一个网络优化问题。

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

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

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

影响力最大化问题涉及哪些技术？

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

在独立级联模型以及很多类似的传播模型中，我们能够论证影响力扩展度函数 σ(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%。

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

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

影响力最大化问题的多种形式

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

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

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

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

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

影响力最大化的研究还有很多其它方面，比如利润最大化、种子集合最小化、自适应影响力最大化、基于影响力的网络中心性、非次模模型的影响力最大化等等，在此不再一一介绍。感兴趣的读者可参考笔者合著的专著[4]及其它综述文章[11,12]等。

另外，笔者详尽总结这一研究领域的专著《大数据网络传播模型和算法》也在近期刚刚出版[13]。

影响力最大化的研究已在多种应用场景中付诸实现。比如 Shakarian 等人将影响力最大化应用于芝加哥警察局挑选暴力团伙成员参加学习劝导班，使其影响其他团伙成员远离暴力犯罪[14]，Yadav、Wilder 等人将影响力最大化应用于在无家可归人士中有效传播对艾滋病的认知[15,16]。

但总体来讲，影响力最大化的研究和应用还有不少挑战。比如大规模的影响力传播数据的获取和共享，传播模型和传播分析的准确性，基于因果关系的影响力传播与基于相关性的网络同质性（homophily）的区别和联系，大规模网络传播的实验验证，影响力最大化对隐私和公平性的影响等等。这些方面还需要研究者进行更广泛深入的研究以及和业界实践者进行更密切的交流合作。相信随着 大数据技术 的发展和影响力传播研究的深入，影响力传播研究会有更广泛的应用前景。

参考文献

[1] Kempe D, Kleinberg J M, and Tardos É. Maximizing thespread of influence through a social network. In Proceedings of the 9thACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD), Washington D C, USA, Aug 2003:137~146. 完整期刊版发表于 Theory of Computing, 2015(11.4): 105~147

[2] Wang C, Chen W, and Wang Y. Scalable influencemaximization for independent cascade model in large-scale social networks. DataMining and Knowledge Discovery, 2012(25.3):545~576

[3] Borgs C, Brautbar M, Chayes J, and Lucier B. Maximizingsocial influence in nearly optimal time. In Proceedings of the 25thACM-SIAMSymposium on Discrete Algorithms (SODA), Portland, USA, Jan 2014:946~957

[4] Chen W, Lakshmanan L V S, and Castillo C. Information andInfluence Propagation in Social Networks, Morgan & Claypool Publishers,2013

[5] He X, Song G, Chen W, and Jiang Q. Influence blockingmaximization in social networks under the competitive linear threshold Model. InProceedings of SIAM International Conference on Data Mining (SDM), Anaheim,USA, Apr 2012:463~474

[6] Lu W, Chen W, and Lakshmanan L V S. From competition tocomplementarity: Comparative influence diffusion and maximization. InProceedings of the 42nd International Conference on Very Large DataBases (VLDB), New Delhi, India, Sep 2016

[7] Goyal A, Bonchi F, and Lakshmanan L V S.A data-based approach to social influence maximization. PVLDB, 2011(5.1):73~84

[8] Chen W, Lin T, Tan Z, Zhao M, and Zhou X. Robustinfluence maximization. In Proceedings of the 22nd ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining (KDD), SanFrancisco, USA, Aug 2016

[9] He X and Kempe D. Robust influence maximization. InProceedings of the 22nd ACM SIGKDD International Conference onKnowledge Discovery and Data Mining (KDD), San Francisco, USA, Aug 2016

[10] Chen W, Wang Y, Yuan Y, and Wang Q. Combinatorialmulti-armed bandit and its extension to probabilistically triggered arms.Journal of Machine Learning Research, 2016(17.50):1~33

[11] 陈卫（Chen W）. 社交网络影响力传播研究. 大数据 (Big DataResearch) , Oct 2015(1)

[12] Li Y, Fan J, Wang Y, and Tan K-L.Influence maximization on social graphs:A survey. IEEE Transactions on Knowledge and DataEngineering, 2018(30.10):1852~1872

[13] 陈卫（Chen W）. 大数据网络传播模型和算法. 中国邮电出版社，2020

[14] Shakarian P, Salmento J, Pulleyblank W and Bertetto J.Reducing gang violence through network influence based targeting of socialprograms. In Proceedings of the 20th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining (KDD), New York City, USA, Aug2014:1829~1836

[15] Yadav A, Wilder B, Rice E, Petering R, Craddock J,Yoshioka-Maxwell A, Hemler M, Onasch-Vera L, Tambe M, and Woo D. Influencemaximization in the field: The arduous journey from emerging to deployedapplication. In Proceedings of the 16th Conference on AutonomousAgents and Multiagent Systems (AAMAS), São Paulo, Brazil, May 2017

[16] Wilder B, Onasch-Vera L, Hudson J, Luna J, Wilson N,Petering R, Woo D, Tambe M, and Rice E. End-to-end influence maximization inthe field. In Proceedings of the 17th International Conference onAutonomous Agents and Multiagent Systems (AAMAS), Stockholm, Sweden, Jul 2018