社交传播和影响力算法在腾讯游戏中的应用实践

导读 本文将分享新加坡国立大学与腾讯互娱在社交传播和影响力算法方面的实践与探索。文章将介绍如何将用户传播能力指标用于熟人推荐和排序场景，如何将社交影响力最大化的算法用于游戏中的病毒式营销场景，以及如何提出影响力最大化的新变种，以更好地适配活动推广场景。社交推荐和病毒式营销的场景是基于我们在 WWW2024 的工作，我们通过对底层传播行为进行建模来解决这两个场景的问题。第三个问题则是基于 KDD2023 的一项工作。

文章主要包括以下三大部分：

1. 将用户传播能力指标用于熟人推荐场景

2. 提出影响力最大化新变种以更好适配活动推广场景

3. Q&A

分享嘉宾｜张诗奇 新加坡国立大学 博士 

编辑整理｜徐亚楠

内容校对｜李瑶

出品社区｜DataFun

---

01

将用户传播能力指标用于熟人推荐场景

首先介绍如何将用户传播能力指标用于熟人推荐场景。这个工作是我们基于腾讯游戏中的邀请行为进行的传播模型的刻画和建模。

游戏场景中有很多熟人邀请机制，以腾讯游戏为例，其中包含很多底层好友关系，比如微信和 QQ 好友，我们可以在游戏中通过活动来促进好友交互。这些交互就需要依托邀请面板，可以给定一定数量的好友，邀请大家一起来做活动。针对这种常见的邀请场景，我们通过 empirical study 发现邀请行为会存在传播级联现象，下图右侧直方图展示的是某一期活动里的传播数深度，可以看到传播数深度大于 1 的情况至少占了 44%，这一发现促使我们去研究用户的邀请行为是如何在社交网络中传播的。

刻画传播行为需要定义一个合适的传播模型，比较直观常用到的方法是独立级联模型，这个模型比较笼统地将用户对用户的影响用独立概率 P_uv 表示，但我们无法直接使用此 IC model，原因是它对影响力概念的刻画过于宽泛，没有考虑到实际业务场景中很多其它的需求，更确切地说它忽略了转化漏斗的概念。

转化漏斗是营销场景中的一个常见概念，它描述的是用户行为的多级转化。我们可以大致将用户体验或他的行为分为三个阶段，第一阶段是最初级阶段，我们在做新品牌推广时可能只需要让用户有初步品牌认识；进一步我们希望用户有更深层次的被动响应，对应转化漏斗中的第二阶段，即 adoption 阶段，第二阶段对应用户行为，可能是用户的点赞和喜欢，这会与用户在平台的活跃度、DAU 等指标相关；第三阶段是最深层次的一个阶段，这一阶段我们希望用户能从被动接受转变为主动响应，因此这一阶段称为 action 阶段。这一步会与电商这类跟收益相关的场景有关。

在这三个阶段中，用户都被影响到了，而每一个阶段对应的应用场景都不一样，每一个场景都十分关键，因此我们希望引入转化漏斗的概念进行传播模型的建模。

转化漏斗在邀请场景中也存在，对一个用户来说，最开始阶段没有收到任何邀请信息，也就是 uninformed；如果有好友对他发出邀请，他会收到邀请提示，会处于知悉状态；然后他可以选择是否接受，接受对应转化漏斗第二阶段；inviting 是他在做完活动后体验不错，会再主动邀请他的好友，这是转化漏斗第三阶段-主动行动。所以邀请行为是转化漏斗的一种实例。

因此我们想在现有经典的 IC 独立级联模型上引入转化漏斗概念。这里每个节点表示的是用户，每一条边表示好友关系，边上会包含一个点是邀请的概率，每一个用户不同的颜色表示其不同状态，比如灰色是暂时还未被触达，红色表示他是邀请者，黄色表示他是被邀请者，被邀请者可以进一步转化为接受者，即橙色。

这个模型是基于模拟的方式刻画用户行为，初始时给定一些现有的初始邀请者，每一步我们对现有邀请者去做仿真。

