劉濤 馬越 姜和芳 伍少成 王浩林

（深圳供電局有限公司 廣東省深圳市 518000）

網(wǎng)絡(luò)社交媒體影響力評模型是促進(jìn)商業(yè)、宣揚(yáng)政治觀點(diǎn)和傳播信息以造福社會的不可缺的工具。影響最大化(IM)[問題要求找到一組k個(gè)初始啟動子模塊，使在網(wǎng)絡(luò)中用戶間傳播單一消息的傳播最大化。在過去的十年中，在推薦[和輿情的背景下被廣泛研究。然而現(xiàn)實(shí)世界中的活動通常需要多方面的：由多個(gè)信息片段組成。例如，涉電力輿情目的是讓老百姓了解電力相關(guān)新聞和事件。對消費(fèi)者行為的研究證實(shí)，當(dāng)用戶只收到活動的單個(gè)元素時(shí)，不太可能觸發(fā)任何有意義的行動(例如，投票給某個(gè)候選人或采用某個(gè)產(chǎn)品)。在另一個(gè)例子中，Youtube頻道可能試圖通過在抖音或微博等社交網(wǎng)站上傳播信息活動視頻來增加訂閱用戶的數(shù)量。由于內(nèi)容的短暫影響，這段信息活動傳播的視頻可能會很快從用戶的記憶中消失，即使已經(jīng)看過并與朋友分享了它。只有在觀看同一頻道的多個(gè)視頻時(shí)，用戶才會轉(zhuǎn)向訂閱者。因此，一個(gè)活動策略應(yīng)該傳播多個(gè)信息活動信息，以達(dá)到重疊的采用結(jié)果。

我們需要分配K啟動子模塊來傳播第i個(gè)片段，其中∑k=k。對于一個(gè)片段t∈T的啟動子模塊的影響擴(kuò)散取決于片段獨(dú)特的主題分布。采用logistic激活模型對用戶接收到多個(gè)片段時(shí)的采用行為進(jìn)行建模，如消費(fèi)者行為研究當(dāng)用戶接收到的信息較少時(shí)，采用概率較小，在暴露于足夠數(shù)量的片段后，隨著額外信息的影響減弱，概率梯度下降。由于邏輯激活模型的影響，OIPA中的目標(biāo)函數(shù)是非子模塊的，因此基于子模塊假設(shè)的技術(shù)是不適用的。同時(shí)，本文提出了一個(gè)分支定界框架，并引入了一個(gè)單調(diào)子模優(yōu)化的新公式，該公式可以通過貪婪的啟發(fā)式逼近因子（1-1/e），從而獲得未探索搜索空間的一個(gè)緊上界。因此，迭代地解決一個(gè)可處理的優(yōu)化問題，直到計(jì)算一個(gè)上界小于或等于得到的最佳解。本文所提模型沒有掃描大量的候選啟動子模塊，而是只在啟動子模塊的用戶采納邊際收益大于預(yù)定義的閾值h時(shí)才選擇啟動子模塊。通過逐步降低閾值，在預(yù)算k允許的情況下選擇更多的啟動子模塊。

1 國內(nèi)外相關(guān)工作

1.1 傳統(tǒng)IM

研究影響力最大化問題的目標(biāo)是找到網(wǎng)絡(luò)中的k個(gè)啟動子模塊以最大化受影響用戶的預(yù)期數(shù)量。IM是NP難問題，當(dāng)今最流行的方法是獨(dú)立級聯(lián)模型（IC）和線性閾值模型（LT）。對于一個(gè)簡單的貪心算法來說，一個(gè)恒定的近似因子是成立的。

經(jīng)典的影響模型將不同的信息活動信息按照其在模型下的影響傳播視為可互換的。與此相反，主題感知模型以依賴于主題的方式區(qū)分每個(gè)獨(dú)特的消息的影響。主題感知IM問題的目的是在這樣一個(gè)主題感知的影響模型下尋找啟動子模塊。

1.2 競爭IM

競爭IM考慮這樣一種場景：多個(gè)競爭者在同一個(gè)網(wǎng)絡(luò)中傳播消息，每個(gè)用戶最多采用一條消息。以往的研究提出了競爭IM問題的三個(gè)主要目標(biāo)：

（1）在競爭對手選擇啟動子模塊的策略下，使競爭對手的影響擴(kuò)散最大化；

（2）利用博弈論的概念，在對手策略未知的情況下，求得競爭的均衡；

（3）最大限度地?cái)U(kuò)大所有競爭對手的總影響力傳播，這是一個(gè)有興趣公平分配競爭活動的網(wǎng)絡(luò)主機(jī)所希望看到的。

1.3 比較IM

一些作品考慮了帶有多個(gè)非競爭性信息的信息活動式營銷。論文的研究了影響傳播是獨(dú)立的運(yùn)動的情況。劉等研究兩組互補(bǔ)產(chǎn)品的場景中，一個(gè)產(chǎn)品只能由一個(gè)用戶采用已經(jīng)采取了相應(yīng)的產(chǎn)品在其他陸集。國外研究人員介紹比較影響模型，該模型包含兩個(gè)競爭和互補(bǔ)的IM：他們認(rèn)為兩種不同的兩個(gè)活動之間的關(guān)系，a和B：在競爭關(guān)系，用戶采用的概率降低了采用B；在一種互補(bǔ)關(guān)系中，用戶采用a會增加采用b的可能性。這種比較影響模型會產(chǎn)生兩個(gè)IM問題：SELFINFMAX，它是為了最大化一個(gè)活動自身的影響力。如表1所示。

表1：論文中常用符號

2 模型預(yù)處理

在本節(jié)中，將介紹一個(gè)主題感知的影響模型，該模型描述了不同的消息塊如何在網(wǎng)絡(luò)中傳播和最優(yōu)影響塊分配(OIPA)問題。

2.1 Topic-aware影響模型

將社交網(wǎng)絡(luò)建模成一個(gè)有向圖網(wǎng)絡(luò)G(V,E),V是一個(gè)用戶集并且每條邊e=(u,v)∈E捕獲了u，v之間的朋友關(guān)系（雙向鏈接）或者追隨者關(guān)系（單向鏈接）。|V|=n，|E|=m。為了對一個(gè)物品在SN中的傳播方式進(jìn)行建模，采用了研究成熟的主題感知傳播模型。該模型從來自一個(gè)SN上傳播的社交活動（比如推文和回復(fù)）提取了一組隱藏的主題Z={z,z,…,z}。形式上，給定一條邊e = (u,v)，主題感知的影響概率p(e|z)對主題z∈z下u如何影響v進(jìn)行建模；將p(e)表示為e的主題影響向量。這些概率可以從過去傳播活動的日志中得知。

2.2 問題定義

信息傳播是由信息活動片段組成的T={t,t,…,t}。假設(shè)每一塊t都在網(wǎng)絡(luò)中獨(dú)立地傳播。使用邏輯模型來模擬用戶的采納行為。在該模型中，用戶v采用活動 T的概率為伯努利隨機(jī)變量X，由邏輯函數(shù)捕獲：

由于每個(gè)啟動子模塊在不同主題上具有不同的傳播消息片段的潛力，目標(biāo)是將T的片段分配給S中明智選擇的啟動子模塊子集，從而使關(guān)于T的所有用戶的總體采用效用最大化。首先正式定義采用實(shí)用程序。

3 問題解析

3.1 采用效用函數(shù)的性質(zhì)

進(jìn)一步定義了一個(gè)分配計(jì)劃與另一個(gè)分配計(jì)劃的并集，以及相關(guān)的邊際效用收益，如下所示。

3.2 可逼近性

4 近似算法

對于一般的OIPA情況，沒有已知的方法來開發(fā)多項(xiàng)式時(shí)間近似算法。盡管如此，社會影響力遵循一個(gè)冪律原則:少數(shù)人的影響力明顯大于其他人?；谶@一原則，本文提出了一個(gè)分支限制的框架，優(yōu)先考慮有較大影響的啟動子模塊，并在必要時(shí)提前終止。在一個(gè)最大的堆中維護(hù)部分候選計(jì)劃，根據(jù)它們的估計(jì)AU得分上界進(jìn)行排序。如果部分計(jì)劃的上界小于當(dāng)前獲得的最佳計(jì)劃的確切AU分?jǐn)?shù)，將安全地修剪部分計(jì)劃。然而，這個(gè)解決方案帶來了不小的技術(shù)挑戰(zhàn)，因?yàn)樾枰?/p>

