基于割點的社交網(wǎng)絡(luò)影響最大化問題

楊書新，宋建繽，梁 文

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

2.長春理工大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院，長春 130000

近年來，信息技術(shù)的飛速發(fā)展帶動了社交網(wǎng)絡(luò)服務(wù)業(yè)的發(fā)展，如Facebook、Twitter、新浪微博和豆瓣等。We Are Social 和Hootsuite 在《2020 全球數(shù)字報告》中指出，普通網(wǎng)民平均每天要花費大約7 h 在社交網(wǎng)絡(luò)上，社交媒體用戶數(shù)更是突破38 億。而微信這一個社交平臺，全球每月就有11.5 億用戶使用它進(jìn)行交互，產(chǎn)生了大量的信息。這些信息傳播的速度之快、范圍之廣，使得社交網(wǎng)絡(luò)上信息傳播問題越來越受到學(xué)者們的關(guān)注。社交網(wǎng)絡(luò)影響最大化問題作為信息傳播問題中的一個重要問題，它蘊含著巨大的商業(yè)價值，如個性營銷、謠言控制和鏈路預(yù)測等。

為了解決影響最大化問題，學(xué)者們給出了不少解決方案?，F(xiàn)有方案主要分為貪心式和啟發(fā)式兩大類。貪心式雖然擁有精度保證，但較低的時間效率使這類算法難以應(yīng)用于大規(guī)模網(wǎng)絡(luò)。相比貪心式，啟發(fā)式可以有效地解決時間效率低的問題，但現(xiàn)有的啟發(fā)式算法對網(wǎng)絡(luò)特征的挖掘不夠充分，沒有結(jié)合節(jié)點特征和結(jié)構(gòu)特征看待影響最大化問題。面臨時間效率低和網(wǎng)絡(luò)特征挖掘不夠充分的兩大問題，本文綜合考慮節(jié)點特征和社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，提出了CVIM（cut-vertex-based influence maximization）啟發(fā)式算法。本文的主要貢獻(xiàn)：（1）將割點相關(guān)理論應(yīng)用到信息傳播問題中，提出了基于割點的影響最大化算法CVIM；（2）在四個開源數(shù)據(jù)集上驗證了CVIM 算法在社交網(wǎng)絡(luò)上的實用性和有效性；（3）對CVIM 算法在社交網(wǎng)絡(luò)上多方面的表現(xiàn)進(jìn)行了分析。

1 相關(guān)工作

影響最大化問題進(jìn)入學(xué)術(shù)界是在2001 年，Domingos 和Richardson提出用馬爾科夫隨機(jī)場來模擬信息傳播過程，并給出了一個啟發(fā)式的解決方案，給學(xué)者們打開了一道新的大門。緊接著，在2003 年，Kempe 等人將影響最大化問題定義為一種top-的離散最優(yōu)化問題，即找出影響傳播范圍最大的個種子節(jié)點。此外，他們還提出了兩種基本的傳播模型，線性閾值模型和獨立級聯(lián)模型，并證明了在這兩種傳播模型下，影響最大化問題是一個NP 難問題。他們提出了一個近似比為(1-1/e)的Greedy 算法，可以得到影響最大化問題最優(yōu)解63%的近似解。他們提出的這些方法和結(jié)論給影響最大化問題的研究奠定了基礎(chǔ)。盡管Greedy 算法得到的近似解效果不錯，但它的時間復(fù)雜度非常高。針對這一問題，學(xué)者們提出了一些降低時間復(fù)雜度、提高效率的方法。

根據(jù)影響最大化問題目標(biāo)函數(shù)的子模性，Leskovec等人提出了CELF（cost-effective lazy-forward）算法。它的主要思想是：對于任意邊=(,)，若節(jié)點在上一輪的邊際收益小于等于節(jié)點的邊際收益，則從當(dāng)前輪開始，節(jié)點的邊際收益不用計算。該算法比傳統(tǒng)的貪心算法提高了近700 倍。為了進(jìn)一步提高時間效率，Goyal 等人在CELF 算法的基礎(chǔ)上提出了CELF++算法。與CELF 算法不同的是，CELF++算法先為任意節(jié)點記錄了在當(dāng)前迭代中邊際收益最大的節(jié)點._，然后計算節(jié)點的邊際收益。若._在當(dāng)前迭代中選為種子節(jié)點，則在下一輪迭代中就不需要計算節(jié)點的邊際收益。相較CELF 算法，CELF++算法節(jié)省了35%～55%的時間。

