李 雷 鄧詩琦 趙 博 施化吉 施磊磊

1(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 江蘇 鎮(zhèn)江 212013) 2(中國傳媒大學(xué)新聞傳播學(xué)部新聞學(xué)院 北京 100024)

0 引 言

社交網(wǎng)絡(luò)的開放性、便利性及內(nèi)容的豐富性吸引了廣大的用戶人群，同時(shí)也為在線推薦系統(tǒng)和病毒式營銷提供了良好的平臺(tái)。近年來，基于社交網(wǎng)絡(luò)的精準(zhǔn)廣告投放已經(jīng)成為首要選擇。其中，影響力最大化問題以“口碑營銷”為基礎(chǔ)對(duì)用戶影響規(guī)則及影響力傳播模式進(jìn)行研究，具有重大的理論意義和實(shí)用價(jià)值。

文獻(xiàn)[1]給出了影響力最大化問題的相關(guān)研究進(jìn)展。Domingos等[2]首先將影響力最大化問題引入社會(huì)網(wǎng)絡(luò)領(lǐng)域，并給出了該問題的詳細(xì)定義與評(píng)價(jià)指標(biāo)。Kempe等[3]在此基礎(chǔ)上將影響力最大化形式化定義為在特定影響力傳播模型中挖掘影響力大的k個(gè)節(jié)點(diǎn)的離散優(yōu)化問題，并證明了影響力最大化問題是一個(gè)NP-hard問題，且用貪心算法可以得到精確度為(1-1/e)的近似最優(yōu)解，但其時(shí)間復(fù)雜度高、效率低下。針對(duì)此問題，一些研究者對(duì)影響力最大化問題的貪心算法作出了一系列改進(jìn)[4-6]，也有研究者提出用啟發(fā)式算法[7-10]解決該問題。除了提升算法的運(yùn)行效率外，很多研究以提升問題模型的實(shí)用性為目標(biāo)進(jìn)行開展，如通過考慮主題感知這一因素以提升影響力傳播模型的準(zhǔn)確性[11-12]；將挖掘全局影響力最大的節(jié)點(diǎn)具體化為挖掘某一特定地理位置內(nèi)影響力最大的節(jié)點(diǎn)[13-14]；將成本因素引入影響力最大化問題[15-16]等。

上述研究都是基于單網(wǎng)絡(luò)對(duì)影響力最大化問題進(jìn)行了較為充分的研究，然而隨著用戶的跨網(wǎng)絡(luò)參與行為逐漸增多，各社交網(wǎng)絡(luò)間的交集也隨之增加，學(xué)者開始從跨網(wǎng)絡(luò)的角度探究影響力最大化問題。Shen等[17]利用“興趣匹配用戶”研究了信息的跨網(wǎng)絡(luò)傳播模式，通過將重疊用戶表示為一個(gè)超級(jí)節(jié)點(diǎn)的方式耦合多個(gè)網(wǎng)絡(luò)，然而這種方式無法體現(xiàn)用戶在不同網(wǎng)絡(luò)中的特性。Nguyen等[18]首次在病毒式營銷的背景下引入跨網(wǎng)絡(luò)影響力最大化的概念，并提出一種完全保留原始網(wǎng)絡(luò)影響傳播特性的耦合方案。隨后，文獻(xiàn)[19]進(jìn)一步提出無損和有損兩種耦合方案，前者保留原始網(wǎng)絡(luò)的所有屬性以獲得高質(zhì)量的解，后者則專注于時(shí)間和內(nèi)存消耗，同時(shí)提出一種可擴(kuò)展的貪心算法解決多社交網(wǎng)絡(luò)上最小花費(fèi)的影響力最大化問題。李小康等[20]證明了多渠道的影響力最大化問題在獨(dú)立級(jí)聯(lián)模型下是NP-hard問題，并針對(duì)該問題提出了貪心算法、基于節(jié)點(diǎn)度、基于反向可達(dá)集三種近似解決方案。但該研究是針對(duì)特定用戶集開展的，即多個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)是相同的，這種特定情況下的算法和實(shí)驗(yàn)都具有一定局限性。李國良等[21]定義了不同網(wǎng)絡(luò)中同一實(shí)體的自傳播特性，并提出了影響計(jì)算模型解決多網(wǎng)絡(luò)上節(jié)點(diǎn)間的影響概率，最后基于獨(dú)立級(jí)聯(lián)模型解決了多網(wǎng)絡(luò)下的影響力最大化問題，算法的伸縮性較好。

然而，現(xiàn)有跨網(wǎng)絡(luò)影響力最大化問題的解決方法[17-21]存在以下兩個(gè)問題：(1) 過多關(guān)注多網(wǎng)絡(luò)的耦合方式，忽略了網(wǎng)絡(luò)中如主題偏好和交互偏好等用戶興趣特質(zhì)對(duì)于影響力傳播的影響。文獻(xiàn)[22]指出，用戶對(duì)自己感興趣的領(lǐng)域的信息接受度大，將一個(gè)游戲廣告推廣給一個(gè)不玩游戲的用戶，其接受廣告并繼續(xù)傳播廣告的可能性很低；反之，用戶更加關(guān)注自己感興趣的人，其從關(guān)注人群中獲取的影響比從其他渠道獲取的更大。因此，社交網(wǎng)絡(luò)中影響力的傳播是由興趣驅(qū)動(dòng)的，充分利用用戶興趣傾向能夠更加精準(zhǔn)地模擬信息在網(wǎng)絡(luò)中的傳播過程。(2) 現(xiàn)有方法沒有很好地解決跨網(wǎng)絡(luò)影響力最大化問題面臨的隨網(wǎng)絡(luò)規(guī)模增加產(chǎn)生的計(jì)算負(fù)擔(dān)。

為此，本文首先構(gòu)建出同一跨網(wǎng)絡(luò)用戶之間的虛擬連接，以此作為媒介形成耦合網(wǎng)絡(luò)；其次基于獨(dú)立級(jí)聯(lián)模型提出了興趣驅(qū)動(dòng)的跨網(wǎng)絡(luò)影響力傳播模型(ID-IPM)，以模擬信息在網(wǎng)絡(luò)內(nèi)部和網(wǎng)絡(luò)之間的傳播方式；最后針對(duì)隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大而增大的時(shí)間開銷問題，提出啟發(fā)式和貪心算法結(jié)合的優(yōu)化種子節(jié)點(diǎn)選取方法(OA-IPaN)以解決跨網(wǎng)絡(luò)影響力傳播問題。本文主要工作如下：

1) 提出了一種興趣驅(qū)動(dòng)的跨網(wǎng)絡(luò)影響力傳播模型ID-IPM。首先，通過跨網(wǎng)絡(luò)用戶的“橋梁”作用進(jìn)行網(wǎng)絡(luò)耦合；其次，對(duì)獨(dú)立級(jí)聯(lián)模型進(jìn)行了改進(jìn)。該模型不僅通過跨網(wǎng)絡(luò)用戶的“橋梁”作用進(jìn)行網(wǎng)絡(luò)耦合，而且綜合考慮跨網(wǎng)絡(luò)用戶在網(wǎng)絡(luò)內(nèi)部、網(wǎng)絡(luò)之間進(jìn)行信息傳播的差異及用戶興趣的差異來計(jì)算節(jié)點(diǎn)間影響概率，以提高用戶影響力的傳播范圍。

