本文將分享新加坡國(guó)立大學(xué)與騰訊互娛在社交傳播和影響力算法方面的實(shí)踐與探索。文章將介紹如何將用戶傳播能力指標(biāo)用于熟人推薦和排序場(chǎng)景，如何將社交影響力最大化的算法用于游戲中的病毒式營(yíng)銷場(chǎng)景，以及如何提出影響力最大化的新變種，以更好地適配活動(dòng)推廣場(chǎng)景。社交推薦和病毒式營(yíng)銷的場(chǎng)景是基于我們?cè)?WWW2024 的工作，我們通過(guò)對(duì)底層傳播行為進(jìn)行建模來(lái)解決這兩個(gè)場(chǎng)景的問(wèn)題。第三個(gè)問(wèn)題則是基于 KDD2023 的一項(xiàng)工作。

一、將用戶傳播能力指標(biāo)用于熟人推薦場(chǎng)景

首先介紹如何將用戶傳播能力指標(biāo)用于熟人推薦場(chǎng)景。這個(gè)工作是我們基于騰訊游戲中的邀請(qǐng)行為進(jìn)行的傳播模型的刻畫(huà)和建模。

游戲場(chǎng)景中有很多熟人邀請(qǐng)機(jī)制，以騰訊游戲?yàn)槔?，其中包含很多底層好友關(guān)系，比如微信和 QQ 好友，我們可以在游戲中通過(guò)活動(dòng)來(lái)促進(jìn)好友交互。這些交互就需要依托邀請(qǐng)面板，可以給定一定數(shù)量的好友，邀請(qǐng)大家一起來(lái)做活動(dòng)。針對(duì)這種常見(jiàn)的邀請(qǐng)場(chǎng)景，我們通過(guò) empirical study 發(fā)現(xiàn)邀請(qǐng)行為會(huì)存在傳播級(jí)聯(lián)現(xiàn)象，下圖右側(cè)直方圖展示的是某一期活動(dòng)里的傳播數(shù)深度，可以看到傳播數(shù)深度大于 1 的情況至少占了 44%，這一發(fā)現(xiàn)促使我們?nèi)パ芯坑脩舻难?qǐng)行為是如何在社交網(wǎng)絡(luò)中傳播的。

刻畫(huà)傳播行為需要定義一個(gè)合適的傳播模型，比較直觀常用到的方法是獨(dú)立級(jí)聯(lián)模型，這個(gè)模型比較籠統(tǒng)地將用戶對(duì)用戶的影響用獨(dú)立概率 Puv 表示，但我們無(wú)法直接使用此 IC model，原因是它對(duì)影響力概念的刻畫(huà)過(guò)于寬泛，沒(méi)有考慮到實(shí)際業(yè)務(wù)場(chǎng)景中很多其它的需求，更確切地說(shuō)它忽略了轉(zhuǎn)化漏斗的概念。

轉(zhuǎn)化漏斗是營(yíng)銷場(chǎng)景中的一個(gè)常見(jiàn)概念，它描述的是用戶行為的多級(jí)轉(zhuǎn)化。我們可以大致將用戶體驗(yàn)或他的行為分為三個(gè)階段，第一階段是最初級(jí)階段，我們?cè)谧鲂缕放仆茝V時(shí)可能只需要讓用戶有初步品牌認(rèn)識(shí)；進(jìn)一步我們希望用戶有更深層次的被動(dòng)響應(yīng)，對(duì)應(yīng)轉(zhuǎn)化漏斗中的第二階段，即 adoption 階段，第二階段對(duì)應(yīng)用戶行為，可能是用戶的點(diǎn)贊和喜歡，這會(huì)與用戶在平臺(tái)的活躍度、DAU 等指標(biāo)相關(guān)；第三階段是最深層次的一個(gè)階段，這一階段我們希望用戶能從被動(dòng)接受轉(zhuǎn)變?yōu)橹鲃?dòng)響應(yīng)，因此這一階段稱為 action 階段。這一步會(huì)與電商這類跟收益相關(guān)的場(chǎng)景有關(guān)。