以上這些算法都是以貪心算法為基礎(chǔ)提出的，因此都具有時間復(fù)雜度高的弊端。為了解決這一問題，學(xué)者們提出了基于啟發(fā)式算法的一系列算法。Chen 等人提出的DegreeDiscount 算法，它的主要思想是：若節(jié)點的鄰居節(jié)點中存在種子節(jié)點，那選擇作為種子節(jié)點時，需要先將節(jié)點的度數(shù)進(jìn)行定量打折，然后選度數(shù)最大的個節(jié)點。DegreeDiscount算法相比貪心算法提高了時間效率，但精度不高。因此，Chen等人基于節(jié)點局部區(qū)域的影響值近似估計全局影響值的思想，提出了PMIA（prefix excluding maximum influence arborescence）算法。它通過最大影響路徑來構(gòu)建最大影響子樹（maximum influencearborescence，MIA），并通過調(diào)控子樹的大小來達(dá)到時間效率和精度之間的平衡。盡管PMIA 算法在一定程度上平衡了時間效率和精度，但當(dāng)網(wǎng)絡(luò)圖的密度較大時，會將影響限制在最大影響路徑范圍內(nèi)，使得影響估計誤差較大。根據(jù)面積密度公式，Ibnoulouafi 等人提出了節(jié)點密度中心性，并用節(jié)點密度中心性來度量節(jié)點的影響力。密度中心性考慮了節(jié)點的多層鄰居的影響，因此比其他中心性的度量值更準(zhǔn)確。但其本質(zhì)仍然是用節(jié)點的度來計算密度，因此精度不是很高。

盡管貪心算法和啟發(fā)式算法分別能得到較好的算法精度和時間效率，但它們都無法較好地平衡算法精度和時間效率。因此，曹玖新等人提出了一種綜合啟發(fā)式和貪心算法的MHG（mix heuristic and greedy）算法。它的核心思想是：先通過啟發(fā)式算法選出候選種子節(jié)點集，再用貪心算法從候選種子節(jié)點集中篩選出種子節(jié)點集。MHG 算法的精度接近于貪心算法，并且時間效率要高于貪心算法，較好地平衡了算法精度和時間效率。但MHG 算法也同時擁有所選啟發(fā)式算法和貪心算法的缺陷。如Cao 等人選擇的PMIA 算法在圖密度大時影響度量不準(zhǔn)確，以及他們沒有考慮邊際收益問題。

為了得到好的算法精度和時間效率，學(xué)者們不再僅僅考慮節(jié)點的單一環(huán)境因素和單一特征。Zareie等人提出度量節(jié)點的影響力需考慮直接影響、間接影響、直接覆蓋、間接覆蓋四因素，他們采用多目標(biāo)決策分析中的TOPSIS（technique for order preference by similarity to an ideal solution）方法綜合考慮這四個因素，并提出了MCIM（multi-criteria influence maximization）算法。雖然MCIM 算法不僅考慮了節(jié)點與鄰居的直接與間接影響，而且考慮了不同節(jié)點的鄰居覆蓋問題，但是它僅僅考慮了節(jié)點的度這一單一特征。Yang 等人則利用多目標(biāo)決策分析中的VIKOR（vlsekriterijumska optimizacija I kompromisno resenje）方法綜合考慮了節(jié)點的度中心性、緊密中心性和介數(shù)中心性三種特征，并提出了EW-VIKOR（entropy weighting VIKOR）算法，但EW-VIKOR 算法的精度與單一特征相比提升并不明顯。

