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

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

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

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

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

1.1 傳統(tǒng)IM

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

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

1.2 競(jìng)爭(zhēng)IM

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

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

（2）利用博弈論的概念，在對(duì)手策略未知的情況下，求得競(jìng)爭(zhēng)的均衡；

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

1.3 比較IM

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

表1：論文中常用符號(hào)

2 模型預(yù)處理

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

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。為了對(duì)一個(gè)物品在SN中的傳播方式進(jìn)行建模，采用了研究成熟的主題感知傳播模型。該模型從來(lái)自一個(gè)SN上傳播的社交活動(dòng)（比如推文和回復(fù)）提取了一組隱藏的主題Z={z,z,…,z}。形式上，給定一條邊e = (u,v)，主題感知的影響概率p(e|z)對(duì)主題z∈z下u如何影響v進(jìn)行建模；將p(e)表示為e的主題影響向量。這些概率可以從過(guò)去傳播活動(dòng)的日志中得知。

2.2 問(wèn)題定義

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

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

3 問(wèn)題解析

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

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

3.2 可逼近性

4 近似算法

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

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

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

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

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

算法1. 分支定界

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

算法2. ComputeBound()

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

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

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

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

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

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

（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的動(dòng)作日志，采用TIC模型來(lái)學(xué)習(xí)數(shù)據(jù)集1的主題感知影響概率p(e|z)（見(jiàn)第三節(jié)）。數(shù)據(jù)集1的主題數(shù)量設(shè)置為20個(gè)。由于數(shù)據(jù)集2中dblp沒(méi)有操作日志，我們?cè)O(shè)置使用研究字段作為主題，并通過(guò)使用主題對(duì)兩位作者的相關(guān)會(huì)議進(jìn)行分類來(lái)計(jì)算p(e|z)。對(duì)于微博涉電力數(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ù)集

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

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

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

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

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

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

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

解決β= 1,不同β/α測(cè)試的性能對(duì)提高難度水平為用戶采取的想法,選擇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啟動(dòng)子模塊是包含在解決方案(1+ε)的比率。檢查參數(shù)ε如何影響B(tài)AB-P質(zhì)量解決方案。結(jié)果如圖1所示。采用效用ε上升時(shí)顯示一個(gè)下行的趨勢(shì)。因此,更大的ε是,越容易包含啟動(dòng)子模塊,這可能會(huì)降低效用。當(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 改變啟動(dòng)子模塊的數(shù)量k

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

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

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

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

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

通過(guò)改變信息活動(dòng)片段的數(shù)量來(lái)進(jìn)行宣傳活動(dòng)的效果。當(dāng)更多的信息活動(dòng)片段被推廣時(shí)，所有比較方法的效用都增加了。這是因?yàn)?，采用概率用戶u隨信息活動(dòng)碎片的數(shù)量影響β= 1時(shí)，模型由Eqn定義與BAB和BABP相比，IM和TIM的質(zhì)量隨著體積的增大而降低，因?yàn)樗鼈儾荒軆?yōu)化多個(gè)信息活動(dòng)片段。以tweet為例，當(dāng)l = 5時(shí)，BAB分別對(duì)IM和TIM獲得71x、2.9x的質(zhì)量增益，而babp對(duì)BAB具有競(jìng)爭(zhēng)優(yōu)勢(shì)。值得注意的是，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òng)片段導(dǎo)致低影響傳播，從而產(chǎn)生較差的整體適應(yīng)效用。

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

5.5 改變比率β/α

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

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

6 總結(jié)與分析