社交网络影响力最大化：Are we there yet?

type

status

date

slug

summary

问题定义

给定一个社交网络（有向图），一个信息传播模型，影响力最大化问题意图找到一个大小为的节点集合，使得它们在中基于传播模型的影响力最大。

传播模型

此前的问题定义也还是算比较抽象，因为传播模型还并未确定，针对不同的传播模型，该优化问题也许会有不同的性质。接下来我们介绍一种最广泛使用的传播模型之一——独立级联模型（Independent Cascade）。

IC模型下，每个节点有激活和未激活两种状态，给定种子节点集合，影响力的传播与计算方式如下：

在第1步，所有种子节点被激活，其余节点处于不激活状态。

在第步新激活的节点，对每个的未激活出邻居，有且仅有一次机会以概率在步激活。

当没有新节点被激活时，传播过程停止。一次传播过程中，我们把激活的点的数量记为。的影响力被定义为传播过程中被激活的点的数量的期望，记作，即:

函数性质

解决问题的第一步是要充分了解这个问题的性质。从计算复杂性的角度看，在IC模型下，影响力最大化是NP-hard的，以及的计算是 #P-hard的。基本就是说这个问题的一般情况很难得到最优解，并且函数值都没法精确计算。不过好消息是，目标函数具有单调（monotone）和次模（submodular）的性质。假设我们能够准确算出给定节点集的影响力，根据次模优化（submodular optimization）的经典结论，简单的贪心算法可以给出的近似比（即，为最优解）。

Naive Method: 基于蒙特卡洛模拟的贪心算法

然而，根据此前所述，没法被精确计算。于是，二十年来，研究者们都在想办法精确估计这个函数。最简单的方式就是就是模拟传播过程次，然后取平均，用来估计的影响力。因为估算误差的存在，这种基于蒙特卡洛模拟的贪心算法最终会获得的近似比。一般来讲，每一次的估计误差（注：为相对/乘性误差，即）和最终的近似误差的关系大约是。可以抽象地理解成估计误差会随着每一轮的迭代而累积。也就是说，保持最终的近似误差不变，随着需要选取的节点数量增多，我们需要越来越精确的估计（即越来越小），于是导致越来越多的开销。

但蒙特卡洛模拟每次需要的时间很长（很可能到量级），并且要大量的模拟次数来达到最后的理论保证，所以在很多文章的实验中，这个理论保证通常都会被舍弃，模拟次数都被设置成10000这样一个固定数字。自2003后的十年里，研究者们提出了各种各样的方法来提出高效的方法来解决IM问题，然而，始终没有方法能够在数百万节点的图上得到具有理论保证的解，直到2014（实际上在更早的时候，未经同行评审的版本已经放在arxiv上）。

State-of-the-art: 反向影响力采样

基本思想

2014年，Christrian Borgs等人在理论领域顶会SODA上发表了Maximizing social influence in nearly optimal time这篇文章，提出了著名的反向影响力采样（Reverse Influence Sampling, RIS）框架（注：在原始文章里作者们把他们的方法称为Hypergraph，反向影响力采样是后来的文章对该方法的命名）。为了帮助读者更好地理解RIS，我们先介绍反向可达集（Reverse Reachable Sets， RR-sets）的概念。

给定一个节点和一个确定的图，一个以为根节点的RR-set包含中所有能到达的点。基于此，一个随机反向可达集（random RR-set）按照如下方式构建：(i) 均匀随机采样一个点，(ii) 在一个随机的传播实例中，存储所有能到达的点，它们构成的集合记作RR-set 。这个定义还是有点晦涩，事实上，在IC模型下，我们构建一个random RR-set就是先随机选一个点，然后从这个点开始反向传播，把能reach的点都存到中。

对于一个种子节点集合来说，如果中有至少一个点在中（即），我们说 cover了。对于一组RR sets 来说，的coverage就被定义为被 cover的RR-sets的数量，即。

直觉上，如果一个种子节点影响力很高，那么它应该会经常出现在别的节点的RR-sets里，也就是说，它的coverage会很大。Borgs等人证明了这个coverage可以用来无偏地估计的影响力。数学上来说，就是，这里的期望是作用在random RR-sets上，即根节点的随机性和传播过程的随机性。High-level地来讲，这个式子的意思就是假设有一堆random RR-sets，他们被 cover的比例就可以（期望上）视作被影响节点占总节点数的比例。一个简单的示意图如下：

