毋 東，何楠群，張霄宏

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

E-mail：xh.zhang@hpu.edu.cn

1 引 言

在線社交網(wǎng)絡(luò)平臺為數(shù)以億計的用戶提供了跨越時間和空間的信息交流服務(wù)，越來越多的人將社交平臺視為主要的信息來源.社交平臺中大V們的言論往往比普通人的言論傳播得更廣，產(chǎn)生的影響更大.而用戶影響力最大化正是通過尋找最具影響力的若干個用戶作為種子，以期信息從這些種子開始傳播時其傳播范圍最大.如何在給定時間期限前使信息得到最大化傳播則是一個更具有現(xiàn)實意義的問題，電商平臺廣泛推出的雙11、雙12促銷活動就是此類問題的典型代表.

影響力最大化可應(yīng)用于政治選舉[1]、在線營銷[2]、謠言控制[3]等多個領(lǐng)域.Kempe等[4]證明了影響力最大化問題是NP-hard問題.簡單貪婪算法及其優(yōu)化算法、啟發(fā)式算法等被廣泛用于篩選優(yōu)質(zhì)種子.隨著研究工作的不斷推進，影響力傳播過程中的時間因素逐漸引起重視[5-7].Li等[8]基于社交網(wǎng)絡(luò)中的時間限制和時間延遲擴散提出了競爭影響力最大化算法.Tong等[9]將時間約束分散到種子選擇的每一步，通過使種子選擇的每步操作都服從預(yù)算約束來達到在既定時間約束下影響力最大化的目標(biāo).Litou等[10]的工作旨在滿足時間約束的前提下，尋找最佳傳播路徑以達到影響力最大化的目標(biāo).盡管圍繞信息傳播的時間屬性已經(jīng)開展了大量的研究，但是如何在給定時間期限內(nèi)使信息得到最大化傳播仍然是一個開放問題.

針對這一問題，本文提出了基于時間約束的影響力最大化算法.該方法首先根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點間的交互信息構(gòu)建帶時間約束的影響力計算模型，然后定義最早激活時間、累積傳播延時等概念，以此控制影響力的傳播過程以滿足給定的時間約束條件；最后，引入有效激活節(jié)點的概念并利用其描述影響力在給定時間約束下的傳播范圍，并據(jù)此選出種子節(jié)點.

2 相關(guān)工作

Kempe[4]等證明了影響力最大化問題是NP-hard問題，并提出了線性閾值模型和獨立級聯(lián)模型模擬影響力的傳播過程.Kempe等提出的簡單貪婪算法可以篩選出接近最優(yōu)的種子，但是時間復(fù)雜度過高.為了降低時間復(fù)雜度，開展了大量對簡單貪婪算法進行了優(yōu)化的工作，并提出了CELF算法[11，12]、混合貪婪算法[13，14]、約束貪婪算法[15]等.除了貪婪算法，啟發(fā)式算法[16]也被用來篩選種子節(jié)點.

篩選種子節(jié)點時需要計算節(jié)點的影響力.現(xiàn)有的方法在計算影響力時除了考慮節(jié)點的拓?fù)鋵傩訹17，18]，還會考慮社交屬性.曹等[19]根據(jù)用戶交互的主題偏好計算不同類別信息下節(jié)點的影響力，Mhadhbi等[20]以節(jié)點周圍存在的密集社區(qū)為派系，根據(jù)派系識別影響力最大的節(jié)點.

隨著相關(guān)研究工作的不斷深入，影響力傳播中的時間因素逐漸引起重視[21，22].Pham等[23]認(rèn)為錯誤信息傳播時間越長受影響的用戶越多，并根據(jù)時間約束和預(yù)算限制提出了最大化錯誤信息限制算法.Ali等[24]認(rèn)為信息的時間緊迫性會加劇群體影響力的差異，提出了在規(guī)定期限內(nèi)、在保證種群傳播公平的前提下實現(xiàn)影響力最大化傳播的方法.Li等[8]基于社交網(wǎng)絡(luò)中的時間限制和時間延遲擴散提出了競爭影響力最大化算法.Tong等[9]將時間約束分散到種子選擇的每一步，通過使種子選擇的每步操作都服從預(yù)算約束來達到在既定時間約束下影響力最大化的目標(biāo).Litou等[10]的工作旨在滿足時間約束的前提下，在位置感知的社交網(wǎng)絡(luò)中尋找最佳傳播路徑，以達到影響力最大化的目標(biāo).

