一種興趣驅動的跨網絡傳播優化算法

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

1(江蘇大學計算機科學與通信工程學院 江蘇 鎮江 212013) 2(中國傳媒大學新聞傳播學部新聞學院 北京 100024)

0 引 言

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

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

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

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

為此，本文首先構建出同一跨網絡用戶之間的虛擬連接，以此作為媒介形成耦合網絡；其次基于獨立級聯模型提出了興趣驅動的跨網絡影響力傳播模型(ID-IPM)，以模擬信息在網絡內部和網絡之間的傳播方式；最后針對隨著網絡規模擴大而增大的時間開銷問題，提出啟發式和貪心算法結合的優化種子節點選取方法(OA-IPaN)以解決跨網絡影響力傳播問題。本文主要工作如下：

1) 提出了一種興趣驅動的跨網絡影響力傳播模型ID-IPM。首先，通過跨網絡用戶的“橋梁”作用進行網絡耦合；其次，對獨立級聯模型進行了改進。該模型不僅通過跨網絡用戶的“橋梁”作用進行網絡耦合，而且綜合考慮跨網絡用戶在網絡內部、網絡之間進行信息傳播的差異及用戶興趣的差異來計算節點間影響概率，以提高用戶影響力的傳播范圍。

2) 基于ID-IPM模型，提出了一種啟發式算法和貪心算法結合的跨網絡影響力傳播的優化算法(OA-IPaN)。該算法基于ID-IPM模型，利用啟發式算法及貪心算法分兩階段進行種子節點的挖掘，以提高OA-IPaN算法的效率。

3) 實驗結果表明本文提出的ID-IPM模型與OA-IPaN算法在影響范圍和時間效率上的有效性，也驗證了跨網絡環境中挖掘種子節點相比單網絡環境中的高效性。

1 相關工作

影響力最大化是以病毒式營銷為背景、信息傳播模型為基礎的種子節點選擇問題，被廣泛應用于廣告投放、謠言預警等領域，已成為社交網絡分析中的研究熱點。然而現有的大部分研究通常應用于某個特定社交網絡，只分析一個網絡中的各類數據，導致用戶的影響力評估準確率低、影響范圍窄。

單一網絡中的影響力最大化問題自提出以來其解決方法已經被學者做了較為充分的探索。部分學者考慮到利用社交網絡的社區結構性質能夠降低問題的處理規模從而節省時間開銷，例如：Wang等[26]提出的CGA先把網絡分成多個社區再采取動態規劃算法計算每輪應該選擇種子節點所在的社區，最后再利用MixGreedy算法在該社區里尋找種子節點。有學者從網絡發布內容出發解決問題，例如：Barbieri等[11]通過主題建模研究社交影響力，并基于傳統的IC模型和LT模型提出了能夠更準確模擬現實世界信息擴散的話題感知模型TIC和TLT；Chen等[12]在此基礎上研究了主題感知下的影響力最大化問題；Li等[13]首次從地理位置的角度出發進行研究，旨在從某一給定地理區域中找到k個能夠將影響力在此區域中傳播到最大范圍的種子節點，此后文獻[14，27-28]也做了更深入的研究。除此之外，有學者從時間感知[29-31]、動態[32-33]和競爭性[34-36]等方向對影響力最大化問題進行了研究。總之，單一網絡中的影響力最大化問題已經從多角度多方位得到了較為充分的研究，而隨著許多用戶的跨社交網絡平臺參與行為逐漸增多，各個社交網絡間的交集也隨之增加，學者開始從跨網絡的角度探究影響力最大化。

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

跨網絡影響力最大化是單網絡影響力最大化的擴展，即在給定的多個社交網絡中挖掘出一群用戶，讓它們在這些社交網絡的整體范圍內影響盡可能多的用戶，其中這些網絡內部的用戶會在各個網絡內部傳播信息，且跨網絡用戶會在網絡間交叉傳播信息。可見跨網絡影響力最大化的研究需要以網絡之間的信息交流為基礎，且跨網絡用戶是不同網絡間的連接媒介。

2 問題描述與相關定義

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

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

定義1跨網絡用戶/非跨網絡用戶。同時在網絡G1和G2中擁有賬號的用戶稱為跨網絡用戶，反之只在其中一個網絡中擁有賬號的用戶稱為非跨網絡用戶。

相應地，在社交網絡拓撲圖中，跨網絡用戶對應的節點稱為跨網絡節點，非跨網絡用戶對應的節點稱為非跨網絡節點。

定義2現實個體。現實個體是社交網絡中的賬號在現實世界中對應的、可以相互區分的個體。

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

