翁克瑞,沈 卉,侯俊東

(中國地質(zhì)大學(xué)(武漢)經(jīng)濟管理學(xué)院，武漢 430078)

0 引言

近年來，社交網(wǎng)絡(luò)的發(fā)展引人注目，這為病毒式營銷創(chuàng)造了廣闊的平臺，即公司選擇一定數(shù)量的有影響力的個人作為目標，通過口碑效應(yīng)創(chuàng)造出大量的用戶。影響力最大化問題為病毒式營銷的理論基礎(chǔ)，更正式地說，給定一個社交網(wǎng)絡(luò)G和擴散模型M，影響力最大化問題研究選擇一個包含k個個體的種子集S(即初始激活節(jié)點集)，這些個體能夠激活最大數(shù)量的后續(xù)節(jié)點。該問題首先由Domingos和Richardson[1]研究，Richardson和Domingos[2]將網(wǎng)絡(luò)建模為一個任意的馬爾可夫隨機域，并給出了最大化的啟發(fā)式算法。Kempe[3]等人首先將問題表述為組合優(yōu)化問題，提出了獨立集聯(lián)(IC)和線性閾值(LT)兩種基本模型。他們證明了這個問題是NP困難的，并提出了一個貪婪算法。此后，大量研究主要集中在大規(guī)模社交網(wǎng)絡(luò)算法的改進。如惰性計算[4-5]、最短路徑[6]、有向無圈圖[7]、局部樹[8]、局部鄰域[9]、度數(shù)修正[10]、學(xué)習自動機[11]、社團探尋[12-13]、進化算法[14-15]、隨機超圖[16]。然而，大多數(shù)現(xiàn)有的研究只關(guān)注于最大化單一產(chǎn)品的擴散。這種模型忽略了涉及多個傳播實體的復(fù)雜社會交互。近年來，少數(shù)研究從競爭角度對獨立級聯(lián)模型和線性閾值模型進行了擴展，討論了多種產(chǎn)品的最大化問題。如，Lu等[17]首先提出了競爭獨立集聯(lián)模型(Com-IC)，擴展了IC模型來描述具有競爭關(guān)系的多個影響的擴散。在此基礎(chǔ)上，提出了自我影響力最大化問題和競爭影響力最大化問題。Ou等[18]也獨立考慮了競爭影響力最大化問題。他們通過擴展LT模型為多產(chǎn)品擴散問題提出了交互線性閾值(ILT)模型，讓后發(fā)者在知道先發(fā)者決策的情況下盡可能抑制先發(fā)者的擴散。Borodin等[19]提出了競爭環(huán)境下的采納機制：消費者根據(jù)朋友圈中所有產(chǎn)品的市場占有率(A產(chǎn)品普及率/所有產(chǎn)品普及率之和)的概率選擇產(chǎn)品A。在A產(chǎn)品擴散最大化的目標下，Borodin證明難以找到算法保證目標值不少于最優(yōu)解的平方根。然而，Borodin沒有給出有效求解問題的算法。Lu等[20]認為消費者主要受新激活用戶的影響，提出了新的競爭機制：消費者根據(jù)朋友圈中(A產(chǎn)品新激活率/所有產(chǎn)品普及率之和)的概率選擇產(chǎn)品A。然而，Lu等并非尋求A產(chǎn)品擴散最大化，而是尋求將一定數(shù)量的種子分配給多種產(chǎn)品的最優(yōu)分配方案，使得所有產(chǎn)品的總擴散最大化。Bozorgi等[21]提出了兩階段競爭機制：第一階段根據(jù)隨機閥值決定是否采納；如果采納，第二階段根據(jù)普及率最高原則選擇產(chǎn)品。然而，Bozorgi等[21]的算法主要尋求如何用最少的種子超過競爭產(chǎn)品的普及率，而非尋求給定種子數(shù)量下的產(chǎn)品擴散最大化目標。此外，現(xiàn)在研究大多基于社會影響的隨機擴散過程，在基于IC模型的競爭模型中，當一個非活動用戶i在時間步長t上變?yōu)榛顒佑脩魰r，它將有一個成功的機會(概率為Pij)在時間步長t+1上獨立地激活它當前非活動的鄰居j，如果有多個產(chǎn)品在同一時間均能激活同一用戶，則用戶按照均勻概率隨機選擇其中一種產(chǎn)品。在基于LT模型的競爭模型中，用戶j的閾值均勻分布在[0,1]范圍內(nèi)，其鄰居N(j)的影響權(quán)重wij，其中Pi∈N(j)，wij≤1。如果傳入的影響權(quán)重之和不小于其閾值，則j被激活，若多個產(chǎn)品同時激活同一用戶，則用戶按照權(quán)重比例隨機選擇產(chǎn)品之一。隨機影響力最大化問題的目標是激活用戶的期望數(shù)量最大化。

