面向線上-線下異步社會網絡的病毒式營銷算法

王長軍， 王葛格， 2

(1.東華大學 旭日工商管理學院，上海 200051; 2.杭州百世網絡技術有限公司，浙江 杭州 310013)

現實中，企業常借助口碑(word of mouth， WOM)實現在消費者中的“病毒式”擴散，激發需求，實現經營目標。無論是文獻[1]中傳統的面對面WOM相關研究，還是文獻[2-3]中基于互聯網媒體工具的e-WOM(electronic WOM)的相關研究，均驗證了信息傳播和市場結果間存在的直接聯系。因此，基于口碑傳播的病毒式營銷策略設計變得至關重要。

一般情況下，營銷者為部分用戶提供免費產品，希望其使用后能在朋友圈中進行宣傳，以吸引新用戶，并由此將影響擴散開來[4]。Domingos等[5]最早將這一問題歸結為網絡中的種子節點選取，旨在通過種子節點的社會聯系擴散口碑，以影響網絡中盡可能多的節點，實現影響最大化(influence maximization， IM)。IM問題的提出引發了研究者們廣泛的研究興趣，但目前相關研究大多針對單層社交網絡展開，故僅考慮了單種口碑[6]。實際中，面對面傳播的WOM和e-WOM同時存在，兩者分別依托線下和線上社會網絡，且網絡結構和傳播速度也不同，通常線上傳播速度快于線下[7]。針對這一雙層異步網絡，如何設計病毒式營銷策略以實現IM，成為決策者面臨的核心問題。

現有文獻在研究基于網絡的IM問題時關注兩個重點：一是構建口碑在網絡中各節點間的擴散機理；二是基于該機理選擇設計營銷策略，即選取口碑擴散的源頭(種子節點)。前者根據口碑擴散過程是確定的還是隨機的，將口碑擴散模型分為確定型[8]和不確定型兩類。后者由于能夠描述傳播過程中的隨機性而廣受關注，其中最常見的是獨立級聯(independent cascade， IC)模型[9-12]。IC模型中，一個已被成功影響(又稱激活)的節點會以一定的概率影響其未被激活的鄰居，由此進行傳播。繼而，大量研究關注了基于IC模型的種子節點選取。

Kempe等[9]較早深入研究了基于IC模型的IM問題，證明最優的種子節點選擇為NP-hard，并設計了選取種子節點的貪婪算法，利用函數的次模性證明了算法具有1-1的性能界，仿真結果也表明貪婪算法的表現優于傳統的出度規則和隨機選擇規則。但是，貪婪算法中的遍歷操作致使其時間復雜度很高，對于稍大的社交網絡存在伸縮性的缺點[13]。Leskovec等[14]利用目標函數次模性對貪婪算法進行改進，減少每次選擇初始種子節點的計算量，由此提出CELF(cost-effective lazy forward)算法。CELF算法運算速度較經典的貪婪算法有顯著提高，但仍難以應用于大規模網絡[15]。王長軍等[16]構建基于IC模型的馬爾科夫模型，采用貪婪算法進行種子節點的選取研究，但也只能針對小規模網絡進行仿真。

由于貪婪算法及其擴展算法存在問題，因此更多文獻考慮設計啟發式算法解決基于IC模型的IM問題。典型的如Chen等[15]提出的Single Discount算法和Degree Discount算法。這兩種算法都是基于“度(degree)”的算法，為避免鄰近的種子節點影響的重疊，兩者在度折算上采用不同的方式。仿真結果顯示，以上兩種算法在計算時間和效果上較出度規則和CELF算法都有著更為優異的綜合表現。Estevez等[17]考慮節點在網絡中的位置，提出集合覆蓋貪婪(set covering greedy， SCG)算法，以避免同一社團中的種子節點被選中，從而獲得影響的最大程度擴散，仿真表明該算法較出度規則和貪婪算法更為有效。然而，這些工作都是基于單層網絡。