定義5影響范圍σ(S)。根據給定影響力傳播模型，所有種子節點u∈S直接或者間接激活的現實個體集合用σ(S)表示。

本文利用被激活的現實個體而非被激活的節點來定義影響范圍，原因是跨網絡環境下被激活的節點中可能包含較多的跨網絡用戶，而影響傳播的效果最終是作用在某一現實個體上的，若利用被激活的節點數量來量化影響范圍的大小會導致影響范圍的重復計算，從而使得影響傳播范圍判定過高。

3 興趣驅動的跨網絡傳播模型

3.1 基于跨網絡節點的重疊網絡耦合策略

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

圖1 重疊網絡耦合策略圖示

定義7跨網連邊集L。一對跨網絡節點之間的虛擬信息傳播通道稱為跨網連邊，所有跨網連邊組成的集合為跨網連邊集，記作L。

例如圖1中跨網絡節點a和b之間的跨網連邊(a,b)∈L就是網絡G1和G2之間信息傳播的一條虛擬通道。在構建網絡G1和G2間的跨網連邊后，信息可以在兩個網絡內部獨立傳播還可以通過跨網絡節點進行傳播，從而實現了重疊網絡G1和G2的耦合。耦合網絡的具體定義如定義8。

定義8耦合網絡G。保留一對重疊網絡G1和G2各自內部的全部節點和節點連接，并構建同一跨網絡節點之間的虛擬跨網連邊，得到耦合網絡G(G1,G2,L)，其中L為G1和G2之間的跨網連邊集。

3.2 興趣驅動的節點間影響概率

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

1) 主題相似度。用戶主題偏好是用戶興趣特質在社交網絡中的表現形式之一，兩個用戶關注內容的主題越相似，他們的興趣就越一致，受到彼此影響的概率越高。本文通過對用戶發布的文本信息進行LDA[23]建模得到用戶關注的主題及相應的頻度，再利用主題分布來表示用戶的主題偏好，最后通過計算主題分布的相似度來表示主題相似度。

定義9主題相似度Φuv。假設u和v是同一網絡內的節點，則這一對網內節點之間的主題相似度Φuv是兩者的主題分布相似程度。

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

(1)

式中：Tu和Tv為節點u和v的主題分布；DJS(Tu,Tv)為兩個分布的JS散度。

2) 交互頻度。由于網絡內部的節點之間依靠關注、轉發和評論等方式進行交互[24]，交互頻度能夠體現出用戶的興趣特質，交互越頻繁影響力傳播的可能性越高，其具體定義見定義10。

定義10交互頻度Ψuv。同一網絡內的節點u和v的交互頻度Ψuv定義為兩者之間轉發消息的頻率，其計算公式如下：

(2)

3) 節點間的影響概率。本文以興趣為驅動綜合考慮網內節點間的主題相似度和交互頻度以判斷影響概率的大小，并如定義11對網內節點間的影響概率進行定義。

定義11節點影響概率Puv。同一網絡內部的節點u對v的影響概率Puv定義如下：

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

u,v∈V1或u,v∈V2

(3)

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

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

ID-IPM模型是獨立級聯模型在跨網絡環境中的應用和改進，該模型的影響力傳播示例圖如圖2所示。

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

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

圖2中，v4∈V1、v5∈V1和u3∈V2為t時刻的激活節點，其中v5和u3為一對跨網絡節點。這三個節點會對各自的出鄰居節點施加影響力，如節點v4分別以概率pv4v3和pv4v6嘗試激活G1內的未激活節點v3和v6，同理節點v5和u3以一定概率嘗試激活G1內的節點v1、v6、v7及G2內的節點u1、u4、u6和u7。若節點u7被節點u3成功激活則會在t+1時刻分別以概率pu7u4和pu7u8去嘗試激活節點u4和u8。若跨網絡節點v7與節點u5是同一個節點，當其中一個被其他節點激活時，另一個就自動被激活，然后就能夠將信息跨網絡傳遞給其他節點，此為一次跨網絡信息傳播的過程。

ID-IPM模型中的激活行為只會執行一次。如圖2中，由于節點u8只能接收到節點u7的影響力，一旦它未能被u7成功激活則它在該影響力傳播過程中只能一直保持未激活狀態。反之，節點u4能夠接收到u3和u7兩個節點的影響力，一旦它被兩者中的任何一個成功激活都能轉換為激活狀態。

4 跨網絡的影響力優化算法

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

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

4.1 候選節點篩選

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