2) 基于ID-IPM模型，提出了一種啟發(fā)式算法和貪心算法結(jié)合的跨網(wǎng)絡(luò)影響力傳播的優(yōu)化算法(OA-IPaN)。該算法基于ID-IPM模型，利用啟發(fā)式算法及貪心算法分兩階段進(jìn)行種子節(jié)點(diǎn)的挖掘，以提高OA-IPaN算法的效率。

3) 實(shí)驗(yàn)結(jié)果表明本文提出的ID-IPM模型與OA-IPaN算法在影響范圍和時(shí)間效率上的有效性，也驗(yàn)證了跨網(wǎng)絡(luò)環(huán)境中挖掘種子節(jié)點(diǎn)相比單網(wǎng)絡(luò)環(huán)境中的高效性。

1 相關(guān)工作

影響力最大化是以病毒式營銷為背景、信息傳播模型為基礎(chǔ)的種子節(jié)點(diǎn)選擇問題，被廣泛應(yīng)用于廣告投放、謠言預(yù)警等領(lǐng)域，已成為社交網(wǎng)絡(luò)分析中的研究熱點(diǎn)。然而現(xiàn)有的大部分研究通常應(yīng)用于某個(gè)特定社交網(wǎng)絡(luò)，只分析一個(gè)網(wǎng)絡(luò)中的各類數(shù)據(jù)，導(dǎo)致用戶的影響力評(píng)估準(zhǔn)確率低、影響范圍窄。

單一網(wǎng)絡(luò)中的影響力最大化問題自提出以來其解決方法已經(jīng)被學(xué)者做了較為充分的探索。部分學(xué)者考慮到利用社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)性質(zhì)能夠降低問題的處理規(guī)模從而節(jié)省時(shí)間開銷，例如：Wang等[26]提出的CGA先把網(wǎng)絡(luò)分成多個(gè)社區(qū)再采取動(dòng)態(tài)規(guī)劃算法計(jì)算每輪應(yīng)該選擇種子節(jié)點(diǎn)所在的社區(qū)，最后再利用MixGreedy算法在該社區(qū)里尋找種子節(jié)點(diǎn)。有學(xué)者從網(wǎng)絡(luò)發(fā)布內(nèi)容出發(fā)解決問題，例如：Barbieri等[11]通過主題建模研究社交影響力，并基于傳統(tǒng)的IC模型和LT模型提出了能夠更準(zhǔn)確模擬現(xiàn)實(shí)世界信息擴(kuò)散的話題感知模型TIC和TLT；Chen等[12]在此基礎(chǔ)上研究了主題感知下的影響力最大化問題；Li等[13]首次從地理位置的角度出發(fā)進(jìn)行研究，旨在從某一給定地理區(qū)域中找到k個(gè)能夠?qū)⒂绊懥υ诖藚^(qū)域中傳播到最大范圍的種子節(jié)點(diǎn)，此后文獻(xiàn)[14，27-28]也做了更深入的研究。除此之外，有學(xué)者從時(shí)間感知[29-31]、動(dòng)態(tài)[32-33]和競爭性[34-36]等方向?qū)τ绊懥ψ畲蠡瘑栴}進(jìn)行了研究?？傊?，單一網(wǎng)絡(luò)中的影響力最大化問題已經(jīng)從多角度多方位得到了較為充分的研究，而隨著許多用戶的跨社交網(wǎng)絡(luò)平臺(tái)參與行為逐漸增多，各個(gè)社交網(wǎng)絡(luò)間的交集也隨之增加，學(xué)者開始從跨網(wǎng)絡(luò)的角度探究影響力最大化。

從文獻(xiàn)[37-38]開始，學(xué)者開始探索多個(gè)網(wǎng)絡(luò)中的信息傳播模式。文獻(xiàn)[37]利用SIR模型(Susceptible Infected Recovered Model)模擬了信息在隨機(jī)網(wǎng)絡(luò)里的擴(kuò)散形式，其首次研究了不相連節(jié)點(diǎn)在多個(gè)網(wǎng)絡(luò)里的性質(zhì)，為進(jìn)一步研究信息以及影響力在多個(gè)網(wǎng)絡(luò)中的擴(kuò)散提供了線索。文獻(xiàn)[38]提出了一種基于事件的社交網(wǎng)絡(luò)，將線上的虛擬社交網(wǎng)絡(luò)與線下的真實(shí)社交網(wǎng)絡(luò)相連，并實(shí)現(xiàn)了該網(wǎng)絡(luò)里的信息流模擬與社區(qū)發(fā)現(xiàn)。此后Nguyen等[18]首次在病毒式營銷的背景下引入了跨網(wǎng)絡(luò)影響力最大化的概念，并提出了一種完全保留原始網(wǎng)絡(luò)影響傳播特性的耦合方案，利用線性閾值模型讓種子節(jié)點(diǎn)在多個(gè)網(wǎng)絡(luò)里交叉?zhèn)鞑ビ绊懥σ赃_(dá)到將影響力在多個(gè)網(wǎng)絡(luò)里擴(kuò)散到最廣范圍的目的。為了進(jìn)一步縮減選擇種子節(jié)點(diǎn)產(chǎn)生的開銷，文獻(xiàn)[19]為跨網(wǎng)絡(luò)影響力最大化問題設(shè)定了預(yù)算的限制，并進(jìn)一步提出無損和有損兩種網(wǎng)絡(luò)耦合方案，前者保留原始網(wǎng)絡(luò)的所有屬性以獲得高質(zhì)量的解，后者則專注于時(shí)間和內(nèi)存消耗，同時(shí)提出了一種可擴(kuò)展的貪心算法，在保證最小開銷的前提下完成了影響力最大化在多個(gè)網(wǎng)絡(luò)中的求解。Zhan等[39]將同時(shí)在多個(gè)網(wǎng)絡(luò)中擁有賬號(hào)的重疊用戶定義為錨用戶，錨用戶各個(gè)賬號(hào)之間的鏈接定義為錨鏈接，擁有錨用戶的多個(gè)社交網(wǎng)絡(luò)定義為部分匹配的在線社交網(wǎng)絡(luò)(Partially Aligned Social Networks)，從部分匹配的在線社交網(wǎng)絡(luò)中挖掘種子節(jié)點(diǎn)，并定義了網(wǎng)間和網(wǎng)內(nèi)兩種路徑來模擬信息的跨網(wǎng)絡(luò)傳播。除此之外也有一部分學(xué)者基于IC模型來求解跨網(wǎng)絡(luò)影響力最大化，文獻(xiàn)[20]證明了IC模型中的多渠道影響力最大化為NP-hard問題，并針對(duì)該問題提出了貪心算法、基于節(jié)點(diǎn)度、基于反向可達(dá)集三種近似解決方案。為了解決跨網(wǎng)絡(luò)影響力最大化問題，文獻(xiàn)[21]考慮了不同網(wǎng)絡(luò)間同一實(shí)體的自傳播特性，利用一種特定的模型計(jì)算多個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)間的影響概率，然后基于IC模型提出了多個(gè)優(yōu)化方法。針對(duì)目前絕大多數(shù)研究跨網(wǎng)絡(luò)影響力最大化的算法均從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)出發(fā)，沒有充分考慮到網(wǎng)絡(luò)中用戶的特殊屬性的情況，Shen等[17]利用“興趣匹配用戶”研究了信息的跨網(wǎng)絡(luò)傳播模式，通過在真實(shí)社交網(wǎng)絡(luò)Twitter-Foursquare和學(xué)術(shù)合作網(wǎng)絡(luò)上的實(shí)驗(yàn)，證明了其算法的有效性。