（1）快速計(jì)算候選計(jì)劃的AU分?jǐn)?shù)；

（2）推導(dǎo)出局部規(guī)劃的AU分?jǐn)?shù)的有效上界；

（3）高效計(jì)算出上界函數(shù)。

4.1 AU估計(jì)

為了使用分支綁定框架，需要對大量的候選分配計(jì)劃評估AU。由于在經(jīng)典的IM問題中評估任意用戶集的影響傳播是#P-hard，因此計(jì)算任意候選計(jì)劃的AU也是#P-hard。然而，可以使用反向可達(dá)集(RR)的擴(kuò)展方法來評估AU的準(zhǔn)確性。下面簡要回顧一下RR集方法。

Reverse-Reachable (RR)集：給出一個(gè)齊次影響圖G'=(V',E'),|V'|=n'。其中，單個(gè)值p(e)通過邊e=(u,v)∈E'表征激活概率，RR集方法估計(jì)任意種子集S∈V'的期望影響。隨機(jī)RR集取決于兩個(gè)隨機(jī)選擇：(i)從圖中隨機(jī)選擇一個(gè)初始節(jié)點(diǎn)x， (ii)通過保持每條邊e∈E的概率為p(e)對圖進(jìn)行采樣。RR集合包含采樣圖中可以到達(dá)x的所有頂點(diǎn)。I[R∩S=?]為指示RR集Ri是否與S相交的布爾變量。生成θRR集之后，可以估計(jì)S的預(yù)期影響σ(S)：