在這三個(gè)階段中，用戶都被影響到了，而每一個(gè)階段對(duì)應(yīng)的應(yīng)用場(chǎng)景都不一樣，每一個(gè)場(chǎng)景都十分關(guān)鍵，因此我們希望引入轉(zhuǎn)化漏斗的概念進(jìn)行傳播模型的建模。

轉(zhuǎn)化漏斗在邀請(qǐng)場(chǎng)景中也存在，對(duì)一個(gè)用戶來(lái)說(shuō)，最開(kāi)始階段沒(méi)有收到任何邀請(qǐng)信息，也就是 uninformed；如果有好友對(duì)他發(fā)出邀請(qǐng)，他會(huì)收到邀請(qǐng)?zhí)崾?，?huì)處于知悉狀態(tài)；然后他可以選擇是否接受，接受對(duì)應(yīng)轉(zhuǎn)化漏斗第二階段；inviting 是他在做完活動(dòng)后體驗(yàn)不錯(cuò)，會(huì)再主動(dòng)邀請(qǐng)他的好友，這是轉(zhuǎn)化漏斗第三階段-主動(dòng)行動(dòng)。所以邀請(qǐng)行為是轉(zhuǎn)化漏斗的一種實(shí)例。

因此我們想在現(xiàn)有經(jīng)典的 IC 獨(dú)立級(jí)聯(lián)模型上引入轉(zhuǎn)化漏斗概念。這里每個(gè)節(jié)點(diǎn)表示的是用戶，每一條邊表示好友關(guān)系，邊上會(huì)包含一個(gè)點(diǎn)是邀請(qǐng)的概率，每一個(gè)用戶不同的顏色表示其不同狀態(tài)，比如灰色是暫時(shí)還未被觸達(dá)，紅色表示他是邀請(qǐng)者，黃色表示他是被邀請(qǐng)者，被邀請(qǐng)者可以進(jìn)一步轉(zhuǎn)化為接受者，即橙色。

這個(gè)模型是基于模擬的方式刻畫(huà)用戶行為，初始時(shí)給定一些現(xiàn)有的初始邀請(qǐng)者，每一步我們對(duì)現(xiàn)有邀請(qǐng)者去做仿真。

讓他以一定邀請(qǐng)概率選擇一個(gè)他的鄰居好友發(fā)出邀請(qǐng)，針對(duì)已經(jīng)接收到邀請(qǐng)的好友 Vj，他會(huì)以一定轉(zhuǎn)化概率變成接受者，進(jìn)一步他會(huì)以一個(gè) γ 概率轉(zhuǎn)換為新的邀請(qǐng)者。

這里我們只是提出比較 general 的傳播行為的建模。這里的每一個(gè)概率都可以用現(xiàn)有的正交方法解決，比如 Pij 可以用 CTR 技術(shù)找到用戶的邀請(qǐng)概率，β 和 γ 可以利用一些歷史數(shù)據(jù)找到每一個(gè)用戶轉(zhuǎn)化行為的分布。

每一次仿真會(huì)從初始邀請(qǐng)者出發(fā)，不斷重復(fù)仿真過(guò)程，直到?jīng)]有新的邀請(qǐng)者出現(xiàn)，一次仿真結(jié)束。我們可能會(huì)進(jìn)行多次仿真從而得到穩(wěn)定的結(jié)果。

我們做了四個(gè)實(shí)驗(yàn)，兩個(gè)是離線探索，兩個(gè)是線上探索。一類是 cascade estimation，給定初始邀請(qǐng)者集合，希望可以估計(jì)其傳播范圍，我們將傳播范圍定義為接受者數(shù)量，真實(shí)場(chǎng)景中可以根據(jù)不同業(yè)務(wù)需求選擇其他估計(jì)狀態(tài)（stage）。我們這里的做法是給定不同傳播模型，進(jìn)行多次蒙特卡洛模擬判斷給定邀請(qǐng)者可以帶來(lái)的平均接受者數(shù)量。