定義12潛在影響力PI。節點的潛在影響力PI表示其影響力傳播能力的大小，u∈V1∪V2的潛在影響力PIu的計算如下：

(4)

式中：du表示節點u的出度；|V1|+|V2|-|C1|表示耦合網絡G中能被影響的全部現實個體數。

算法1候選節點篩選

1.初始化候選節點集合S0=?，并將耦合網絡G中所有的狀態標簽標記為Selected=0；

2.根據式(4)計算耦合網絡G中全部節點的潛在影響力PI，并按照PI值的大小進行排序；

3.選擇PI值最大且狀態標簽為Selected=0的節點v作為候選節點并放入集合S0；

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

5.判斷v是否為跨網絡節點：若v是跨網絡節點，則將v的狀態標簽設置為Selected=1，轉到第3步；否則將v及其對應跨網絡節點u的狀態標簽均設置為Selected=1，轉到第3步；

6.輸出候選節點集S0。

4.2 種子節點集選取

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

定義13影響力增量Δσ(u|S)。若當前種子節點集S經模擬影響擴散后的影響范圍為σ(u|S)，則加入節點u后增加的新激活現實個體集合即為影響力增量Δσ(u|S)，其計算方法如下：

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

(5)

算法2種子節點集選取

1.初始化種子節點集合，并設置t=1；

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

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

4.若|S|≥k，則轉到第16步，否則執行第11步；

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

6.令t=t+1；

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

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

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

10.輸出種子節點集S，算法結束。

4.3 算法復雜度分析

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

(1) 計算耦合網絡中所有節點的潛在影響力PI的時間復雜度為O(l)；(2) 啟發式階段篩選k0個候選節點的時間復雜度為O(pnl)；(3) 貪心階段從候選節點集S0中挑選k個種子節點的時間復雜度為O(kRpnl)，R是蒙特卡洛模擬次數。

5 實 驗

5.1 實驗數據集和實驗環境

本文使用的實驗數據集來自Facebook和Twitter兩個社交網絡，利用爬蟲技術隨機獲取用戶公開數據，并分析重疊用戶信息確定跨兩個社交網絡的用戶，除網絡中的推文數據外，具體統計結果如表1所示。實驗環境采用Windows 10操作系統，Intel CoreTM i7-7500U 2.9 GHz CPU處理器，8 GB內存，編程工具是Anaconda 2，采用Python語言編寫代碼和進行相關實驗。

表1 從Facebook和Twitter獲取的社交網絡數據信息

5.2 實驗結果與分析

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

5.2.1算法性能對比

為驗證OA-IPaN算法在選擇種子節點時的有效性，本文選擇以下三種基準算法與之對比，其中OA-IPaN算法中的參數p設置為0.25。

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

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

圖3 影響范圍的比較

另一方面，可以看出Degree-IMaN算法的影響范圍曲線呈現持續上升的趨勢，但遠低于OA-IPaN算法和Greedy-IMaN算法。可見這種啟發式算法雖然思想簡單，卻因為選擇種子節點時沒有進行影響力的模擬傳播，使得無法避免被選擇的節點之間存在大量影響力重疊的情況，從而導致影響力無法傳播到較大的范圍中。這也說明在跨網絡影響力傳播環境下，節點度的大小并不能直接代表其影響力的大小，直接利用節點的度選擇種子節點得到的集合不一定能得到較好的影響力傳播范圍。此外，可以看出Random-IMaN算法取得的影響范圍很小且其曲線呈現不規律的變化趨勢，甚至在k值增加的過程中出現了下降的情況，原因是隨機選擇種子節點進行影響力傳播的方式沒有合理利用網絡的拓撲結構和節點的性質。這種效果的不佳也側面說明了利用影響力最大化算法選擇影響力較大的種子節點進行影響力傳播的作用是顯著的。

2) 算法運行時間對比。為驗證算法的時間效率，本文測試4種對比算法在耦合網絡中挖掘出大小為k=50的種子節點集所需的時間，具體結果如表2所示。

表2 各算法運行時間對比表

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

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

5.2.2參數p設置對算法性能的影響

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

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

圖4 參數p對影響范圍的影響

2) 參數p對算法運行時間的影響。表3展示了k=50時不同p取值對算法運行時間的影響。可以看出隨著p取值增加，算法運行時間變長，因為p越大候選節點集越大，貪心階段需要計算邊際影響力增量的節點數就越多，蒙特卡洛模擬的次數也越多。

表3 p值對算法運行時間影響對比

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

5.2.3種子節點集和激活節點集組成

本文通過實驗分析種子節點集和最終被激活節點集的組成，從而分析兩個網絡對于影響力傳播的貢獻能力的差異。