鑒于已有的影響最大化算法大多數(shù)關(guān)注于節(jié)點的特征（如度、密度等），很少關(guān)注社交網(wǎng)絡(luò)的結(jié)構(gòu)特征（如連通分量、橋等）。因為割點連接著圖中的連通分量，是圖的重要組成部分。并且文獻(xiàn)[16-17]都證實了割點在網(wǎng)絡(luò)中扮演著重要角色，在網(wǎng)絡(luò)的連通性方面起重要性作用，它們一旦失效或被移除，網(wǎng)絡(luò)都將可能癱瘓。因此，本文綜合考慮節(jié)點特征和社交網(wǎng)絡(luò)結(jié)構(gòu)特征，提出了一種基于割點的影響最大化算法CVIM。

2 相關(guān)概念及形式化描述

在現(xiàn)實生活中，往往存在著一些關(guān)鍵角色，雖然它們可能不是主角，但它們是整個拼圖中必不可少的一塊（如中介、經(jīng)紀(jì)人、交通樞紐等）。把這些關(guān)鍵角色映射到網(wǎng)絡(luò)圖上，他們就是網(wǎng)絡(luò)圖中的割點。在給出割點的定義之前，必須先提一下連通圖和連通分量的基本概念。因為割點是圖中的一種特殊的點，它與圖的連通性有關(guān)。本文通過圖例介紹了連通性的相關(guān)概念，詳細(xì)情況見圖1。

圖1 圖的連通性示例Fig.1 Example of graph connectivity

在圖1 中，是一個無向圖，同時也是非連通圖。而1 是一個連通圖，因為在1 中，任意兩個不同的節(jié)點之間都存在可達(dá)路徑。此外，1 是的子圖，并且如果往1 中加上(8,9)這條邊，1 就不是連通圖?；谶@些前提，則可以推斷1 是的極大連通子圖，同時也可以稱1 是的連通分量。因為連通圖的極大連通子圖就是它本身，所以1 也是1 的極大連通子圖，即1 是1 的連通分量，并且是唯一連通分量。2 是將1 中的節(jié)點2 以及與節(jié)點2 相關(guān)聯(lián)的邊刪除后得到的無向圖。從圖中可以看出，2有3 個連通分量，1 只有1 個連通分量，去除節(jié)點2以及與節(jié)點2 相關(guān)聯(lián)的邊使得圖的連通分量增加，滿足這個條件的節(jié)點被稱為割點，即節(jié)點2 是1 的割點。割點的定義如定義1 所示。

（割點）假設(shè)=(,)是無向連通圖，若存在′?，且′≠?，將′中的節(jié)點和與這些節(jié)點相關(guān)聯(lián)的邊都從中刪除，可以得到兩個或兩個以上的連通分量，則稱′為的點割集。若′={}，則稱是連通圖的割點。

給定一個無向連通圖=(,)，對任意節(jié)點∈都滿足C=(-{})-()，且C≥0。

其中C是節(jié)點對應(yīng)的連通分量增加數(shù)，-{}是從圖中去除節(jié)點以及它相關(guān)聯(lián)的邊后得到的圖，(-{}) 是圖-{} 中的連通分量數(shù)。如果C＞0，則節(jié)點是割點。在圖1 中＞0，因此節(jié)點2 是割點，它連接著3 個連通分量。在信息傳播過程中，一旦節(jié)點2 被阻塞，3 個連通分量之間就無法傳遞信息。但如果從節(jié)點2 開始傳遞信息，3 個連通分量都可達(dá)，傳播范圍變廣。本文分別選取度數(shù)高的節(jié)點和割點進(jìn)行信息傳播對比，如圖2 所示。

圖2 信息傳播對比（假設(shè)傳播概率為1）Fig.2 Comparison of information spreading(Suppose probability of propagation is 1)

