確定性社會影響力競爭擴散問題研究

翁克瑞,沈 卉,侯俊東

(中國地質大學(武漢)經濟管理學院，武漢 430078)

0 引言

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

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

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

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

1.1 問題定義

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

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

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

1.2 整數規劃模型

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

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

算法1 DC-DIG算法

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

輸出：B的種子集合SB

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

第5步：若|SB|≤p，則循環執行以下步驟：

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

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

算法2 更新邊際影響

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

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

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

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

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

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

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

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

3 計算實驗

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

表1 小規模網絡實例計算

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

表2 擴展實驗數據集

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

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

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

4 結論

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

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

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