社交網(wǎng)絡(luò)中對(duì)立影響最大化算法

楊書新，梁 文，朱凱麗

（江西理工大學(xué)信息工程學(xué)院，江西贛州 341000）

（*通信作者電子郵箱jhcpl05@163.com）

0 引言

社交網(wǎng)絡(luò)用戶間的關(guān)系是多樣化的，或協(xié)作配合、或?qū)α⑴懦饣騽?dòng)態(tài)博弈，傳統(tǒng)單源信息的影響傳播研究無法描述其復(fù)雜性，因此產(chǎn)生了多源信息影響傳播的研究。多源信息影響最大化也稱之為競爭影響最大化。謠言阻礙、捆綁銷售、黨派博弈、病毒營銷、游戲競賽的規(guī)則模擬均屬于多源信息影響最大化的研究問題［1-3］?，F(xiàn)有工作主要依靠經(jīng)典獨(dú)立級(jí)聯(lián)（Independent Cascade，IC）模型和線性閾值（Linear Threshold，LT）模型開展研究，部分用于求解競爭影響最大化問題的算法僅適用于特定結(jié)構(gòu)的數(shù)據(jù)，尚缺乏普適性。針對(duì)上述不足，本文擴(kuò)展熱量傳播模型為多源熱量傳播模型，研究對(duì)立影響最大化問題。

1 相關(guān)工作

2007 年，Bharathi 等［4］首次給出競爭影響最大化（Competitive Influence Maximization）問題的定義：已知種子集SA分布的情況下，選拔種子集SB，使SB的影響傳播效果最大化，其中SA和SB代表不同信息源。競爭影響最大化的相關(guān)研究產(chǎn)生了許多具有代表性的成果，本文圍繞競爭影響傳播模型、競爭影響傳播問題的優(yōu)化算法兩方面介紹國內(nèi)外研究現(xiàn)狀。關(guān)于競爭傳播模型，已有相關(guān)工作主要針對(duì)單源信息的獨(dú)立級(jí)聯(lián)（IC）模型和線性閾值（LT）模型加以擴(kuò)展?；贗C模型，文獻(xiàn)［5-6］提出了基于IC 模型的多實(shí)體競爭（Multi-Campaign IC）模型、波擴(kuò)散（Wave Propagation）模型及基于距離的（Distance-based）多源信息傳播模型。Borodin等［7］率先利用LT 模型研究競爭影響最大化問題，設(shè)計(jì)了權(quán)重競爭閾值（Weight Competitive LT）模型、分隔競爭閾值（Separate Competitive LT）模型。He 等［8］首次定 義了競爭線性 閾值（Competitive LT）模型。

關(guān)于競爭影響最大化問題的優(yōu)化算法，相關(guān)工作已取得了積極進(jìn)展。文獻(xiàn)［4］提出的FPTAS（Fully Polynomial-Time Approximation Scheme）在理論上具有63%的下界保證。針對(duì)競爭影響最大化問題，He 等［8］提出了適用于有向無環(huán)圖的CLDAG（Competitive Local Directed Acyclic Graph）算法。Zhu等［9］研究了基于位置感知的影響阻礙最大化（Location-aware Influence Blocking Maximization，LIBM）問題，利用位置數(shù)據(jù)劃分區(qū)域，設(shè)計(jì)了LIBM-H和LIBM-C兩種啟發(fā)式算法，實(shí)驗(yàn)表明兩種算法均能有效求解競爭最大化問題。文獻(xiàn)［4，9］的算法僅適用于樹型數(shù)據(jù)結(jié)構(gòu)。Pham 等［10］研究了回避多余用戶（unwanted users）的競爭影響最大化問題，多余用戶是非預(yù)期內(nèi)被影響的特定群體。文獻(xiàn)［10］基于競爭閾值模型證明了該問題是NP-Complete問題，設(shè)計(jì)了一種啟發(fā)式方法并在真實(shí)數(shù)據(jù)集中驗(yàn)證了有效性。