4.2 由分支定界得到上界函數(shù)

一個(gè)簡單的OIPA解決方案應(yīng)該枚舉所有可能的候選計(jì)劃，并使用MRR集計(jì)算它們的AU分?jǐn)?shù)，相反，通過分支和界來估計(jì)AU的上界函數(shù)。

算法1. 分支定界

算法1給出了該框架。首先生成θ MRR集競選T。然后初始化一個(gè)最大堆。S是一個(gè)部分計(jì)劃。V的啟動子模塊集尚未考慮和U對應(yīng)的搜索空間的上限。在每個(gè)迭代的搜索循環(huán),堆的頂部進(jìn)入的上界值。并更新全局上限，只要部分計(jì)劃沒有被填滿在搜索循環(huán)的每次迭代中，通過上界值獲得堆的頂部條目。對于每一個(gè)局部計(jì)劃運(yùn)用函數(shù)ComputeBound()。當(dāng)全局下界大于或等于全局上界時(shí)，算法終止。

算法2. ComputeBound()

4.3 漸進(jìn)上界估計(jì)

漸進(jìn)估計(jì)法的思想如下：在每個(gè)迭代中，推動者v通過個(gè)人τ(?| Sa)。然后，設(shè)置一個(gè)閾值h，如果候選計(jì)劃的邊際收益大于h，則在候選計(jì)劃中加入一個(gè)啟動子模塊。通過逐步降低閾值，以便包含更多的啟動子模塊。該方法加速了上限估計(jì)，這得益于兩個(gè)特性：首先，排序過程不需要在每次迭代中重新運(yùn)行。只需要更新在Sa中受到新啟動子模塊v影響的啟動子模塊v的位置，即，它們與v共存于一個(gè)MRR集合中。第二，當(dāng)閾值足夠小，算法終止并返回一個(gè)計(jì)劃即使作業(yè)的數(shù)量低于k，第二個(gè)特性嚴(yán)格界限的數(shù)量τ(?)評估。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)設(shè)置

數(shù)據(jù)集：我們對以下三個(gè)真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。

（1）（數(shù)據(jù)集1）：電力技術(shù)論壇是一個(gè)電力技術(shù)共享數(shù)據(jù)集，來自一個(gè)在線網(wǎng)站，該網(wǎng)站包含一個(gè)社交網(wǎng)絡(luò)和一個(gè)記錄用戶投票活動的行動日志。

（2）（數(shù)據(jù)集2）：電力學(xué)術(shù)論文圖譜是一個(gè)從在線學(xué)術(shù)搜索服務(wù)下載的dblp合著圖。

