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

（華南師范大學 計算機學院，廣州 510631）

0 概述

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

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

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

1 相關工作

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

表1 重要變量的說明Table 1 The description of important variables

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

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

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

2 本文算法

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

2.1 K-truss 分解

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

定義1（邊的支持度sup（e，G））邊的支持度等于圖G=（V，E）中邊e∈E所在三角形的個數(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}。

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

圖1 無向圖示例Fig.1 The example of undirected graph

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

2.2 有效投票能力

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

2.3 得票分數(shù)

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

2.4 衰減因子

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

當節(jié)點v被選為種子節(jié)點后，其鄰居節(jié)點u∈Nv需去除來自v的資源，本文將減去的這部分視為節(jié)點u投票能力的衰減程度fu，其計算過程如式（4）所示：

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

2.5 復雜度分析

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

算法1TrussVote 算法

3 實驗設計

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

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

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

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

3.2 對比算法

為驗證本文算法的性能，本文將其與當前具有代表性的啟發(fā)式算法進行對比。不同算法的時間復雜度對比如表3 所示。

表3 不同算法的時間復雜度對比Table 3 Time complexity comparison among different algorithms

3.3 實驗設置與評價指標

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

3.3.1 IC 模型

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

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

3.3.2 SIR 模型

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

其中：nI（t）表示t時感染狀態(tài)的節(jié)點個數(shù)；nR（t）表示t時恢復狀態(tài)的節(jié)點個數(shù)。第2 個評價指標是當初始感染比例不同時，對比算法的最終感染規(guī)模F（tc），計算過程如式（8）所示：

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

4 實驗結果分析

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

4.1 IC 模型下的結果分析

本文將CCA 算法作為基準算法來計算不同算法在各個數(shù)據(jù)集上的傳播差異。當種子節(jié)點數(shù)k分別為10、20、30、40、50 時，CCA 算法在不同數(shù)據(jù)集上的傳播差異如表4 所示。

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

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

圖2 IC 模型下不同算法的運行結果Fig.2 The running results of different algorithms under IC model

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

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

4.2 SIR 模型下的結果與分析

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

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

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

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

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

5 結束語

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