本文考慮信息對(duì)立式競爭影響傳播的形式。對(duì)立影響傳播是指多源信息傳播中，成功影響個(gè)體的信息是唯一的。對(duì)立信息的影響傳播可以概括許多生活化的場景。例如社交網(wǎng)絡(luò)中用戶對(duì)輿論事件正面及負(fù)面觀點(diǎn)往往是對(duì)立的。或是通過社交網(wǎng)絡(luò)的廣告影響，用戶確定購買某個(gè)品牌商品后，短期內(nèi)不會(huì)考慮再購買同類別其他品牌商品。針對(duì)信息的對(duì)立競爭形式，本文擴(kuò)展單源熱量傳播模型為多源熱量傳播模型，設(shè)計(jì)了預(yù)選式貪心算法，并在編程爬取的大規(guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集中驗(yàn)證其有效性。

2 問題及模型的定義

2.1 對(duì)立影響最大化問題的定義

給定社交網(wǎng)絡(luò)G=（V，E）與信息傳播模型，其中：V表示由網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)成的集合，E表示網(wǎng)絡(luò)節(jié)點(diǎn)間邊的集。已知種子集SA?V的分布情況，選拔由k個(gè)節(jié)點(diǎn)構(gòu)成的種子集SB?V且SB?VSA，使SB的影響收益σ(SB，SA)最大化，其中SA和SB代表對(duì)立的信息源。對(duì)立影響最大化（Reverse Influence Maximization）問題的形式化表達(dá)為：

當(dāng)SA=?時(shí)，傳統(tǒng)單源信息傳播的影響最大化問題即為對(duì)立影響最大化問題的特例。σ(SB，SA)是集合V的子模函數(shù)，因此仍具有子模特性。以σ(SB，SA)為目標(biāo)函數(shù)，貪心近似（Greedy Approximation）算法經(jīng)過有限次的迭代計(jì)算，可以得到保證下界的近似最優(yōu)種子集SB，即≥(1-1/e)σ(SB，SA)。

2.2 多源熱量傳播模型的推導(dǎo)

根據(jù)物理經(jīng)驗(yàn)，熱量總是自高處向低處轉(zhuǎn)移以達(dá)到均衡。社交網(wǎng)絡(luò)的信息傳播過程與此相似，向外傳播影響的個(gè)體總是最先被激活的種子。同樣，設(shè)具有不同標(biāo)記的熱量與不同的信息是對(duì)應(yīng)的，則單源信息的熱量傳播（Heat Diffusion，HD）模型［11］可被擴(kuò)展為多源信息熱量傳播（Multi-Source HD，MSHD）模型。該模型可用于模擬對(duì)立信息的影響傳播，解決對(duì)立影響最大化問題。下面給出MSHD模型的推導(dǎo)過程。

給定有向社交網(wǎng)絡(luò)G=（V，E），G中的任意一個(gè)節(jié)點(diǎn)vi在傳播初始時(shí)刻t=0時(shí)，其熱量參數(shù)記為hi(0)；t≥1時(shí)，vi的熱量值記為hi(t)。采用h(ξε，t)記錄G中全部節(jié)點(diǎn)在t時(shí)刻的熱值，向量長度為節(jié)點(diǎn)總數(shù)n(n=|V|)，其表達(dá)式為：

其中，ξε(ε＞2，ε∈Z+)對(duì)應(yīng)的是ε個(gè)信息源的不同激活狀態(tài)。熱量總是沿有向邊，自高向低轉(zhuǎn)移。以節(jié)點(diǎn)vi為例，若節(jié)點(diǎn)vi與節(jié)點(diǎn)vj間存在有向邊，即evj，vi∈E。根據(jù)節(jié)點(diǎn)有向邊的不同方向，將vj與vi的熱量轉(zhuǎn)移分兩種情況討論。

