社會網(wǎng)絡下更新產(chǎn)品擴散的投放時機和種子優(yōu)化

翁克瑞,周 靜

(中國地質(zhì)大學 經(jīng)濟管理學院,武漢 430074)

近年來,面對快速的需求變化和技術更新,許多企業(yè)加速產(chǎn)品更新升級換代。在這一背景下,決策者需要從企業(yè)和產(chǎn)品生命周期角度考慮更新產(chǎn)品的發(fā)布和投放時間,以尋求全生命周期的產(chǎn)品利潤最大化。研究顯示,推遲上市的策略可以使廠商獲得更高的利潤和市場效果[1-2]。推遲上市的一個重要原因是避免擠壓舊產(chǎn)品的市場空間和利潤,同時在舊產(chǎn)品的口碑效應帶動下更好地促進新產(chǎn)品的市場滲透。許多企業(yè)運用了延期投放策略,例如蘋果公司大部分iPhone發(fā)布和發(fā)售的間隔不超過10天,而iPhone X的間隔時間有52天,美國市場調(diào)查機構Slice Intelligence的數(shù)據(jù)顯示,iPhone X預訂量是iPhone 6的1.25倍,延期投放使得蘋果X 預定數(shù)量和利潤增加。此外,豐田汽車也多次在中國市場延期推出已經(jīng)發(fā)布的新款汽車,以保證舊產(chǎn)品的利潤空間。由此可見,更新產(chǎn)品、技術等通過社會網(wǎng)絡進行擴散時,尋找合適的市場對象和投放時機已成為社交商務的一個重要研究方向。

現(xiàn)有學者研究的產(chǎn)品擴散模型基本分為宏觀擴散模型和微觀擴散模型。宏觀擴散從創(chuàng)新擴散的總體水平上對擴散現(xiàn)象進行描述,以Bass[3]模型為代表。針對Bass 模型僅考慮單一產(chǎn)品擴散問題,Norton等[4]提出一個經(jīng)典的多代更新高科技或耐用產(chǎn)品的生命過程銷售模型。宏觀擴散模型忽略了用戶的異質(zhì)性,沒有考慮具體的網(wǎng)絡結構。從微觀角度研究并建立微觀模型這一概念早有學者提出,Oren等[5]將消費者的某種異質(zhì)性引入到消費者個體采用決策模型中,并在此基礎上構建了一個新產(chǎn)品市場擴散模型。隨后,微觀擴散模型不斷發(fā)展,有滲流模型[6]、元胞自動機模型[7]、多Agent模型[8]、復雜網(wǎng)絡仿真模型[9]以及臨界值模型[10]等。現(xiàn)實中的世界網(wǎng)絡具有小世界和無標度特征,周琦萍等[9]和吳靖[11]指出,在社會網(wǎng)絡中選擇高度數(shù)節(jié)點作為種子可以促進擴散。李丹丹等[12]證明了控制群體影響力較大的節(jié)點能有效控制輿論傳播。相比宏觀模型,考慮社會網(wǎng)絡結構的微觀模型更真實地反映產(chǎn)品擴散的動態(tài)變化。

現(xiàn)有文獻中關于產(chǎn)品擴散的投放時間研究很少,主要有：Su等[13]建立了一個博弈論模型來研究新產(chǎn)品在競爭條件下的發(fā)布時間；許博等[14]認為廠商將產(chǎn)品投入市場時要考慮到所面臨的市場環(huán)境和成本因素；Shocker等[15]指出相對于單個產(chǎn)品的擴散,多代產(chǎn)品的擴散沒有得到足夠的重視；全雄文等[16]通過Bass銷售模型,建立了企業(yè)利潤模型,對更新產(chǎn)品投放市場時機的相關影響因素做了數(shù)值分析,認為更新產(chǎn)品投放時機與潛在市場用戶、產(chǎn)品利潤以及產(chǎn)品生命周期有關；龔田華等[17]通過運用最優(yōu)控制理論、擴散理論和方法建立了相關的擴散數(shù)學模型,分析了更新?lián)Q代產(chǎn)品投放時機和動態(tài)定價。然而,上述關于更新產(chǎn)品投放時機的研究仍然基于用戶的同質(zhì)性假定,沒有考慮社會網(wǎng)絡結構,也沒有考慮種子選擇問題。