近年來，有研究[7， 18-19]注意到多層網絡下的IM問題的重要性，并指出這是一個新的、快速發展的領域，但多數研究僅考慮多層線上網絡(如推特、Facebook)的信息傳播[13]。由于網絡特性相似，故而研究要么單獨對每層建模，再將每層影響直接疊加(如Erlandsson等[20])，要么將多層網絡縮減為單層網絡予以研究(如Zhang等[21])。這就忽略了不同層級網絡下WOM和e-WOM傳播可能具有的不同特性，如傳播異步性等[7， 22]。現有工作也未研究適用于單層網絡的啟發式算法是否能擴展至多層網絡這一問題。顯然，設計高效啟發式算法對解決現實中的大規模雙層網絡下的IM問題是至關重要的[6]。

綜上，本文擴展經典IC模型以描述影響WOM和e-WOM在雙層社交網絡下的病毒式傳播，并對經典的啟發式算法(包括Single Discount、 Degree Discount和SCG算法等)進行改造，解決雙層網絡下IM問題中的營銷策略設計問題，通過仿真對比分析其營銷結果。本文創新點：一是擴展了經典IC模型，構建適用于雙層異步網絡IM模型；二是設計可求解大規模情境下這一問題的啟發式算法；三是無論是模型構建還是算法設計，都考慮了WOM和e-WOM所依托的網絡結構和傳播速度的不同。

1 模型構建

依托雙層的線下和線上網絡，WOM和e-WOM分別進行傳播，并考慮傳播的不同步性。考慮現實情境，假設WOM傳播慢于e-WOM。為此，引入變量ξ(∈N+)，設定e-WOM在上層網絡中每周期傳播1次，而WOM每ξ個周期才傳播1次。為反映當前時刻t是否存在WOM傳播，引入0～1變量λ(t)，如式(1)所示。

(1)

式中：ξ|t表明t為ξ整數倍，λ(t)取1，表示WOM傳播也可起作用，反之，λ(t)為0，此時信息僅通過上層網絡傳播。

將經典IC模型擴展至雙層相依網絡的關鍵在于，網絡中任一節點如何處理來自于某鄰居節點由不同傳播途徑傳遞的信息的問題。注意到文獻[23，25]在相依網絡研究中對來自不同層級網絡的影響做疊加處理，可以理解為現實社交網絡中的人會受到WOM和e-WOM的疊加影響。基于這一想法，同時考慮λ(t)的存在，對IC模型進行擴展，則在t時刻，節點vi被vj激活的概率pij(t)可表述為式(2)。

(2)

該動態擴散過程始于種子節點的選取，即需從節點集合V中最多選取k(≤N)個節點，構成種子節點集合，定義為S，作為影響擴散的起點。另記最終被激活節點集合為δ(S)。假設決策者掌握準確的雙層相依網絡(V，Ez)信息，由此相應的IM問題如式(3)所示。

(3)

Kempe等[9]證明單層網絡下IM問題為NP-hard。顯然，對于大規模網絡，求解問題的精確解是困難的。為此，本文關注高效的啟發式算法的設計。

2 病毒式營銷中的種子節點選取算法設計

現有研究設計的Single Discount算法、Degree Discount算法和SCG算法已被成功應用于單層網絡，此處將3種算法進行擴展，以使其適用于上文的雙層相依網絡下的IM問題。

2.1 擴展Single Discount算法

輸入：(V，Ez) (z={u，l})，k和ξ

輸出：集合S

1：INITIALIZES=φ，N=|V|

2：FORi=1 toNDO

4：ENDFOR

5：FORt=1 tokDO

6： 找到vi=argmaxvi∈VShi(ξ)，更新S=S∪{vi}

7：FORvj∈VSDO

8：COMPUTEhj(ξ)=hj(ξ)-

10：ENDFOR

11：ENDFOR

12：OUTPUTS

2.2 擴展Degree Discount算法

輸入：(V，Ez)(z={u，l})，k和ξ

輸出：集合S

1：INITIALIZES=φ，N=|V|

2：FORi=1 toNDO