考慮情況一，若節(jié)點(diǎn)vj指向節(jié)點(diǎn)vi，此時(shí)節(jié)點(diǎn)vi熱值為0，或節(jié)點(diǎn)vj和vi的激活態(tài)相同且vj熱值高于vi。自t時(shí)刻開始，經(jīng)過一段時(shí)間Δt后，熱量從vj向vi轉(zhuǎn)移的量為(α?hj(t)?Δt)/dj，dj表示節(jié)點(diǎn)vi的出度鄰居數(shù)量，導(dǎo)熱系數(shù)（Thermal Conductivity）α表示信息的傳播能力。在Δt的時(shí)間長度內(nèi)，節(jié)點(diǎn)vi收到的總熱量記為Ghi(t，Δt)。

考慮情況二，若節(jié)點(diǎn)vi指向節(jié)點(diǎn)vj，此時(shí)節(jié)點(diǎn)vi和vj的激活態(tài)相同且vi熱值高于vj。自t時(shí)刻開始，經(jīng)過一段時(shí)間Δt后，熱量自vi向vj轉(zhuǎn)移的量設(shè)為Phi(t，Δt)。則節(jié)點(diǎn)vi對(duì)其前向節(jié)點(diǎn)及后繼節(jié)點(diǎn)的能量轉(zhuǎn)移公式為：

仍以節(jié)點(diǎn)vi為例，在t+Δt時(shí)刻內(nèi)，節(jié)點(diǎn)vi所轉(zhuǎn)移的熱量為應(yīng)為hi(t+Δt)-hi(t)，其表達(dá)函數(shù)為：

式中，φi是熱量輸出的標(biāo)志位，其值只能為0 或1。當(dāng)φi為0時(shí)，表示熱量無法發(fā)生轉(zhuǎn)移，即節(jié)點(diǎn)vi無后繼節(jié)點(diǎn)（di=0）或節(jié)點(diǎn)vi與其鄰居的熱量標(biāo)記不同(ξε(i) ≠ξε(j))；當(dāng)φi值為1時(shí)，熱量可以發(fā)生轉(zhuǎn)移，即節(jié)點(diǎn)vi存在后繼節(jié)點(diǎn)（di＞0）且節(jié)點(diǎn)vi與其鄰居的熱量標(biāo)記相同(ξε(i)=ξε(j))。根據(jù)泰勒公式（Taylor series），整理式（5）得到節(jié)點(diǎn)在t時(shí)刻的熱量表達(dá)式為：

其中：e是自然數(shù)，H是圖G中節(jié)點(diǎn)連接關(guān)系的n階矩陣：

同樣，根據(jù)節(jié)點(diǎn)當(dāng)前的標(biāo)記狀態(tài)、熱量值的大小加以相應(yīng)的調(diào)整，MSHD 模型也可適用于無向網(wǎng)絡(luò)。將MSHD 模型應(yīng)用至實(shí)際問題中，以對(duì)立的兩個(gè)信息源為例即可。

2.3 打破平局規(guī)則的設(shè)定

傳播模型和打破平局規(guī)則（tie-breaking rule）［12］是對(duì)立信息影響傳播機(jī)制的核心。打破平局規(guī)則用于處理節(jié)點(diǎn)被多源對(duì)立信息同時(shí)影響的狀態(tài)響應(yīng)問題?，F(xiàn)實(shí)社交網(wǎng)絡(luò)中，個(gè)體所接收的信息五花八門，而其最終采納的信息源總是唯一的。以市場上存在競爭的筆記本電腦品牌為例，用戶若鎖定某品牌并購買，該用戶在短期內(nèi)不會(huì)購買同類別商品?？梢哉J(rèn)為不同品牌的商品對(duì)普通用戶的影響是對(duì)立傳播的。為合理表達(dá)上述情境中個(gè)體的決策問題，本文設(shè)計(jì)了一種隨機(jī)規(guī)則（random rule）。該規(guī)則設(shè)定激活同一個(gè)節(jié)點(diǎn)的信息源是唯一的，且被激活的過程不可逆，其具體步驟見圖1。

