影響最大化問題中基于K-truss 的投票改進算法

孫飛翔，陳衛東，林天森

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

0 概述

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

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

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

1 相關工作

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

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

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

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

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

2 本文算法

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

2.1 K-truss 分解

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

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

定義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 相關理論，不僅考慮網絡的拓撲結構對投票能力產生的影響，同時有效地區分節點對其不同鄰居擁有不同的投票傾向。對于邊e=（v，u），tvu的計算與v和u的公共鄰居相關，因此邊的truss 值在一定程度上反映了節點間聯系的緊密程度。對于同一節點的不同鄰居，鄰邊的truss 值越大，其兩端節點的聯系越緊密。無向圖示例如圖1 所示。

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

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

2.2 有效投票能力

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

2.3 得票分數

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

2.4 衰減因子

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

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

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

2.5 復雜度分析

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

算法1TrussVote 算法

3 實驗設計

本文所有的算法均使用Python 語言來實現。運行環境為Windows10 操作系統，內存8 GB，處理器Intel?CoreTMi7-7700 CPU @3.60 GHz。

3.1 數據集

本文實驗選用4 個不同規模的真實網絡數據集，數據集的統計特征如表2 所示，其中pc表示網絡的傳播閾值［25］。

表2 數據集的統計特征Table 2 Statistics characteristic of datasets

3.2 對比算法

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

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

3.3 實驗設置與評價指標

本文在4 個不同規模的真實網絡數據集上，使用IC 模型［4］和SIR 模型［26］對不同算法進行對比實驗。

3.3.1 IC 模型

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

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

3.3.2 SIR 模型

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

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

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

4 實驗結果分析

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

4.1 IC 模型下的結果分析

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

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

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

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

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

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

4.2 SIR 模型下的結果與分析

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

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

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

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

因此，相比基于中心的算法，TrussVote 在不增大時間復雜度的同時取得了更穩定且有效的實驗效果。當迭代輪次較多時，RNR 和IM-ELPR 在較大網絡規模中的時間和影響范圍相比TrussVote 較差。另外，與VoteRank++更新節點兩跳之內的鄰居投票能力不同，TrussVote 在更新階段對節點一跳之內的鄰居投票能力賦予了不同程度的更新，不僅具有更低的時間復雜度，同時也能夠獲得擁有更大影響范圍的種子集合。以上實驗結果也驗證了TrussVote算法的正確性及有效性。

5 結束語

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