5：ENDFOR

6：FORt=1 tokDO

11：ENDFOR

12：ENDFOR

13：OUTPUTS

注意到以上算法的第10步中為修正vj的影響程度，故要判斷當vi被選作種子節點時對它的影響，因此，式中采用的是pji(t)而非pij(t)。

2.3 擴展SCG-d算法

輸入：(V，Ez)(z={u，l})，k、ξ和d

輸出： 集合S

1：INITIALIZES=φ，N=|V|

2：FORv=1 toNDO

4：ENDFOR

5：FORt=1 tokDO

6： 找到vi=argmaxvi∈VShi(ξ)，

8：ENDFOR

9：OUTPUTS

3 試驗與分析

基于擴展IC模型，利用所提的3種啟發式算法和傳統的Max Degree規則(即直接選取出度hi(ξ)最大的節點)與Random規則(即隨機選取種子節點)求解雙層相依網絡IM問題，觀察對比各自的營銷結果。

3.1 試驗設置

以人際間的線下和線上網絡為背景，構建仿真所需的雙層相依網絡。注意到線下人際關系滿足“六度分離”，具有典型的小世界特征[26]，而線上網絡不僅具有小世界特征，其“度”還服從冪律分布，符合無標度網絡[27]，故分別采用這兩個網絡構建仿真所需的線下和線上網絡，這一做法與文獻[3，22]一致。

小世界模型的構造算法[26]：(1)構建規則網絡。給定一含有I個點的環狀最近鄰耦合網絡，每個節點都與它左右相鄰的各Q/2個節點相連，其中Q為偶數。(2)隨機化連邊。隨機重新連接網絡中原有邊，即保持每條邊的一端點不變，而將另一端點改為連接至隨機選擇的一個節點，但不能有重邊和自環。

無標度模型的構造方法[27]：(1)增長。建立一個具有m0個節點的連通網絡，每次引入一新節點并且連到網絡中m(≤m0)個節點上。(2)優先連接。新節點會優先與網絡中連接度大的節點相連。

將從傳播概率、網絡結構、WOM/e-WOM傳播異步程度3等方面進行仿真試驗。其中，網絡節點數為10 000，種子節點數量k的取值規模取值為[5～50]。定義影響擴散比例(influence diffusion ratio， IDR)為IDR=|δ(S)|/N，即用激活節點數占網絡總節點比例來衡量營銷結果。為避免擴散模型的隨機性帶來的干擾，每組參數重復計算10次，將IDR均值作為仿真結果。

所有試驗均在配有Windows 10 64位操作系統、主頻為4.00 GHz、內存為32 GB的臺式電腦上運行，編程采用C語言。

3.2 基于不同影響傳播概率的試驗與分析

圖1 不同值下的仿真結果

表1 不同下SCG-3與其他算法IDR的差異Table 1 IDR difference between SCG-3 and other algorithms under different %

由圖1和表1可得出以下結果：

(1) 隨著激活概率的增大，各算法的IDR都呈上升趨勢。這是因為口碑在傳播能力強的網絡中的擴散范圍必然大于傳播能力弱的網絡。Single Discount、 Degree Discount和Max Degree算法的效果較為接近，這是因為從根本上它們都是基于節點出度做選擇的。

(3) SCG-3始終優于SCG-1，這是因為SCG-3考慮了更大的鄰域，減少種子節點的聚集情況，使傳播更為快速有效。

表2給出了k=50下的平均計算時間。不難發現，隨機算法的耗時最短，Max Degree只需計算一次所有節點的出度，耗時次之。SCG-1節省了節點出度更新的步驟，但需給出鄰域；SCG-3需要在更大的領域中搜索，耗時最長。但考慮到此處網絡規模為10 000個節點，不同算法的計算耗時都是可以接受的。

表2 k=50不同算法的平均運行時間Table 2 Calculation time of different algorithms when k=50 s

3.3 基于不同網絡結構的試驗與分析