跨網(wǎng)絡(luò)影響力最大化是單網(wǎng)絡(luò)影響力最大化的擴(kuò)展，即在給定的多個(gè)社交網(wǎng)絡(luò)中挖掘出一群用戶，讓它們?cè)谶@些社交網(wǎng)絡(luò)的整體范圍內(nèi)影響盡可能多的用戶，其中這些網(wǎng)絡(luò)內(nèi)部的用戶會(huì)在各個(gè)網(wǎng)絡(luò)內(nèi)部傳播信息，且跨網(wǎng)絡(luò)用戶會(huì)在網(wǎng)絡(luò)間交叉?zhèn)鞑バ畔ⅰ？梢娍缇W(wǎng)絡(luò)影響力最大化的研究需要以網(wǎng)絡(luò)之間的信息交流為基礎(chǔ)，且跨網(wǎng)絡(luò)用戶是不同網(wǎng)絡(luò)間的連接媒介。

2 問題描述與相關(guān)定義

跨網(wǎng)絡(luò)影響力最大化問題的目標(biāo)是從n(n>1,n∈N*)個(gè)社交網(wǎng)絡(luò)中尋找一個(gè)能將影響力傳播到最廣范圍的種子節(jié)點(diǎn)集，其問題描述與相關(guān)定義如下。

不失一般性，本文工作在n=2個(gè)社交網(wǎng)絡(luò)G1(V1,E1)和G2(V2,E2)上展開，其中Vi(i=1,2)和Ei(i=1,2)分別是網(wǎng)絡(luò)Gi(i=1,2)的節(jié)點(diǎn)集合和節(jié)點(diǎn)間連接的集合。

定義1跨網(wǎng)絡(luò)用戶/非跨網(wǎng)絡(luò)用戶。同時(shí)在網(wǎng)絡(luò)G1和G2中擁有賬號(hào)的用戶稱為跨網(wǎng)絡(luò)用戶，反之只在其中一個(gè)網(wǎng)絡(luò)中擁有賬號(hào)的用戶稱為非跨網(wǎng)絡(luò)用戶。

相應(yīng)地，在社交網(wǎng)絡(luò)拓?fù)鋱D中，跨網(wǎng)絡(luò)用戶對(duì)應(yīng)的節(jié)點(diǎn)稱為跨網(wǎng)絡(luò)節(jié)點(diǎn)，非跨網(wǎng)絡(luò)用戶對(duì)應(yīng)的節(jié)點(diǎn)稱為非跨網(wǎng)絡(luò)節(jié)點(diǎn)。

定義2現(xiàn)實(shí)個(gè)體?，F(xiàn)實(shí)個(gè)體是社交網(wǎng)絡(luò)中的賬號(hào)在現(xiàn)實(shí)世界中對(duì)應(yīng)的、可以相互區(qū)分的個(gè)體。

定義4種子節(jié)點(diǎn)集S。種子節(jié)點(diǎn)作為影響力傳播的起點(diǎn)，是最初被激活的并嘗試以自身影響力激活其鄰居的節(jié)點(diǎn)。由種子節(jié)點(diǎn)組成的集合稱為種子節(jié)點(diǎn)集，記作S。

定義5影響范圍σ(S)。根據(jù)給定影響力傳播模型，所有種子節(jié)點(diǎn)u∈S直接或者間接激活的現(xiàn)實(shí)個(gè)體集合用σ(S)表示。

本文利用被激活的現(xiàn)實(shí)個(gè)體而非被激活的節(jié)點(diǎn)來定義影響范圍，原因是跨網(wǎng)絡(luò)環(huán)境下被激活的節(jié)點(diǎn)中可能包含較多的跨網(wǎng)絡(luò)用戶，而影響傳播的效果最終是作用在某一現(xiàn)實(shí)個(gè)體上的，若利用被激活的節(jié)點(diǎn)數(shù)量來量化影響范圍的大小會(huì)導(dǎo)致影響范圍的重復(fù)計(jì)算，從而使得影響傳播范圍判定過高。

3 興趣驅(qū)動(dòng)的跨網(wǎng)絡(luò)傳播模型

3.1 基于跨網(wǎng)絡(luò)節(jié)點(diǎn)的重疊網(wǎng)絡(luò)耦合策略

耦合重疊網(wǎng)絡(luò)的關(guān)鍵是結(jié)合現(xiàn)實(shí)背景理解信息跨網(wǎng)絡(luò)傳播的具體方式。如圖1所示，給定一對(duì)重疊網(wǎng)絡(luò)G1(V1,E1)和G2(V2,E2)，其中節(jié)點(diǎn)a∈C1?V1和b∈C2?V2是一對(duì)跨網(wǎng)絡(luò)節(jié)點(diǎn)，它們從各自參與的網(wǎng)絡(luò)中接收到信息后會(huì)以一定的概率將該信息傳播到另一個(gè)網(wǎng)絡(luò)中。利用這一特性，ID-IPM模型在保留兩個(gè)網(wǎng)絡(luò)中全部結(jié)構(gòu)特征的基礎(chǔ)上，抽象出每一對(duì)跨網(wǎng)絡(luò)節(jié)點(diǎn)之間信息傳遞的虛擬通道，從而將G1和G2耦合成耦合網(wǎng)絡(luò)G。本文將該信息虛擬通道定義為跨網(wǎng)連邊，具體定義見定義7。

圖1 重疊網(wǎng)絡(luò)耦合策略圖示

定義7跨網(wǎng)連邊集L。一對(duì)跨網(wǎng)絡(luò)節(jié)點(diǎn)之間的虛擬信息傳播通道稱為跨網(wǎng)連邊，所有跨網(wǎng)連邊組成的集合為跨網(wǎng)連邊集，記作L。

例如圖1中跨網(wǎng)絡(luò)節(jié)點(diǎn)a和b之間的跨網(wǎng)連邊(a,b)∈L就是網(wǎng)絡(luò)G1和G2之間信息傳播的一條虛擬通道。在構(gòu)建網(wǎng)絡(luò)G1和G2間的跨網(wǎng)連邊后，信息可以在兩個(gè)網(wǎng)絡(luò)內(nèi)部獨(dú)立傳播還可以通過跨網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行傳播，從而實(shí)現(xiàn)了重疊網(wǎng)絡(luò)G1和G2的耦合。耦合網(wǎng)絡(luò)的具體定義如定義8。

定義8耦合網(wǎng)絡(luò)G。保留一對(duì)重疊網(wǎng)絡(luò)G1和G2各自內(nèi)部的全部節(jié)點(diǎn)和節(jié)點(diǎn)連接，并構(gòu)建同一跨網(wǎng)絡(luò)節(jié)點(diǎn)之間的虛擬跨網(wǎng)連邊，得到耦合網(wǎng)絡(luò)G(G1,G2,L)，其中L為G1和G2之間的跨網(wǎng)連邊集。

3.2 興趣驅(qū)動(dòng)的節(jié)點(diǎn)間影響概率

構(gòu)建出耦合網(wǎng)絡(luò)G后，ID-IPM模型需要定義網(wǎng)絡(luò)G中節(jié)點(diǎn)u∈V1∪V2之間的影響概率。用戶受到和自己興趣相似的用戶的影響力更大，主題相似度和交互頻度是描述用戶興趣相似的重要因素，因此ID-IPM模型依靠用戶興趣驅(qū)動(dòng)——綜合考慮主題相似度和交互頻度定義網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)之間的影響概率大小。