這里實(shí)驗(yàn)比較的是 RMSE，我們一共實(shí)驗(yàn)了 6 個(gè)數(shù)據(jù)集，包括 4 個(gè)騰訊內(nèi)部的邀請(qǐng)數(shù)據(jù)集和 2 個(gè)公開(kāi)數(shù)據(jù)集，可以看到我們提出的 ICI 方法的 RMSE 最小。

仿真技術(shù)指給定種子集即初始邀請(qǐng)人，我們希望能預(yù)測(cè)出其他用戶在梯次模擬中有多少次被激活。我們把比例作為 prediction，可以接入不同的 diffusion model，因此我們對(duì)比了 6 個(gè)不同的傳播模型。

實(shí)驗(yàn)數(shù)據(jù)表明，在 6 個(gè)數(shù)據(jù)集上除了 Diggs 我們模型的 AUC 和 MAP 指標(biāo)處于第二位置，其他都是 outperform other competitors。

游戲中的熟人推薦場(chǎng)景，目標(biāo)是給用戶推薦他的熟人，提升他們的組隊(duì)意愿，從而提高游戲參與度。為了把 ICI model 接入進(jìn)來(lái)，我們引入了 influence spread 作為影響力中心度，針對(duì)每一個(gè)用戶去計(jì)算其單點(diǎn)傳播能力，將每個(gè)好友的單點(diǎn)傳播能力做降序排序選擇 top k 進(jìn)行推薦。而傳統(tǒng)算法是基于親密度等歷史交互指標(biāo)進(jìn)行排序加推薦。

我們?cè)趦蓚€(gè)角色扮演游戲抽獎(jiǎng)活動(dòng)中進(jìn)行了實(shí)驗(yàn)，這個(gè)活動(dòng)除了抽獎(jiǎng)還會(huì)設(shè)計(jì)支付行為，支付行為是主動(dòng)行為，還會(huì)有邀請(qǐng)面板做好友邀請(qǐng)，讓大家一起參與抽獎(jiǎng)活動(dòng)享受折扣。我們上線觀察兩種行為指標(biāo)，發(fā)現(xiàn)基于傳播和影響力的兩種方法 ICI 和 IC，它們的效果都優(yōu)于傳統(tǒng)親密度方法。

游戲中對(duì)應(yīng)的病毒式營(yíng)銷是星云傳播，我們選影響力足夠大的種子用戶將其初始化為幸運(yùn)用戶，幸運(yùn)用戶可能會(huì)有雙倍積分，或者一些其他福利。當(dāng)幸運(yùn)用戶與其好友對(duì)戰(zhàn)后，好友會(huì)繼承其特權(quán)，特權(quán)不是傳遞關(guān)系，而是復(fù)制關(guān)系。我們目標(biāo)是選定初始 k 個(gè)有影響力的用戶盡可能讓整個(gè)活動(dòng)參與度最高。

根據(jù)我們?cè)?battle royale game 實(shí)際上線帶來(lái)的傳播增量上來(lái)看，基于影響力最大化方法的效果，不論是傳播的增量，還是邀請(qǐng)率都會(huì)比傳統(tǒng)基于 degree 的方法好。這也說(shuō)明之前在學(xué)術(shù)界廣泛研究的影響力最大化問(wèn)題可以在工業(yè)界實(shí)際應(yīng)用。底層模型 diffusion model 的建模也會(huì)對(duì)算法產(chǎn)生一定影響。我們新提出的 ICI model 比傳統(tǒng)的 IC 模型有著顯著的效果提升。

我們?cè)?WWW 的工作提出了一個(gè)簡(jiǎn)單易用的對(duì)于用戶邀請(qǐng)行為傳播的建模。我們主要在傳播規(guī)模估計(jì)和擴(kuò)散預(yù)測(cè)上做了一些離線的實(shí)驗(yàn)，無(wú)論是在騰訊內(nèi)部的數(shù)據(jù)集，還是公開(kāi)的數(shù)據(jù)集上，都取得了不錯(cuò)的效果。同時(shí)我們也在實(shí)際的好友排序和病毒式營(yíng)銷的場(chǎng)景中進(jìn)行了落地實(shí)踐。