（3）（數(shù)據(jù)集3）：微博電力信息是由用戶在微博中的轉(zhuǎn)發(fā)和回復(fù)操作構(gòu)建的社交網(wǎng)絡(luò)。

基于數(shù)據(jù)集1的動作日志，采用TIC模型來學(xué)習(xí)數(shù)據(jù)集1的主題感知影響概率p(e|z)（見第三節(jié)）。數(shù)據(jù)集1的主題數(shù)量設(shè)置為20個(gè)。由于數(shù)據(jù)集2中dblp沒有操作日志，我們設(shè)置使用研究字段作為主題，并通過使用主題對兩位作者的相關(guān)會議進(jìn)行分類來計(jì)算p(e|z)。對于微博涉電力數(shù)據(jù)集3，將單個(gè)用戶的所有涉及電力視為一個(gè)文檔，并將LDA應(yīng)用于所有文檔，以獲得每個(gè)用戶的主題分布。給定一條邊e=(u,v)，根據(jù)u和v的主題分布計(jì)算p(e|z)。數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)列于表2。

表2：統(tǒng)計(jì)數(shù)據(jù)集

比較方法：目前沒有OIPA的工作。因此，將以下基線與本文提出的方法進(jìn)行比較。

IM：在圖G上基于IC模型運(yùn)行最先進(jìn)的IM算法來獲得k個(gè)種子節(jié)點(diǎn)，隨后，對使用S傳播每個(gè)信息活動片段t∈T之間的采用效用進(jìn)行比較，選擇效用最大的信息活動片段由S傳播。

BAB：本文提出的分支定界算法如4.2節(jié)。當(dāng)上界和最佳解之間的效用差在1%的錯(cuò)誤率以內(nèi)時(shí)，終止搜索。

參數(shù)與查詢：實(shí)驗(yàn)的參數(shù)為：

（1）k為活動t選擇的啟動子模塊的數(shù)量。

（2）l為t中信息活動片段的數(shù)量。對于每個(gè)信息活動片段，通過均勻采樣非零的主題維度來生成主題向量。

（3）α,β是邏輯模型中的參數(shù)。

解決β= 1,不同β/α測試的性能對提高難度水平為用戶采取的想法,選擇10%用戶從V在現(xiàn)實(shí)中并不是所有的用戶都有資格為促進(jìn)廣告。參數(shù)設(shè)置表3中可以找到。

表3：實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)設(shè)置：所有的方法都是用c++實(shí)現(xiàn)的，運(yùn)行在Ubuntu 14.04服務(wù)器上。

5.2 校準(zhǔn)參數(shù)ε

BAB-P逐步降低了閾值h啟動子模塊是包含在解決方案(1+ε)的比率。檢查參數(shù)ε如何影響B(tài)AB-P質(zhì)量解決方案。結(jié)果如圖1所示。采用效用ε上升時(shí)顯示一個(gè)下行的趨勢。因此,更大的ε是,越容易包含啟動子模塊,這可能會降低效用。當(dāng)降低ε從0.1到0.9,采用效用下降了0.08%,6.6%和1.4%,結(jié)果與理論結(jié)果提出了定理3。其余部分的實(shí)驗(yàn),修復(fù)參數(shù)ε是0.5

圖1：數(shù)據(jù)集1、2、3的校準(zhǔn)參數(shù)ε

5.3 改變啟動子模塊的數(shù)量k

比較兩種方法在k值變化時(shí)的實(shí)驗(yàn)結(jié)果如圖2所示。所有提議的方法的效用都隨著k值的增大而增加，這是預(yù)期的，因?yàn)楦嗟耐茝V者會使活動信息片段更廣泛地傳播，并導(dǎo)致更高的推廣活動的采用效用。IM和TIM的效用不如BAB和BABP. IM的效用最差，因?yàn)樗耆雎粤瞬煌黝}分布的信息活動片段的影響行為。與IM相比，TIM有更好的結(jié)果，因?yàn)樗x擇了那些將單個(gè)信息活動片段的傳播最大化的啟動子模塊。然而，如果用戶只收到一篇信息活動式的文章，那么他們采用該活動的可能性就很低，因此總體采用的可能性也很低。我們提出的BAB和BABP作為分支和約束框架，取得了較好的采用效果，為其提供了理論保證。最重要的是，BABP證明了與BAB具有競爭力的解決方案質(zhì)量，與BAB具有幾乎相同的采用實(shí)用程序。因此，在BABP中引入的漸進(jìn)上界估計(jì)技術(shù)即使在經(jīng)驗(yàn)值較大的k下也沒有顯示出明顯的質(zhì)量下降。