1) 主題相似度。用戶主題偏好是用戶興趣特質(zhì)在社交網(wǎng)絡(luò)中的表現(xiàn)形式之一，兩個(gè)用戶關(guān)注內(nèi)容的主題越相似，他們的興趣就越一致，受到彼此影響的概率越高。本文通過對(duì)用戶發(fā)布的文本信息進(jìn)行LDA[23]建模得到用戶關(guān)注的主題及相應(yīng)的頻度，再利用主題分布來表示用戶的主題偏好，最后通過計(jì)算主題分布的相似度來表示主題相似度。

定義9主題相似度Φuv。假設(shè)u和v是同一網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)，則這一對(duì)網(wǎng)內(nèi)節(jié)點(diǎn)之間的主題相似度Φuv是兩者的主題分布相似程度。

Φuv=1-DJS(Tu,Tv)u,v∈V1或u,v∈V2

(1)

式中：Tu和Tv為節(jié)點(diǎn)u和v的主題分布；DJS(Tu,Tv)為兩個(gè)分布的JS散度。

2) 交互頻度。由于網(wǎng)絡(luò)內(nèi)部的節(jié)點(diǎn)之間依靠關(guān)注、轉(zhuǎn)發(fā)和評(píng)論等方式進(jìn)行交互[24]，交互頻度能夠體現(xiàn)出用戶的興趣特質(zhì)，交互越頻繁影響力傳播的可能性越高，其具體定義見定義10。

定義10交互頻度Ψuv。同一網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)u和v的交互頻度Ψuv定義為兩者之間轉(zhuǎn)發(fā)消息的頻率，其計(jì)算公式如下：

(2)

3) 節(jié)點(diǎn)間的影響概率。本文以興趣為驅(qū)動(dòng)綜合考慮網(wǎng)內(nèi)節(jié)點(diǎn)間的主題相似度和交互頻度以判斷影響概率的大小，并如定義11對(duì)網(wǎng)內(nèi)節(jié)點(diǎn)間的影響概率進(jìn)行定義。

定義11節(jié)點(diǎn)影響概率Puv。同一網(wǎng)絡(luò)內(nèi)部的節(jié)點(diǎn)u對(duì)v的影響概率Puv定義如下：

Puv=αΦuv+(1-α)Ψuv

u,v∈V1或u,v∈V2

(3)

由于主題相似度和交互頻度具有同等的重要性，因此本文將調(diào)和因子α取值為0.5。

3.3 ID-IPM模型的影響力傳播過程

ID-IPM模型是獨(dú)立級(jí)聯(lián)模型在跨網(wǎng)絡(luò)環(huán)境中的應(yīng)用和改進(jìn)，該模型的影響力傳播示例圖如圖2所示。

圖2 ID-IPM模型影響力傳播示例圖

耦合網(wǎng)絡(luò)G(G1,G2,L)中的影響力傳播包括在G1和G2內(nèi)部傳播和在兩者之間跨網(wǎng)絡(luò)傳播兩部分。每個(gè)種子節(jié)點(diǎn)u∈S都以一定的概率去嘗試激活其相鄰的未激活節(jié)點(diǎn)，每一時(shí)刻產(chǎn)生的新激活節(jié)點(diǎn)會(huì)在下一時(shí)刻以同樣的方式參與影響傳播，如果G中沒有新節(jié)點(diǎn)被激活或達(dá)到設(shè)置的閾值時(shí)傳播過程終止。

圖2中，v4∈V1、v5∈V1和u3∈V2為t時(shí)刻的激活節(jié)點(diǎn)，其中v5和u3為一對(duì)跨網(wǎng)絡(luò)節(jié)點(diǎn)。這三個(gè)節(jié)點(diǎn)會(huì)對(duì)各自的出鄰居節(jié)點(diǎn)施加影響力，如節(jié)點(diǎn)v4分別以概率pv4v3和pv4v6嘗試激活G1內(nèi)的未激活節(jié)點(diǎn)v3和v6，同理節(jié)點(diǎn)v5和u3以一定概率嘗試激活G1內(nèi)的節(jié)點(diǎn)v1、v6、v7及G2內(nèi)的節(jié)點(diǎn)u1、u4、u6和u7。若節(jié)點(diǎn)u7被節(jié)點(diǎn)u3成功激活則會(huì)在t+1時(shí)刻分別以概率pu7u4和pu7u8去嘗試激活節(jié)點(diǎn)u4和u8。若跨網(wǎng)絡(luò)節(jié)點(diǎn)v7與節(jié)點(diǎn)u5是同一個(gè)節(jié)點(diǎn)，當(dāng)其中一個(gè)被其他節(jié)點(diǎn)激活時(shí)，另一個(gè)就自動(dòng)被激活，然后就能夠?qū)⑿畔⒖缇W(wǎng)絡(luò)傳遞給其他節(jié)點(diǎn)，此為一次跨網(wǎng)絡(luò)信息傳播的過程。

ID-IPM模型中的激活行為只會(huì)執(zhí)行一次。如圖2中，由于節(jié)點(diǎn)u8只能接收到節(jié)點(diǎn)u7的影響力，一旦它未能被u7成功激活則它在該影響力傳播過程中只能一直保持未激活狀態(tài)。反之，節(jié)點(diǎn)u4能夠接收到u3和u7兩個(gè)節(jié)點(diǎn)的影響力，一旦它被兩者中的任何一個(gè)成功激活都能轉(zhuǎn)換為激活狀態(tài)。

4 跨網(wǎng)絡(luò)的影響力優(yōu)化算法

針對(duì)IMaN問題，本文提出跨網(wǎng)絡(luò)影響力傳播優(yōu)化算法(OA-IPaN)。兼顧時(shí)間開銷和算法精度，將OA-IPaN算法分為以下兩個(gè)階段：1) 篩選候選節(jié)點(diǎn)集，利用節(jié)點(diǎn)的度中心性[25]初步篩選出能顯著擴(kuò)散影響力的候選節(jié)點(diǎn)集S0(|S0|=k0，k0>k)；2) 選取種子節(jié)點(diǎn)集，通過ID-IPM模型模擬候選節(jié)點(diǎn)的影響力傳播情況從候選種子集合S0中篩選出種子集合S(|S|=k)。

該算法輸入為耦合網(wǎng)絡(luò)G，種子節(jié)點(diǎn)數(shù)k，比例參數(shù)p=k0/n(n=|V1|+|V2|,p∈(0,1])；輸出為種子節(jié)點(diǎn)集S。

4.1 候選節(jié)點(diǎn)篩選

OA-IPaN算法在篩選階段篩選出潛在影響力最大的候選節(jié)點(diǎn)集S0(|S0|=k0，k0>k)，通過忽略潛在邊際影響力增量較小的節(jié)點(diǎn)來減少節(jié)點(diǎn)邊際影響力增量的計(jì)算次數(shù)。綜合考慮節(jié)點(diǎn)的度中心性[17]及跨網(wǎng)絡(luò)節(jié)點(diǎn)的特性，潛在影響力PI的定義如下。

定義12潛在影響力PI。節(jié)點(diǎn)的潛在影響力PI表示其影響力傳播能力的大小，u∈V1∪V2的潛在影響力PIu的計(jì)算如下：