在圖2 中，信息源是度最高的節(jié)點，信息源是割點。子圖（a）～（c）分別是信息源和信息源在=0、1、2 時的傳播狀態(tài)圖。很顯然，信息源雖然在傳播前期因為鄰居節(jié)點多而占據(jù)優(yōu)勢，但是到了=2 時，信息源因為它所處的關(guān)鍵位置而比信息源傳播得更廣。因此，割點作為種子節(jié)點是可行的。但是在實際網(wǎng)絡(luò)中存在的割點也不占少數(shù)，尤其是大規(guī)模網(wǎng)絡(luò)。因此本文提出用割點所對應(yīng)的連通分量增加數(shù)來度量節(jié)點的影響力，并且綜合考慮節(jié)點的特征與網(wǎng)絡(luò)的結(jié)構(gòu)特征。種子集的求解式如式（1）所示：

式（1）中，是大小為的種子集，和是調(diào)節(jié)參數(shù)，其中+=1。和分別是以度值和連通分量增加數(shù)篩選出的候選種子集。(×,)表示從候選種子集中選出前×個種子，-(×,)是候選種子集與前×個種子集合的差集，防止最終篩選出的種子出現(xiàn)重復(fù)。

3 CVIM 算法

為了解決影響最大化問題，本文提出先計算網(wǎng)絡(luò)圖=(,)中節(jié)點對應(yīng)的連通分量增加數(shù)，然后根據(jù)節(jié)點度數(shù)排序挑選出影響力最大的×個種子節(jié)點，根據(jù)節(jié)點對應(yīng)的連通分量增加數(shù)排序挑選出除之前挑選出的種子之外的×個種子節(jié)點。CVIM算法的流程圖如圖3 所示。

圖3 CVIM 流程圖Fig.3 Flow chart of CVIM

傳統(tǒng)的求解割點的算法是刪除一個節(jié)點，然后使用DFS 算法遍歷圖，如果圖的連通分量增加，則刪除的節(jié)點是割點。這種求解割點的算法需要使用||次DFS 算法，而本文使用的算法僅僅需要將所有的節(jié)點和邊訪問一次即可，即時間復(fù)雜度僅為(||+||)就能找出圖中所有的割點，并求出其所對應(yīng)的連通分量增加數(shù)。圖4 是一個割點求解實例。

圖4（b）所示為從節(jié)點出發(fā)深度優(yōu)先搜索遍歷子圖（a）所得的深度優(yōu)先生成樹。子圖（b）中的實線代表樹邊，虛線代表回邊（即不在生成樹上的邊）。觀察深度優(yōu)先生成樹的結(jié)構(gòu)，可以發(fā)現(xiàn)有兩類節(jié)點可以成為割點。這兩類節(jié)點的具體情況如下：

圖4 割點求解實例Fig.4 Instance of getting cut-vertex

（1）對于根節(jié)點，若它有兩棵或兩棵以上的子樹，則該根節(jié)點是割點。因為深度優(yōu)先生成樹中不存在連接不同子樹中頂點的邊，所以，如果刪除根節(jié)點，生成樹變成森林。

（2）對于分支節(jié)點（即非根節(jié)點，也非葉子節(jié)點），若它的子樹的節(jié)點都沒有指向節(jié)點的祖先節(jié)點的回邊，則節(jié)點是割點。因為如果刪除節(jié)點，它的子樹和生成樹的其他部分將不再連通。

對于根節(jié)點，可以直接判斷它的孩子節(jié)點個數(shù)，處理十分簡單。但是對于非根節(jié)點，判斷節(jié)點之間是否有回邊就顯得有些困難。本文采用[]和[]分別記錄節(jié)點在深度優(yōu)先遍歷過程中被遍歷到的次序和記錄節(jié)點或它的子樹追溯到最早的祖先節(jié)點的次序。這樣，只需將所有的節(jié)點和邊遍歷一次，就可以更新所有節(jié)點的和值。這兩個值的計算公式如式（2）所示：

式（2）分為兩種情況：（1）(,)是樹邊；（2）(,)是回邊，并且不是的父親節(jié)點。根據(jù)式（2），得到圖3（a）節(jié)點∈{,,…,}對應(yīng)的[]和[]值，詳細(xì)數(shù)據(jù)如表1 所示。