盡管圍繞信息的時間屬性已經(jīng)開展了大量的研究，但是如何在特定時間約束下使信息得到最大化傳播仍是一個開放問題.

3 問題定義

本文用有向圖表示社交網(wǎng)絡(luò).圖中的節(jié)點表示社交網(wǎng)絡(luò)中的用戶，邊表示用戶之間的交互活動.記G=(V，E)表示有向圖，V表示節(jié)點集合且V={v1，v2，v3，…，vn}，E表示邊集合且E={(vi，vj)|vi∈V，vj∈V}.影響力最大化問題旨在選擇一個節(jié)點集合S且S?V，以S中的節(jié)點為種子開始信息傳播時其傳播范圍最大.影響力最大化問題可由式(1)描述，式中k表示種子節(jié)點的數(shù)量，δ表示種子節(jié)點影響力的傳播范圍.

S*=arg|S|≤kmax(δ)

(1)

S*=arg|S|≤k，te-tb≤Δtmax(δ)

(2)

4 基于時間約束的種子選擇方法

本方法根據(jù)節(jié)點的影響力和節(jié)點在特定時間約束下傳播信息的能力兩個因素選擇種子節(jié)點.本方法包含三部分內(nèi)容，首先設(shè)計包含時間約束的影響力計算模型，然后在影響力傳播過程中引入了最早激活時間和累計傳播時延以控制影響力的傳播過程符合時間約束條件，最后根據(jù)每個節(jié)點在給定時間約束下的影響力傳播范圍選出種子節(jié)點.

4.1 影響力計算

節(jié)點的影響力與該節(jié)點是否能夠選為種子密切相關(guān).本文主要從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和用戶之間的社交活動兩方面入手來計算節(jié)點的影響力.為便于計算節(jié)點影響力，定義了節(jié)點的重要性和親密度兩個概念.

定義1.(重要性)從拓?fù)浣Y(jié)構(gòu)的角度刻畫節(jié)點在整個社交網(wǎng)絡(luò)中的重要程度.

記Imp表示重要性，Imp(vi)表示節(jié)點vi的重要性，可根據(jù)文獻[25]中的方法計算.

定義2.(親密度)從社交活動的角度刻畫節(jié)點之間聯(lián)系的緊密程度.

記Inm表示親密度，節(jié)點vi和節(jié)點vj之間的親密度則由Inm(vi，vj)表示，根據(jù)式(3)計算.

Inm(vi，vj)=α·con(vi，vj)

(3)

給定有向圖G′，α是由G′中的集合T決定的一個量，α=1/|T|，con(vi，vj)的值由vi和vj之間社交活動決定，con(vi，vj)=|Ti，j|，Ti，j?T且Ti，j={ti，j|?(vi，vj)∈E且ti，j∈T}.vi和vj之間的社交活動越頻繁，Inm(vi，vj)的值就越大.

(4)

式(4)從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和總體社交活動的角度描述vi的影響力.現(xiàn)實世界中用戶在不同時期參與社交活動的程度往往有差異.用戶在某些時期參與社交活動的積極性會比較高，而在另外某個時期參與社交活動的積極性可能會明顯降低.這種積極性的變化會影響其影響力的傳播.正如參與競選活動的候選人在退出競選前后其影響力的傳播截然不同.

為了體現(xiàn)用戶影響力在不同時期的差異，在式(4)所定義的影響力模型的基礎(chǔ)上引入了基于時間約束的變化因子，該因子由用戶在給定的時間約束內(nèi)的社交活躍度決定.引入該因子后，vi的影響力記為InfΔ(vi)，由式(5)計算.

InfΔ(vi)=Inf(vi)*(1+δ(tb，te，vi))

(5)

(6)