更新產(chǎn)品、技術等在社會網(wǎng)絡擴散的投放時機和種子優(yōu)化決策可看作是在一個已存在舊產(chǎn)品的社會網(wǎng)絡G(N,E)中,產(chǎn)品以擴散模型P的形式傳播其影響力,但新產(chǎn)品投放時舊產(chǎn)品停止擴散,選擇投放階段t和p個新產(chǎn)品種子新舊產(chǎn)品利潤之和最大化。龔田華等[17]提出了兩類擴散模型：獨立集聯(lián)模型(Independent Cascade Model,ICM)與線性閾值模型(Linear Threshold Model,LTM),其中新產(chǎn)品擴散通常基于LTM。Kempe等[18]提出了求解種子的貪婪算法,傳統(tǒng)貪婪算法由于每次選取新節(jié)點加入種子集合時需要模擬擴散過程計算并更新所有候選種子的邊際影響力,因此時間復雜度過高。此后研究主要集中在大規(guī)模社交網(wǎng)絡算法的改進,如惰性計算[19-20]、最短路徑[21]、有向無圈圖[22]、局部樹[23]、局部鄰域[24]、度數(shù)修正[25]、學習自動機[26]、社團探尋[27-28]、進化算法[29-30]以及隨機超圖[31]等。然而,這些研究一般基于隨機閾值,難以反映消費者的個性特征和社會網(wǎng)絡的消費環(huán)境；在更新產(chǎn)品的擴散中,擴散模型將面臨確定性閾值。因此,本文研究社會網(wǎng)絡下更新產(chǎn)品擴散的投放時機和種子優(yōu)化(Launching Time and Seed Selection Optimization of Updated Product,LTSSOUP)問題：在一個已存在舊產(chǎn)品的社會網(wǎng)絡G(N,E)中,如果某節(jié)點收到來自已激活鄰居(指已購買舊產(chǎn)品和新產(chǎn)品的鄰居)的影響力不少于確定閾值則被激活,并影響自己的鄰居,當未有新節(jié)點時停止擴散,并假定新產(chǎn)品投放時舊產(chǎn)品停止擴散,如何選擇投放階段t和p個新產(chǎn)品的種子使得新舊產(chǎn)品利潤之和最大化。考慮更新產(chǎn)品的投放時機后,擴散模型將面臨確定閾值和動態(tài)種子選擇問題,傳統(tǒng)貪婪算法無法高效求解,尚不能處理大規(guī)模復雜網(wǎng)絡(如5 萬個節(jié)點以上的網(wǎng)絡)。

本文建立了社會網(wǎng)絡下LTSSOUP問題整數(shù)規(guī)劃模型,模型同時對更新產(chǎn)品的投入種子和投放時間進行優(yōu)化。對大規(guī)模LTSSOUP問題設計了多階段貪婪算法,該方法避免了重新計算擴散仿真,能夠高效率地更新邊際影響力并獲取最優(yōu)投放時機。實驗顯示：相比傳統(tǒng)貪婪算法,該算法具有更高的求解效率；相比度數(shù)下降法、隨機算法,該算法能夠得到更好的求解質(zhì)量。通過在一個真實網(wǎng)絡中進行擴散模擬,發(fā)現(xiàn)考慮社會網(wǎng)絡的種子優(yōu)化后,更新產(chǎn)品利潤小、種子數(shù)量少、計劃階段限制大時,延期投放容易使廠商獲得更高的利潤和市場效果。

1 整數(shù)規(guī)劃模型

在社會網(wǎng)絡G(N,E)中,N={1,2,…,n}為所有節(jié)點的集合,E為邊的集合。假定擴散階段為0→T1→T2,其中,T2為已知的最大擴散時間(假定的產(chǎn)品計劃期限),T1為最優(yōu)投放時間,在未投放新產(chǎn)品的情況下,可以計算所有階段的舊產(chǎn)品擴散情況,即舊產(chǎn)品在社會網(wǎng)絡中的激活情況是已知的參數(shù),令零一系數(shù)Sit表示這一參數(shù),即在第t階段且新產(chǎn)品未投時,節(jié)點i是否被舊產(chǎn)品激活。定義系數(shù)：θi為節(jié)點i的閾值；wji為j對i的影響力；p為更新產(chǎn)品的種子投放數(shù)量；C1為舊產(chǎn)品的單位利潤,C2為更新產(chǎn)品的單位利潤。0-1變量Xit表示第t階段時更新產(chǎn)品或舊產(chǎn)品是否激活節(jié)點i,即階段t時,i是否已購買更新產(chǎn)品或舊產(chǎn)品；0-1變量Ut表示第t階段是否投放更新產(chǎn)品,決定更新產(chǎn)品的投放時間T1；0-1變量Zit表示第t階段是否將i作為更新產(chǎn)品的種子。在產(chǎn)品擴散中：未激活節(jié)點的鄰居觀察自己收到的影響力是否超過自己的固定閾值,如果“是”則該鄰居被激活,如果沒有新的鄰居被激活則擴散結束；更新產(chǎn)品投放時,舊產(chǎn)品停止擴散。綜上定義,LTSSOUP 的零一整數(shù)規(guī)劃模型(P)為：

