影響最大化問(wèn)題中基于K-truss 的投票改進(jìn)算法

孫飛翔，陳衛(wèi)東，林天森

（華南師范大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510631）

0 概述

隨著微信、Facebook 和Twitter 等在線社交網(wǎng)絡(luò)的興起，越來(lái)越多的人們使用不同的社交網(wǎng)絡(luò)進(jìn)行交流和分享，使得網(wǎng)絡(luò)中信息擴(kuò)散研究成為社交網(wǎng)絡(luò)分析的熱點(diǎn)。影響最大化（Influence Maximization，IM）作為信息擴(kuò)散研究中的關(guān)鍵問(wèn)題，具有較廣泛的應(yīng)用場(chǎng)景。文獻(xiàn)［1-3］分別把IM 問(wèn)題應(yīng)用于病毒式營(yíng)銷、謠言控制和社會(huì)計(jì)算領(lǐng)域，將社交網(wǎng)絡(luò)建模為一個(gè)圖G，并給圖G的每條邊分配一個(gè)傳播概率。IM 問(wèn)題是給定一個(gè)傳播模型及正整數(shù)k，從節(jié)點(diǎn)集V中選擇一個(gè)不多于k個(gè)節(jié)點(diǎn)的種子集合S，使得S的影響范圍σ(S)達(dá)到最大。

文獻(xiàn)［4］證明IM 問(wèn)題也是NP-hard 問(wèn)題，表明IM問(wèn)題在多項(xiàng)式時(shí)間內(nèi)不可能得到最優(yōu)解的精確算法，其求解方法主要是近似算法和啟發(fā)式算法。文獻(xiàn)［5-6］針對(duì)IM 問(wèn)題，提出基于次模函數(shù)的貪心近似算法，具有較大的時(shí)間復(fù)雜度，因此，該算法在規(guī)模較大的圖上難以得到實(shí)際有效的應(yīng)用。以上貪心近似算法均具有較大的時(shí)間復(fù)雜度，其原因?yàn)樵诠?jié)點(diǎn)選擇過(guò)程中，每個(gè)種子節(jié)點(diǎn)的選擇均使用大量的Monte-Carlo 模擬來(lái)計(jì)算節(jié)點(diǎn)集的影響范圍。為了更快地求解IM 問(wèn)題，啟發(fā)式算法利用不同的策略來(lái)代替模擬過(guò)程。此類算法分為基于中心性的算法、基于社區(qū)的算法和基于排序的算法。啟發(fā)式算法與近似算法相比具有較低的時(shí)間復(fù)雜度，但是在具有不同拓?fù)浣Y(jié)構(gòu)的圖上，啟發(fā)式算法和近似算法都缺乏穩(wěn)定性。文獻(xiàn)［7］提出基于VoteRank的投票算法，在求解IM 問(wèn)題時(shí)具有較強(qiáng)的穩(wěn)定性。在該類算法中，節(jié)點(diǎn)v具有投票能力vav和得票分?jǐn)?shù)vsv兩種屬性，其中vav表示節(jié)點(diǎn)v能夠給鄰居節(jié)點(diǎn)投票的票數(shù)，vsv表示節(jié)點(diǎn)v的鄰居給其投票的票數(shù)總和。此外，在每輪投票中得票分?jǐn)?shù)最高的節(jié)點(diǎn)將不參與后續(xù)的投票，即投票能力為0，其鄰居節(jié)點(diǎn)的投票能力也會(huì)隨之得到一定程度的弱化。投票算法通常定義一個(gè)衰減因子f來(lái)表示投票能力的弱化程度。然而該算法并未有效地區(qū)分節(jié)點(diǎn)對(duì)其不同鄰居的投票能力，種子節(jié)點(diǎn)所有的鄰居均使用相同的衰減因子，不能有效地表示出它們投票能力的弱化程度。