让他以一定邀请概率选择一个他的邻居好友发出邀请，针对已经接收到邀请的好友 V_j，他会以一定转化概率变成接受者，进一步他会以一个 γ 概率转换为新的邀请者。

这里我们只是提出比较 general 的传播行为的建模。这里的每一个概率都可以用现有的正交方法解决，比如 P_ij 可以用 CTR 技术找到用户的邀请概率，β 和 γ 可以利用一些历史数据找到每一个用户转化行为的分布。

每一次仿真会从初始邀请者出发，不断重复仿真过程，直到没有新的邀请者出现，一次仿真结束。我们可能会进行多次仿真从而得到稳定的结果。

我们做了四个实验，两个是离线探索，两个是线上探索。一类是 cascade estimation，给定初始邀请者集合，希望可以估计其传播范围，我们将传播范围定义为接受者数量，真实场景中可以根据不同业务需求选择其他估计状态（stage）。我们这里的做法是给定不同传播模型，进行多次蒙特卡洛模拟判断给定邀请者可以带来的平均接受者数量。

这里实验比较的是 RMSE，我们一共实验了 6 个数据集，包括 4 个腾讯内部的邀请数据集和 2 个公开数据集，可以看到我们提出的 ICI 方法的 RMSE 最小。

仿真技术指给定种子集即初始邀请人，我们希望能预测出其他用户在梯次模拟中有多少次被激活。我们把比例作为 prediction，可以接入不同的 diffusion model，因此我们对比了 6 个不同的传播模型。

实验数据表明，在 6 个数据集上除了 Diggs 我们模型的 AUC 和 MAP 指标处于第二位置，其他都是 outperform other competitors。

游戏中的熟人推荐场景，目标是给用户推荐他的熟人，提升他们的组队意愿，从而提高游戏参与度。为了把 ICI model 接入进来，我们引入了 influence spread 作为影响力中心度，针对每一个用户去计算其单点传播能力，将每个好友的单点传播能力做降序排序选择 top k 进行推荐。而传统算法是基于亲密度等历史交互指标进行排序加推荐。

我们在两个角色扮演游戏抽奖活动中进行了实验，这个活动除了抽奖还会设计支付行为，支付行为是主动行为，还会有邀请面板做好友邀请，让大家一起参与抽奖活动享受折扣。我们上线观察两种行为指标，发现基于传播和影响力的两种方法 ICI 和 IC，它们的效果都优于传统亲密度方法。

游戏中对应的病毒式营销是星云传播，我们选影响力足够大的种子用户将其初始化为幸运用户，幸运用户可能会有双倍积分，或者一些其他福利。当幸运用户与其好友对战后，好友会继承其特权，特权不是传递关系，而是复制关系。我们目标是选定初始 k 个有影响力的用户尽可能让整个活动参与度最高。

根据我们在 battle royale game 实际上线带来的传播增量上来看，基于影响力最大化方法的效果，不论是传播的增量，还是邀请率都会比传统基于 degree 的方法好。这也说明之前在学术界广泛研究的影响力最大化问题可以在工业界实际应用。底层模型 diffusion model 的建模也会对算法产生一定影响。我们新提出的 ICI model 比传统的 IC 模型有着显著的效果提升。

我们在 WWW 的工作提出了一个简单易用的对于用户邀请行为传播的建模。我们主要在传播规模估计和扩散预测上做了一些离线的实验，无论是在腾讯内部的数据集，还是公开的数据集上，都取得了不错的效果。同时我们也在实际的好友排序和病毒式营销的场景中进行了落地实践。

02

影响力最大化新变种以更好适配活动推广场景

接下来介绍我们在 KDD 2023 的一项工作，也是基于游戏社交网络考虑用户传播能力和影响力的一项工作。

前文中提到了影响力最大化的问题，其主要应用场景就是病毒营销的场景。在一个社交网络中，我们希望商家自己主动选一些种子用户，具体场景可以理解为带货，种子用户收取商家的钱，去帮忙做推广，推广的方式是利用其自身影响力零成本传播，例如利用其口碑效应传播给他的粉丝或好友，他的好友也进一步传播，在病毒式营销场景里形成影响力扩散。