下面以圖1所示網(wǎng)絡(luò)中的節(jié)點v2為例說明影響力的計算過程.在圖1中，邊上的數(shù)字標(biāo)識節(jié)點間發(fā)生社交活動的時刻.假設(shè)tb=3，Δt=4，則有Imp(v2)=1.44，α=1/9，con(v2，v3)=1，con(v2，v4)=2，con(v2，v5)=3，根據(jù)式(5)可計算InfΔ(v2)=1.44，根據(jù)式(6)可計算得InfΔ(v2，v3)=0.24，InfΔ(v2，v4)=0.48，InfΔ(v2，v5)=0.72.

圖1 包含5個節(jié)點社交網(wǎng)絡(luò)圖Fig.1 Social network graph with five nodes

4.2 種子選擇

本方法在選擇種子節(jié)點時主要考慮兩個因素：一是節(jié)點的影響力傳播范圍是否屬于top k之列，二是影響力傳播開始與結(jié)束的時間是否滿足時間約束條件，即te-tb≤Δt.如果某個節(jié)點的影響力傳播范圍屬于top k之列，但所需的傳播時間超過了Δt，則該節(jié)點不能選作種子節(jié)點.如果傳播過程滿足時間約束條件，但是該節(jié)點影響力的傳播范圍不在top k之列，則該節(jié)點也不能選作種子節(jié)點.

為了識別能在給定時間約束下使影響力得到最大化傳播的節(jié)點，定義了節(jié)點的最早激活時間、影響力傳播累積時延以及有效激活節(jié)點等概念.

定義3.(最早激活時間)用于標(biāo)記某節(jié)點被激活的最早時間.

(7)

定義4.(傳播累積延時)描述某節(jié)點的影響力傳播到另一節(jié)點的累積延時.

(8)

如果在某個時刻t′，節(jié)點的影響力傳播累積延時突破了時間約束條件，即t′-tb≤Δt，則自此時刻起激活的節(jié)點不再計入影響力的傳播范圍.換而言之，節(jié)點的影響力傳播范圍根據(jù)該節(jié)點在影響力傳播累積延時滿足時間約束條件時激活的節(jié)點進行計算.為便于識別此類激活的節(jié)點，引入了有效激活節(jié)點的概念.

定義5.(有效激活節(jié)點)若某節(jié)點的最早激活時間滿足時間約束條件的限制，則此節(jié)點是有效的激活節(jié)點.

以vi為例，若滿足Tal(vi)≤tb+Δt，則vi是有效激活節(jié)點.

由定義3至定義5可知，在影響力傳播過程中，如果遍歷到某個節(jié)點時影響力的傳播累積延時不再滿足時間約束條件，則在該節(jié)點處停止傳播，即不嘗試激活該節(jié)點以及該節(jié)點指向的所有節(jié)點.最終，節(jié)點的影響力傳播范圍由有效激活節(jié)點的數(shù)量決定.影響力傳播范圍最大的k個節(jié)點將被選作種子節(jié)點.

4.3 算法描述

帶時間約束的影響力最大化目標(biāo)是找到有效激活節(jié)點最多的k個節(jié)點作為種子節(jié)點，當(dāng)從這k個種子節(jié)點開始傳播信息時，能在Δt時間內(nèi)將信息在最大范圍內(nèi)傳播.

算法1.基于時間約束的種子選擇算法

輸入：社交網(wǎng)絡(luò)圖G′=(V，E，T)；

輸出：種子集seeds；

1. for eachvinV

2. 將節(jié)點v加入anodes

3. while(anodes≠Φ)do

4.curnode←取anodes中的一個節(jié)點

5. 計算curnode的所有出邊鄰居節(jié)點，存入變量negs

6. for eachneginnegsdo

7. if(InfΔ(curnode，neg)≥激活閾值)

8. 計算Tal(curnode，neg)

9. if(Tal(curnode，neg)滿足時間約束條件)

10.v的有效激活節(jié)點數(shù)加一

11. 計算Ipt(v，neg)

12. If(Ipt(v，neg)≤Δt)

13. 將neg加入anodes