表1 圖3（a）中各節(jié)點對應(yīng)的dfn 和low 值Table 1 dfn and low of nodes in Fig.3(a)

得到節(jié)點∈{,,…,}的[]和[]值之后，本文根據(jù)這兩個值的關(guān)系判別節(jié)點是否為割點。判別節(jié)點是割點的條件如下所示：

（1）節(jié)點是根節(jié)點，并且有兩個或兩個以上的孩子節(jié)點；

（2）節(jié)點不是根節(jié)點，但對于(,)滿足[]≥[]。

根據(jù)第3章中對割點相關(guān)概念的介紹，再加上圖4的求解割點過程，下面給出割點以及其對應(yīng)的連通分量數(shù)的求解算法()。

(,)

其中，第1～4 行是初始化階段，初始化一個空棧，次序標(biāo)記和子樹數(shù)量，以及節(jié)點對應(yīng)的連通分量增加數(shù)[]，并為節(jié)點設(shè)置[]和[]初值，然后將節(jié)點放入棧中。第5～17 行是迭代階段，更新節(jié)點的[]和[]值。其中第9～15 行是當(dāng)(,) 為樹邊時，先遞增子樹數(shù)量，然后遞歸求出[]用來更新[]的值。若節(jié)點是根節(jié)點并有兩個或兩個以上的子樹時，節(jié)點對應(yīng)的連通分量增加數(shù)量加1；若節(jié)點不是根節(jié)點但[]≥[]時，節(jié)點對應(yīng)的連通分量增加數(shù)量也加1。第16～18 行是(,)為回邊時的情況，最后返回[]。根據(jù)表1 和算法1，可以得出圖1 中的割點為，并且對應(yīng)的連通分量增加數(shù)為2。

算法1 獲得了割點以及它所對應(yīng)的連通分量增加數(shù)。基于此，本文給出求解種子集的算法CVIM。

(,,)

算法CVIM 中，第1 行先初始化種子集。第2～5行，根據(jù)節(jié)點的度排序，獲取前×個種子節(jié)點。第6～12 行，先根據(jù)算法1 獲取節(jié)點所對應(yīng)的連通分量增加數(shù)，再根據(jù)它排序，獲取剩下的-×個種子節(jié)點。最后返回種子集。

在算法1 中，找出連通圖中的割點并記錄它所對應(yīng)的連通分量增加數(shù)的時間復(fù)雜度僅為(||+||)，而在算法2 中，獲取節(jié)點度排序的時間復(fù)雜度為(||)，獲取所有節(jié)點對應(yīng)的連通分量增加數(shù)的時間復(fù)雜度為(||×(||+||))，因此，綜合兩個算法的時間復(fù)雜度為(||×(||+||))。

4 仿真實驗

為了驗證CVIM 算法求解影響最大化問題的有效性，本文在4 個真實的開源網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了仿真實驗，這4 個網(wǎng)絡(luò)數(shù)據(jù)集都下載自開源網(wǎng)站http://networkrepository.com。其中數(shù)據(jù)集anybeat 是從在線社交平臺anybeat 上收集到的用戶關(guān)系網(wǎng)絡(luò)，數(shù)據(jù)集brightkite 是從基于位置的網(wǎng)絡(luò)服務(wù)網(wǎng)站的開源API 獲取到的友誼網(wǎng)絡(luò)，數(shù)據(jù)集epinions 是從在線社交網(wǎng)站epinions 上獲取到的信任關(guān)系網(wǎng)，數(shù)據(jù)集HepPh 是來自Arxiv 網(wǎng)站上的高能物理合作網(wǎng)絡(luò)。數(shù)據(jù)集的基本信息如表2 所示。

本文實驗采用傳染病模型進(jìn)行信息傳播模擬，其中感染概率為0.1，恢復(fù)率為網(wǎng)絡(luò)平均度的倒數(shù)，傳播步長為網(wǎng)絡(luò)直徑（網(wǎng)絡(luò)直徑是網(wǎng)絡(luò)的平均路徑長度，代表了網(wǎng)絡(luò)的一定特征。將傳播步長設(shè)置為網(wǎng)絡(luò)直徑更貼近現(xiàn)實生活中的信息傳播）。感染率和恢復(fù)率的取值都是基于傳染病模型的信息傳播仿真實驗的常見取值，見文獻(xiàn)[14]和文獻(xiàn)[18]。