本文基于K-truss 提出一種改進(jìn)的投票算法TrussVote，用于求解IM 問(wèn)題?；谶叺膖russ 值設(shè)計(jì)節(jié)點(diǎn)有效投票能力的計(jì)算方法，該方法不僅考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)投票能力的影響，同時(shí)也有效地區(qū)分節(jié)點(diǎn)對(duì)其不同鄰居的投票能力?；诠?jié)點(diǎn)的相似性提出動(dòng)態(tài)的衰減因子，表示節(jié)點(diǎn)鄰居的投票能力具有不同程度的弱化。此外，本文結(jié)合IC 模型下的原始傳播結(jié)果提出影響范圍的等價(jià)分析指標(biāo)——傳播差異（Diffusion Difference，DD），以直觀地區(qū)分各個(gè)算法的實(shí)驗(yàn)效果。

1 相關(guān)工作

為了表述方便，表1 所示為本文所需主要變量的說(shuō)明。

表1 重要變量的說(shuō)明Table 1 The description of important variables

網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性是衡量節(jié)點(diǎn)重要性的關(guān)鍵指標(biāo)，中心性較高的節(jié)點(diǎn)在網(wǎng)絡(luò)中通常占據(jù)著信息傳播的關(guān)鍵位置。節(jié)點(diǎn)的中心性分為局部中心性和全局中心性。文獻(xiàn)［8-10］和文獻(xiàn)［11-12］分別基于局部中心性和全局中心性提出不同的啟發(fā)式算法，以求解IM 問(wèn)題。此類算法的主要原理是在計(jì)算每個(gè)節(jié)點(diǎn)的中心性之后，選擇中心性最高的前k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)集。相比基于局部中心性的啟發(fā)式算法，基于全局中心性的啟發(fā)式算法在獲得較優(yōu)實(shí)驗(yàn)效果的同時(shí)提高了算法的時(shí)間復(fù)雜度。

影響力的擴(kuò)散與社區(qū)結(jié)構(gòu)有著密切關(guān)聯(lián)，并且在社區(qū)內(nèi)節(jié)點(diǎn)之間聯(lián)系緊密，更容易傳播影響力。文獻(xiàn)［13-14］基于圖的社區(qū)提出用于求解IM 問(wèn)題的方法，其原理是將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為不同的社區(qū)，并在每個(gè)社區(qū)中選取影響力較大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。文獻(xiàn)［15-16］提出基于排序的算法，采用不同方式定義節(jié)點(diǎn)的影響力，通過(guò)迭代方式使節(jié)點(diǎn)按照影響力的排序達(dá)到一個(gè)穩(wěn)定狀態(tài)。該類算法與基于中心性的算法相比能夠獲得更廣泛的影響力覆蓋范圍，但迭代次數(shù)的增加也提升了算法的時(shí)間復(fù)雜度。

文獻(xiàn)［7］提出一種新的解決方案用來(lái)求解IM 問(wèn)題，它最早基于投票機(jī)制提出VoteRank 算法。在初始化階段，每個(gè)節(jié)點(diǎn)的投票能力均被設(shè)置為1，在投票過(guò)程中，每輪選出一個(gè)得票分?jǐn)?shù)最高的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，在此基礎(chǔ)上，使用固定的衰減因子弱化該種子節(jié)點(diǎn)一跳鄰居的投票能力。當(dāng)權(quán)重表示節(jié)點(diǎn)間聯(lián)系緊密性的加權(quán)網(wǎng)絡(luò)時(shí)，文獻(xiàn)［17］基于VoteRank提出WVoteRank 算法，在計(jì)算節(jié)點(diǎn)的得票分?jǐn)?shù)時(shí)，權(quán)重的差異使得節(jié)點(diǎn)對(duì)其不同鄰居的投票能力產(chǎn)生差異。文獻(xiàn)［18］設(shè)計(jì)的NCVoteRank 算法認(rèn)為節(jié)點(diǎn)的投票能力取決于其在網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)，并提出鄰居核心值（Neighborhood Coreness，NC）的概念，當(dāng)計(jì)算節(jié)點(diǎn)的得票分?jǐn)?shù)時(shí)，綜合考慮了鄰居節(jié)點(diǎn)的NC 值及投票能力。文獻(xiàn)［19］提出EnRenew 算法，采用信息熵的方式來(lái)表示節(jié)點(diǎn)的重要性及投票能力。文獻(xiàn)［20］不僅引入投票比例的概念以區(qū)分節(jié)點(diǎn)對(duì)其不同鄰居的投票能力，而且在更新種子節(jié)點(diǎn)鄰居的投票能力時(shí)，采用不同程度的衰減因子分別弱化其一跳和二跳鄰居的投票能力。