圖2：改變啟動子模塊的數(shù)量k（數(shù)據(jù)集1、2、3）

所有提出的方法的效率結(jié)果也顯示在圖3中（y軸在對數(shù)刻度圖中）。當(dāng)更多的啟動子模塊被選擇到一個(gè)計(jì)劃中時(shí)，所有比較的方法的運(yùn)行時(shí)間都會增加。IM和TIM是高效的，因?yàn)樗鼈冎皇窃谏傻臉颖旧线\(yùn)行貪心最大覆蓋算法。巴布需要更長的運(yùn)行時(shí)間，因?yàn)樗枰啻握{(diào)用ComputeBound(?)功能，每一個(gè)都是一個(gè)貪婪的過程來選擇啟動子模塊，直到程序結(jié)束(算法1)。BAB-P優(yōu)化計(jì)算ComputeBound(?)通過先進(jìn)的上界估計(jì)技術(shù)提前終止和展示了卓越的效率(2)算法，實(shí)現(xiàn)24 x, 22 x, 8.1倍加速效果與巴布在數(shù)據(jù)集1相比，數(shù)據(jù)集2和數(shù)據(jù)集3。對于更大的k,BABP顯示了巨大的可伸縮性，并具有與TIM相同的性能。這是因?yàn)锽ABP不需要掃描所有候選啟動子模塊來獲得一個(gè)上限估計(jì)，即使選擇的啟動子模塊少于k個(gè)，也可以提前終止。相反，TIM、IM和BAB需要迭代地掃描所有候選對象，因此對于較大的k，它們的性能下降比BABP更嚴(yán)重。

圖3：改變信息活動片段數(shù)量（數(shù)據(jù)集1、2、3）

5.4 改變信息活動片段的數(shù)量

通過改變信息活動片段的數(shù)量來進(jìn)行宣傳活動的效果。當(dāng)更多的信息活動片段被推廣時(shí)，所有比較方法的效用都增加了。這是因?yàn)?，采用概率用戶u隨信息活動碎片的數(shù)量影響β= 1時(shí)，模型由Eqn定義與BAB和BABP相比，IM和TIM的質(zhì)量隨著體積的增大而降低，因?yàn)樗鼈儾荒軆?yōu)化多個(gè)信息活動片段。以tweet為例，當(dāng)l = 5時(shí)，BAB分別對IM和TIM獲得71x、2.9x的質(zhì)量增益，而babp對BAB具有競爭優(yōu)勢。值得注意的是，IM和TIM在數(shù)據(jù)集3上的質(zhì)量非常差. 這是因?yàn)榉橇阒黝}的平均影響概率(即在數(shù)據(jù)集中，p(e|z))的所有邊僅為1.5，而數(shù)據(jù)集3的主題比數(shù)據(jù)集1和數(shù)據(jù)集2多. 優(yōu)化單個(gè)信息活動片段導(dǎo)致低影響傳播，從而產(chǎn)生較差的整體適應(yīng)效用。

所有比較方法的運(yùn)行時(shí)間都隨著規(guī)模的增大而增加，性能趨勢與之前的觀察結(jié)果一致:考慮到具有競爭力的解決方案質(zhì)量，babp能夠在BAB上實(shí)現(xiàn)顯著的效率改進(jìn)。盡管IM和TIM具有更好的總體性能，但這是以顯著降低效用為代價(jià)的。

5.5 改變比率β/α

實(shí)驗(yàn)結(jié)果的比較方法和不同β/α是圖4所示。當(dāng)該比率設(shè)置為較大值時(shí)，其效用呈上升趨勢。因?yàn)榻鉀Qβ= 1,β/αα下跌時(shí)上漲。當(dāng)這種情況發(fā)生時(shí)，用戶v采用活動的概率增加，這將導(dǎo)致更高的總體效用。

圖4：改變比率β/α（數(shù)據(jù)集1、2、3）

6 總結(jié)與分析