二、影響力最大化新變種以更好適配活動(dòng)推廣場(chǎng)景

接下來(lái)介紹我們?cè)?KDD 2023 的一項(xiàng)工作，也是基于游戲社交網(wǎng)絡(luò)考慮用戶傳播能力和影響力的一項(xiàng)工作。

前文中提到了影響力最大化的問(wèn)題，其主要應(yīng)用場(chǎng)景就是病毒營(yíng)銷的場(chǎng)景。在一個(gè)社交網(wǎng)絡(luò)中，我們希望商家自己主動(dòng)選一些種子用戶，具體場(chǎng)景可以理解為帶貨，種子用戶收取商家的錢(qián)，去幫忙做推廣，推廣的方式是利用其自身影響力零成本傳播，例如利用其口碑效應(yīng)傳播給他的粉絲或好友，他的好友也進(jìn)一步傳播，在病毒式營(yíng)銷場(chǎng)景里形成影響力擴(kuò)散。

給定一個(gè)商家的預(yù)算，比如他只想選 k 個(gè)網(wǎng)紅做初始推廣，我們?nèi)绾螏椭x擇k 個(gè)人，使他最終活動(dòng)觸達(dá)的范圍最廣？這就是影響力最大化問(wèn)題的最原始定義。

解決這個(gè)問(wèn)題的辦法是先找一個(gè)底層傳播模型，把底層傳播模型作為傳播范圍的評(píng)估方式。

比如給定一些初始用戶，可以依托于底層傳播模型，做蒙特卡洛仿真，或用其他方法估計(jì)這些用戶的實(shí)際傳播范圍，進(jìn)而利用貪心方法迭代選擇一組影響力最大的種子用戶。

傳統(tǒng)的影響力最大化問(wèn)題存在一些限制。

在實(shí)際探索中我們發(fā)現(xiàn)，傳統(tǒng)影響力最大化算法本身是服務(wù)于病毒式營(yíng)銷場(chǎng)景。雖然游戲中有病毒式營(yíng)銷場(chǎng)景，但其與傳統(tǒng)病毒營(yíng)銷區(qū)別在于游戲中不需要付費(fèi)給玩家。但玩家登錄游戲時(shí)間有限，游戲時(shí)長(zhǎng)這個(gè) capacity 相比于 cost 在游戲場(chǎng)景中更值得關(guān)注。

第二點(diǎn)限制是在傳統(tǒng)的影響力最大化場(chǎng)景，商家付費(fèi)給傳播者，讓其參與。但是游戲里的活動(dòng)需要依靠用戶主觀能動(dòng)性，主動(dòng)參與。根據(jù)在游戲場(chǎng)景下的數(shù)據(jù)觀察，我們發(fā)現(xiàn)傳播能力比較強(qiáng)的用戶往往不會(huì)主動(dòng)參加活動(dòng)，反而是一些比較活躍但自身傳播能力不強(qiáng)的用戶特別喜歡參與活動(dòng)，并邀請(qǐng)其好友。

這就引出一個(gè)問(wèn)題，如何讓這些有實(shí)際影響力、傳播能力的用戶參與進(jìn)來(lái)？我們想到的方法是通過(guò)他們的活躍好友對(duì)其發(fā)出邀請(qǐng)，而不是直接推送。

針對(duì)游戲活動(dòng)推廣中的缺陷和挑戰(zhàn)，我們提出了基于容量（capacity） 限制的影響力最大化問(wèn)題。我們的輸入是社交網(wǎng)絡(luò)和給定的傳播模型還有初始參與者，初始參與者就是這些活躍度和參與意愿很高的用戶，我們給他們提供一個(gè)邀請(qǐng)窗口，邀請(qǐng)窗口大小根據(jù)其自身 capacity 限制，我們只會(huì)給他推薦 k 個(gè)好友，基于之前觀察的經(jīng)驗(yàn)，我們希望他收到的好友是盡可能有影響力的好友。