2 本文算法

本文基于第1節(jié)中的投票機(jī)制提出TrussVote算法，該算法在投票階段使用K-truss的相關(guān)理論及算法區(qū)分節(jié)點(diǎn)對(duì)其不同鄰居的投票能力，在更新階段通過(guò)節(jié)點(diǎn)相似性指標(biāo)定義一個(gè)動(dòng)態(tài)的衰減因子，用于表示種子節(jié)點(diǎn)鄰居的投票能力具有不同程度的衰減。

2.1 K-truss 分解

K-core［21］揭示了網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)和層次性質(zhì)，而K-truss 則是K-core 基于三角形的一種擴(kuò)展，它所推導(dǎo)的子圖在結(jié)構(gòu)上更接近一個(gè)團(tuán)［22］。

定義1（邊的支持度sup（e，G））邊的支持度等于圖G=（V，E）中邊e∈E所在三角形的個(gè)數(shù)。

定義2（K-truss 子圖TK）若滿足K≥2，?e∈且sup（e，G）≥K-2，則稱TK為G的K-truss子圖。

定義3（邊e=（v，u）的truss 值tvu）tvu=max｛K：e∈，TK為圖G的K-truss 子圖｝。

定義4（邊集K-class，記為ΦK）圖G=（V，E）的ΦK={e=(v，u)|e∈E，tvu=K}。

本文的投票算法通過(guò)引入K-truss 相關(guān)理論，不僅考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)投票能力產(chǎn)生的影響，同時(shí)有效地區(qū)分節(jié)點(diǎn)對(duì)其不同鄰居擁有不同的投票傾向。對(duì)于邊e=（v，u），tvu的計(jì)算與v和u的公共鄰居相關(guān)，因此邊的truss 值在一定程度上反映了節(jié)點(diǎn)間聯(lián)系的緊密程度。對(duì)于同一節(jié)點(diǎn)的不同鄰居，鄰邊的truss 值越大，其兩端節(jié)點(diǎn)的聯(lián)系越緊密。無(wú)向圖示例如圖1 所示。

圖1 無(wú)向圖示例Fig.1 The example of undirected graph

在節(jié)點(diǎn)3 的鄰邊中，邊（3，4）具有最大的truss 值，它們的聯(lián)系也更加緊密?；诰W(wǎng)絡(luò)的核分解理論［23］，K-truss 分解與K-core 分解相似，K值越大的子圖在網(wǎng)絡(luò)中的相對(duì)位置越趨于核心。對(duì)于網(wǎng)絡(luò)中不同位置的節(jié)點(diǎn)，truss 值可以對(duì)節(jié)點(diǎn)的投票能力進(jìn)行有針對(duì)性和不同程度的放大。從圖1 可以看出，Φ3和Φ1中的邊對(duì)它們兩端節(jié)點(diǎn)投票能力的放大程度不同，在同一輪投票中趨于中心位置的節(jié)點(diǎn)將會(huì)獲得更高的得票分?jǐn)?shù)。

2.2 有效投票能力

