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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二、影響力最大化新變種以更好適配活動推廣場景

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

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

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

解決這個問題的辦法是先找一個底層傳播模型，把底層傳播模型作為傳播范圍的評估方式。

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

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

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

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

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

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

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

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

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

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

第二種思路對候選集的劃分是采用 round robin 形式，分別對當(dāng)前仍然還有容量的初始傳播者單獨看其自身好友列表，從里面選取影響力最大的。針對上述例子，首先會選擇 U₁，他可以影響三個人。U₂ 就不能再選 V₂，因為他已經(jīng)被 U₁ 選過，剩下可以選擇 V₄，因為它的邊際收益最大。

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

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

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

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

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

除了公開數(shù)據(jù)集，我們還針對游戲場景做了一些實驗。

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

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

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

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

三、Q&A

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

A1：

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

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

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

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

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

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