以圖1（a）的簡單網(wǎng)絡(luò)為例，此時(shí)節(jié)點(diǎn)u同時(shí)面對(duì)4股對(duì)立的熱源，采用隨機(jī)規(guī)則，節(jié)點(diǎn)u的狀態(tài)響應(yīng)的過程如下：列舉由節(jié)點(diǎn)u直接鄰居構(gòu)成的序列，如圖1（b），將圖1（b）的序列亂序排列得到圖1（c）。根據(jù)圖1（c）的排列次序，種子以激活概率p（本文設(shè)為0.5）依次嘗試激活節(jié)點(diǎn)u，首個(gè)激活節(jié)點(diǎn)u的信息源將作為成功激活節(jié)點(diǎn)u的種子。節(jié)點(diǎn)u被激活后，不再接受其他狀態(tài)種子的影響。

圖1 隨機(jī)規(guī)則Fig.1 Random rule

2.4 模型的傳播步驟及示例

2.2 和2.3 節(jié)完善了MSHD 模型的傳播機(jī)制，下面給出該模型的傳播步驟：初始時(shí)刻t=0，對(duì)立種子集SA已知，部署種子集SB至網(wǎng)絡(luò)G中并賦予初始熱量。當(dāng)t＞0時(shí)，集合SA和SB中的初始節(jié)點(diǎn)參照熱量傳導(dǎo)公式沿有向邊轉(zhuǎn)移熱量，當(dāng)節(jié)點(diǎn)預(yù)接收的熱量不屬于同個(gè)信息源，采用隨機(jī)規(guī)則處理。重復(fù)該過程直至經(jīng)過有限步長，統(tǒng)計(jì)當(dāng)前熱值高于熱量閾值的節(jié)點(diǎn)，并標(biāo)記為激活節(jié)點(diǎn)。以圖2 的簡單網(wǎng)絡(luò)為例，給出MSHD模型的仿真計(jì)算過程。

圖2 MSHD模型的計(jì)算過程Fig.2 Computing process of MSHD model

假定網(wǎng)絡(luò)中存在A、B兩種對(duì)立信息源，初始節(jié)點(diǎn)的熱量值為20，導(dǎo)熱系數(shù)為0.15，f（）表示節(jié)點(diǎn)當(dāng)前的熱量值，節(jié)點(diǎn)的熱量激活閾值等于0.2。當(dāng)t=0時(shí)，網(wǎng)絡(luò)中僅有S1、S2作為初始節(jié)點(diǎn)被激活；當(dāng)t=1時(shí)，熱量開始傳導(dǎo)，對(duì)立種子S1、S2共同影響節(jié)點(diǎn)u1、u2、u3。根據(jù)2.3節(jié)的隨機(jī)規(guī)則，考慮節(jié)點(diǎn)u1、u3被信息B激活以及節(jié)點(diǎn)u2被信息A激活的情況（對(duì)應(yīng)圖2（b）至圖2（d））；當(dāng)t=2時(shí)，節(jié)點(diǎn)u4接收節(jié)點(diǎn)u1、u3共同傳導(dǎo)的熱量，根據(jù)式（6），f（u4）=0.3。傳播結(jié)束，根據(jù)熱量閾值，信息A對(duì)應(yīng)的激活節(jié)點(diǎn)數(shù)量為2，信息B對(duì)應(yīng)的激活節(jié)點(diǎn)數(shù)量為4。

3 預(yù)選式貪心近似算法