現(xiàn)有研究主要集中于隨機閾值而非確定閾值可以歸結(jié)為兩個原因：一方面，由于對閾值信息掌握不充分，只能假定閾值為[0,1]均勻分布。另一方面，確定性模型失去了次模性特征(反映邊際效益遞減的函數(shù)特性，指新種子的邊際擴散能力隨著已選種子集合的增加而呈遞減趨勢)，使得確定閾值模型比傳統(tǒng)的LT模型更難求解。然而，隨著技術(shù)和先進算法的發(fā)展，這兩個理由似乎已不再充分。首先，隨著大數(shù)據(jù)技術(shù)在社交網(wǎng)絡(luò)中的應(yīng)用，現(xiàn)在實際上可以找到一些估算閾值的方法[22]。比如，在微信小程序中，可以了解同類app在朋友圈的普及率，假定用戶按最大普及率選擇產(chǎn)品，則最大普及率可作為確定閾值。再者，有一些算法可以直接應(yīng)用于確定性模型，如基于中心測度的方法。一些研究開發(fā)出了不依賴次模性特征的求解算法，并且得到較好的結(jié)果[13,15]。同時考慮到這類基于隨機化的擴散模型不利于建立具體的整數(shù)規(guī)劃模型求解和跟蹤分析擴散過程，本文研究確定性社會影響力競爭擴散問題(Deterministic Competitive Diffusion of Social Influence，DCDOSI)，即競爭環(huán)境下確定性社會影響力最大化問題。

本文首先，考慮競爭與確定性因素，結(jié)合現(xiàn)實營銷決策拓展了社會影響力最大化問題，提出了DCDOSI，構(gòu)建了該問題的整數(shù)規(guī)劃模型，對小規(guī)模實例運用Gurobi的分支切割算法進行求解，并給出了計算實驗結(jié)論；其次，為DCDOSI提出了基于擴散信息的邊際影響力糾正算法(Diffusion Information Greedy，DIG)來獲得大規(guī)模實例的解決方案。實驗表明，改進后的DIG算法在保證了AG算法的求解質(zhì)量的前提下縮短了90%以上的求解時間，且在大規(guī)模實例中的績效表現(xiàn)始終領(lǐng)先于其它算法20%以上。

1 確定性社會影響力競爭擴散模型

1.1 問題定義

在真實的市場中，為了達到各自目的，A和B兩家公司都會制定適合自己的初始用戶選取方案。

在競爭環(huán)境下，一個產(chǎn)品激活用戶需要滿足兩個條件：一是該用戶收到該產(chǎn)品的影響力大于其激活閾值；二是該用戶收到競爭產(chǎn)品的影響力弱于該產(chǎn)品的影響力，或競爭產(chǎn)品的影響力本身未達到閾值。稱以上條件為確定性動態(tài)競爭閾值模型的規(guī)則。于是，在競爭的過程中，新產(chǎn)品B不僅要考慮用戶對自己的閾值，還要考慮A的擴散情況，進而選擇更優(yōu)種子使得比A更早激活用戶或者與A在同一激活用戶階段時使其影響力大于A，最終使得B的激活用戶數(shù)量最大。影響力最大化問題就是研究在已知社交網(wǎng)絡(luò)G(V,E)和A的用戶時，如何從B的角度選擇初始種子節(jié)點，使得最終B的激活用戶數(shù)量最大化，該問題的定義如下所示。

