楊書新，宋建繽，梁 文

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

給定一個(gè)無(wú)向連通圖=(,)，對(duì)任意節(jié)點(diǎn)∈都滿足C=(-{})-()，且C≥0。

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

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

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

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

3 CVIM 算法

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

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

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

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

圖4 割點(diǎn)求解實(shí)例Fig.4 Instance of getting cut-vertex

（1）對(duì)于根節(jié)點(diǎn)，若它有兩棵或兩棵以上的子樹，則該根節(jié)點(diǎn)是割點(diǎn)。因?yàn)樯疃葍?yōu)先生成樹中不存在連接不同子樹中頂點(diǎn)的邊，所以，如果刪除根節(jié)點(diǎn)，生成樹變成森林。

（2）對(duì)于分支節(jié)點(diǎn)（即非根節(jié)點(diǎn)，也非葉子節(jié)點(diǎn)），若它的子樹的節(jié)點(diǎn)都沒有指向節(jié)點(diǎn)的祖先節(jié)點(diǎn)的回邊，則節(jié)點(diǎn)是割點(diǎn)。因?yàn)槿绻麆h除節(jié)點(diǎn)，它的子樹和生成樹的其他部分將不再連通。

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

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

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

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

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

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

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

(,)

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

算法1 獲得了割點(diǎn)以及它所對(duì)應(yīng)的連通分量增加數(shù)?；诖耍疚慕o出求解種子集的算法CVIM。

(,,)

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

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

4 仿真實(shí)驗(yàn)

為了驗(yàn)證CVIM 算法求解影響最大化問題的有效性，本文在4 個(gè)真實(shí)的開源網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了仿真實(shí)驗(yàn)，這4 個(gè)網(wǎng)絡(luò)數(shù)據(jù)集都下載自開源網(wǎng)站http://networkrepository.com。其中數(shù)據(jù)集anybeat 是從在線社交平臺(tái)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 是來(lái)自Arxiv 網(wǎng)站上的高能物理合作網(wǎng)絡(luò)。數(shù)據(jù)集的基本信息如表2 所示。

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

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

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

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

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

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

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

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

圖6 運(yùn)行時(shí)間對(duì)比Fig.6 Comparison of running time

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

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

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

圖8 種子富集性對(duì)比Fig.8 Comparison of seed enrichment

在圖8 中，橫坐標(biāo)是五種算法，縱坐標(biāo)是算法挖掘出的種子之間的連邊條數(shù)。在4 個(gè)數(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 因?yàn)榭紤]了影響覆蓋因素，所以種子間的緊密性較低。在數(shù)據(jù)集HepPh 中，算法MCIM 挖掘的種子緊密性高于CVIM 是因?yàn)樵摂?shù)據(jù)集的聚類系數(shù)明顯比其他數(shù)據(jù)集高（見表2）。綜合4個(gè)數(shù)據(jù)集上的表現(xiàn)，除去算法MCIM，CVIM 體現(xiàn)出了割點(diǎn)的優(yōu)勢(shì)，一定程度上消除了“富人俱樂部”現(xiàn)象。

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

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