模型(P)中：目標函數(shù)式(1)表示所有產(chǎn)品利潤最大化,由于包括舊產(chǎn)品與新產(chǎn)品的激活用戶數(shù),故在式(1)左邊式子中用(C1-C2)扣除重復計算的利潤；約束式(2)表示在[1,T2]的某一階段投放更新產(chǎn)品；式(3)表示只能在Ut=1的階段投放更新產(chǎn)品的種子；式(4)表示初始種子自動為激活狀態(tài)；式(5)表示Xit繼承舊產(chǎn)品的激活狀態(tài)；式(6)表示更新產(chǎn)品的初始種子數(shù)量為p；式(7)表示節(jié)點i被激活必須滿足兩個條件之一：一是節(jié)點i是種子節(jié)點,二是節(jié)點i來自于已激活鄰居的影響力超過閾值；式(8)、(9)表示保證已激活的節(jié)點始終保持激活狀態(tài)。在本研究中,假定舊產(chǎn)品可以促進更新產(chǎn)品的傳播(例如,初代的良好口碑推動了后續(xù)產(chǎn)品的市場影響力)。因此,在式(7)中,影響力的計算考慮了所有Xit=1的鄰居,而Xit既反映了更新產(chǎn)品的激活狀態(tài)也反映了舊產(chǎn)品的激活狀態(tài)。

2 算 法

這一部分將介紹一種多階段貪婪算法(MSDG Multiple Stages Greedy Algorithm,MSDG),該算法的基本思想是：計劃期限T2內(nèi)的某一階段迭代選取新產(chǎn)品種子,并重新計算其他所有候選種子的邊際影響力,計算出所有情況的總收益,找出使總收益最大更新產(chǎn)品種子的投放階段和種子；同時,也提出了一種快速更新邊際影響力的方法,這種方法避免了重復的仿真?zhèn)鞑ビ嬎恪?/p>

正如Swaminathan[32]所描述的,在確定性閾值的社會影響力最大化模型中,候選種子的邊際影響力由計算得出。其中：(j,i)表示候選種子所有的傳播路徑上的弧,θi為節(jié)點i的當前閾值。假定舊產(chǎn)品對更新產(chǎn)品有促進作用,節(jié)點閾值會降低,當一個新產(chǎn)品種子的影響力到節(jié)點i時,MSDG 算法將會更新i節(jié)點的閾值至θ′i。然后,MSDG 算法會更新傳播路徑上能抵達i節(jié)點的所有候選種子(定義為傳入候選種子i)的邊際影響力。算法1模擬在產(chǎn)品全生命周期中任意階段加入第2代產(chǎn)品種子的擴散過程,調(diào)用算法1.1獲得第2代最優(yōu)種子,計算出所有情況的總收益,得出使總受益最大的第2代最優(yōu)的種子和其加入的最優(yōu)階段；算法1.1計算當前候選種子的邊際影響力、計算加入一個最優(yōu)種子后的所有候選種子矯正了的邊際影響力,采用基于邊際影響力糾正的貪婪算法進行種子選取。

算法1最優(yōu)投入階段與最優(yōu)種子優(yōu)化主程序。

輸入舊種子當前激活節(jié)點集合N,舊產(chǎn)品節(jié)點激活狀態(tài)R,更新產(chǎn)品種子數(shù)量p,舊產(chǎn)品和新產(chǎn)品單個收益C1和C2,影響力權重w,計劃階段限制T2,閾值θ,社會網(wǎng)絡圖G(N,E)。

輸出最優(yōu)投入階段T1與最優(yōu)種子S*。

步驟1擴散舊產(chǎn)品,計算投放擴散期限Steptime；初始化所有階段投放舊產(chǎn)品的總利潤Steptime(t)=0,初始化新產(chǎn)品投放時間t=0,初始化最優(yōu)種子S*=[]。

步驟2t=t+1。計算舊產(chǎn)品擴散到階段t時的所有節(jié)點激活狀態(tài)R,令ActiveNum1=以及所有節(jié)點受到的影響力Infed和剩余閾值θ′；計算新產(chǎn)品的擴散階段限制T3=T2-t。