表2 實驗數(shù)據(jù)集的基本信息Table 2 Basic information about experimental datasets

由于CVIM 算法是根據(jù)式（1）來選擇種子節(jié)點，需要先確定式（1）中的參數(shù)和，然后才能從候選種子集和中篩選出種子節(jié)點。本文設(shè)計了實驗來確定這兩個參數(shù)，由于+=1，只要確定其中一個參數(shù)，另一個便可得知。因此，本文通過信息傳播模擬，根據(jù)參數(shù)在不同取值時，獲取到的種子節(jié)點的激活節(jié)點數(shù)來評估參數(shù)的優(yōu)劣，實驗結(jié)果見圖5。

在圖5 中，橫坐標(biāo)是參數(shù)的取值，縱坐標(biāo)是種子節(jié)點最終激活節(jié)點數(shù)（即影響傳播范圍）。此外，本文考慮到種子集大小對結(jié)果的影響，還對比了在取不同值的情況下，參數(shù)對應(yīng)的激活節(jié)點數(shù)的變化。根據(jù)圖5 的實驗結(jié)果，可以看出小于40 時，激活節(jié)點數(shù)大體呈上升趨勢，因為種子集小時，度更能充分發(fā)揮它的前期優(yōu)勢；而當(dāng)大于40 時，激活節(jié)點數(shù)先呈上升趨勢，在參數(shù)=0.5 時，激活節(jié)點數(shù)達(dá)到峰值，取值大于0.5 時開始呈下降趨勢，因為此時割點占據(jù)主導(dǎo)地位。這也印證了圖2 表現(xiàn)出的現(xiàn)象。對于數(shù)據(jù)集anybeat 出現(xiàn)上升、下降、上升的趨勢，是因為取值從0.5 到0.6 時，從anybeat數(shù)據(jù)集挖掘的種子節(jié)點間影響力重疊增加量最多（見表3，設(shè)置為100，以=0.1 時的種子間邊條數(shù)為基準(zhǔn)），導(dǎo)致激活節(jié)點數(shù)急劇下降，之后得到緩解，從而又開始上升，這是數(shù)據(jù)集的特殊性。而數(shù)據(jù)集brightkite 大體出現(xiàn)上升趨勢，只有=100 這條曲線有上升、下降的趨勢，這是因為該數(shù)據(jù)集的規(guī)模相對較大，而種子集大小就顯得較小，從而激活節(jié)點數(shù)的峰值點滯后。數(shù)據(jù)集epinions 也出現(xiàn)了輕微的滯后現(xiàn)象，而數(shù)據(jù)集規(guī)模相對較小的HepPh 則沒有出現(xiàn)滯后現(xiàn)象。綜合4 個數(shù)據(jù)集的模擬結(jié)果，本文將參數(shù)設(shè)置為0.5，即參數(shù)也為0.5。

圖5 參數(shù)α 對比Fig.5 Comparison of parameter α

表3 anybeat數(shù)據(jù)集影響力重疊分析Table 3 Influence overlap analysis of anybeat dataset

參數(shù)取值確定之后，根據(jù)參數(shù)從候選種子集中獲取了種子節(jié)點。為了驗證CVIM 算法挖掘種子的實用性和有效性，本文分別根據(jù)算法運行時間和種子影響傳播范圍兩個指標(biāo)設(shè)計了算法對比實驗。算法運行時間即指算法挖掘種子所花費的時間，種子影響傳播范圍則指用算法挖掘出的種子節(jié)點進(jìn)行信息傳播模擬，得到的激活節(jié)點數(shù)。算法運行時間對比實驗中，種子數(shù)設(shè)置為100。參與對比的算法有：緊密中心性（closeness centrality，CC）、度中心性（degree centrality，DC）、密度（density）和混合多種影響因素的MCIM 算法。實驗結(jié)果如圖6 和圖7 所示。