確定性社會影響力競爭擴散問題定義：給定一個社交網(wǎng)絡(luò)G(V,E,θA,θB)，其中,V={1,2,…,n}為所有節(jié)點的集合，E為邊的集合，θA、θB為節(jié)點對A和B的閾值信息，已知A的種子集合為SA(SA∈V)，如何選擇由k個節(jié)點組成的種子集合SB按照確定性動態(tài)競爭閾值模型的規(guī)則最終使得B所激活的節(jié)點數(shù)目最大。

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

(1)

S.T. ∑iXi0=k?i∈N

(2)

Yi0=1 ?i∈SA

(3)

Xit+Yit≤1 ?i∈N,t∈{0,1,…,T}

(4)

Xi,t≥Xi,t-1?i∈N,t∈{1,2,…,T}

(5)

Yi,t≥Yi,t-1?i∈N,t∈{1,2,…,T}

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2 種子選取算法

P1擁有網(wǎng)絡(luò)規(guī)模二次冪級的變量和約束式，最快的求解器也不能得到競爭影響力在大規(guī)模網(wǎng)絡(luò)里的擴散結(jié)果(例如：網(wǎng)絡(luò)節(jié)點數(shù)量大于1 000時)，因此需要借助啟發(fā)式算法求解。在本節(jié)中，算法的目標是基于確定性動態(tài)競爭閾值模型去找出k個種子節(jié)點，從而使k個節(jié)點組成的種子集合能夠最大化B的傳播范圍。適應(yīng)性貪婪算法可以直接用于求解確定性動態(tài)競爭閾值模型下的種子選取問題，但貪婪算法時間復(fù)雜度還是過高，在網(wǎng)絡(luò)規(guī)模達到一定程度便無法在短時間內(nèi)求解了。因此，本文提出了基于貪婪算法的改進算法：基于擴散信息的邊際影響力糾正算法(Diffusion Information Greedy，DIG)。

DIG算法基于貪婪框架，算法流程如算法1所示，算法1、2步使用悲觀策略讓A完全擴散，第4步第一次計算所有候選種子的邊際影響力的同時記錄整個社交網(wǎng)絡(luò)的擴散信息，之后迭代的選取邊際影響力最大的種子并根據(jù)該種子和擴散信息更新其它候選種子的邊際影響力和社交網(wǎng)絡(luò)的擴散信息。

算法1 DC-DIG算法

輸入：社會網(wǎng)絡(luò)G=(V,E,θ)，最大擴散階段限制T,A的種子SA，B的種子個數(shù)p

輸出：B的種子集合SB

開放存取期刊在20世紀90年代末興起，作為在線出版物，免費供用戶使用。1995年，美國斯坦福大學(xué)建立了High Wire出版社，它是全球最大的免費提供全文的學(xué)術(shù)文獻出版商，而且提供的都是高質(zhì)量的電子期刊。最初它僅提供一種期刊，現(xiàn)在它已經(jīng)能夠提供《科學(xué)》、《美國國家科學(xué)院院刊》等多種高端刊物的電子全文［4］。

第5步：若|SB|≤p，則循環(huán)執(zhí)行以下步驟：

1)令v*=argmaxν∈V(SA∪SB)mfv,SB=SB∪v*；

相對于AG算法而言，DIG算法的改進之處在于：運用數(shù)據(jù)結(jié)構(gòu)記憶邊際影響力的來源，當選擇一個新的種子后，直接對邊際影響力的來源進行糾正，進而近似更新邊際影響力，從而避免所有候選節(jié)點的擴散模擬計算，節(jié)約了計算時間。其潛在收益更新策略如算法2所示，需要注意的是影響力擴散信息在算法1中的第4步初始化，其數(shù)據(jù)結(jié)構(gòu)為詞典Info，表示方式如下Info[i]={[s,u,invsv],…}，表示候選點s經(jīng)過i的鄰居u，擴散至i時產(chǎn)生了invsv的影響力。在更新過程中，對所有新種子擴散路徑上的節(jié)點i，算法2步驟3根據(jù)Info[i]追溯并更新與i有關(guān)的侯選點邊際影響力。