算法框架

基于上述估计方法，RIS框架基本分两步走：(i) 采样大量RR-sets，随后 (ii) 找coverage最大的。而第二步，即优化，实质上就是经典的最大覆盖问题（maximum coverage），贪心算法可以在线性时间复杂度下完成。剩下的就是第一步的事情：怎么决定采样多少RR-sets？此后的一系列工作都在围绕这个问题进行改进。Borgs等人通过数采样过程中遍历的边的数目来确定RR-sets是否足够。他们提出只要总共遍历的边数超过（为某个常数），就能以较高概率获得具有理论保证的近似解。随后的TIM提出上述方式是有问题的，因为这种采样会使得采样的RR-sets之间并不完全独立，影响Chernoff不等式的使用。TIM从RR-sets的数量角度来思考，提出当RR-sets的数目大于时，我们能以较高概率获得具有理论保证的近似解。这种框架一直被沿用至今。此后的IMM、OPIM等，都是在想办法减少RR-sets的数量，去达到相同的的理论保证。

好在哪里？

从时间复杂度上来说，RIS-based的方法当然是显著优于其他方法，但它到底好在哪里呢？首先，在RIS的框架下，我们的估算函数也是monotone and submodular的，使得贪心算法能获得的近似解。这个特性让我们只需要bound住一个size-种子节点集合的绝对误差在内就行。更细节来说，这种近似的模式可以大致表示成下面的形式：

这种近似模式需要的采样数量更少，因为不再需要非常精确地估计每一个点的influence。此外，对coverage函数的优化也可以高效完成。而且，一般来讲，RR-set的大小一般不会很大，而在此前介绍的蒙特卡洛估计方式中，随着选的点越来越多，一次模拟（采样）的时间会越来越长。

以上几点就是RIS这个框架比较高效的主要原因。

问题

事实上，虽然所有文章的实验效果都很好，但在各种setting上跑一下代码就会发现还是有一些问题的。主流的文章里，都把每条边的概率设置成，其中是的入度。这种设置其实比较tricky，因为这样的话相当于做反向采样的时候，对每个点来说期望只有一个邻居被采到，使得RR-sets整体来说都不会太大，而且这种设定下，最优解的influence也不会很小，所以整体运行时间较快。

然而，当每条边的传播概率都很高时，RR-sets会很大，采样会很耗时间，不过这一点在Qintian Guo等人的文章里已经得到部分解决，他们提出先根据很少的采样选出一些哨兵节点，然后在后续的每个RR-set的采样中，如果遇到哨兵节点就立即停止，这样的方式可以减小RR-set的size。但这个只适用于节点选取，当涉及其他变种问题时（如对给定节点集合的影响力估计），这种方式就不能直接使用了。第二种情况就是当每条边的传播概率都很低时，最优解的influence变得很小，达到理论保证需要的RR-sets数量也会非常大，使得算法运行时间变长。

值得一提的是，RIS这种估计方式的方差实际上是比蒙特卡洛方法要大的，但采样的过程比蒙特卡洛快很多。有没有办法结合正向和反向的传播，使得估算更加高效，也是一个潜在的研究方向。

The Road Ahead

除了研究IM本身的一系列主线文章，基于它的变种问题也有不少，像是改传播模型、改目标函数、改限制条件、Adaptive和dynamic settings之类的。问题总是能捏造出来的，但要提出新问题的话，motivation是非常重要的，再怎么强调都不为过，再辅以non-trivial的解决方法，也许能发到较好的会议上；对于已有的问题，直接adapt RIS基本是收不到什么正面反馈的。毕竟，IM也已经是个被研究了22年的问题了，RIS也被提出十年有余，所以做变种问题时，还是要有一点新的结果才行。

在这里我姑且列一些花式使用RR-sets的文章，读者们可以再挖挖会不会有什么新东西：

Dynamic update: [6-10]

Adaptive: [10-14]

Varying constraints: [15-17]

Real-valued RR-sets: [17-19]

理论之外