根據(jù)2.2 節(jié)，熱量值和激活閾值是多源熱量模型傳播機(jī)制的重要組成部分，該部分信息可用于統(tǒng)計(jì)個(gè)體的傳播收益，本章基于多源熱量模型對(duì)個(gè)體影響力的評(píng)價(jià)特性及目標(biāo)優(yōu)化函數(shù)的子模特性，設(shè)計(jì)了預(yù)選式貪心近似（Pre-Selected Greedy Approximation，PSGA）算法。該算法對(duì)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)賦予0～1 隨機(jī)值，將隨機(jī)值大于攔截值r、出度值大于平均出度值的節(jié)點(diǎn)加入臨時(shí)種子集S，且該臨時(shí)集的長度不能大于k。在M次的迭代過程中，根據(jù)式（6）和隨機(jī)規(guī)則，統(tǒng)計(jì)第m次迭代的臨時(shí)種子集Sm中全部個(gè)體的影響收益，迭代結(jié)束后將其收益值降序排列，取Top-k節(jié)點(diǎn)作為種子。

對(duì)于有向的社會(huì)網(wǎng)絡(luò)圖G，選擇節(jié)點(diǎn)出度及出度均值作為PSGA 算法關(guān)鍵指標(biāo)的理由如下：在有限的傳播步長內(nèi)，熱量和影響總是沿有向路徑向外傳遞和擴(kuò)散，因此節(jié)點(diǎn)的出度值可概括其傳播能力。其次，度方法的同一度量值存在若干節(jié)點(diǎn)與其對(duì)應(yīng)，眾多具有相同度量值的節(jié)點(diǎn)被確定為種子時(shí)其順序相對(duì)隨機(jī)，存在高影響力節(jié)點(diǎn)被排除的可能。PSGA算法的隨機(jī)策略可避免該缺陷，并減少計(jì)算量。算法1 給出了PSGA算法的運(yùn)行步驟。

在算法1中，u.degree表示節(jié)點(diǎn)u出度值，avgD（G）表示圖G中節(jié)點(diǎn)的出度均值，I（u）表示節(jié)點(diǎn)u的傳播收益，SM表示第M次迭代的臨時(shí)種子集，getSize（）函數(shù)用于獲取臨時(shí)種子集Sm的寬度。其中，第2）～7）行含義為：對(duì)于每個(gè)節(jié)點(diǎn)進(jìn)行判斷，將滿足條件的節(jié)點(diǎn)加入臨時(shí)種子集，作為種子候選。

算法1 預(yù)選式貪心近似算法。

4 仿真結(jié)果及分析

4.1 網(wǎng)絡(luò)數(shù)據(jù)集

表1列舉了仿真實(shí)驗(yàn)所需的四組網(wǎng)絡(luò)數(shù)據(jù)，n表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量，m表示邊的數(shù)量，＜c＞表示網(wǎng)絡(luò)的平均聚類系數(shù)，type表示網(wǎng)絡(luò)類型。表1中：p2p-Gnutella08 和CA-HepTH 網(wǎng)絡(luò)是SNAP的開源數(shù)據(jù)集，分別表示分布式協(xié)議交互網(wǎng)絡(luò)和維基百科的管理員投票網(wǎng)絡(luò)。twitter 數(shù)據(jù)集通過編程爬取自twitter社交平臺(tái)，記錄的是用戶間的互粉關(guān)系。TecentWeibo 爬取自騰訊微博，該數(shù)據(jù)記錄的是朋友間的關(guān)注關(guān)系。

表1 實(shí)驗(yàn)網(wǎng)絡(luò)基本特征Tab.2 Basic characteristic of experimental networks

4.2 仿真實(shí)驗(yàn)條件

本節(jié)介紹仿真實(shí)驗(yàn)的對(duì)比算法、算法特點(diǎn)、實(shí)驗(yàn)參數(shù)和評(píng)價(jià)方法。