之后我們借助 influential friends 進(jìn)一步推廣活動(dòng)。最終的目標(biāo)是盡可能最大化傳播范圍，這個(gè)問(wèn)題是 NP hard 問(wèn)題，但我們可以利用貪心方法解決。

這里我們的解決方法是利用貪心算法，給定初始傳播者，候選集是每一個(gè)用戶自身好友集合，每次從里面選影響力最大的，同時(shí)兼顧每一個(gè)初始用戶容量限制，不停地迭代。

比如 V₁、V₂、V₃、V₄ 是 U₁、U₂ 所有好友，每個(gè)人會(huì)有一個(gè)自身可以觸達(dá)到的用戶數(shù)量。這個(gè)數(shù)值是通過(guò)底層傳播模型仿真得到的。

第一種貪心思路是先從 4 個(gè)候選人里面選取影響范圍最大的 V₂，他可以影響三個(gè)人，然后把 V₂ 分配給 U₁、U₂，這里隨機(jī)分配給了 U₂，那么 U₂ 就等于是選滿了。接著從 V₁、V₃、V₄ 里選，因?yàn)?V₂ 已經(jīng)被選，V₁、V₃ 可以額外影響一個(gè)人，V₄ 可以影響兩個(gè)人，但 U₂ capacity 已滿，不能選擇 V₄。這里選擇 V₁，我們可以把 V₁ 再賦給 U₁，因?yàn)樗€有 capacity。這樣用貪心方法一輪輪迭代，直到所有用戶選滿為止。

第二種思路對(duì)候選集的劃分是采用 round robin 形式，分別對(duì)當(dāng)前仍然還有容量的初始傳播者單獨(dú)看其自身好友列表，從里面選取影響力最大的。針對(duì)上述例子，首先會(huì)選擇 U₁，他可以影響三個(gè)人。U₂ 就不能再選 V₂，因?yàn)樗呀?jīng)被 U₁ 選過(guò)，剩下可以選擇 V₄，因?yàn)樗倪呺H收益最大。

考慮到方法的可擴(kuò)展性和效率，我們借用了 SIGMOD‘18 的一個(gè)經(jīng)典采樣框架，大概思路是需要不停地 double 采樣數(shù)量來(lái)看當(dāng)前估計(jì)結(jié)果是否足夠準(zhǔn)確。

基于這個(gè)思路我們提出了 CIM 問(wèn)題下的一個(gè)擴(kuò)展性實(shí)現(xiàn)方式，最終的版本為 RR-OPIM+。我們分別將剛才提到的兩種貪心方法加入進(jìn)來(lái)，最終方法是（1/2-ε）近似比，同時(shí)可以保證其 running time 是近線性的。

我們對(duì)比了五個(gè)公開(kāi)數(shù)據(jù)集，以及一個(gè)帶有 ground truth spread 的騰訊內(nèi)部數(shù)據(jù)集。

對(duì)比的方法處理剛才介紹的 Greedy 方法和它對(duì)應(yīng)的可擴(kuò)展性 implementation，還有一些比較直觀的方法，比如單獨(dú)給每一個(gè)初始的傳播者選配一個(gè)好友，比如獨(dú)立運(yùn)行傳統(tǒng) IM 解決方法，或者直接用一些啟發(fā)式方法如 Degree or PageRank。

我們通過(guò)廣泛的評(píng)估發(fā)現(xiàn)，RR-OPIM+ 在 spread 和running time 上都可以超越其他方法。

除了公開(kāi)數(shù)據(jù)集，我們還針對(duì)游戲場(chǎng)景做了一些實(shí)驗(yàn)。