節(jié)點(diǎn)間相似性差異會(huì)導(dǎo)致節(jié)點(diǎn)對(duì)其鄰居的投票能力不同。為了更準(zhǔn)確地表示這種差異，本文基于邊的truss 值提出有效投票能力，用于計(jì)算節(jié)點(diǎn)v對(duì)其鄰居節(jié)點(diǎn)u∈Nv的投票能力。當(dāng)不考慮節(jié)點(diǎn)間的相似性時(shí)，節(jié)點(diǎn)v給其每個(gè)鄰居投票的概率均為1/dv；當(dāng)考慮節(jié)點(diǎn)間的相似性時(shí)，本文基于邊的truss值定義了節(jié)點(diǎn)v對(duì)其鄰居節(jié)點(diǎn)u∈Nv的有效投票能力，其計(jì)算過(guò)程如式（1）所示：

2.3 得票分?jǐn)?shù)

本文在計(jì)算節(jié)點(diǎn)的得票分?jǐn)?shù)時(shí)，利用有效投票能力來(lái)表示節(jié)點(diǎn)對(duì)其鄰居擁有不同的投票票數(shù)，而這種有效的投票能力也會(huì)受到邊的傳播概率的影響。在實(shí)際傳播過(guò)程中，節(jié)點(diǎn)v通過(guò)邊（v，u）將u激活，其激活概率大于該邊的傳播概率。因此，基于傳播模型的隨機(jī)性特點(diǎn)，本文將投票算法中能夠得到的有效投票能力乘以傳播概率，用來(lái)表示u能夠獲得v投票的票數(shù)期望值。對(duì)于節(jié)點(diǎn)表示能夠得到其鄰居節(jié)點(diǎn)u∈Nv的實(shí)際票數(shù)，其中puv為邊（u，v）的傳播概率。與其他投票算法相似，本文節(jié)點(diǎn)v的得票分?jǐn)?shù)來(lái)源于鄰居節(jié)點(diǎn)的投票，其計(jì)算過(guò)程如式（2）所示：

2.4 衰減因子

本文基于ra 指標(biāo)［24］提出一種動(dòng)態(tài)的衰減因子，以區(qū)分種子節(jié)點(diǎn)不同鄰居的衰減情況。ra 指標(biāo)是一種基于資源分配策略的節(jié)點(diǎn)相似性指標(biāo)，ra（v，u）表示節(jié)點(diǎn)v、u之間的相似度，也表示v接收到u資源的能力。其計(jì)算過(guò)程如式（3）所示：

當(dāng)節(jié)點(diǎn)v被選為種子節(jié)點(diǎn)后，其鄰居節(jié)點(diǎn)u∈Nv需去除來(lái)自v的資源，本文將減去的這部分視為節(jié)點(diǎn)u投票能力的衰減程度f(wàn)u，其計(jì)算過(guò)程如式（4）所示：

當(dāng)節(jié)點(diǎn)v被選為種子節(jié)點(diǎn)后，其鄰居節(jié)點(diǎn)u∈Nv的投票能力可根據(jù)式（5）計(jì)算：

2.5 復(fù)雜度分析

TrussVote 的算法過(guò)程：首先，在初始化階段，計(jì)算所有邊的truss 值，并且給每個(gè)節(jié)點(diǎn)都賦予相同的初始投票能力；然后，重復(fù)k輪投票，每次均將投票分?jǐn)?shù)最高的節(jié)點(diǎn)選為種子節(jié)點(diǎn)，并使用動(dòng)態(tài)的衰減因子更新其鄰居節(jié)點(diǎn)的投票能力。TrussVote 如算法1所示。

算法1TrussVote 算法

3 實(shí)驗(yàn)設(shè)計(jì)

本文所有的算法均使用Python 語(yǔ)言來(lái)實(shí)現(xiàn)。運(yùn)行環(huán)境為Windows10 操作系統(tǒng)，內(nèi)存8 GB，處理器Intel?CoreTMi7-7700 CPU @3.60 GHz。

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

本文實(shí)驗(yàn)選用4 個(gè)不同規(guī)模的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，數(shù)據(jù)集的統(tǒng)計(jì)特征如表2 所示，其中pc表示網(wǎng)絡(luò)的傳播閾值［25］。

