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

一、將用戶傳播能力指標用于熟人推薦場景

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

游戲場景中有很多熟人邀請機制，以騰訊游戲為例，其中包含很多底層好友關(guān)系，比如微信和 QQ 好友，我們可以在游戲中通過活動來促進好友交互。這些交互就需要依托邀請面板，可以給定一定數(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)化。我們可以大致將用戶體驗或他的行為分為三個階段，第一階段是最初級階段，我們在做新品牌推廣時可能只需要讓用戶有初步品牌認識；進一步我們希望用戶有更深層次的被動響應(yīng)，對應(yīng)轉(zhuǎn)化漏斗中的第二階段，即 adoption 階段，第二階段對應(yīng)用戶行為，可能是用戶的點贊和喜歡，這會與用戶在平臺的活躍度、DAU 等指標相關(guān)；第三階段是最深層次的一個階段，這一階段我們希望用戶能從被動接受轉(zhuǎn)變?yōu)橹鲃禹憫?yīng)，因此這一階段稱為 action 階段。這一步會與電商這類跟收益相關(guān)的場景有關(guān)。

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

轉(zhuǎn)化漏斗在邀請場景中也存在，對一個用戶來說，最開始階段沒有收到任何邀請信息，也就是 uninformed；如果有好友對他發(fā)出邀請，他會收到邀請?zhí)崾荆瑫幱谥顟B(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)，比如灰色是暫時還未被觸達，紅色表示他是邀請者，黃色表示他是被邀請者，被邀請者可以進一步轉(zhuǎn)化為接受者，即橙色。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一種貪心思路是先從 4 個候選人里面選取影響范圍最大的 V₂，他可以影響三個人，然后把 V₂ 分配給 U₁、U₂，這里隨機分配給了 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₄，因為它的邊際收益最大。

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

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

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

對比的方法處理剛才介紹的 Greedy 方法和它對應(yīng)的可擴展性 implementation，還有一些比較直觀的方法，比如單獨給每一個初始的傳播者選配一個好友，比如獨立運行傳統(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ù)他的親密度進行排序，等于額外在親密度基礎(chǔ)上加了影響力過濾，我們發(fā)現(xiàn)其傳播效果會比對照組更好。

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

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

三、Q&A

Q1：關(guā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 中去，進行下游傳播任務(wù)的預(yù)測。

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

A2：我們?nèi)蝿?wù)中的 CTR 只是一個垂直內(nèi)容作為輸入，它是計算邀請概率的輸入。針對傳播場景中我們經(jīng)常用到的一些評估指標，比如傳播規(guī)模，這是比較宏觀層面的指標。微觀上的評估我們希望model 實現(xià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 緩解污染問題。