步驟3調(diào)用算法1.1節(jié)的邊際影響力糾正貪婪算法(IRG)計算在t投放的優(yōu)選種子S(t)；將舊產(chǎn)品已激活的節(jié)點與新種子合并,S(t)=S(t)∪{i|Ri=1,i∈N}；模擬擴散過程,計算新產(chǎn)品投放后的激活節(jié)點數(shù)量ActiveNum2。

步驟4計算在階段T1投放的總收入

步驟5若t＜Steptime,則返回步驟2；否則,令T1=arg maxtStepIncome[t],S*=S[T1]。

算法1.1基于影響力糾正的種子選取算法。

輸入舊產(chǎn)品節(jié)點激活狀態(tài)R,更新產(chǎn)品種子個數(shù)p,影響力權重w,新產(chǎn)品的擴散階段限制T3,當前閾值θ′,社會網(wǎng)絡圖G(N,E),候選種子節(jié)點s。

輸出選取的種子集合S。

步驟1初始化種子集合S=?,信息詞典Inform={}。

步驟2對所有的候選節(jié)點i,計算邊際影響力MI[i],并更新信息詞典：

(1)構造一個初始隊列Q={s},初始化s的邊際影響力MI[s]=1,備份閾值θ′=θ,初始化信息詞典Inform={}；

(2)從隊列Q中取一個節(jié)點u=Q.get()；

(3)對所有的z∈N+(u)且滿足Rz=0與z?List Path,執(zhí)行：更新擴散階段,如果L[z]＜L[u]+1,則L[z]=L[u]+1；如果Wuz≥,則MI[s]=MI[s]+1,同時更新信息詞典(將[s,u,1]加入詞典Inform[z])并將z加入列表(若L[z]≤T3-1,則Q.enqueue(z)),如果Wuz＜,則,同時更新剩余閾值

(4)若隊列為空集,則計算結束。

步驟3初始化新產(chǎn)品種子數(shù)K=1。

用SPSS 13.0統(tǒng)計軟件對數(shù)據(jù)進行分析。將Ⅰ組、Ⅱ組靶區(qū)，心臟，患側(cè)肺，健側(cè)肺和甲狀腺等數(shù)據(jù)進行配對t檢驗分析，以P≤0.05表示差異具有統(tǒng)計學意義。

步驟4選擇邊際影響力最大的節(jié)點所有種子,即s=arg maxiMI[i]；合并種子S=S+s。

步驟5糾正其他候選節(jié)點的邊際影響力,并更新已激活節(jié)點R和信息詞典Inform；K=K+1。

(1)構造一個初始隊列Q={s},令Rs=1,θ′s=0,初始化節(jié)點的擴散階段L[：]=0,初始化擴散路徑ListPath={s}；

(2)從隊列Q中取一個節(jié)點u=Q.get()；

(3)對所有的z∈N+(u)且滿足Rz=0與z?List Path,執(zhí)行：更新擴散階段,如果L[z]＜L[u]+1,則L[z]=L[u]+1；如果Wuz≥則Rz=1,Qz=0,同時將z加入列表(若L[z]≤L[u]+1,則Q.enqueue(z)),并對Inform[z]的第i個元素更新邊際影響力,

(4)若隊列為空集,則計算結束。

步驟6若K＜p,則返回步驟4；否則,計算結束。

3 計算實驗與數(shù)值分析

