社交活动的“超级传播者”：揭秘网络影响力最大化算法在推荐中的应用

01、背景

在现代社交网络中，信息和影响力的传播无处不在。影响力最大化（Influence Maximization，以下简称 IM）旨在找出网络中最有影响力的少数用户，从而最大化信息传播效果。这一概念起源于病毒式营销，即企业通过奖励有影响力的用户（如赠送试用产品）来促进他们在朋友圈推广产品，因为人们通常认为来自朋友或信任源的推荐比商家宣传更可靠。

传统IM模型的目标是找到网络中 s 个节点作为种子集，使其能影响到的节点数最多。然而，在实际应用中，IM 面临着节点容量受限的挑战。例如，在在线社交媒体平台上，尽管有许多内容推广活动，但公众的时间和精力有限，对内容的消费能力（如观看、阅读、转发）也有限，很大程度上影响推广效果。在游戏社交中也是如此，许多在线游戏会推出活动以促进玩家之间的互动，例如通过奖励抽奖券、皮肤碎片等激励玩家参与活动并与好友互动。关键问题在于，如何向活跃参与者（active participant, 简称 ap）推荐有限数量的好友，以便覆盖更多用户。

图一：社交传播示意图

02、解决方案：容量约束的影响力最大化算法

针对上述问题，我们提出了一种新的 IM 框架——容量约束的影响力最大化（Constrained-IM，CIM）。其目标是为每个初始种子用户选择有限数量的有影响力好友，以便推广能覆盖更多用户。我们设计了两种贪心策略 MG-Greedy 和 RR-Greedy，分别保证解是最优解的1/2和至少1/2。为了适应大规模网络，我们基于反向可达集（Reverse Reachable Set）的思想，进一步提出了 RR-OPIM+算法，该算法具有近线性时间复杂度，并且解与最优解的接近度为(1/2−ϵ)。该工作已被国际顶级数据挖掘会议 KDD 2023 收录。

2.1 问题定义

给定一个有向图 G=(V,E)，其中 V 是节点集合（如每个玩家），E 是连边集合（如玩家间的互动关系）。给定传播模型 M，ap 用户集合 A 和节点容量常数 k，CIM 的目标是为每个 ap 用户 u 找到一个最优邻居集合 S_{u}^，使得邻居集合的传播范围

最大化，并满足约束

。

2.2 贪心算法设计

CIM 问题在大多数传播模型下都是 NP 难的，因此找到有效的近似算法非常重要。我们提出了两种贪心近似算法 MG-Greedy 和 RR-Greedy 来解决 CIM 问题。前者每次选择边际收益最大的 seed，然后随机分配至相连的 ap；后者则采用 round-robin 策略，为每个 ap 候选者选取一个在全局条件下边际收益最大的 seed。

在解的质量上，MG-greedy 和 RR-greedy 能够保证得到的解分别是最优解的1/2和至少1/2。在时间复杂度上，RR-greedy 较 MG-greedy 提升了 d 倍，其中 d 是 ap 集合的大小（对数学证明和复杂度分析感兴趣的读者，详见 KDD 原文）。

图二：MG-greedy 和 RR-greedy 算法的伪代码实现

2.3 可扩展性实现

计算影响力扩展度 σ(⋅) 是贪心算法中的关键环节，这通常需要进行蒙特卡罗模拟，计算代价非常大。为了借鉴计算效率问题，我们设计了一个通用的可扩展式贪心算法，利用反向可达集（Reverse Reachable Set）来估计 CIM 中的影响力扩展度。具体实现上，我们借鉴了 OPIM 的计算框架，用最大化覆盖反向可达集数量来优化贪心算法，得到了 MG-OPIM 和 RR-OPIM，其输出结果具有与最优解接近的近似比，且时间复杂度为近线性阶。进一步优化后，我们得到了算法 RR-OPIM+。

图三：反向可达集的示例

03、应用效果

我们在多个公开的网络数据集进行了仿真实验。我们随机选取了网络中5%的节点作为 ap，并使用 IC 模型作为传播模型。实验结果显示，，本文设计的贪心算法都显著优于传统方法。例如，当 k=10 时，RR-Greedy 算法在 DNC 数据集上的传播范围相对 Degree 提升了27%。对于 Orkut 数据集，RR-OPIM+相对于启发式算法提高了39%。

图四：算法传播范围对比

在运行时间上，可扩展式算法 RR-OPIM+ 在所有情况下都优于其他解决方案。例如，在 Twitch 上，RR-OPIM+ 将 RR-OPIM 和 MG-OPIM 的运行时间降低了两个数量级。

图五：算法运行时间对比

最后，我们把 RR-OPIM+ 算法应用到腾讯某射击竞技类游戏的熟人好友推荐场景。传统的社交推荐类做法一般是通过游戏内亲密度来度量玩家之间的交互意愿，并按照该值排序产生好友推荐列表。然而这样的方法忽略了被推荐用户群体的社交影响力。这里我们先按 RR-OPIM+ 计算出影响力最大的好友集合，同时结合亲密度，推荐出影响力最大且交互概率大的好友。我们发现算法在活动实际传播人数上相对亲密度排序提升了6.5%，并且对用户活跃时长也有相应的正向提升（如图六所示）。

图六：线上业务效果

3.1 团队信息

腾讯互娱社交算法团队（https://socialalgo.github.io/）致力于研发高效的社交网络智能算法和分析技术，挖掘海量丰富的图数据，构建高性能的图模型，服务于大量腾讯产品的多样社交场景，旨在提升用户留存和产品收益。团队负责的场景包括好友推荐、社群推荐、社交传播、社交营销、社交分析等围绕大规模社交网络的应用。团队研发的技术已落地应用于20+款腾讯互娱产品，获得多项腾讯公司级荣誉奖项，包括卓越运营奖、业务突破奖、腾讯专利奖、腾讯代码奖、犀牛鸟精英人才计划优秀导师等，并且已在国际前沿学术会议和期刊上发表了20+篇论文。

3.2 参考资料

Zhang, Shiqi, Yiqian Huang, Jiachen Sun, Wenqing Lin, Xiaokui Xiao, and Bo Tang. "Capacity constrained influence maximization in social networks." In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3376-3385. 2023.

-End-

原创作者｜林文清