第一部分是離線實(shí)驗(yàn)，我們的數(shù)據(jù)啟動(dòng)包含每一個(gè)用戶在這次活動(dòng)中的實(shí)際傳播能力（ground truth），我們拿出這些有傳播能力的用戶作為 candidate，然后使用不同的方法，比如 Degree、PageRank 以及我們自己的方法，看選出來(lái)的這些用戶誰(shuí)的 spread 更大。我們提出的這三個(gè)方法，RR-OPIM+、MG-OPIM、RR-OPIM 的 spread 都比啟發(fā)式方法更好。

之后我們做了線上部署，把 control group 直接用親密度做排序，因?yàn)橐扑]一些有影響力的人作為初始傳播者，而 treatment group 在用親密度排序之前，先用 RR-OPIM+ 方法對(duì)好友列表進(jìn)行過(guò)濾，保留有影響力的用戶，再把有影響力的用戶根據(jù)他的親密度進(jìn)行排序，等于額外在親密度基礎(chǔ)上加了影響力過(guò)濾，我們發(fā)現(xiàn)其傳播效果會(huì)比對(duì)照組更好。

以上就是我們 KDD 2023 工作中提出的更符合游戲中影響力最大化的算法。同時(shí)，我們提出了兩種高效的貪心方法以及他們的可擴(kuò)展性實(shí)現(xiàn)，并將其應(yīng)用到了實(shí)際的傳播場(chǎng)景之中。

以上就是本次分享的內(nèi)容，謝謝大家。

三、Q&A

Q1：關(guān)于傳播模型，具體是如何對(duì)傳播概率進(jìn)行建模的？

A1：

參見(jiàn)上圖，P_ij 表示的是用戶發(fā)出邀請(qǐng)的概率。我們本身會(huì)有用戶歷史數(shù)據(jù)，可以看到他發(fā)出過(guò)多少次邀請(qǐng)，我們可以直接用歷史數(shù)據(jù)做 normalization。

這些 probability 無(wú)論是 P_ij 還是 β、γ 這些概率的選擇跟我們傳播模型的工作是正交的。也就是說(shuō)我們可以用不同方法，比如 learning model，或者其他一些常用方法得到傳播概率，然后利用我們提出的傳播模型將這些 probability 串到一起。比如在 P_ij 學(xué)到點(diǎn)擊的概率，β、γ 學(xué)到的是用戶參與意愿，實(shí)際任務(wù)中可以把三種 probability 導(dǎo)入到 ICI 中去，進(jìn)行下游傳播任務(wù)的預(yù)測(cè)。

Q2：傳播概率建模跟 CTR 很相關(guān)，CTR 主要是預(yù)測(cè)用戶是否點(diǎn)擊。所以它的衡量標(biāo)準(zhǔn)很簡(jiǎn)單，即 AUC 等線上指標(biāo)，但這里介紹的工作中是一個(gè)傳播模型，它的衡量指標(biāo)是不是跟傳統(tǒng)推薦系統(tǒng)中的衡量指標(biāo)不太一樣？

A2：我們?nèi)蝿?wù)中的 CTR 只是一個(gè)垂直內(nèi)容作為輸入，它是計(jì)算邀請(qǐng)概率的輸入。針對(duì)傳播場(chǎng)景中我們經(jīng)常用到的一些評(píng)估指標(biāo)，比如傳播規(guī)模，這是比較宏觀層面的指標(biāo)。微觀上的評(píng)估我們希望model 實(shí)現(xiàn)精準(zhǔn)預(yù)測(cè)被命中人，可以用傳統(tǒng)的 AUC or MAP 方法衡量。

Q3：傳播模型 AB 測(cè)試中可能存在網(wǎng)絡(luò)效應(yīng)，實(shí)踐中如何避免網(wǎng)絡(luò)效應(yīng)？

A3：社交網(wǎng)絡(luò) AB test 時(shí)會(huì)存在污染。我們采用的方式是先做聚類，劃分出一些 community，在相同的 community 中劃分 AB 組，利用 community level 的 AB test 緩解污染問(wèn)題。