仿真實(shí)驗(yàn)采用C++語言編寫，在內(nèi)存為16 GB 的個(gè)人工作站上運(yùn)行。實(shí)驗(yàn)選取局部中心性（Local Centrality，LC）［13］、SIR（Susceptible Infected Recovered）評(píng)價(jià)方法、k-shell［14］方法、基于局部集體影響的自適應(yīng)排序（Local Collective Influence Rank-Adaptive Recalculation，LCIR-AR）算法［15］、局部三角中心性（Local Triangle Centrality，LTC）方法［16］、密度中心性（Density Centrality，DC）方法［17］同PSGA 算法對(duì)比。LC、kshell、LCIR-AR 及LTC 均屬于依賴網(wǎng)絡(luò)拓?fù)涮匦缘膯l(fā)式算法，SIR 評(píng)價(jià)屬于模型評(píng)價(jià)方法。SIR 評(píng)價(jià)方法利用傳染病模型計(jì)算個(gè)體的影響值F（t），每個(gè)節(jié)點(diǎn)的F（t）均為重復(fù)運(yùn)行103次的均值。其中，twitter 和TecentWeibo 網(wǎng)絡(luò)數(shù)據(jù)因節(jié)點(diǎn)數(shù)量較多，分別重復(fù)運(yùn)行100 次及50 次。SIR 模型設(shè)定傳染概率為0.015，傳播步長為10，治愈概率為1/k，k為網(wǎng)絡(luò)節(jié)點(diǎn)度的均值。傳播步長設(shè)定太短會(huì)抑制部分節(jié)點(diǎn)的傳播能力，導(dǎo)致傳播停止的時(shí)刻提前，傳播步長參數(shù)對(duì)應(yīng)的值較高，可以反映出節(jié)點(diǎn)的真實(shí)傳播能力。SIR 模型相關(guān)參數(shù)的設(shè)定是復(fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)文獻(xiàn)較為常見的設(shè)置辦法，該方法也常用于節(jié)點(diǎn)重要性的評(píng)估領(lǐng)域，例如本文所對(duì)比的文獻(xiàn)［13，16］。實(shí)驗(yàn)設(shè)定LCIR-AR 算法的控制參數(shù)為0.3，度量層級(jí)為3，根據(jù)對(duì)比文獻(xiàn)［15］的描述，此時(shí)該參數(shù)對(duì)應(yīng)的實(shí)驗(yàn)效果最佳。PSGA算法的攔截值r設(shè)為0.85，迭代次數(shù)M設(shè)為104。

以A、B兩種對(duì)立信息為例，設(shè)100個(gè)由隨機(jī)選拔得到的A種子已知。為了滿足實(shí)驗(yàn)的公平性，MSHD 模型的傳播步長同SIR 評(píng)價(jià)模型的傳播步長均為10。MSHD 模型初始熱量值100，激活閾值0.5，導(dǎo)熱系數(shù)0.15。B信息的種子個(gè)數(shù)自0 至50 以2 為間隔，逐批投放。其中，B種子仿真收益的計(jì)算公式等于B種子收益同A種子收益的差。當(dāng)信息A的種子集SA和信息B的種子集SB存在相同節(jié)點(diǎn)，即SA∩SB≠?時(shí)，采用拋硬幣式隨機(jī)規(guī)則處理該沖突。因所采用的沖突處理辦法具有隨機(jī)性，最終仿真收益均為重復(fù)運(yùn)行104次的均值。評(píng)價(jià)對(duì)立影響最大化算法的優(yōu)劣，從運(yùn)行時(shí)長及影響收益兩方面判斷。運(yùn)行時(shí)長短，影響收益高，則算法更優(yōu)。

4.3 仿真結(jié)果及分析

圖3描述的是7種算法在四組網(wǎng)絡(luò)數(shù)據(jù)集的收益表現(xiàn)，其縱坐標(biāo)影響收益值被歸一化處理，橫坐標(biāo)表示種子數(shù)量。

圖3 7種算法的仿真收益比較Fig.3 Simulated revenue comparison of seven algorithms