表2 數(shù)據(jù)集的統(tǒng)計(jì)特征Table 2 Statistics characteristic of datasets

3.2 對(duì)比算法

為驗(yàn)證本文算法的性能，本文將其與當(dāng)前具有代表性的啟發(fā)式算法進(jìn)行對(duì)比。不同算法的時(shí)間復(fù)雜度對(duì)比如表3 所示。

表3 不同算法的時(shí)間復(fù)雜度對(duì)比Table 3 Time complexity comparison among different algorithms

3.3 實(shí)驗(yàn)設(shè)置與評(píng)價(jià)指標(biāo)

本文在4 個(gè)不同規(guī)模的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上，使用IC 模型［4］和SIR 模型［26］對(duì)不同算法進(jìn)行對(duì)比實(shí)驗(yàn)。

3.3.1 IC 模型

在IM 問(wèn)題中，IC 模型是一種應(yīng)用最為廣泛的影響力傳播模型。在IC 模擬傳播過(guò)程中，每個(gè)數(shù)據(jù)集使用pc作為傳播概率，并且每次選擇50 個(gè)節(jié)點(diǎn)作為初始傳播源的種子集合。在IC 模型下的影響范圍即種子節(jié)點(diǎn)影響擴(kuò)散的個(gè)數(shù)，并將其作為算法的主要評(píng)價(jià)指標(biāo)。由于IC模型的傳播具有隨機(jī)性，因此本文使用10 000次的Monte-Carlo 模擬來(lái)保證實(shí)驗(yàn)?zāi)軌虻玫捷^為精確的影響范圍。但是多數(shù)算法在IC 模型下的影響范圍比較接近，并且當(dāng)k值不同時(shí)，不同算法的表現(xiàn)也會(huì)上下浮動(dòng)。為了便于分析，本文給出一個(gè)等價(jià)的分析指標(biāo)——傳播差異。算法a1和a2在k=x時(shí)的傳播差異如式（6）所示：

其中：σa(Sk)表示算法a選取大小為k的種子集Sk所達(dá)到的影響范圍。

3.3.2 SIR 模型

SIR模型是一種經(jīng)典的病毒傳播模型，近年來(lái)在IM問(wèn)題中得到了廣泛的應(yīng)用。在SIR 模型中，每個(gè)節(jié)點(diǎn)具有易感S、感染I和治愈R 這3種狀態(tài)。節(jié)點(diǎn)由易感S到感染I 的狀態(tài)轉(zhuǎn)換稱為感染，感染率為μ；節(jié)點(diǎn)由感染I 到治愈R 的狀態(tài)轉(zhuǎn)換稱為治愈，治愈率為β。該模型下算法的評(píng)價(jià)指標(biāo)有2 個(gè)，第1 個(gè)是當(dāng)給定初始感染比例時(shí)對(duì)比算法在t時(shí)的感染規(guī)模F（t），計(jì)算過(guò)程如式（7）所示：

其中：nI（t）表示t時(shí)感染狀態(tài)的節(jié)點(diǎn)個(gè)數(shù)；nR（t）表示t時(shí)恢復(fù)狀態(tài)的節(jié)點(diǎn)個(gè)數(shù)。第2 個(gè)評(píng)價(jià)指標(biāo)是當(dāng)初始感染比例不同時(shí)，對(duì)比算法的最終感染規(guī)模F（tc），計(jì)算過(guò)程如式（8）所示：

在SIR 模型中，感染比例λ=μ/β對(duì)模型的傳播速度具有至關(guān)重要的作用，本文將其設(shè)置為1.5。感染率的選擇沒(méi)有固定標(biāo)準(zhǔn)［19］，一些算法根據(jù)邊的傳播概率來(lái)選取種子節(jié)點(diǎn)，而本文為了保證算法的有效性及統(tǒng)一性，將每個(gè)數(shù)據(jù)集的傳播閾值pc設(shè)置為感染率。

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