在圖6 中，橫坐標(biāo)為5 種算法，縱坐標(biāo)是各個算法挖掘100 個種子節(jié)點所耗的時間。從圖6 可以看出，算法CC 挖掘種子所耗時間最長，這是因為算法CC 挖掘種子過程中需要反復(fù)地遍歷路徑，十分耗時，這一特點在網(wǎng)絡(luò)直徑較大的數(shù)據(jù)集brightkite 和epinions 上特別明顯。算法DC 挖掘種子所耗時間最短，本文所提算法CVIM 與算法DC 基本持平，差距僅在0.3 s 以內(nèi)。因為算法DC 僅需要統(tǒng)計節(jié)點鄰居個數(shù)，極少時間內(nèi)就能完成。算法CVIM 除了需要統(tǒng)計節(jié)點鄰居個數(shù)之外，還要統(tǒng)計節(jié)點對應(yīng)的連通分量增加數(shù)，因此比算法DC 多花了些時間。算法Density 雖然也是統(tǒng)計節(jié)點鄰居個數(shù)，但它需要統(tǒng)計3級鄰居，因此花費時間比算法DC 和算法CVIM 多。相比算法Density，算法MCIM 僅考慮了2 級鄰居，在稀疏的社交網(wǎng)絡(luò)上，去重操作花費時間并不多，因此一般情況下的運行時間比算法Density 少。但在聚類系數(shù)較高的數(shù)據(jù)集HepPh 上，算法MCIM 的去重操作需要花費不少時間，因此運行時間比算法Density長一些。算法CVIM 在4 個數(shù)據(jù)集上的運行速度比算法CC、Density 和MCIM 平均快9 089 倍、790 倍和280 倍。從圖6 中的整體表現(xiàn)可以看出，算法CVIM擁有很高的時間效率，因此它在運行時間指標(biāo)上具有一定的優(yōu)勢，更適用于大規(guī)模網(wǎng)絡(luò)。

圖6 運行時間對比Fig.6 Comparison of running time

圖7 影響傳播范圍對比Fig.7 Comparison of influence spreading

在圖7 中，橫坐標(biāo)為種子集大小，縱坐標(biāo)為激活節(jié)點數(shù)量，5 條曲線分別對應(yīng)CC、DC、Density、MCIM和CVIM 五種算法。在4 個數(shù)據(jù)集中，種子集較小時，CVIM 算法處于劣勢，但當(dāng)種子集逐漸變大時，CVIM 算法也逐漸接近其他算法，尤其是在數(shù)據(jù)集anybeat和epinions 中后來者居上，占據(jù)優(yōu)勢地位。在數(shù)據(jù)集brightkite 和epinions 中，算法MCIM 表現(xiàn)一般，是因為這兩個數(shù)據(jù)集的聚類系數(shù)相對較小，而在聚類系數(shù)較大的HepPh 中，表現(xiàn)突出（見表2）。算法CC 是根據(jù)路徑長度度量節(jié)點的影響力，因此在網(wǎng)絡(luò)直徑較小的數(shù)據(jù)集anybeat 上，節(jié)點影響力的區(qū)分度比較低，篩選出的種子節(jié)點的傳播效果較差。算法DC 和Density 都是根據(jù)節(jié)點的度評估節(jié)點影響力，不同點在于Density 將2 級和3 級鄰居的度也作為評估因素，因此Density 比DC 占據(jù)微弱的優(yōu)勢。與算法DC 和Density 相比，算法CVIM 在種子集小時(＜50)效果一般，這是因為在種子集較小時，度占主導(dǎo)優(yōu)勢，但這種優(yōu)勢是短暫的，只有少數(shù)節(jié)點的度數(shù)特別大。在＞50 時，割點獲取了主動權(quán)，實現(xiàn)反超。因為算法CVIM 考慮了網(wǎng)絡(luò)的結(jié)構(gòu)特性，使得算法CVIM 對網(wǎng)絡(luò)的特征差異敏感度低，對網(wǎng)絡(luò)的適配度較高。因此比算法MCIM 和CC 都穩(wěn)定。綜合4 個數(shù)據(jù)集上的實驗結(jié)果來看，隨種子集大小的增加，算法CVIM 對應(yīng)種子的影響傳播范圍穩(wěn)步擴(kuò)大，受到其他因素的干擾較小，因此算法CVIM具有一定的優(yōu)勢。