根據(jù)圖3 仿真結(jié)果，PSGA 算法隨著種子投放數(shù)量的增加，其影響收益漲幅十分明顯。twitter 數(shù)據(jù)集種子數(shù)量小于8以及TecentWeibo 數(shù)據(jù)集種子數(shù)量小于14時(shí)，PSGA 算法的優(yōu)勢不夠明顯，但整體上PSGA 所獲得的收益最高。尤其是在p2p-Guntella08 和CA-HepTH 數(shù)據(jù)集中，PSGA 算法表現(xiàn)最優(yōu)?？梢哉J(rèn)為，在對(duì)立影響最大化問題中，種子投放數(shù)量越多，PSGA 算法越能體現(xiàn)出優(yōu)越性。SIR 模型作為復(fù)雜網(wǎng)絡(luò)度量單體影響力的評(píng)價(jià)標(biāo)準(zhǔn)，在解決對(duì)立影響最大化問題中的表現(xiàn)遜于PSGA 算法。密度中心性（DC）方法在所對(duì)比的啟發(fā)式算法中表現(xiàn)最優(yōu)，但其整體表現(xiàn)仍無法超過PSGA 算法。LC、LTC、LCIR-AR 及k-shell 方法在四組數(shù)據(jù)集中的收益排名并不穩(wěn)定，說明在不同規(guī)模和不同類型的網(wǎng)絡(luò)中，其適用性有限。以k-shell方法對(duì)TecentWeibo 網(wǎng)絡(luò)數(shù)據(jù)的度量結(jié)果為例，k值為57 的個(gè)體有759 個(gè)，自759 個(gè)節(jié)點(diǎn)中選拔50 個(gè)作為種子，其次序相對(duì)隨機(jī)。因此，k-shell方法度量值區(qū)分度不高是其影響收益較低的關(guān)鍵因素。LTC 方法統(tǒng)計(jì)節(jié)點(diǎn)所處拓?fù)浣Y(jié)構(gòu)的三元閉包數(shù)量，在有向圖中其表達(dá)的含義為節(jié)點(diǎn)經(jīng)有向路徑指向自己的回路數(shù)量，在無向圖中，其表達(dá)含義為節(jié)點(diǎn)與緊鄰個(gè)體的緊密程度?？梢哉J(rèn)為，針對(duì)對(duì)立影響最大化問題，三元閉包的統(tǒng)計(jì)量無法高效地反映節(jié)點(diǎn)潛在的博弈和競爭能力。

為直觀表達(dá)不同算法的影響收益水平，圖4 給出了各方法的平均收益。根據(jù)圖4 的仿真結(jié)果，在四組數(shù)據(jù)集中，PSGA 算法的平均收益最多，DC算法表現(xiàn)次優(yōu)，其他算法的表現(xiàn)則不夠穩(wěn)定。

圖5 給出了仿真實(shí)驗(yàn)每運(yùn)行104次的平均時(shí)間。為統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的F（t）值，SIR 模型在四個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間均超過3.5×105s（4 d），TecentWeibo 網(wǎng)絡(luò)數(shù)據(jù)的運(yùn)行時(shí)間超過1.8×106s（20 d），其平均時(shí)長在圖中沒有標(biāo)注。根據(jù)圖5統(tǒng)計(jì)結(jié)果，整體上DC 算法的平均運(yùn)行時(shí)間最短，在所對(duì)比的啟發(fā)式算法中，LC 算法的運(yùn)行時(shí)間較長。根據(jù)4.2 節(jié)對(duì)立影響最大化的兩項(xiàng)評(píng)價(jià)指標(biāo)，PSGA 算法同SIR 評(píng)價(jià)方法相比，影響收益高、運(yùn)行時(shí)長短，具有優(yōu)越性。同其他啟發(fā)式算法相比，PSGA算法雖耗時(shí)更久，但平均收益領(lǐng)先于啟發(fā)式算法?？梢哉J(rèn)為，PSGA算法能夠有效求解對(duì)立影響最大化問題。

圖4 7種算法的平均收益比較Fig.4 Average revenue comparison of seven algorithms

圖5 7種算法的運(yùn)行時(shí)間比較Fig.5 Running time comparison of seven algorithms