14. end if

15. end if

16. end if

17. end for

18. 從anodes中刪除curnode

19. end while

20. end for

21. 按有效激活節(jié)點有大到小的順序?qū)λ泄?jié)點排序

22.將前k個節(jié)點加入seeds，并返回seeds

5 實 驗

本實驗采用線性閾值模型模擬影響力的傳播過程.為了體現(xiàn)時間約束，對該模型進行了修改.通過比較本文算法和多種不同算法在修改后的線性閾值模型上的執(zhí)行結(jié)果來來評價本文方法的正確性和有效性.

5.1 實驗設(shè)置

5.1.1 實驗環(huán)境

本次實驗在單臺主機上運行，該主機采用2.4GHz雙核處理器，12GB主存和Windows10操作系統(tǒng).

5.1.2 數(shù)據(jù)集

所有實驗選用了斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集(1)https：//snap.stanford.edu/data/中帶有時間屬性的六個數(shù)據(jù)集，這些數(shù)據(jù)集的信息介紹如下：

· email-Eu-core-temporal數(shù)據(jù)集是根據(jù)歐洲大型研究機構(gòu)在803天內(nèi)的電子郵件數(shù)據(jù)生成的社交網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含986個節(jié)點和332334條邊，節(jié)點表示機構(gòu)成員，邊表示機構(gòu)成員之間的通信.

· email-Eu-core-temporal-Dept1數(shù)據(jù)集是根據(jù)歐洲大型研究機構(gòu)部門1的成員在803天內(nèi)的電子郵件數(shù)據(jù)生成的社交網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含309個節(jié)點和61046條邊，節(jié)點表示機構(gòu)成員，邊表示機構(gòu)成員之間的通信.

· CollegeMsg數(shù)據(jù)集來自加州大學(xué)歐文分校的在線社交網(wǎng)絡(luò)應(yīng)用.該數(shù)據(jù)集包含1899個節(jié)點和59835條邊，節(jié)點表示用戶，邊表示用戶之間的消息通信.該數(shù)據(jù)集的時間跨度為193天.

· sx-mathoverflow-a2q數(shù)據(jù)集是根據(jù)Math Overflow網(wǎng)站的問答信息生成的社交網(wǎng)絡(luò).該網(wǎng)絡(luò)包含21688節(jié)點和107581條邊.節(jié)點表示用戶，邊表示一個用戶在時間t回答了另一個用戶的提問.該數(shù)據(jù)集的時間跨度為2350天.

· sx-superuser-c2a數(shù)據(jù)集根據(jù)Super User網(wǎng)站上的問答信息生成的社交網(wǎng)絡(luò).該網(wǎng)絡(luò)包含101052節(jié)點和430033條邊.節(jié)點表示用戶，邊表示一個用戶在時間t評論了另一個用戶的答案.該數(shù)據(jù)集的時間跨度為2735天.

· sx-superuser-a2q數(shù)據(jù)集也來自Super User網(wǎng)站.該網(wǎng)絡(luò)包含167981節(jié)點和534239條邊.節(jié)點表示用戶，邊表示一個用戶在時間t評論了另一個用戶的提問.該數(shù)據(jù)集的時間跨度為2773天.

5.1.3 評價指標(biāo)

本實驗采用執(zhí)行時間和影響力傳播范圍作為評價指標(biāo).執(zhí)行時間指的是各算法選擇種子節(jié)點所消耗的時間.影響力傳播范圍由各算法所選種子節(jié)點在線性閾值模型下能夠激活的節(jié)點數(shù)表示.

在線性閾值模型中，一個節(jié)點能否被激活主要取決于該節(jié)點的激活閾值以及鄰居節(jié)點對該節(jié)點的傳播概率(影響力).在本次實驗中，所有節(jié)點的激活閾值都取固定值0.2.節(jié)點間的傳播概率根據(jù)式(9)描述的模型計算.在該式中，fp(vi，vj)根據(jù)式(10)計算，其中Imp()的值由PageRank算法獲得.在計算Imp()時，每個節(jié)點的PageRank初始值為1/|V|，V為節(jié)點集合，抑制因子d=0.85.