1) 種子節點集組成分析。圖5展示了p=0.25時OA-IPaN算法選擇的種子節點集S的組成情況，即S中跨網絡節點和非跨網絡節點的比例隨著種子節點數k的變化。圖5中“Both”表示同時參與兩個網絡的節點，即跨網絡節點，對應的“Twitter”和“Facebook”分別表示只參與這兩個網絡的非跨網絡節點。

圖5 種子節點集所屬網絡

(1) 兩個網絡中的非跨網絡節點對比。由圖5可知，無論k設置為多少，種子節點集S中來自Twitter網絡的非跨網絡節點的比例總是大于來自Facebook網絡的節點，即Twitter網絡對于種子節點的貢獻率更高，均超過了37%，對應的Facebook網絡的貢獻率在k=200時達到最大值也僅為33.5%。這是因為本實驗數據集中Twitter網絡的規模明顯大于Facebook網絡，且Twitter網絡中節點的度數普遍較高，所以選擇Twitter網絡中的節點作為種子節點能夠取得較優的影響范圍。

進一步分析可知，隨著k值增大，Twitter網絡對種子節點的貢獻率逐漸降低，而Facebook網絡的貢獻率逐漸升高。原因是當k較小時，規模較大的Twitter網絡中的節點比Facebook網絡中的節點能為整個耦合網絡提供更多的潛在可影響節點。當k增加到一定值時，Twitter網絡中大部分節點已被激活，這時Facebook網絡中的高影響力節點在耦合網絡中反而能取得更好的影響效果，因此算法傾向于選擇Facebook網絡中的節點作為種子節點。

(2) 跨網絡節點與非跨網絡節點對比。從圖5中可以看出，種子節點集S中跨網絡節點占有較高的比例，在4組實驗中其比例均大于25%，然而實驗數據集中兩個網絡的重疊度僅有約8.5%。其中當k=50時種子節點中跨網絡節點的比例最高，達到了36%，此后隨著k值增加該比例略有下降，k=200時降為25.5%。跨網絡節點在種子節點集S中的比例較高是因為它們能同時影響兩個網絡中各自的朋友，所以相比于只參與一個網絡的用戶節點擁有更廣的潛在影響力傳播范圍，更容易被選為種子節點。k值較小時，跨網絡節點對影響力傳播的貢獻很大，且k值越大貢獻越小，這是由于當許多在兩個網絡中影響力都很大的跨網絡節點已被選為種子節點后，影響范圍已經在耦合網絡中有了較大的擴散，此時兩個網絡中不參與跨網絡傳播的群體之間的影響力擴散對于整體的影響范圍貢獻更大，因此跨網絡節點不再受青睞。

綜上可知，合理利用跨網絡節點的跨網絡傳播特性能有效減少種子節點的數量。

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

圖6 激活節點集所屬網絡

在所有被激活節點中，跨網絡節點所占的比例較小，在k=50時該比例最大也不到8%，隨著種子節點集S增大被激活的跨網絡節點的數目呈現出較緩的增長趨勢，但占所有被激活節點的比例逐漸下降，在k=200時該比例降為6.7%。

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

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

5.2.4跨網絡影響力傳播的優勢

本文在不考慮時間效率的情況下比較了在耦合網絡中與在多個獨立網絡中分別挖掘出的種子節點各自能將影響力傳播到多大的范圍。此組對比實驗中影響范圍都用最終被激活的節點數目來量化，其中三種對比算法描述如下。

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

(2) Twitter-IM：僅利用Twitter網絡中內部的傳播通道進行影響力傳播，并利用貪心算法選擇種子節點，其中影響力傳播的模擬利用IC模型實現。

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

圖7展示了為達到同等規模的影響范圍(即激活節點數)三個對比算法各需要的種子節點數目。可見對比另兩種算法，本文OA-IPaN算法利用平均約1/5的節點數就能將影響力傳播到兩個網絡的大量節點中，即OA-IPaN算法挖掘出的種子節點質量更高。此外，對比Twitter-IM 和Facebook-IM算法發現，在Facebook網絡中想要達到同等規模的影響范圍需要的種子節點數目更多，這是因為Facebook網絡中節點數以及節點間連接數都很小，影響力在該網絡中較難傳播。

圖7 相同規模影響范圍所需種子節點數量

綜上所述，合理利用跨網絡節點的跨網絡影響力傳播特性進行影響力傳播不僅能擁有更大的影響力傳播空間，而且能以更高的效率取得更廣的影響范圍。

6 結 語

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