给定一个商家的预算，比如他只想选 k 个网红做初始推广，我们如何帮助他选择k 个人，使他最终活动触达的范围最广？这就是影响力最大化问题的最原始定义。

解决这个问题的办法是先找一个底层传播模型，把底层传播模型作为传播范围的评估方式。

比如给定一些初始用户，可以依托于底层传播模型，做蒙特卡洛仿真，或用其他方法估计这些用户的实际传播范围，进而利用贪心方法迭代选择一组影响力最大的种子用户。

传统的影响力最大化问题存在一些限制。

在实际探索中我们发现，传统影响力最大化算法本身是服务于病毒式营销场景。虽然游戏中有病毒式营销场景，但其与传统病毒营销区别在于游戏中不需要付费给玩家。但玩家登录游戏时间有限，游戏时长这个 capacity 相比于 cost 在游戏场景中更值得关注。

第二点限制是在传统的影响力最大化场景，商家付费给传播者，让其参与。但是游戏里的活动需要依靠用户主观能动性，主动参与。根据在游戏场景下的数据观察，我们发现传播能力比较强的用户往往不会主动参加活动，反而是一些比较活跃但自身传播能力不强的用户特别喜欢参与活动，并邀请其好友。

这就引出一个问题，如何让这些有实际影响力、传播能力的用户参与进来？我们想到的方法是通过他们的活跃好友对其发出邀请，而不是直接推送。

针对游戏活动推广中的缺陷和挑战，我们提出了基于容量（capacity） 限制的影响力最大化问题。我们的输入是社交网络和给定的传播模型还有初始参与者，初始参与者就是这些活跃度和参与意愿很高的用户，我们给他们提供一个邀请窗口，邀请窗口大小根据其自身 capacity 限制，我们只会给他推荐 k 个好友，基于之前观察的经验，我们希望他收到的好友是尽可能有影响力的好友。

之后我们借助 influential friends 进一步推广活动。最终的目标是尽可能最大化传播范围，这个问题是 NP hard 问题，但我们可以利用贪心方法解决。

这里我们的解决方法是利用贪心算法，给定初始传播者，候选集是每一个用户自身好友集合，每次从里面选影响力最大的，同时兼顾每一个初始用户容量限制，不停地迭代。

比如 V₁、V₂、V₃、V₄ 是 U₁、U₂ 所有好友，每个人会有一个自身可以触达到的用户数量。这个数值是通过底层传播模型仿真得到的。

第一种贪心思路是先从 4 个候选人里面选取影响范围最大的 V₂，他可以影响三个人，然后把 V₂ 分配给 U₁、U₂，这里随机分配给了 U₂，那么 U₂ 就等于是选满了。接着从 V₁、V₃、V₄ 里选，因为 V₂ 已经被选，V₁、V₃ 可以额外影响一个人，V₄ 可以影响两个人，但 U₂ capacity 已满，不能选择 V₄。这里选择 V₁，我们可以把 V₁ 再赋给 U₁，因为它还有 capacity。这样用贪心方法一轮轮迭代，直到所有用户选满为止。

第二种思路对候选集的划分是采用 round robin 形式，分别对当前仍然还有容量的初始传播者单独看其自身好友列表，从里面选取影响力最大的。针对上述例子，首先会选择 U₁，他可以影响三个人。U₂ 就不能再选 V₂，因为他已经被 U₁ 选过，剩下可以选择 V₄，因为它的边际收益最大。

考虑到方法的可扩展性和效率，我们借用了 SIGMOD‘18 的一个经典采样框架，大概思路是需要不停地 double 采样数量来看当前估计结果是否足够准确。

基于这个思路我们提出了 CIM 问题下的一个扩展性实现方式，最终的版本为 RR-OPIM+。我们分别将刚才提到的两种贪心方法加入进来，最终方法是（1/2-ε）近似比，同时可以保证其 running time 是近线性的。