算法2 更新邊際影響

第1步：初始化隊列Q={s}，令mfs=0，受s影響的節(jié)點集合PATH=?。

第3步：?u∈PATH，若au=B則執(zhí)行a步驟，否則執(zhí)行b步驟：

1)根據(jù)Info清除所有能到達u的邊際影響力。

2)?q∈Info[u],若Info[u][q][1]≠1,則執(zhí)行以下步驟：

(2)mfq=mfq+mf′-Info[u][q][1]

(3)Info[u][q][1]=mf′

(4)若mf′=1，則令隊列Q={u}，當Q≠?時，迭代的從Q中取出隊首元素u執(zhí)行以下步驟：

對于具有n個節(jié)點和m條邊的圖，DIG算法的時間復(fù)雜度為Ο((n*M1)+(N1*M2))，其中M1,M2≤m和N1≤n。M1是候選節(jié)點的影響路徑中的邊數(shù)。M2是所選種子的影響路徑中的邊數(shù)。N1是需要從活動節(jié)點更新其邊際影響的節(jié)點數(shù)。

3 計算實驗

在小型實驗中，采用Barabasi-Albert[23]模型生成網(wǎng)絡(luò)(設(shè)置平均度數(shù)為3、隨機種子為100)作為實驗網(wǎng)絡(luò)。我們分別設(shè)置在節(jié)點數(shù)量為20、30、40、50、60、70、80的網(wǎng)絡(luò)里使用Gurobi的分支切割算法(Branch & Cut)、AG算法與DIG算法選取B的種子，A產(chǎn)品的種子為隨機選取的20%比例的網(wǎng)絡(luò)節(jié)點。實驗結(jié)果如表1所示，表1分別給出了DIG、AG、商業(yè)軟件的求解質(zhì)量與求解時間，同時最后兩列分別比較了DIG與AG、AG與商業(yè)軟件的求解質(zhì)量差距。從求解質(zhì)量上看，DIG與AG的激活數(shù)量差別非常小，通常只有一個節(jié)點數(shù)的差距，同時AG與商業(yè)軟件最優(yōu)解的差距也并不明顯。這說明，從小規(guī)模實例的實驗來看，貪婪算法的求解質(zhì)量令人滿意。然而，由于商業(yè)軟件無法求解更大規(guī)模實例，算法在大規(guī)模問題的求解質(zhì)量將通過與其它啟發(fā)式算法的比較來反映。從求解時間上看，DIG算法相比AG算法節(jié)約了大量時間，同時AG算法也相比商業(yè)軟件節(jié)約了大量時間。從實驗結(jié)果上看，DIG算法相比AG算法節(jié)約了95%，AG算法相比商業(yè)軟件節(jié)約了99%。此外，當問題規(guī)模超過80個點時，我們的實驗機器已經(jīng)無法在1小時內(nèi)用商業(yè)軟件求解，而DIG只花費0.005秒求解，求解質(zhì)量只相差一個激活數(shù)量。算法時間節(jié)約的原因主要在于AG算法在選擇新種子后，必須模擬擴散所有候選節(jié)點以更新邊際影響力；而本文的算法通過數(shù)據(jù)結(jié)構(gòu)記憶對溯源更新，以近似更新的方式避免了擴散模擬計算。

表1 小規(guī)模網(wǎng)絡(luò)實例計算