IM作为一个科学问题，或者说数学问题，收获了不少研究者的关注，并且有不少先进算法已经被设计出来。但它离实际应用可以说相当远了，因为现实世界的传播模型根本没那么理想化，也就导致了实际的影响力可能并不具备单调和次模的性质，于是这些所谓的理论保证就都都成扯淡了。说到底，在二十一世纪，信息甚至不可能只通过用户构成的图结构进行传播（但也许这种传播也能抽象成图的形式，如异质图）。而研究这类更“现实”的传播模型，其实不好发表，因为复杂的机制往往不具备较好的性质，也就很难得到一些non-trivial的理论保证（当然，或许在其他方面能有一些有趣的结果）。做科研就是这么抽象，不能做太难的问题，不然做不出来，也不能做太简单的问题，直接就会lack of technical quality被拒。

我认为信息传播仍是一个非常重要的研究课题，尤其是在这个信息大爆炸的时代。但仅靠图算法进行建模是非常局限的。如何分析现实世界中的信息传播，集成各种形式的传播模式，是一个有前景但难度很高的事情。

在科研逐渐浮躁化，人均深度学习，很多phd三个月就能发一篇文章的今天，我并没有勇气迎难而上。

参考文献

Kempe, D., Kleinberg, J., & Tardos, É. (2003, August). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 137-146).

Borgs, C., Brautbar, M., Chayes, J., & Lucier, B. (2014, January). Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (pp. 946-957). Society for Industrial and Applied Mathematics.

Tang, Y., Xiao, X., & Shi, Y. (2014, June). Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data (pp. 75-86).

Tang, Y., Shi, Y., & Xiao, X. (2015, May). Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD international conference on management of data (pp. 1539-1554).

Tang, J., Tang, X., Xiao, X., & Yuan, J. (2018, May). Online processing algorithms for influence maximization. In Proceedings of the 2018 international conference on management of data (pp. 991-1005).

Ohsaka, N., Akiba, T., Yoshida, Y., & Kawarabayashi, K. I. (2016). Dynamic influence analysis in evolving networks. Proceedings of the VLDB Endowment, 9(12), 1077-1088.

Peng, B. (2021). Dynamic influence maximization. Advances in Neural Information Processing Systems, 34, 10718-10731.

Yang, Y., Wang, Z., Pei, J., & Chen, E. (2017). Tracking influential individuals in dynamic networks. IEEE Transactions on Knowledge and Data Engineering, 29(11), 2615-2628.

Chen, X., Song, Y., & Tang, J. (2024, May). Link recommendation to augment influence diffusion with provable guarantees. In Proceedings of the ACM Web Conference 2024 (pp. 2509-2518).

Guo, Q., Feng, C., Zhang, F., & Wang, S. (2023). Efficient algorithm for budgeted adaptive influence maximization: An incremental rr-set update approach. Proceedings of the ACM on Management of Data, 1(3), 1-26.

Han, K., Huang, K., Xiao, X., Tang, J., Sun, A., & Tang, X. (2018). Efficient algorithms for adaptive influence maximization. Proceedings of the VLDB Endowment, 11(9), 1029-1040.

Huang, K., Tang, J., Han, K., Xiao, X., Chen, W., Sun, A., ... & Lim, A. (2020). Efficient approximation algorithms for adaptive influence maximization. The VLDB Journal, 29(6), 1385-1406.

Cautis, B., Maniu, S., & Tziortziotis, N. (2019, July). Adaptive influence maximization. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 3185-3186).

Tang, J., Huang, K., Xiao, X., Lakshmanan, L. V., Tang, X., Sun, A., & Lim, A. (2019, June). Efficient approximation algorithms for adaptive seed minimization. In Proceedings of the 2019 International Conference on Management of Data(pp. 1096-1113).

Sun, L., Huang, W., Yu, P. S., & Chen, W. (2018, July). Multi-round influence maximization. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining (pp. 2249-2258).

Zhang, S., Huang, Y., Sun, J., Lin, W., Xiao, X., & Tang, B. (2023, August). Capacity constrained influence maximization in social networks. In Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining (pp. 3376-3385).

Huang, Y., Zhang, S., Lakshmanan, L. V., Lin, W., Xiao, X., & Tang, B. (2024). Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint. Proceedings of the VLDB Endowment, 18(2), 117-129.

Chen, X., & Tang, J. (2025, July). Scalable Link Recommendation for Influence Maximization. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1 (pp. 130-141).

Rui, X., Wang, Z., Zhao, J., Sun, L., & Chen, W. (2023). Scalable fair influence maximization. Advances in Neural Information Processing Systems, 36, 66675-66691.