(4)

式中：du表示節(jié)點(diǎn)u的出度；|V1|+|V2|-|C1|表示耦合網(wǎng)絡(luò)G中能被影響的全部現(xiàn)實(shí)個(gè)體數(shù)。

算法1候選節(jié)點(diǎn)篩選

1.初始化候選節(jié)點(diǎn)集合S0=?，并將耦合網(wǎng)絡(luò)G中所有的狀態(tài)標(biāo)簽標(biāo)記為Selected=0；

2.根據(jù)式(4)計(jì)算耦合網(wǎng)絡(luò)G中全部節(jié)點(diǎn)的潛在影響力PI，并按照PI值的大小進(jìn)行排序；

3.選擇PI值最大且狀態(tài)標(biāo)簽為Selected=0的節(jié)點(diǎn)v作為候選節(jié)點(diǎn)并放入集合S0；

4.如果|S0|≥p×n，轉(zhuǎn)到第6步，否則轉(zhuǎn)到第5步；

5.判斷v是否為跨網(wǎng)絡(luò)節(jié)點(diǎn)：若v是跨網(wǎng)絡(luò)節(jié)點(diǎn)，則將v的狀態(tài)標(biāo)簽設(shè)置為Selected=1，轉(zhuǎn)到第3步；否則將v及其對(duì)應(yīng)跨網(wǎng)絡(luò)節(jié)點(diǎn)u的狀態(tài)標(biāo)簽均設(shè)置為Selected=1，轉(zhuǎn)到第3步；

6.輸出候選節(jié)點(diǎn)集S0。

4.2 種子節(jié)點(diǎn)集選取

OA-IPaN算法選取階段通過ID-IPM模型模擬影響力傳播過程，并利用子模優(yōu)化[9]的貪心策略選擇影響力增量大的節(jié)點(diǎn)得到種子節(jié)點(diǎn)集S(|S|=k)。其中向集合S中加入某一節(jié)點(diǎn)u影響范圍的變化為影響力增量Δσ(u|S)，其具體定義見定義13。

定義13影響力增量Δσ(u|S)。若當(dāng)前種子節(jié)點(diǎn)集S經(jīng)模擬影響擴(kuò)散后的影響范圍為σ(u|S)，則加入節(jié)點(diǎn)u后增加的新激活現(xiàn)實(shí)個(gè)體集合即為影響力增量Δσ(u|S)，其計(jì)算方法如下：

Δσ(u|S)=σ(S∪{u})-σ(S)u∈S0S

(5)

算法2種子節(jié)點(diǎn)集選取

1.初始化種子節(jié)點(diǎn)集合，并設(shè)置t=1；

2.根據(jù)式(5)計(jì)算節(jié)點(diǎn)u∈S0S在t輪的影響力增量Δσ(u|S)并按照結(jié)果從大到小排序；

3.選出t輪有最大影響力增量Δσ(v1|S)=maxΔσ(u|S)的節(jié)點(diǎn)v1放入S，然后把v1從S0中移除；

4.若|S|≥k，則轉(zhuǎn)到第16步，否則執(zhí)行第11步；

5.將此時(shí)S0中影響力增量次大的節(jié)點(diǎn)v3記錄為BaseNode，并將v3在t輪的影響力增量記錄為BaseValue=Δσ(v3|S)；

6.令t=t+1；

7.計(jì)算此時(shí)S0中在t-1輪影響力增量最大的節(jié)點(diǎn)v2在第t輪的影響力增量Δσ(v2|S)，若Δσ(v2|S)≥BaseValue，轉(zhuǎn)到第8步，否則轉(zhuǎn)到第9步；

8.將v2放入集合S并從S0中移除，轉(zhuǎn)到第4步；

9.按照第t-1輪的影響力增量排序依次計(jì)算除v2以外的其他節(jié)點(diǎn)在第t輪的影響力增量Δσ(u|S)，其中u∈S0S，轉(zhuǎn)到第3步；

10.輸出種子節(jié)點(diǎn)集S，算法結(jié)束。

4.3 算法復(fù)雜度分析

耦合網(wǎng)絡(luò)G包含社交網(wǎng)絡(luò)G1(V1,E1,C1)和G2(V2,E2,C2)，因此G中節(jié)點(diǎn)總數(shù)為n=|V1|+|V2|，連接總數(shù)為l=|E1|+|E2|+|L|，則OA-IPaN算法的時(shí)間復(fù)雜度分析如下：

(1) 計(jì)算耦合網(wǎng)絡(luò)中所有節(jié)點(diǎn)的潛在影響力PI的時(shí)間復(fù)雜度為O(l)；(2) 啟發(fā)式階段篩選k0個(gè)候選節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(pnl)；(3) 貪心階段從候選節(jié)點(diǎn)集S0中挑選k個(gè)種子節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(kRpnl)，R是蒙特卡洛模擬次數(shù)。

5 實(shí) 驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境

本文使用的實(shí)驗(yàn)數(shù)據(jù)集來自Facebook和Twitter兩個(gè)社交網(wǎng)絡(luò)，利用爬蟲技術(shù)隨機(jī)獲取用戶公開數(shù)據(jù)，并分析重疊用戶信息確定跨兩個(gè)社交網(wǎng)絡(luò)的用戶，除網(wǎng)絡(luò)中的推文數(shù)據(jù)外，具體統(tǒng)計(jì)結(jié)果如表1所示。實(shí)驗(yàn)環(huán)境采用Windows 10操作系統(tǒng)，Intel CoreTM i7-7500U 2.9 GHz CPU處理器，8 GB內(nèi)存，編程工具是Anaconda 2，采用Python語言編寫代碼和進(jìn)行相關(guān)實(shí)驗(yàn)。

表1 從Facebook和Twitter獲取的社交網(wǎng)絡(luò)數(shù)據(jù)信息

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

影響力最大化旨在從網(wǎng)絡(luò)中識(shí)別k個(gè)種子節(jié)點(diǎn)，使得通過這k個(gè)種子節(jié)點(diǎn)產(chǎn)生的影響傳播范圍最大。種子節(jié)點(diǎn)的選擇是影響力最大化問題的核心，為此本文從以下四個(gè)方面對(duì)OA-IPaN算法的運(yùn)行結(jié)果進(jìn)行討論：對(duì)比OA-IPaN算法與基準(zhǔn)算法的影響范圍和時(shí)間開銷以驗(yàn)證算法性能；通過實(shí)驗(yàn)結(jié)果分析參數(shù)p設(shè)置對(duì)OA-IPaN算法的影響；分析種子節(jié)點(diǎn)的構(gòu)成以及被激活節(jié)點(diǎn)的構(gòu)成，從而說明跨網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)于影響力傳播的重要性及不同網(wǎng)絡(luò)信息傳播能力的差異；通過對(duì)比實(shí)驗(yàn)驗(yàn)證跨網(wǎng)絡(luò)影響力傳播的優(yōu)勢。

5.2.1算法性能對(duì)比

為驗(yàn)證OA-IPaN算法在選擇種子節(jié)點(diǎn)時(shí)的有效性，本文選擇以下三種基準(zhǔn)算法與之對(duì)比，其中OA-IPaN算法中的參數(shù)p設(shè)置為0.25。