選取4種不同的(Q，m，m0)組合，分別為Ⅰ=(4， 5， 5)、Ⅱ=(6， 7， 7)、Ⅲ=(8， 9， 9)、Ⅳ=(10， 11， 11)，用以表達不同的雙層網絡結構。節點間激活概率服從[0， 0.1]之間的均勻分布，ξ=1。

仿真結果見表3和圖2。結果表明：隨著網絡間連接的增加，各算法IDR逐漸改善。這是因為網絡中邊的數量和節點平均出度增大，利于WOM和e-WOM的擴散。隨網絡間節點連接的加強，SCG-1和SCG-3的所得結果改善明顯。這是因為節點間的鄰居節點重疊率在上升，激活行為重疊的現象也愈加明顯，而SCG算法能夠削弱種子節點重疊的概率并使之分布相對分散。各算法計算耗時與第3.2節結果相近，此處不再贅述。

表3 不同網絡結構下SCG-3與其他算法的IDR差異Table 3 IDR difference between SCG-3 and other algorithms under different network structures %

(a) 網絡結構Ⅰ

(b) 網絡結構Ⅱ

圖2 不同網絡結構下的仿真結果

3.4 基于WOM/e-WOM異步程度的試驗與分析

研究不同傳播異質程度下的營銷結果，取ξ={2， 4， 6， 8}，Q=10，m=10，m0=10。雙層網絡中各節點間激活概率服從[0， 0.1]的均勻分布。

觀察差異化網絡傳播異步程度時SCG與其他算法的IDR百分比差異(見表4)和IDR變化情況(見圖3)，可以得出：隨著WOM/e-WOM傳播異步程度的增加，式(2)中λ=1的情形越來越少，節點間的總體激活概率減小，導致各方法的營銷結果普遍變差。此外，在這一網絡結構下，無論ξ取何值，SCG算法的結果始終穩定地優于Single Discount、 Degree Discount以及Max Degree等基于度的算法。

表4 差異化WOM/e-WOM傳播異步程度時SCG-3算法與其他算法的IDR差異Table 4 IDR difference between SCG-3 and other algorithms under different asynchronous extents of WOM/e-WOM diffusion %

(a) ξ=2

(b) ξ=4

(c) ξ=6

(d) ξ=8

4 結 語

基于口碑的病毒式傳播已成為企業獲取需求的重要方式。在復雜的商業環境中，口碑以不同形式結合不同的途徑進行傳播，典型的則是面對面的傳統口碑和基于互聯網媒介的數字化口碑的共存。研究面向雙層異步網絡病毒式口碑營銷策略，擴展經典獨立級聯模型，構建相應的影響最大化模型，并將單層網絡下的典型種子節點選取算法擴展到雙層相依網絡下，以解決營銷策略的制定問題。結果表明：所設計的基于度的算法和集合覆蓋算法明顯優于傳統的隨機規則和最大度規則，揭示不同算法對于不同傳播概率以及網絡結構情境的適用性，同時發現傳播異步性對于以上算法的營銷效果的負面影響。此外，包括消費者規模、網絡結構、口碑傳播概率以及異步性等在內的市場信息，對于成功展開病毒式營銷、預測營銷結果是至關重要的。顯然，這一問題的研究和相關結論對于身處復雜信息傳播環境的企業營銷決策有著重要意義。

后續研究可從3個方面展開：(1)在口碑方面，僅考慮了2種不同的口碑形式，而未考慮口碑的內容，關于正負口碑的研究已不鮮見，但在雙層網絡上考慮口碑的正負性還有待進一步研究。(2)本文揭示傳播概率和網絡結構等因素對于營銷效果的影響，可以繼而考慮雙層網絡中不同影響概率分布以及人群的社團效應，設計更有針對性的種子節點選取方法，以解決復雜場景下的現實問題。(3)本文假設決策者掌握準確的網絡結構信息，這對于線上網絡是可能的，但對于線下人際關系網絡并不容易。因此，如何在網絡信息有限的情況下進行病毒式營銷也是未來一個重要的研究問題。