為了進(jìn)一步驗證CVIM 算法的有效性，本文還設(shè)計了種子間緊密性實驗，探究各算法所選種子是否存在“富人俱樂部”現(xiàn)象?！案蝗司銟凡俊爆F(xiàn)象是復(fù)雜網(wǎng)絡(luò)的一種結(jié)構(gòu)屬性，可以用來區(qū)分冪律拓?fù)?。它表現(xiàn)為“富人”節(jié)點之間的連通性遠(yuǎn)遠(yuǎn)高于其他節(jié)點。即“富人”節(jié)點之間緊密性遠(yuǎn)遠(yuǎn)高于其他節(jié)點。本實驗中的“富人”節(jié)點即指種子節(jié)點。該實驗的設(shè)計思路：首先讀取社交圖，再讀取各算法選出的種子節(jié)點，匹配種子節(jié)點間邊的條數(shù)，若邊的條數(shù)越多，說明種子間的緊密性越高，它們的影響力重疊量越大，“富人俱樂部”現(xiàn)象越明顯。實驗設(shè)置種子集大小為100，實驗結(jié)果如圖8 所示。

圖8 種子富集性對比Fig.8 Comparison of seed enrichment

在圖8 中，橫坐標(biāo)是五種算法，縱坐標(biāo)是算法挖掘出的種子之間的連邊條數(shù)。在4 個數(shù)據(jù)集中，算法CC、DC 和Density 挖掘出的種子，它們的緊密性偏高，進(jìn)一步解釋了圖7 中這三種算法的表現(xiàn)一般的結(jié)果。算法CC 的種子富集性比算法CVIM 和MCIM 平均高2.4 倍和14.6 倍，算法DC 的種子富集性比算法CVIM 和MCIM 平均 高2.5 倍和15.5 倍，算法Density的種子富集性比算法CVIM 和MCIM 平均高2.5 倍和15.4 倍。算法MCIM 因為考慮了影響覆蓋因素，所以種子間的緊密性較低。在數(shù)據(jù)集HepPh 中，算法MCIM 挖掘的種子緊密性高于CVIM 是因為該數(shù)據(jù)集的聚類系數(shù)明顯比其他數(shù)據(jù)集高（見表2）。綜合4個數(shù)據(jù)集上的表現(xiàn)，除去算法MCIM，CVIM 體現(xiàn)出了割點的優(yōu)勢，一定程度上消除了“富人俱樂部”現(xiàn)象。

5 結(jié)束語

由于割點在圖論中扮演著不可或缺的角色，本文基于圖論中的割點理論，提出了基于割點的影響最大化算法CVIM。它將連通分量納入到評估節(jié)點影響力的指標(biāo)中，并結(jié)合度的優(yōu)勢，篩選出了有效的種子集，從而求解了影響最大化問題。實驗結(jié)果表明，CVIM 與部分具有代表性的算法相比，在影響傳播范圍和種子富集性指標(biāo)上具有一定的優(yōu)勢，并且能有穩(wěn)定的表現(xiàn)。但在現(xiàn)實生活中，挑選出的種子節(jié)點的影響力往往會因為時間、空間等因素而衰減，已有研究表明可以通過修改網(wǎng)絡(luò)的結(jié)構(gòu)，提升種子節(jié)點的影響力。因此，未來工作將從網(wǎng)絡(luò)的結(jié)構(gòu)出發(fā)，進(jìn)一步分析如何減緩種子節(jié)點影響力的衰減或提升種子節(jié)點的影響力。