(1) Greedy-IMaN：利用貪心算法從耦合網(wǎng)絡(luò)中依次選取邊際影響力高的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，并采用ID-IPM模型進(jìn)行影響力的模擬擴(kuò)散。(2) Degree-IMaN：基于最大度啟發(fā)式算法，其種子節(jié)點(diǎn)選取策略是從耦合網(wǎng)絡(luò)中依次選取節(jié)點(diǎn)中出度最大的節(jié)點(diǎn)。(3) Random-IMaN：隨機(jī)選擇種子節(jié)點(diǎn)直到節(jié)點(diǎn)數(shù)量達(dá)到要求。

1) 算法影響范圍對(duì)比。如圖3所示，OA-IPaN算法與Greedy-IMaN算法得到的影響范圍大小幾乎一致，且始終優(yōu)于另兩種算法。OA-IPaN算法在k≤75時(shí)影響范圍略低于Greedy-IMaN算法，隨著k值增大在k=100時(shí)實(shí)現(xiàn)反超，并在k=175時(shí)又降到后者之下。這是因?yàn)镺A-IPaN算法在篩選階段篩選出潛在影響力PI較高的候選節(jié)點(diǎn)集，但是這種策略無法避免某些影響力高的節(jié)點(diǎn)被剝奪了選作種子節(jié)點(diǎn)的可能。當(dāng)k較小時(shí)，OA-IPaN算法幾乎能保證選出的候選節(jié)點(diǎn)即為真正影響力排名靠前的節(jié)點(diǎn)，而基本不會(huì)排除掉某些真正影響力高的節(jié)點(diǎn)，因此在k=175之前，OA-IPaN算法都能保持和Greedy-IMaN算法幾乎一致的影響范圍曲線。而隨著k值不斷增加達(dá)到某一數(shù)值(本實(shí)驗(yàn)中為k=175)后，算法無法保證候選節(jié)點(diǎn)是整個(gè)耦合網(wǎng)絡(luò)中真正影響力最高的，因此OA-IPaN算法得到的影響范圍逐漸減小直到低于Greedy-IMaN算法。然而在現(xiàn)實(shí)的病毒式營銷中，一次廣告投放的預(yù)算通常是有限的，種子節(jié)點(diǎn)的數(shù)目通常不會(huì)很大，因此在一定的預(yù)算內(nèi)，OA-IPaN算法仍然能保證良好的效果。

圖3 影響范圍的比較

另一方面，可以看出Degree-IMaN算法的影響范圍曲線呈現(xiàn)持續(xù)上升的趨勢，但遠(yuǎn)低于OA-IPaN算法和Greedy-IMaN算法?？梢娺@種啟發(fā)式算法雖然思想簡單，卻因?yàn)檫x擇種子節(jié)點(diǎn)時(shí)沒有進(jìn)行影響力的模擬傳播，使得無法避免被選擇的節(jié)點(diǎn)之間存在大量影響力重疊的情況，從而導(dǎo)致影響力無法傳播到較大的范圍中。這也說明在跨網(wǎng)絡(luò)影響力傳播環(huán)境下，節(jié)點(diǎn)度的大小并不能直接代表其影響力的大小，直接利用節(jié)點(diǎn)的度選擇種子節(jié)點(diǎn)得到的集合不一定能得到較好的影響力傳播范圍。此外，可以看出Random-IMaN算法取得的影響范圍很小且其曲線呈現(xiàn)不規(guī)律的變化趨勢，甚至在k值增加的過程中出現(xiàn)了下降的情況，原因是隨機(jī)選擇種子節(jié)點(diǎn)進(jìn)行影響力傳播的方式?jīng)]有合理利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)的性質(zhì)。這種效果的不佳也側(cè)面說明了利用影響力最大化算法選擇影響力較大的種子節(jié)點(diǎn)進(jìn)行影響力傳播的作用是顯著的。

2) 算法運(yùn)行時(shí)間對(duì)比。為驗(yàn)證算法的時(shí)間效率，本文測試4種對(duì)比算法在耦合網(wǎng)絡(luò)中挖掘出大小為k=50的種子節(jié)點(diǎn)集所需的時(shí)間，具體結(jié)果如表2所示。

表2 各算法運(yùn)行時(shí)間對(duì)比表

可以看出，Degree-IMaN算法和Random-IMaN算法的時(shí)間效率很高，因?yàn)榍罢咧恍栌?jì)算節(jié)點(diǎn)的出度再依次選擇種子節(jié)點(diǎn)，后者的運(yùn)行時(shí)間則取決于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n和種子節(jié)點(diǎn)數(shù)k的大小。節(jié)點(diǎn)的出度計(jì)算起來十分簡單而n和k是事先給定的，因此這兩種算法用時(shí)很短。Greedy-IMaN算法利用貪心策略選取種子節(jié)點(diǎn)，每選取一個(gè)種子節(jié)點(diǎn)就需要模擬一次影響力傳播并重新計(jì)算各節(jié)點(diǎn)的影響力增量，耗時(shí)很長。在k=50時(shí)，Greedy-IMaN算法的運(yùn)行時(shí)間已經(jīng)達(dá)到了25 614 s，隨著k值的繼續(xù)增大，其運(yùn)行時(shí)間長到難以應(yīng)用到現(xiàn)實(shí)場景中。OA-IPaN算法采用兩階段方法挖掘種子節(jié)點(diǎn)，其中啟發(fā)式階段篩選出了潛在影響力較高的候選節(jié)點(diǎn)，后續(xù)貪心階段僅需要從較小的候選節(jié)點(diǎn)集中挖掘種子節(jié)點(diǎn)，所以耗時(shí)僅為Greedy -IMaN算法耗時(shí)的1/7。Degree-ImaN和Random-ImaN算法盡管耗時(shí)更少，但影響范圍小。

綜上所述，OA-IPaN算法能在幾乎和貪心算法保持一致的影響范圍時(shí)顯著減少運(yùn)行時(shí)間，從而其有效性得以驗(yàn)證。

5.2.2參數(shù)p設(shè)置對(duì)算法性能的影響

候選節(jié)點(diǎn)集S0的大小k0由參數(shù)p=k0/n進(jìn)行調(diào)節(jié)，參數(shù)p的選擇對(duì)種子節(jié)點(diǎn)選擇的結(jié)果、影響范圍σ(S)的大小以及算法的運(yùn)行效率都有著極大的影響，因此本文設(shè)置參數(shù)p從0.05開始以0.05為單位依次取值直到p=0.3，通過對(duì)比實(shí)驗(yàn)分析p值變化對(duì)算法的影響。

1) 參數(shù)p對(duì)算法影響范圍的影響。由圖4可知，當(dāng)k取值較小時(shí)，p值的變化對(duì)算法影響范圍的影響很小，這是由于影響力最高的節(jié)點(diǎn)幾乎均被選為候選節(jié)點(diǎn)，極少高影響力的節(jié)點(diǎn)被遺漏，為貪心階段挖掘出高質(zhì)量節(jié)點(diǎn)提供了保證。而當(dāng)k值增加到某一數(shù)值(本組對(duì)比實(shí)驗(yàn)中為k=100)時(shí)，p值對(duì)算法的影響逐漸變大。p值較小導(dǎo)致啟發(fā)式階段選出的候選節(jié)點(diǎn)集較小，其中難免排除一些影響力較高的節(jié)點(diǎn)，算法精度下降。

圖4 參數(shù)p對(duì)影響范圍的影響