4.4 種子富集性分析

為進(jìn)一步分析各算法的仿真收益表現(xiàn)，設(shè)計(jì)了種子富集性實(shí)驗(yàn)，探究各算法所選種子集的特征。種子富集性（richclub）也稱富人俱樂部現(xiàn)象，它描述的是關(guān)鍵節(jié)點(diǎn)間邊的密集情況。種子節(jié)點(diǎn)間連接緊密，則不利于影響力的擴(kuò)散；種子節(jié)點(diǎn)間連接稀疏，則有利于初期快速地?cái)U(kuò)散影響。以圖6（a）的簡單網(wǎng)絡(luò)為例，該網(wǎng)絡(luò)中被對(duì)立信息A激活的節(jié)點(diǎn)已知。當(dāng)B種子以圖6（b）的方式投放，種子節(jié)點(diǎn)相互抱團(tuán)，處于網(wǎng)絡(luò)邊緣的種子無法對(duì)傳播起到促進(jìn)作用。當(dāng)B種子以圖6（c）的方式投放，則有利于初期的影響傳播。圖6（b）中B信息種子間邊的數(shù)目為7，圖6（c）中B種子間邊的數(shù)目為0?？梢哉J(rèn)為種子節(jié)點(diǎn)間邊的數(shù)量能夠反映出種子集的富集程度。

根據(jù)上述分析，本節(jié)設(shè)計(jì)了種子富集性實(shí)驗(yàn)。實(shí)驗(yàn)首先讀取社交網(wǎng)絡(luò)圖G=（V，E），輸入某方法選拔出的k個(gè)關(guān)鍵節(jié)點(diǎn)，針對(duì)E中每條邊ei，j∈E作如下判斷：若圖G中的邊ei，j所連接的節(jié)點(diǎn)均為關(guān)鍵節(jié)點(diǎn)，則對(duì)該條邊添加標(biāo)記。最后統(tǒng)計(jì)該方法的標(biāo)記數(shù)量。其中，CA-HepTH 網(wǎng)絡(luò)添加了預(yù)處理過程，刪掉了個(gè)體指向自身的12 條回環(huán)邊。圖7 是種子富集性的實(shí)驗(yàn)結(jié)果。

圖6 種子富集性示例Fig.6 Diagram of seed enrichment degree

根據(jù)圖7的實(shí)驗(yàn)結(jié)果，整體上SIR評(píng)價(jià)模型的種子富集性最為稀疏，PSGA 算法其次。LC 算法在有向圖中的富集性程度高，即種子間的連接較為緊密，在無向圖中其富集程度較弱，即種子間的連接較為稀疏，DC、k-shell 和LCIR-AR 算法則與之相反。啟發(fā)式算法依靠網(wǎng)絡(luò)局部拓?fù)涮匦?，SIR 和PSGA依靠各自模型傳播機(jī)制評(píng)價(jià)節(jié)點(diǎn)的重要性，因此在種子富集性方面具有優(yōu)勢。

圖7 種子富集性實(shí)驗(yàn)結(jié)果Fig.7 Experimental results of seed enrichment degree

5 結(jié)語

針對(duì)信息的對(duì)立傳播情形，本文研究對(duì)立信息傳播的影響力最大化問題。研究分析了對(duì)立信息的傳播機(jī)制，設(shè)計(jì)了多源熱量傳播模型以及用于處理傳播沖突的隨機(jī)處理辦法。實(shí)驗(yàn)結(jié)果表明，本文所設(shè)計(jì)的PSGA 算法能夠有效求解對(duì)立影響最大化問題，且在種子富集性的指標(biāo)上占據(jù)優(yōu)勢。然而，PSGA算法存在時(shí)間復(fù)雜度較高的問題，未來將針對(duì)算法運(yùn)行效率加以改進(jìn)，使其合理適用于規(guī)模較大的社交網(wǎng)絡(luò)數(shù)據(jù)集。