我们对比了五个公开数据集，以及一个带有 ground truth spread 的腾讯内部数据集。

对比的方法处理刚才介绍的 Greedy 方法和它对应的可扩展性 implementation，还有一些比较直观的方法，比如单独给每一个初始的传播者选配一个好友，比如独立运行传统 IM 解决方法，或者直接用一些启发式方法如 Degree or PageRank。

我们通过广泛的评估发现，RR-OPIM+ 在 spread 和running time 上都可以超越其他方法。

除了公开数据集，我们还针对游戏场景做了一些实验。

第一部分是离线实验，我们的数据启动包含每一个用户在这次活动中的实际传播能力（ground truth），我们拿出这些有传播能力的用户作为 candidate，然后使用不同的方法，比如 Degree、PageRank 以及我们自己的方法，看选出来的这些用户谁的 spread 更大。我们提出的这三个方法，RR-OPIM+、MG-OPIM、RR-OPIM 的 spread 都比启发式方法更好。

之后我们做了线上部署，把 control group 直接用亲密度做排序，因为要推荐一些有影响力的人作为初始传播者，而 treatment group 在用亲密度排序之前，先用 RR-OPIM+ 方法对好友列表进行过滤，保留有影响力的用户，再把有影响力的用户根据他的亲密度进行排序，等于额外在亲密度基础上加了影响力过滤，我们发现其传播效果会比对照组更好。

以上就是我们 KDD 2023 工作中提出的更符合游戏中影响力最大化的算法。同时，我们提出了两种高效的贪心方法以及他们的可扩展性实现，并将其应用到了实际的传播场景之中。

以上就是本次分享的内容，谢谢大家。

03

Q&A

Q1：关于传播模型，具体是如何对传播概率进行建模的？

A1：

参见上图，P_ij 表示的是用户发出邀请的概率。我们本身会有用户历史数据，可以看到他发出过多少次邀请，我们可以直接用历史数据做 normalization。

这些 probability 无论是 P_ij 还是 β、γ 这些概率的选择跟我们传播模型的工作是正交的。也就是说我们可以用不同方法，比如 learning model，或者其他一些常用方法得到传播概率，然后利用我们提出的传播模型将这些 probability 串到一起。比如在 P_ij 学到点击的概率，β、γ 学到的是用户参与意愿，实际任务中可以把三种 probability 导入到 ICI 中去，进行下游传播任务的预测。

Q2：传播概率建模跟 CTR 很相关，CTR 主要是预测用户是否点击。所以它的衡量标准很简单，即 AUC 等线上指标，但这里介绍的工作中是一个传播模型，它的衡量指标是不是跟传统推荐系统中的衡量指标不太一样？

A2：我们任务中的 CTR 只是一个垂直内容作为输入，它是计算邀请概率的输入。针对传播场景中我们经常用到的一些评估指标，比如传播规模，这是比较宏观层面的指标。微观上的评估我们希望model 实现精准预测被命中人，可以用传统的 AUC or MAP 方法衡量。

Q3：传播模型 AB 测试中可能存在网络效应，实践中如何避免网络效应？

A3：社交网络 AB test 时会存在污染。我们采用的方式是先做聚类，划分出一些 community，在相同的 community 中划分 AB 组，利用 community level 的 AB test 缓解污染问题。

以上就是本次分享的内容，谢谢大家。

分享嘉宾

INTRODUCTION

张诗奇

新加坡国立大学

博士

张诗奇，新加坡国立大学计算学院博士毕业生。他的研究兴趣集中在随机游走邻近度和社交影响力两方面的高效计算及其实际应用。作为第一作者，他在 SIGMOD、SIGKDD、WWW 等 CCF-A 类会议上发表了 5 篇论文，并在 IJCAI 等多个国际会议上担任审稿人。他曾在腾讯互动娱乐事业群公共数据平台科研实习，并荣获月度最佳员工奖。此外，他还获得了新加坡国立大学计算机科学学院颁发的研究生研究优秀奖和研究成就奖。

活动推荐

往期推荐

点个在看你最好看

SPRING HAS ARRIVED