2) 參數(shù)p對(duì)算法運(yùn)行時(shí)間的影響。表3展示了k=50時(shí)不同p取值對(duì)算法運(yùn)行時(shí)間的影響?？梢钥闯鲭S著p取值增加，算法運(yùn)行時(shí)間變長，因?yàn)閜越大候選節(jié)點(diǎn)集越大，貪心階段需要計(jì)算邊際影響力增量的節(jié)點(diǎn)數(shù)就越多，蒙特卡洛模擬的次數(shù)也越多。

表3 p值對(duì)算法運(yùn)行時(shí)間影響對(duì)比

在影響范圍和時(shí)間效率之間找尋合理的平衡是算法的目標(biāo)，在本數(shù)據(jù)集的實(shí)驗(yàn)中，從p=0.25開始，OA-IPaN算法的影響范圍與Greedy-IMaN算法的結(jié)果相差無幾，反而隨著p值的繼續(xù)增大，其運(yùn)行時(shí)間大大增加，因此交叉對(duì)比實(shí)驗(yàn)結(jié)果可知當(dāng)p=0.25時(shí)OA-IPaN算法的綜合性能最好。

5.2.3種子節(jié)點(diǎn)集和激活節(jié)點(diǎn)集組成

本文通過實(shí)驗(yàn)分析種子節(jié)點(diǎn)集和最終被激活節(jié)點(diǎn)集的組成，從而分析兩個(gè)網(wǎng)絡(luò)對(duì)于影響力傳播的貢獻(xiàn)能力的差異。

1) 種子節(jié)點(diǎn)集組成分析。圖5展示了p=0.25時(shí)OA-IPaN算法選擇的種子節(jié)點(diǎn)集S的組成情況，即S中跨網(wǎng)絡(luò)節(jié)點(diǎn)和非跨網(wǎng)絡(luò)節(jié)點(diǎn)的比例隨著種子節(jié)點(diǎn)數(shù)k的變化。圖5中“Both”表示同時(shí)參與兩個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)，即跨網(wǎng)絡(luò)節(jié)點(diǎn)，對(duì)應(yīng)的“Twitter”和“Facebook”分別表示只參與這兩個(gè)網(wǎng)絡(luò)的非跨網(wǎng)絡(luò)節(jié)點(diǎn)。

圖5 種子節(jié)點(diǎn)集所屬網(wǎng)絡(luò)

(1) 兩個(gè)網(wǎng)絡(luò)中的非跨網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)比。由圖5可知，無論k設(shè)置為多少，種子節(jié)點(diǎn)集S中來自Twitter網(wǎng)絡(luò)的非跨網(wǎng)絡(luò)節(jié)點(diǎn)的比例總是大于來自Facebook網(wǎng)絡(luò)的節(jié)點(diǎn)，即Twitter網(wǎng)絡(luò)對(duì)于種子節(jié)點(diǎn)的貢獻(xiàn)率更高，均超過了37%，對(duì)應(yīng)的Facebook網(wǎng)絡(luò)的貢獻(xiàn)率在k=200時(shí)達(dá)到最大值也僅為33.5%。這是因?yàn)楸緦?shí)驗(yàn)數(shù)據(jù)集中Twitter網(wǎng)絡(luò)的規(guī)模明顯大于Facebook網(wǎng)絡(luò)，且Twitter網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)普遍較高，所以選擇Twitter網(wǎng)絡(luò)中的節(jié)點(diǎn)作為種子節(jié)點(diǎn)能夠取得較優(yōu)的影響范圍。

進(jìn)一步分析可知，隨著k值增大，Twitter網(wǎng)絡(luò)對(duì)種子節(jié)點(diǎn)的貢獻(xiàn)率逐漸降低，而Facebook網(wǎng)絡(luò)的貢獻(xiàn)率逐漸升高。原因是當(dāng)k較小時(shí)，規(guī)模較大的Twitter網(wǎng)絡(luò)中的節(jié)點(diǎn)比Facebook網(wǎng)絡(luò)中的節(jié)點(diǎn)能為整個(gè)耦合網(wǎng)絡(luò)提供更多的潛在可影響節(jié)點(diǎn)。當(dāng)k增加到一定值時(shí)，Twitter網(wǎng)絡(luò)中大部分節(jié)點(diǎn)已被激活，這時(shí)Facebook網(wǎng)絡(luò)中的高影響力節(jié)點(diǎn)在耦合網(wǎng)絡(luò)中反而能取得更好的影響效果，因此算法傾向于選擇Facebook網(wǎng)絡(luò)中的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。

(2) 跨網(wǎng)絡(luò)節(jié)點(diǎn)與非跨網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)比。從圖5中可以看出，種子節(jié)點(diǎn)集S中跨網(wǎng)絡(luò)節(jié)點(diǎn)占有較高的比例，在4組實(shí)驗(yàn)中其比例均大于25%，然而實(shí)驗(yàn)數(shù)據(jù)集中兩個(gè)網(wǎng)絡(luò)的重疊度僅有約8.5%。其中當(dāng)k=50時(shí)種子節(jié)點(diǎn)中跨網(wǎng)絡(luò)節(jié)點(diǎn)的比例最高，達(dá)到了36%，此后隨著k值增加該比例略有下降，k=200時(shí)降為25.5%。跨網(wǎng)絡(luò)節(jié)點(diǎn)在種子節(jié)點(diǎn)集S中的比例較高是因?yàn)樗鼈兡芡瑫r(shí)影響兩個(gè)網(wǎng)絡(luò)中各自的朋友，所以相比于只參與一個(gè)網(wǎng)絡(luò)的用戶節(jié)點(diǎn)擁有更廣的潛在影響力傳播范圍，更容易被選為種子節(jié)點(diǎn)。k值較小時(shí)，跨網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)影響力傳播的貢獻(xiàn)很大，且k值越大貢獻(xiàn)越小，這是由于當(dāng)許多在兩個(gè)網(wǎng)絡(luò)中影響力都很大的跨網(wǎng)絡(luò)節(jié)點(diǎn)已被選為種子節(jié)點(diǎn)后，影響范圍已經(jīng)在耦合網(wǎng)絡(luò)中有了較大的擴(kuò)散，此時(shí)兩個(gè)網(wǎng)絡(luò)中不參與跨網(wǎng)絡(luò)傳播的群體之間的影響力擴(kuò)散對(duì)于整體的影響范圍貢獻(xiàn)更大，因此跨網(wǎng)絡(luò)節(jié)點(diǎn)不再受青睞。

綜上可知，合理利用跨網(wǎng)絡(luò)節(jié)點(diǎn)的跨網(wǎng)絡(luò)傳播特性能有效減少種子節(jié)點(diǎn)的數(shù)量。

2) 激活節(jié)點(diǎn)集組成分析。圖6展示了激活節(jié)點(diǎn)集的組成情況隨k值變化的柱狀圖，即OA-IPaN算法選擇的種子節(jié)點(diǎn)最終激活的所有節(jié)點(diǎn)在兩個(gè)網(wǎng)絡(luò)中的分布情況。圖6中 “Both”表示被激活的跨網(wǎng)絡(luò)節(jié)點(diǎn)，對(duì)應(yīng)的“Twitter”和“Facebook”分別表示被激活的、只參與這兩個(gè)網(wǎng)絡(luò)的非跨網(wǎng)絡(luò)節(jié)點(diǎn)。

圖6 激活節(jié)點(diǎn)集所屬網(wǎng)絡(luò)