實驗用Python編寫程序,測試電腦為聯(lián)想筆記本,配備2.1 GHz CPU(型號為AMD R5 3550H)、16 GB 2400 MHz內(nèi)存。測試調(diào)用Network 程序包(https：//networkx.github.io/)生成網(wǎng)絡。在算法比較時,采用Barabasi-Albert[33]模型生成網(wǎng)絡(又稱無標度網(wǎng)絡),該模型的生成過程：每次產(chǎn)生一個節(jié)點(直到生成n個節(jié)點),每個新節(jié)點從現(xiàn)有節(jié)點中選擇m個節(jié)點并相互連接,選擇概率與現(xiàn)有節(jié)點的個數(shù)成正比。在Python 中,生成網(wǎng)絡的方法為：nx.barabasi_albert_graph(n,m,隨機種子)。舊產(chǎn)品隨機種子為50,單位利潤C1=1。

表1描述了不限制新產(chǎn)品種子數(shù)量的情況下,MSDG、DD、RA 和DG 算法在求解質(zhì)量上的對比情況。對與最優(yōu)投放時機相關的參數(shù)T2、n、m、p和C2選擇不同水平的值,p取值10～200,控制n=1 500,m=3,C2=0.5,T2=10。測試結果發(fā)現(xiàn)：MSDG 算法時間復雜度較低,在計算時間上比DG算法提高了84%,具有較高的求解效率；MSDG 算法能夠使用更少的種子激活取得更多的激活數(shù)量,目標函數(shù)值比DD 算法提高了6%,比RA 算法提高了44%,具有較好的求解質(zhì)量。

表1 MSDG、DD、RA和DG算法實驗結果

同時,本文發(fā)現(xiàn),最優(yōu)投放時機與更新產(chǎn)品的單位利潤、更新產(chǎn)品的種子數(shù)量以及計劃階段限制有關系。在測試中,采用一個真實的社交網(wǎng)絡數(shù)據(jù)集Epinions,它是一個基于信任關系的網(wǎng)絡,也是一個產(chǎn)品評分網(wǎng)站,用戶可以根據(jù)產(chǎn)品評價信息選擇是否相信其他用戶,該數(shù)據(jù)集來自http：//snap.stanford.edu/data/index.html,常被用于社交網(wǎng)絡影響力方面的研究。數(shù)據(jù)集Epinions有75 879個節(jié)點,508 837條邊,控制參數(shù)C2、p和T2選擇不同水平的值。

令p=20,T2=15,最優(yōu)投放時機隨著更新產(chǎn)品單位利潤C2的增加而減小,即更新產(chǎn)品利潤小時,延期投放使得產(chǎn)品利潤更高。但是,隨著C2的增加,最優(yōu)投放時機的減小并不大,尤其是在C2＞C1的情況下,最優(yōu)投放時機幾乎沒有變化,如圖1所示。

圖1 更新產(chǎn)品單位利潤對投放時機的影響

令p=20,C2=0.5,最優(yōu)投放時機隨著計劃階段限制T2的增大而明顯增大,即計劃階段限制大的產(chǎn)品,延期投放會使得產(chǎn)品利潤更高,如圖2所示。

圖2 更新產(chǎn)品計劃階段限制對投放時機的影響

令T2=15,C2=0.5,實驗發(fā)現(xiàn),最優(yōu)投放時機隨著更新產(chǎn)品種子數(shù)量的增加而減少,即更新產(chǎn)品種子數(shù)量少的產(chǎn)品,延期投放會使得產(chǎn)品利潤更高,如圖3所示。

圖3 更新產(chǎn)品初種子數(shù)量對投放時機的影響

4 結語

本文立足于社會網(wǎng)絡的視角,考慮到現(xiàn)實社會中產(chǎn)品的更新?lián)Q代,提出了相對舊產(chǎn)品何時推出更新產(chǎn)品和選取種子節(jié)點使得企業(yè)的利潤最大的問題。本文建立了LTSSOUP問題整數(shù)規(guī)劃模型,對大規(guī)模LTSSOUP 問題設計了MSDG 算法,并將MSDG 算法與DD、RA 和DG 算法進行比較,顯示MSDG 算法比DG 算法具有更高的求解效率,比RA 和DG 算法具有較好的求解質(zhì)量。同時發(fā)現(xiàn),投放時機延后可使廠商獲得更高的利潤和市場效果,據(jù)此在一個真實網(wǎng)絡中進行擴散模擬,討論更新產(chǎn)品最優(yōu)投放時機與更新產(chǎn)品的單位利潤、更新產(chǎn)品的種子數(shù)量等因素的關系。針對這些相關因素進行數(shù)值分析,發(fā)現(xiàn)最優(yōu)投放時機隨著更新產(chǎn)品利潤C2、種子數(shù)量p的增加而減小,隨著計劃階段限制T2的增加而增加。并找出了最優(yōu)投放時機時選取的最優(yōu)種子,例如,在現(xiàn)實網(wǎng)絡數(shù)據(jù)集Epinions中,當T2=15,p=10,C2=0.5時,利用MSDG 算法可求得最優(yōu)投放時機為階段3,最優(yōu)的種子節(jié)點為[1 677,1 867,8 499,363,2 776,4 125,4 971,8 491,8 918,2 660],可為企業(yè)進行網(wǎng)絡營銷提供決策。然而,本文研究提供的模型只能求解較小規(guī)模的問題,多階段貪婪算法也無法在2 h內(nèi)求解50 000個節(jié)點的實例。因此,下一步的研究將重點針對超大網(wǎng)絡規(guī)模實例的求解算法。此外,該問題還可以在考慮新舊產(chǎn)品同時擴散的情況開展拓展研究。