為了比較DIG與各算法績效，在擴展實驗中我們使用了真實的社交網(wǎng)絡(luò)數(shù)據(jù)集，Hept與Phy來源于http://research.microsoft.com/enus/people/weic/graphdata.zip，Epinion來源于http://snap.stanford.edu/data/，各數(shù)據(jù)集具體說明如表2所示。首先采用隨機算法選取15%比例的網(wǎng)絡(luò)節(jié)點作為市場先發(fā)者A的種子，再分別采用DIG算法、DD算法、PageRank算法、Random算法選取5%比例的網(wǎng)絡(luò)節(jié)點作為市場后發(fā)者B的種子，在T=10下進行實驗，實驗結(jié)果如圖1至3所示。圖1顯示了4種算法最終激活B的數(shù)量和求解時間的對比情況，觀察可得DIG算法在求解質(zhì)量上優(yōu)勢明顯，且求解效率只存在線性差別。圖2顯示了在改變最大擴散階段的限制時各算法的績效比較，不僅可以得出DIG算法求解質(zhì)量穩(wěn)定領(lǐng)先，還可以得出擴散階段限制在大于某一范圍時便沒有了“限制”效果，即增加擴散階段不影響擴散結(jié)果。圖3顯示了在更改B的閾值時各算法績效對比，DIG算法仍然始終領(lǐng)先其它算法且求解效率穩(wěn)定。同時，圖3表明隨著閾值增加，激活數(shù)量會呈指數(shù)下降，這一現(xiàn)象可解釋為：隨著閾值增加，不僅消費者興趣下降，同時競爭對手也會趁機滲透。綜上，DIG算法具有良好的擴展性能。

表2 擴展實驗數(shù)據(jù)集

圖1 隨種子數(shù)量變化的各算法績效對比

圖2 限制最大擴散階段變化時的各算法績效對比

圖3 隨閾值變化的各算法績效對比

4 結(jié)論

影響力最大化(IM)最著名應(yīng)用是病毒式營銷，除了病毒式營銷，IM在許多其他重要領(lǐng)域中也有廣泛應(yīng)用，如網(wǎng)絡(luò)監(jiān)控、謠言控制、社會推薦等。本文針對一類競爭環(huán)境下具有確定性閾值的社會影響最大化問題提出了兩種方法。第一種方法基于整數(shù)規(guī)劃模型，使用Gurobi優(yōu)化軟件求解問題模型，得到了小規(guī)模實例的精確解決方案。

第二種方法是包括DIG在內(nèi)的啟發(fā)式算法。啟發(fā)式算法比Gurobi快得多，其中AG算法能夠用更少的時間提供具有競爭力且更高質(zhì)量的解決方案種子集。與現(xiàn)有其他算法相比，DIG算法的求解質(zhì)量從對新產(chǎn)品最終激活數(shù)量上和對競爭產(chǎn)品的競爭策略都明顯優(yōu)于其他算法。通過對在線社交網(wǎng)絡(luò)的數(shù)據(jù)挖掘，我們最終可以了解個人的閾值，也可以得到競爭對手的種子分布。在此基礎(chǔ)上，競爭環(huán)境下確定性閾值模型可以擴展到各種產(chǎn)品與服務(wù)的競爭中，為創(chuàng)新產(chǎn)品或服務(wù)爭取到更大的效益。

傳統(tǒng)的貪婪算法難以處理5 000個節(jié)點以上的確定性競爭問題，本文提出的DIG算法能夠在2分鐘內(nèi)求解70 000個節(jié)點的實例。然而，現(xiàn)實社會網(wǎng)絡(luò)可能高達幾十億個節(jié)點，仍然無法直接運用DIG算法求解，有兩個解決這類超大規(guī)模網(wǎng)絡(luò)的思路：1)運用社區(qū)探尋的方法，對超大規(guī)模網(wǎng)絡(luò)社區(qū)進行壓縮；2)引入分布式計算與存儲，進行并行運用。對超大規(guī)模現(xiàn)實網(wǎng)絡(luò)的處理，將是該問題未來重點的研究方向。此外，近年來網(wǎng)絡(luò)達人、明星直播的傳播效應(yīng)成為許多企業(yè)的營銷手段，對于這類明星種子來說，節(jié)點成本將成為一個重要因素?？紤]節(jié)點成本后，算法需要評估侯選節(jié)點的單位邊際影響力(即邊際影響力/節(jié)點成本)，然后按照背包問題的求解思路尋求解決方案。因此，考慮成本預(yù)算，節(jié)點成本的競爭擴散問題也是一個較有現(xiàn)實意義的研究拓展。此外，該問題還可以在考慮用戶偏好、負面觀點等方面開展研究。