在所有被激活節(jié)點(diǎn)中，跨網(wǎng)絡(luò)節(jié)點(diǎn)所占的比例較小，在k=50時(shí)該比例最大也不到8%，隨著種子節(jié)點(diǎn)集S增大被激活的跨網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)目呈現(xiàn)出較緩的增長趨勢，但占所有被激活節(jié)點(diǎn)的比例逐漸下降，在k=200時(shí)該比例降為6.7%。

若不考慮跨網(wǎng)絡(luò)節(jié)點(diǎn)，單獨(dú)分析被激活的非跨網(wǎng)絡(luò)節(jié)點(diǎn)在兩個(gè)網(wǎng)絡(luò)中的分布可知，隨著k值從50增加到200，最終被激活的非跨網(wǎng)絡(luò)節(jié)點(diǎn)中屬于Facebook網(wǎng)絡(luò)的比例從39.5%提升到45.8%，反之被激活的非跨網(wǎng)絡(luò)節(jié)點(diǎn)屬于Twitter網(wǎng)絡(luò)的比例略有下降，從52.4%下降到47.7%。這種現(xiàn)象與種子節(jié)點(diǎn)集S的組成情況相對(duì)應(yīng)，k較小時(shí)來自Twitter網(wǎng)絡(luò)的種子節(jié)點(diǎn)較多，因此最終激活的節(jié)點(diǎn)也大多來自Twitter網(wǎng)絡(luò)，而隨著k值的增大，算法更傾向于選取Facebook網(wǎng)絡(luò)中的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，所以屬于Facebook的對(duì)應(yīng)激活節(jié)點(diǎn)更多。

進(jìn)一步分析可知兩個(gè)網(wǎng)絡(luò)中選出的種子節(jié)點(diǎn)數(shù)和最終被激活的節(jié)點(diǎn)數(shù)略不平衡。以k=50為例，被激活的節(jié)點(diǎn)約有52.4%的節(jié)點(diǎn)(不考慮跨網(wǎng)絡(luò)節(jié)點(diǎn))屬于Twitter網(wǎng)絡(luò)，然而結(jié)合圖5可知k=50時(shí)來自Twitter的種子節(jié)點(diǎn)占總種子節(jié)點(diǎn)的63%；同理可知，k=50時(shí)有37%的種子節(jié)點(diǎn)屬于Facebook網(wǎng)絡(luò)，而最終Facebook網(wǎng)絡(luò)中被激活的節(jié)點(diǎn)卻占總被激活節(jié)點(diǎn)的約39.5%。顯然種子節(jié)點(diǎn)數(shù)占比較小的網(wǎng)絡(luò)激活的節(jié)點(diǎn)占比提升了，反之含種子節(jié)點(diǎn)多的網(wǎng)絡(luò)未能按照同等的比例激活此網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)。這種現(xiàn)象說明即使跨網(wǎng)絡(luò)節(jié)點(diǎn)為兩個(gè)網(wǎng)絡(luò)提供了影響力傳播的通道，但不同網(wǎng)絡(luò)中的用戶接受影響的能力是不同的，影響力在不同網(wǎng)絡(luò)中的傳播能力也是不一樣的。

5.2.4跨網(wǎng)絡(luò)影響力傳播的優(yōu)勢

本文在不考慮時(shí)間效率的情況下比較了在耦合網(wǎng)絡(luò)中與在多個(gè)獨(dú)立網(wǎng)絡(luò)中分別挖掘出的種子節(jié)點(diǎn)各自能將影響力傳播到多大的范圍。此組對(duì)比實(shí)驗(yàn)中影響范圍都用最終被激活的節(jié)點(diǎn)數(shù)目來量化，其中三種對(duì)比算法描述如下。

(1) OA-IPaN(p=0.25)：本文算法采用ID-IPM模型模擬耦合網(wǎng)絡(luò)中影響力的傳播，并利用啟發(fā)式和貪心策略兩階段選取種子節(jié)點(diǎn)，其中參數(shù)p取值為0.25。

(2) Twitter-IM：僅利用Twitter網(wǎng)絡(luò)中內(nèi)部的傳播通道進(jìn)行影響力傳播，并利用貪心算法選擇種子節(jié)點(diǎn)，其中影響力傳播的模擬利用IC模型實(shí)現(xiàn)。

(3) Facebook-IM：與Twitter-IM類似，在Facebook網(wǎng)絡(luò)中利用貪心算法挖掘種子節(jié)點(diǎn)并利用IC模型模擬影響力的傳播方式。

圖7展示了為達(dá)到同等規(guī)模的影響范圍(即激活節(jié)點(diǎn)數(shù))三個(gè)對(duì)比算法各需要的種子節(jié)點(diǎn)數(shù)目?？梢妼?duì)比另兩種算法，本文OA-IPaN算法利用平均約1/5的節(jié)點(diǎn)數(shù)就能將影響力傳播到兩個(gè)網(wǎng)絡(luò)的大量節(jié)點(diǎn)中，即OA-IPaN算法挖掘出的種子節(jié)點(diǎn)質(zhì)量更高。此外，對(duì)比Twitter-IM 和Facebook-IM算法發(fā)現(xiàn)，在Facebook網(wǎng)絡(luò)中想要達(dá)到同等規(guī)模的影響范圍需要的種子節(jié)點(diǎn)數(shù)目更多，這是因?yàn)镕acebook網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)以及節(jié)點(diǎn)間連接數(shù)都很小，影響力在該網(wǎng)絡(luò)中較難傳播。

圖7 相同規(guī)模影響范圍所需種子節(jié)點(diǎn)數(shù)量

綜上所述，合理利用跨網(wǎng)絡(luò)節(jié)點(diǎn)的跨網(wǎng)絡(luò)影響力傳播特性進(jìn)行影響力傳播不僅能擁有更大的影響力傳播空間，而且能以更高的效率取得更廣的影響范圍。

6 結(jié) 語

本文首先將多個(gè)網(wǎng)絡(luò)耦合成一個(gè)網(wǎng)絡(luò)再綜合考慮跨網(wǎng)絡(luò)節(jié)點(diǎn)的信息傳播特性和用戶的興趣特質(zhì)，提出了ID-IPM模型。其次，在ID-IPM模型基礎(chǔ)上，提出了OA-IPaN算法分挖掘種子節(jié)點(diǎn)，其中在篩選階段利用節(jié)點(diǎn)的度中心性初步篩選候選節(jié)點(diǎn)，減少了大量運(yùn)行時(shí)間，在選取階段根據(jù)子模特性優(yōu)化的貪心算法進(jìn)一步挖掘種子節(jié)點(diǎn)，提升了算法精度。實(shí)驗(yàn)結(jié)果說明了OA-IPaN算法在解決跨網(wǎng)絡(luò)影響力最大化問題時(shí)在影響范圍和時(shí)間效率上的有效性，并驗(yàn)證了跨網(wǎng)絡(luò)挖掘種子節(jié)點(diǎn)相對(duì)單網(wǎng)絡(luò)環(huán)境中的高效性。未來將通過增加網(wǎng)絡(luò)個(gè)數(shù)從而在更大的網(wǎng)絡(luò)環(huán)境中研究跨網(wǎng)絡(luò)影響力最大化問題，以及嘗試找尋其他的切入點(diǎn)，研究和設(shè)計(jì)出更加全面的、符合現(xiàn)實(shí)規(guī)律的影響力傳播模型。