(9)

(10)

5.1.4 對比算法

本實驗采用了6個對比算法，分別是Degree算法、Random算法、IMIT算法[22]、SingleSingle算法[22]、TCIM算法[24]和PageRank算法[26].通過與這些算法對比執(zhí)行時間和影響力傳播范圍兩項指標(biāo)驗證本文方法的正確性和有效性.

5.2 實驗結(jié)果及分析

本次實驗展示的所有結(jié)果均為相關(guān)算法獨立運行50次的平均結(jié)果.

圖2和圖3展示了在Δt取不同值時各算法所選種子的影響力傳播范圍.圖2展示了5個種子的影響力傳播范圍，圖3展示了10個種子的影響力傳播范圍.在這兩幅圖中，縱坐標(biāo)表示種子節(jié)點激活的節(jié)點數(shù)，橫坐標(biāo)表示不同的Δt取值.當(dāng)累積傳播延時達到Δt所對應(yīng)的值時，停止傳播.

圖2 種子數(shù)為5時的傳播結(jié)果對比Fig.2 Comparison of spread results with 5 seeds

圖3 種子數(shù)為10時傳播結(jié)果對比Fig.3 Comparison of spread results with 10 seeds

當(dāng)種子數(shù)為5時，在sx-mathoverflow-a2q數(shù)據(jù)集上，只有在Δt=100%*t總時本文算法所選種子的影響力傳播范圍比Degree算法所選種子的影響力傳播范圍稍小.在Δt取其它值時，本文算法都比Degree算法要好.在除了sx-mathoverflow-a2q數(shù)據(jù)集之外的其它5個數(shù)據(jù)集上，本文算法所選種子的影響力傳播范圍都是最大.

當(dāng)種子數(shù)為10時，本文算法在sx-superuser-c2a數(shù)據(jù)集上，只有在Δt=40%*t總時本文算法所選種子的影響力傳播范圍比TCIM算法和IMIT所選種子的影響力傳播范圍稍小，在此數(shù)據(jù)集上Δt取其它值以及在另外5個數(shù)據(jù)集上，本文算法的結(jié)果均優(yōu)于6個對比算法.

根據(jù)圖2和圖3的結(jié)果計算了在種子數(shù)分別是5和10兩種情況下各算法的歸一化平均傳播范圍，結(jié)果如表1和表2所示.在種子數(shù)分別是5和10的情況下，本文方法的歸一化傳播范圍要優(yōu)于6個對比算法.

表1 種子數(shù)為5時的歸一化平均傳播范圍比較Table 1 Comparison of normalized average spread range with five seeds

表2 種子數(shù)為10的歸一化平均傳播范圍比較Table 2 Comparison of normalized average spread range with 10 seeds

圖4展示了各算法在不同數(shù)據(jù)集上執(zhí)行時間的比較結(jié)果.由圖可知，本文算法在6個數(shù)據(jù)集上的執(zhí)行時間要小于PageRank算法和SingleSingle算法，與IMIT算法不相上下.雖然Random算法的執(zhí)行時間比其它算法短，但是它的影響力傳播范圍沒有其它算法的大.由于TCIM算法的執(zhí)行時間過大，為了突出本文算法和其它5個算法的對比結(jié)果，未將TCIM的結(jié)果在圖4中展示.

圖4 各算法在不同數(shù)據(jù)集上執(zhí)行時間對比Fig.4 Execution time comparison of various algorithms on different data sets

6 結(jié) 論

本文提出了一種基于時間限制的影響力最大化方法.該方法根據(jù)社交活動的時間屬性、節(jié)點拓?fù)鋵傩砸约皶r間約束條件等因素計算節(jié)點的影響力，并引入最早激活時間和有效激活節(jié)點以識別滿足給定時間約束的激活節(jié)點，引入累積傳播延時以控制影響力的傳播過程符合約束條件.在真實數(shù)據(jù)集上的實驗結(jié)果驗證了本文方法的正確性和有效性.下一步，將在本文方法的基礎(chǔ)上進行傳播模型的改進.