在解決IM 問(wèn)題的投票算法中，節(jié)點(diǎn)向其鄰居的投票可以被看作是一個(gè)局部信息的擴(kuò)散過(guò)程，當(dāng)每輪投票結(jié)束后均選擇信息量最高的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。投票算法通過(guò)信息擴(kuò)散最大化的方法來(lái)識(shí)別網(wǎng)絡(luò)中最有影響力的節(jié)點(diǎn)。因此，IM 問(wèn)題作為信息擴(kuò)散的核心及關(guān)鍵問(wèn)題，使用投票機(jī)制獲得較優(yōu)的實(shí)驗(yàn)效果。

4.1 IC 模型下的結(jié)果分析

本文將CCA 算法作為基準(zhǔn)算法來(lái)計(jì)算不同算法在各個(gè)數(shù)據(jù)集上的傳播差異。當(dāng)種子節(jié)點(diǎn)數(shù)k分別為10、20、30、40、50 時(shí)，CCA 算法在不同數(shù)據(jù)集上的傳播差異如表4 所示。

表4 CCA 算法的傳播差異Table 4 Diffusion difference of CCA algorithm

在不同數(shù)據(jù)集上各個(gè)算法使用IC 模型產(chǎn)生的傳播差異如圖2 所示。從圖2 可以看出，大多數(shù)算法在開(kāi)始時(shí)選擇的節(jié)點(diǎn)擁有類似的影響范圍，但隨著種子節(jié)點(diǎn)數(shù)的增大，算法的表現(xiàn)呈現(xiàn)出不同的特點(diǎn)。

圖2 IC 模型下不同算法的運(yùn)行結(jié)果Fig.2 The running results of different algorithms under IC model

在Email 數(shù)據(jù)集上，TrussVote 和VoteRank++具有類似的傳播特點(diǎn)，當(dāng)種子節(jié)點(diǎn)數(shù)較小時(shí)影響的范圍相較于其他算法小，但隨著種子節(jié)點(diǎn)數(shù)增大，影響范圍逐步增大并趨于穩(wěn)定。相比VoteRank++，TrussVote 在種子節(jié)點(diǎn)數(shù)較大時(shí)影響范圍最大。這種變化趨勢(shì)也說(shuō)明了TrussVote 在消除影響力重合時(shí)的作用更加顯著。在Hamster和CacondMat數(shù)據(jù)集上，TrussVote 與MCDE總體的變化趨勢(shì)接近，但TrussVote的表現(xiàn)更好，在Email和Brightkite數(shù)據(jù)集上，TrussVote具有較優(yōu)的實(shí)驗(yàn)結(jié)果。在CacondMat 數(shù)據(jù)集上，除CCA 算法以外，其他算法具有相似的傳播特點(diǎn)，影響范圍的變化情況都基本類似，而TrussVote 算法在k∈［1，50］的多數(shù)情況下能獲得最廣泛的影響范圍。

在Brightkite 數(shù)據(jù)集上，CCA 與DegreeDistance算法的表現(xiàn)較差，在其他數(shù)據(jù)集中的表現(xiàn)也有波動(dòng)。這說(shuō)明基于中心性的算法，在網(wǎng)絡(luò)特點(diǎn)不同的數(shù)據(jù)集中難以產(chǎn)生持續(xù)有效的實(shí)驗(yàn)效果。在Hamster 數(shù)據(jù)集上RNR 算法的表現(xiàn)說(shuō)明它在度數(shù)較大的數(shù)據(jù)集中，也不能有效解決富人俱樂(lè)部效應(yīng)。與投票類算法相似，隨著種子節(jié)點(diǎn)數(shù)增大，IM-ELPR 算法的影響范圍逐漸優(yōu)于其他算法，但TrussVote 與其相比，不僅時(shí)間復(fù)雜度更低，而且傳播效果也更好。在IC模型下不同算法的實(shí)驗(yàn)結(jié)果表明，TrussVote 算法具有更廣泛的影響范圍。

4.2 SIR 模型下的結(jié)果與分析

當(dāng)給定初始感染比例時(shí)，SIR 模型下不同算法的感染規(guī)模F（t）隨迭代輪次變化的結(jié)果如圖3 所示。當(dāng)初始感染節(jié)點(diǎn)數(shù)相同時(shí)，TrussVote 只在Hamster數(shù)據(jù)集上的峰值略低于MCDE，而在其他數(shù)據(jù)集上均達(dá)到峰值。TrussVote 選取的種子集能夠在最短的時(shí)間內(nèi)感染更多的節(jié)點(diǎn)，說(shuō)明TrussVote 具有更快的感染速度與更大的感染規(guī)模。

圖3 不同算法的感染規(guī)模隨迭代輪次的變化曲線Fig.3 Change curves of infection scale of different algorithms with iterations

各個(gè)算法的最終感染規(guī)模F（tc）隨初始感染比例增大的變化曲線如圖4所示。在Email和CacondMat數(shù)據(jù)集上，TrussVote 在初始感染比例較小的情況下最終感染規(guī)模略低于VoteRank++及IM-ELPR 算法，但隨著初始感染比例的增大，TrussVote擁有更大的感染規(guī)模。TrussVote 在Hamster 數(shù)據(jù)集上初始感染比例為2.65%時(shí)表現(xiàn)相對(duì)較差，但在Hamster 和Brightkite 數(shù)據(jù)集上，TrussVote 的最終感染規(guī)?？傮w最優(yōu)。這說(shuō)明TrussVote選取節(jié)點(diǎn)的策略及算法更新的過(guò)程都較為合理，具有較優(yōu)的穩(wěn)定性。在SIR 模型下不同算法的實(shí)驗(yàn)結(jié)果表明，TrussVote 不僅具有更快的感染速度及更大的感染規(guī)模，在不同初始感染比例下也擁有最好的表現(xiàn)。

圖4 不同算法的最終感染規(guī)模隨初始感染比例的變化曲線Fig.4 Change curves of final infection scale of different algorithms with initial infection ratio

因此，相比基于中心的算法，TrussVote 在不增大時(shí)間復(fù)雜度的同時(shí)取得了更穩(wěn)定且有效的實(shí)驗(yàn)效果。當(dāng)?shù)喆屋^多時(shí)，RNR 和IM-ELPR 在較大網(wǎng)絡(luò)規(guī)模中的時(shí)間和影響范圍相比TrussVote 較差。另外，與VoteRank++更新節(jié)點(diǎn)兩跳之內(nèi)的鄰居投票能力不同，TrussVote 在更新階段對(duì)節(jié)點(diǎn)一跳之內(nèi)的鄰居投票能力賦予了不同程度的更新，不僅具有更低的時(shí)間復(fù)雜度，同時(shí)也能夠獲得擁有更大影響范圍的種子集合。以上實(shí)驗(yàn)結(jié)果也驗(yàn)證了TrussVote算法的正確性及有效性。

5 結(jié)束語(yǔ)

針對(duì)社交網(wǎng)絡(luò)中的影響最大化問(wèn)題，本文提出基于K-truss 的投票改進(jìn)算法。在投票階段和更新階段分別引入邊的truss 值及節(jié)點(diǎn)相似性指標(biāo)對(duì)投票類算法進(jìn)行改進(jìn)，以區(qū)分更新節(jié)點(diǎn)鄰居的投票能力。在不同規(guī)模的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法在具有較低時(shí)間復(fù)雜度的同時(shí)，給IM 問(wèn)題提供了較有效的解決方案。下一步考慮將本文TrussVote 投票算法應(yīng)用到IM 的拓展問(wèn)題中，如利潤(rùn)最大化問(wèn)題，使其具有更優(yōu)的魯棒性。