宋甲秀，楊曉翠，張曦煌

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

0 引言

受益于評(píng)估節(jié)點(diǎn)影響力標(biāo)準(zhǔn)的多樣性，節(jié)點(diǎn)影響力度量方法的研究也是各有側(cè)重。本文，主要關(guān)注復(fù)雜網(wǎng)絡(luò)中基于網(wǎng)絡(luò)結(jié)構(gòu)中心性指標(biāo)的一類影響力度量方法。這類方法又可分為基于網(wǎng)絡(luò)全局結(jié)構(gòu)、基于網(wǎng)絡(luò)局部結(jié)構(gòu)、基于特征向量中心性的影響力度量方法等。一般地，局部度量指標(biāo)效率較高，但是度量效果不盡理想，如度數(shù)中心性、局部中心性等。而以接近度中心性、介數(shù)中心性為代表的全局度量指標(biāo)雖然更為有效，但計(jì)算復(fù)雜度普遍很高。相比之下，k-核中心性在時(shí)間復(fù)雜度上有極大改善，但由于粗粒度特性的存在，使得其無法區(qū)分部分節(jié)點(diǎn)的影響力大小。特征向量中心性指標(biāo)及其變體方法更適用于有向網(wǎng)絡(luò)，在無向網(wǎng)絡(luò)上效果不佳。近來，F(xiàn)laviano Morone和Makse[1]在Nature上提出了一種復(fù)雜度較低的基于滲流理論的集體影響(Collective Influence，簡(jiǎn)稱CI)中心性指標(biāo)。關(guān)于其有效性，在文獻(xiàn)[1]～[3]中均有所證明。直觀地來看，該指標(biāo)考慮了節(jié)點(diǎn)的度數(shù)和l層所有鄰居的度數(shù)(l可取1,2,3…)，但忽略了節(jié)點(diǎn)鄰域可能存在的不平衡結(jié)構(gòu)以及鄰域間連接緊密程度的差異，導(dǎo)致其在異質(zhì)性明顯的實(shí)際復(fù)雜網(wǎng)絡(luò)適用中，表現(xiàn)出很大的局限性。對(duì)此，本章創(chuàng)新性地提出了基于鄰域平衡性及魯棒性的節(jié)點(diǎn)影響力度量方法NewCI(New Collective Influence)中心性，并通過實(shí)驗(yàn)結(jié)果證明了該方法能夠在保留原CI中心性較低計(jì)算復(fù)雜度優(yōu)勢(shì)的同時(shí)突破其局限性，有效性得到進(jìn)一步地增強(qiáng)。

1 相關(guān)工作

在信息傳播過程中，位于網(wǎng)絡(luò)特殊位置的某些節(jié)點(diǎn)往往能夠引發(fā)大規(guī)模的信息擴(kuò)散[4-5]。較之于其他節(jié)點(diǎn)，此類節(jié)點(diǎn)在影響力方面具有明顯優(yōu)勢(shì)，以產(chǎn)品的病毒營銷、流行病傳播等場(chǎng)景中最為常見。這些影響力節(jié)點(diǎn)的識(shí)別對(duì)于理解和分析網(wǎng)絡(luò)中的各類信息流動(dòng)過程有著重要的作用，與如今形式多樣的生活應(yīng)用更是密切相關(guān)。近年來，學(xué)術(shù)界對(duì)于節(jié)點(diǎn)影響力度量方面的研究也是在不斷突破，取得了相對(duì)豐富的成果。其中，給定復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)位置的結(jié)構(gòu)信息，衡量單個(gè)節(jié)點(diǎn)影響力最簡(jiǎn)單的方式是基于中心性的啟發(fā)式度量，如度中心性、k-核、介數(shù)和PageRank等。這些指標(biāo)主要是根據(jù)網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)在擴(kuò)散過程中的作用大小進(jìn)行排序，并以此作為對(duì)節(jié)點(diǎn)影響力的衡量，為后續(xù)實(shí)現(xiàn)加速或限制信息擴(kuò)散的目標(biāo)提供理論支持。

直觀地，擁有大量連接的節(jié)點(diǎn)應(yīng)該具有更大的影響力，這也是度中心性指標(biāo)的核心思想。關(guān)于此理論的合理性，于無標(biāo)度網(wǎng)絡(luò)脆弱性的早期研究中[6]有所揭示。該研究認(rèn)為節(jié)點(diǎn)的連接數(shù)對(duì)動(dòng)態(tài)過程的影響是非線性相關(guān)的，針對(duì)網(wǎng)絡(luò)極少數(shù)的高度節(jié)點(diǎn)進(jìn)行攻擊，會(huì)使得服從重尾分布網(wǎng)絡(luò)中的巨大連通圖迅速崩潰。此外，與其他較復(fù)雜的中心性指標(biāo)相比，度數(shù)的計(jì)算復(fù)雜性可以忽略不計(jì)，所以度中心性被視為識(shí)別影響力節(jié)點(diǎn)最簡(jiǎn)易有效的方法之一。

然而，度中心性存在一明顯不足，表現(xiàn)為該指標(biāo)只考慮了節(jié)點(diǎn)的一階鄰居數(shù)量，忽略了節(jié)點(diǎn)所處位置的網(wǎng)絡(luò)信息。大量實(shí)證表明多數(shù)的傳播現(xiàn)象是以層疊的方式進(jìn)行的。因此，單個(gè)節(jié)點(diǎn)影響力的最終評(píng)估也應(yīng)該受到全局網(wǎng)絡(luò)結(jié)構(gòu)的作用。此外，在實(shí)際的復(fù)雜網(wǎng)絡(luò)中，高度節(jié)點(diǎn)在網(wǎng)絡(luò)的核心位置以及邊緣部分均有出現(xiàn)的可能。這也就意味著以度作為影響力節(jié)點(diǎn)識(shí)別指標(biāo)，在真實(shí)世界中并不可靠。據(jù)此，Kitsak等人通過對(duì)各種實(shí)際社交網(wǎng)絡(luò)上的數(shù)據(jù)在SIS和SIR模型上進(jìn)行了廣泛的模擬證實(shí)了這一推測(cè)[7]。取決于節(jié)點(diǎn)在全網(wǎng)絡(luò)中位置的差異，兩個(gè)度數(shù)相等的節(jié)點(diǎn)在SIR模型的傳播過程中可能會(huì)感染完全不同的人群。相較而言，k-核指標(biāo)可以區(qū)分網(wǎng)絡(luò)的核心位置和邊緣部分，且能在O(m)(m為網(wǎng)絡(luò)邊數(shù))的運(yùn)算時(shí)間內(nèi)完成分解過程，故被廣泛應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)分析。一般認(rèn)為，具有低k-核指標(biāo)值的節(jié)點(diǎn)被大量的低度鄰居包圍，會(huì)限制影響的傳播，而位于核心區(qū)域的節(jié)點(diǎn)(高k-核指標(biāo)值者)可以通過其高度鄰居促進(jìn)大規(guī)模擴(kuò)散。但在SIS模型下，由于I群體被治愈后仍然可能被再次感染，所以高k-核區(qū)域一直會(huì)存在I群體。對(duì)此，文獻(xiàn)[8][9][10]考慮到網(wǎng)絡(luò)中高k-核區(qū)域的局部結(jié)構(gòu)信息，提出了幾種更為一般化的強(qiáng)化k-核方法。

除了k-核指標(biāo)之外，特征向量中心性也可作為基于全局網(wǎng)絡(luò)結(jié)構(gòu)的指標(biāo)。該指標(biāo)認(rèn)為節(jié)點(diǎn)的影響力取決于其鄰居的傳播能力。首先給網(wǎng)絡(luò)中的所有節(jié)點(diǎn)分配統(tǒng)一的聲望分?jǐn)?shù)，聲望分?jǐn)?shù)一般初始化為向量(1,1,…,1)T∈Rn(n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù))，該分?jǐn)?shù)會(huì)沿著邊進(jìn)行傳播直到達(dá)到穩(wěn)定狀態(tài)為止。在計(jì)算過程中，聲望分?jǐn)?shù)傳播的每一個(gè)迭代對(duì)應(yīng)于當(dāng)前得分向量左乘網(wǎng)絡(luò)的鄰接矩陣。該過程實(shí)際上是通過冪迭代來計(jì)算鄰接矩陣的主特征向量及其對(duì)應(yīng)的特征值，聲望分?jǐn)?shù)向量最終會(huì)收斂到最大特征值的右特征向量。PageRank和LeaderRank算法都為基于特征向量中心性的著名變體。

無獨(dú)有偶，F(xiàn)laviano Morone等人[1]為解決影響最大化問題，把尋找一組最小化的種子節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)中信息擴(kuò)散進(jìn)行控制使其達(dá)到免疫狀態(tài)這一問題，精確地映射到最優(yōu)滲流模型中，并提出CI中心性來對(duì)量化個(gè)體節(jié)點(diǎn)的影響力。該中心性度量方法考慮了節(jié)點(diǎn)間的拓?fù)湎嗷プ饔?，卻對(duì)節(jié)點(diǎn)鄰域分布以及網(wǎng)絡(luò)結(jié)構(gòu)的健壯程度未予關(guān)注?；诖耍疚脑贑I中心性的基礎(chǔ)上，對(duì)其所忽略的重要影響因素分別進(jìn)行了分析、定義及量化，繼而創(chuàng)新性地提出了在一般化網(wǎng)絡(luò)下仍然普遍適用的影響力度量方法—NewCI中心性。通過在真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行的節(jié)點(diǎn)免疫網(wǎng)絡(luò)抗毀性實(shí)驗(yàn)，證明了該中心性影響力度量方法在性能上具有很高的穩(wěn)定性，且對(duì)影響力大小度量的準(zhǔn)確性優(yōu)于CI中心性。

2 算法描述

2.1 定義描述

滲流理論：是復(fù)雜網(wǎng)絡(luò)理論研究中的一個(gè)重要發(fā)現(xiàn)，主要包括鍵滲流和點(diǎn)滲流。給定無向網(wǎng)絡(luò)G(V,E)，在鍵滲流的模型下，G中的每條邊以一定的概率q被保留，同時(shí)以1-q的概率被刪除。當(dāng)q=0時(shí)，所有的邊都會(huì)被刪除；隨著q的增大，G中將會(huì)保留了較多的邊并形成一些網(wǎng)絡(luò)簇；僅當(dāng)q大于臨界閾值qc時(shí)，G中會(huì)出現(xiàn)規(guī)模為O(|V|)(V為網(wǎng)絡(luò)節(jié)點(diǎn)集)的巨型連通分量。點(diǎn)滲流模型與鍵滲流模型類似，不同之處在于保留概率q被分配給節(jié)點(diǎn)而不是邊。

(1)

(2)

其中，向量v=(v1,v2,…,vn)表示節(jié)點(diǎn)是否屬于巨型連通分量，vi取值為1(或0)，表示節(jié)點(diǎn)vi屬于(或不屬于)該巨型連通分量。在刪除節(jié)點(diǎn)等量的情況下，G(q)的值越小，說明網(wǎng)絡(luò)分裂越嚴(yán)重，反映出所刪除節(jié)點(diǎn)在網(wǎng)絡(luò)中承擔(dān)的角色越重要，即個(gè)體影響力較大。

連通分量的數(shù)量：給定初始網(wǎng)絡(luò)G(V,E)，C(q)為基于某種特定的中心性度量方法刪除nq數(shù)目的節(jié)點(diǎn)之后的網(wǎng)絡(luò)中連通圖的數(shù)量，連通分量的數(shù)量分?jǐn)?shù)Rc則定義為C(q)與初始網(wǎng)絡(luò)G的規(guī)模的比值，即

(3)

式中Rc的值越大，網(wǎng)絡(luò)的分段就越多。Rc(q)=1時(shí)，網(wǎng)絡(luò)將完全分散，所有的節(jié)點(diǎn)之間幾乎相互孤立，網(wǎng)絡(luò)的性質(zhì)也就不復(fù)存在；Rc(q)=0時(shí)，則表示網(wǎng)絡(luò)為一個(gè)連通網(wǎng)絡(luò)，具有較強(qiáng)的抗毀性。在以刪除相同數(shù)量節(jié)點(diǎn)為前提條件下，C(q)和Rc(q)都可通過網(wǎng)絡(luò)被破壞的碎片化程度來衡量這些節(jié)點(diǎn)的實(shí)際影響力。

2.2 基本方法介紹

本文主要就五種最為常用的節(jié)點(diǎn)影響力度量方法進(jìn)行簡(jiǎn)要介紹，包括介數(shù)中心性[4,13-14]、接近度中心性[4,15]，k-核[16]、特征向量中心性[17]以及CI中心性[7]。它們也將作為后續(xù)實(shí)驗(yàn)研究中的基準(zhǔn)方法。

(4)

接近度中心性(Closeness Centrality，簡(jiǎn)稱CC)[4]，定義連通網(wǎng)絡(luò)G中節(jié)點(diǎn)vi的接近度中心性為從該節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短距離平均值的倒數(shù)，即

(5)

其中，dij為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj間的最短距離。顯然，CC值越大，節(jié)點(diǎn)越處于網(wǎng)絡(luò)中心，影響力就越大。

k-核(簡(jiǎn)稱k-core)方法[13]的主要思想基于核心度，即認(rèn)為位于網(wǎng)絡(luò)核心部分的節(jié)點(diǎn)的影響力要高于邊緣節(jié)點(diǎn)。實(shí)現(xiàn)流程如下：設(shè)網(wǎng)絡(luò)的孤立節(jié)點(diǎn)的核心度為0，并將其從網(wǎng)絡(luò)中去除，而后進(jìn)行k-核分解。首先，把所有核心度為1的節(jié)點(diǎn)從網(wǎng)絡(luò)中移除，之后繼續(xù)移除剩余度小于等于1的節(jié)點(diǎn)，直到網(wǎng)絡(luò)中所有剩余節(jié)點(diǎn)的剩余度都大于1為止。該步中所有移除的節(jié)點(diǎn)即為1-核節(jié)點(diǎn)，其核心度都等于1。接著遵循以上步驟，對(duì)網(wǎng)絡(luò)中核心度為2的節(jié)點(diǎn)進(jìn)行處理。以此類推，直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都被移除。在該方法下，較大核心度的節(jié)點(diǎn)意味著位于網(wǎng)絡(luò)更中心的位置，有更大的影響力。

特征向量中心性(Eigenvector Centrality，簡(jiǎn)稱EC)[17]認(rèn)為節(jié)點(diǎn)的影響力取決于鄰居的數(shù)量以及其影響力，定義節(jié)點(diǎn)vi的特征向量中心性如公式(6)，可通過冪迭代方法計(jì)算得出。

(6)

Α={aij}

(7)

其中，c為比例常數(shù)，一般取1/λ，λ為鄰接矩陣A的最大特征向量。

集體影響(Collective Influence，簡(jiǎn)稱CI)[7]是一種中心性優(yōu)化方法，旨在尋找在最優(yōu)滲透模型下使網(wǎng)絡(luò)結(jié)構(gòu)碎片化的最小影響力節(jié)點(diǎn)集，該指標(biāo)從選擇節(jié)點(diǎn)并將其刪除給網(wǎng)絡(luò)中巨型連通分量所帶來的破環(huán)程度來衡量節(jié)點(diǎn)的影響力大小。定義Ball(i,l)為圍繞節(jié)點(diǎn)vi，且屬于半徑(最短路徑)為l的球內(nèi)的節(jié)點(diǎn)集合，?Ball(i,l)為該球的邊界，那么節(jié)點(diǎn)vi的CI中心性值為

(8)

其中，ki是節(jié)點(diǎn)vi的度，l是預(yù)定義的不超過有限網(wǎng)絡(luò)的網(wǎng)絡(luò)直徑的非負(fù)整數(shù)，在大中型網(wǎng)絡(luò)一般取3，小網(wǎng)絡(luò)中取2。

2.3 融合鄰域魯棒性及度均衡性的集體影響中心性度量方法

真實(shí)的復(fù)雜網(wǎng)絡(luò)中普遍存在著異質(zhì)性，如微博、Twitter等社交網(wǎng)絡(luò)，考慮該因素對(duì)提出合理的節(jié)點(diǎn)影響力度量方法有著重要意義。而CI中心性只考慮到了節(jié)點(diǎn)的度數(shù)和以該節(jié)點(diǎn)為中心，半徑在l(節(jié)點(diǎn)間的最短路徑)的球面邊界上所有節(jié)點(diǎn)的度數(shù)，忽略了由于優(yōu)先連接造成的度分布不平衡問題所帶來的影響。

如圖1所示，首先，本文針對(duì)多個(gè)節(jié)點(diǎn)的CI中心性度量值相等的情況，對(duì)各節(jié)點(diǎn)所對(duì)應(yīng)的局部拓?fù)浣Y(jié)構(gòu)進(jìn)行詳細(xì)分析。簡(jiǎn)單起見，1)令l=1，后續(xù)的分析將推廣至l階鄰居，2)以局部樹狀網(wǎng)絡(luò)為研究起點(diǎn)，逐步擴(kuò)展到節(jié)點(diǎn)及其l階鄰居的局部聚類系數(shù)不為0的一般網(wǎng)絡(luò)。根據(jù)CI中心性的定義可知，CI中心性度量值相等的節(jié)點(diǎn)無外乎是兩種情況：一是其一階鄰居節(jié)點(diǎn)的數(shù)量相同，且一階鄰居節(jié)點(diǎn)的度之和也相等，如圖1a和c中的節(jié)點(diǎn)1。如此一來，一階鄰居的度分布平衡與否便成為了區(qū)分兩節(jié)點(diǎn)影響力的關(guān)鍵，本文稱此問題為目標(biāo)節(jié)點(diǎn)的1階鄰域的度均衡性。第二種則是其一階鄰居的數(shù)量不相等，如圖1a和b中的節(jié)點(diǎn)1。

除了目標(biāo)節(jié)點(diǎn)的一階鄰居節(jié)點(diǎn)度分布及其一階鄰居數(shù)量這兩個(gè)因素之外，目標(biāo)節(jié)點(diǎn)的一階鄰居的鄰居之間的相互連接關(guān)系也會(huì)對(duì)該節(jié)點(diǎn)的影響力評(píng)估產(chǎn)生影響，本文稱此因素為1階鄰域簇間連接強(qiáng)度。鑒于在CI中心性度量方法中，半徑l考慮的是最短路徑，所以該因素并不會(huì)對(duì)CI的計(jì)算結(jié)果產(chǎn)生影響。以圖1e為例，節(jié)點(diǎn)一階鄰居的鄰居之間的連接關(guān)系對(duì)應(yīng)于最外層球面節(jié)點(diǎn)的連接情況。顯然，節(jié)點(diǎn)6和節(jié)點(diǎn)7、節(jié)點(diǎn)12與節(jié)點(diǎn)13之間的連接在目標(biāo)節(jié)點(diǎn)1從網(wǎng)絡(luò)中去除后，不會(huì)對(duì)碎片化網(wǎng)絡(luò)的連通分量的數(shù)量以及巨型連通分量的規(guī)模產(chǎn)生影響。然而節(jié)點(diǎn)7與節(jié)點(diǎn)9、節(jié)點(diǎn)10和節(jié)點(diǎn)12之間連接的存在與否，將導(dǎo)致在對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行相同的操作后，網(wǎng)絡(luò)結(jié)構(gòu)會(huì)產(chǎn)生截然不同的變化。

此外，還有一個(gè)不容忽視的影響因素：目標(biāo)節(jié)點(diǎn)一階鄰居間的連接關(guān)系，本文稱之為鄰域魯棒性，以局部聚類系數(shù)這一基本網(wǎng)絡(luò)特征來衡量。假設(shè)突破CI中心性度量方法對(duì)于局部樹狀網(wǎng)絡(luò)的限制，推廣到一般化網(wǎng)絡(luò)，節(jié)點(diǎn)局部的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)將會(huì)發(fā)生巨大變化。如圖1d，若目標(biāo)節(jié)點(diǎn)1在樹狀網(wǎng)絡(luò)中的一階鄰居全部沒有互相連接(即虛線鏈接不存在)，即該節(jié)點(diǎn)的局部聚類系數(shù)為0，其與一階鄰居的局部拓?fù)浣Y(jié)構(gòu)是樹狀網(wǎng)絡(luò)；隨著一階鄰居互連強(qiáng)度的增大，該節(jié)點(diǎn)的局部區(qū)域的結(jié)構(gòu)趨于穩(wěn)定，當(dāng)該節(jié)點(diǎn)的聚類系數(shù)增加到1時(shí)，其與一階鄰居節(jié)點(diǎn)在拓?fù)渖蟿t構(gòu)成了全連接網(wǎng)絡(luò)圖(圖1d中虛線鏈接全都存在的情況)。不難發(fā)現(xiàn)，目標(biāo)節(jié)點(diǎn)在樹狀網(wǎng)絡(luò)中被刪除后，該網(wǎng)絡(luò)因抗毀性差，迅速分段瓦解成多個(gè)碎片網(wǎng)絡(luò)。而在全連接網(wǎng)絡(luò)中，網(wǎng)絡(luò)結(jié)構(gòu)具有較強(qiáng)的健壯性，刪除目標(biāo)節(jié)點(diǎn)后，網(wǎng)絡(luò)仍然連通。因此，網(wǎng)絡(luò)中目標(biāo)節(jié)點(diǎn)的一階鄰居間連接關(guān)系的復(fù)雜性對(duì)于準(zhǔn)確有效地衡量節(jié)點(diǎn)的影響力至關(guān)重要。

圖1 NewCI中心性分析示意圖Fig.1 Analysis diagram of NewCI centrality

綜上所述，CI方法忽視了研究目標(biāo)節(jié)點(diǎn)的度數(shù)及其1階鄰域度均衡性、1階鄰域簇間連接強(qiáng)度、鄰域魯棒性等四個(gè)與影響力節(jié)點(diǎn)的度量相關(guān)的因素。本文對(duì)其進(jìn)行改進(jìn)，將1階鄰域度均衡性、1階鄰域簇間連接強(qiáng)度推廣到l階鄰域，對(duì)目標(biāo)節(jié)點(diǎn)的l階鄰域度均衡性、l階鄰域簇間連接強(qiáng)度、鄰域魯棒性給出了相應(yīng)的定義與分析，并以真實(shí)復(fù)雜網(wǎng)絡(luò)為應(yīng)用背景，提出更具合理性的影響力度量方法。同時(shí)，針對(duì)目標(biāo)節(jié)點(diǎn)的度數(shù)這一影響因素，制定出相應(yīng)的排序局部調(diào)整策略。以下，將就這些概念逐一介紹。

2.3.1l階鄰域度均衡性

節(jié)點(diǎn)的l階鄰域度分布的異質(zhì)程度是評(píng)估節(jié)點(diǎn)影響力的重要因素。為了量化l階鄰域節(jié)點(diǎn)度分布的均衡程度，本文定義l階鄰域度均衡性如式(9)。其中，Nl(i)表示節(jié)點(diǎn)vi的l階鄰域的節(jié)點(diǎn)集合，kj代表節(jié)點(diǎn)vj的度。分母中的第一項(xiàng)理解為l階鄰域度的振幅與l階鄰域度的理論中間值的比值，加1為防止分母為0的平滑操作。

(9)

目標(biāo)節(jié)點(diǎn)的l階鄰域各節(jié)點(diǎn)的度越均衡，去除該節(jié)點(diǎn)后分裂成的網(wǎng)絡(luò)碎片，規(guī)模會(huì)相對(duì)更均衡，網(wǎng)絡(luò)中巨型連通分量會(huì)驟減，即該節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力更強(qiáng)。反之，則越弱?；诖耍疚膶I中心性方法修正為NewCIB中心性(New Collective Influence centrality based on Neighborhood Balance)方法，如式(10)。當(dāng)Bl(i)為1(目標(biāo)節(jié)點(diǎn)的l階鄰域各節(jié)點(diǎn)的度絕對(duì)均衡)時(shí)，該方法退化為CI方法。

NewCIB(i)=Bl(i)CI(i)

(10)

為驗(yàn)證NewCIB中心性方法的合理性，本文以圖1a,c舉例說明。令l=1，節(jié)點(diǎn)1為研究對(duì)象，根據(jù)式(8)兩圖中節(jié)點(diǎn)1的CI中心性值都為24。NewCIB(1)考慮了鄰域度分布均衡性，節(jié)點(diǎn)1對(duì)應(yīng)的鄰域節(jié)點(diǎn)的度均衡程度越高，則NewCIB值越大。對(duì)于a，c兩圖中的目標(biāo)節(jié)點(diǎn)1，根據(jù)式(10)計(jì)算出的NewCIB方法值分別為24、16.8，表明節(jié)點(diǎn)1的刪除對(duì)a網(wǎng)絡(luò)的破壞性更大，與圖中所反映的實(shí)際情況一致。由此可知，與CI中心性方法相比，NewCIB方法對(duì)節(jié)點(diǎn)影響力大小的評(píng)估更為準(zhǔn)確。

2.3.2l階鄰域簇間連接強(qiáng)度

如上所述，在目標(biāo)節(jié)點(diǎn)l階鄰域的節(jié)點(diǎn)度分布均衡性一定的情況下，l階鄰域節(jié)點(diǎn)間的連接情況則成為評(píng)估節(jié)點(diǎn)影響力的主要干擾因素。其中，目標(biāo)節(jié)點(diǎn)的l階鄰域簇內(nèi)節(jié)點(diǎn)間的連接(圖1e中的連邊(6,7)和(12,13))與該節(jié)點(diǎn)的刪除對(duì)網(wǎng)絡(luò)的破壞性相互獨(dú)立。而其l階鄰域簇間節(jié)點(diǎn)間的連接(圖1e,1f中的虛線)則影響了刪除該節(jié)點(diǎn)后的網(wǎng)絡(luò)連通性，增強(qiáng)了網(wǎng)絡(luò)的健壯性。更直接的表述是，虛線連接之后的網(wǎng)絡(luò)，目標(biāo)節(jié)點(diǎn)的影響力減弱。本文中以目標(biāo)節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)為簇頭的網(wǎng)絡(luò)簇中l(wèi)階鄰域連通簇的數(shù)量來定義l階鄰域簇間連接強(qiáng)度這一影響因素。

對(duì)于目標(biāo)節(jié)點(diǎn)vt，Nl(t)表示其l階鄰居的集合，l階鄰域連通簇對(duì)(Connected cluster pairs)的集合記為Ccp(初始化為?)，N(x)為vx的鄰居集合。當(dāng)|Nl(t)|=1時(shí)，l階鄰域連通簇的數(shù)量為1。當(dāng)|Nl(t)|>1時(shí)，對(duì)于任意vi，vj∈Nl(t)，且j>i，利用Ψij來判斷vt所有鄰居節(jié)點(diǎn)為簇頭的網(wǎng)絡(luò)簇之間在l階鄰域上是否連通，即

Ψij=(N(Nl(i))-N(Nl(i))INl(i))INl(j)

(11)

此時(shí)，若Ψij=?，表明以vi和vj為簇頭的網(wǎng)絡(luò)簇之間不連通；Ψij≠?，則連通，連通簇的簇頭對(duì)集合記為{(vi,vj)}。所以有

(12)

記Ccp中簇對(duì)所形成的連通簇團(tuán)個(gè)數(shù)(Number of connected clusters)為Ncc，目標(biāo)節(jié)點(diǎn)的鄰居中未和其他簇頭連通的節(jié)點(diǎn)數(shù)，即獨(dú)立簇頭個(gè)數(shù)(Number of independent cluster)為Nic，則最終目標(biāo)節(jié)點(diǎn)的l階鄰域連通簇的數(shù)量為

Tc=Ncc+Nic

(13)

l階鄰域簇間連接強(qiáng)度定義為

(14)

同樣，CI中心性方法不能實(shí)現(xiàn)根據(jù)l階鄰域簇內(nèi)節(jié)點(diǎn)間的連接存在與否以及連接強(qiáng)度對(duì)節(jié)點(diǎn)影響力的大小進(jìn)行區(qū)分。為克服這一不足，在目標(biāo)節(jié)點(diǎn)l階鄰域的節(jié)點(diǎn)度分布均衡性一定的情況下，本文將CI方法重寫為NewCIS中心性(New Collective Influence Centrality based on Neighborhood Strength Coefficient)方法：

NewCIs(i)=Sl(i)CI(i)

(15)

以圖1a和e、c和f為對(duì)比，來分析驗(yàn)證NewCIS中心性方法的合理性。首先，當(dāng)e和f中虛線不連接時(shí)，根據(jù)式(8)得到目標(biāo)節(jié)點(diǎn)1在4個(gè)圖中的CI均為24。其次，虛線連接后，e和f中目標(biāo)節(jié)點(diǎn)1的NewCIS分別為12和6。顯然，簇間連接的加入，會(huì)使得e(或f)中目標(biāo)節(jié)點(diǎn)1的影響力弱于a(或c)，與實(shí)際情況相符。

2.3.3 鄰域魯棒性

為了量化節(jié)點(diǎn)的局部鄰域結(jié)構(gòu)拓?fù)涞慕研圆町悓?duì)節(jié)點(diǎn)影響力大小的影響，本文引入“鄰域魯棒性”概念來衡量目標(biāo)節(jié)點(diǎn)的鄰域節(jié)點(diǎn)間連接的密集程度，認(rèn)為鄰域節(jié)點(diǎn)間的連接越密集，網(wǎng)絡(luò)結(jié)構(gòu)的魯棒性則越強(qiáng)，反之亦然。這里采用目標(biāo)節(jié)點(diǎn)的局部聚類系數(shù)這一網(wǎng)絡(luò)統(tǒng)計(jì)量來計(jì)算其鄰域魯棒性，形式化表示為

(16)

考慮到目標(biāo)節(jié)點(diǎn)的鄰域魯棒性與其在網(wǎng)絡(luò)結(jié)構(gòu)上發(fā)揮的影響力成反比，且該節(jié)點(diǎn)鄰域節(jié)點(diǎn)間的連接程度會(huì)直接影響鄰域節(jié)點(diǎn)的度分布均衡性，本文修正CI中心性方法為NewCIB/R中心性(New Collective Influence centrality based on Neighborhood Balance and Robustness)方法，定義如下：

(17)

接下來結(jié)合圖1a、d來驗(yàn)證NewCIB/R中心性方法的合理性。在圖1a、d中，節(jié)點(diǎn)1為研究對(duì)象，即目標(biāo)節(jié)點(diǎn)。a中節(jié)點(diǎn)1的CI中心性值為24；d中節(jié)點(diǎn)1的CI值會(huì)隨著其聚類系數(shù)的增加而增加，當(dāng)節(jié)點(diǎn)2與節(jié)點(diǎn)5之間有連接時(shí)，目標(biāo)節(jié)點(diǎn)的CI值為30。顯然，節(jié)點(diǎn)1在a網(wǎng)絡(luò)中被刪除之后，該網(wǎng)絡(luò)會(huì)分解成4個(gè)碎片網(wǎng)絡(luò)，而圖d中，由于節(jié)點(diǎn)2與節(jié)點(diǎn)5的相互連接，刪除節(jié)點(diǎn)1后，該網(wǎng)絡(luò)只分段為3個(gè)碎片網(wǎng)絡(luò)，且巨型連通分量更大，說明了節(jié)點(diǎn)1在a網(wǎng)絡(luò)中有更大的影響力，這與兩圖中由CI中心性方法所度量的影響力結(jié)果相悖。然而，基于本文的NewCIB/R中心性方法，節(jié)點(diǎn)1在a網(wǎng)絡(luò)中的NewCIB/R中心性值同樣為24，但在d圖中該節(jié)點(diǎn)的NewCIB/R中心性值為21.4，與CI中心性方法相比，NewCIB/R中心性方法對(duì)目標(biāo)節(jié)點(diǎn)的影響力度量更為合理。

同上思路，基于節(jié)點(diǎn)的NewCIS中心性度量方法，其鄰域魯棒性也能加強(qiáng)度量方法的有效性，故在CI中心性指標(biāo)的基礎(chǔ)上融合節(jié)點(diǎn)的l階鄰域簇間連接強(qiáng)度與鄰域魯棒性，定義NewCIS/R中心性(New Collective Influence Centrality based on Neighborhood Robustness and Strength Coefficient)方法為：

(18)

綜上所述，結(jié)合l階鄰域度均衡性、l階鄰域簇間連接強(qiáng)度、鄰域魯棒性等CI方法忽略的影響力度量影響因素，本文定義NewCI中心性方法為：

(19)

其中，參數(shù)α一般取0.5。

需要補(bǔ)充的一點(diǎn)是，NewCI中心性方法是針對(duì)目標(biāo)節(jié)點(diǎn)的鄰居數(shù)目一定，CI值相同的情況(圖1a、c、d、e、f)而設(shè)計(jì)，并不能適用于鄰居數(shù)目不等，CI值相等的情況。如圖1a、b所示，兩圖中目標(biāo)節(jié)點(diǎn)1的鄰居數(shù)分別為3和4，CI值均為24，且l階鄰域度均衡性、l階鄰域簇間連接強(qiáng)度以及鄰域魯棒性都相等，故二者的NewCI值相等。但b中節(jié)點(diǎn)1的影響力顯然比a中的要弱。也就是說，在這種情況下，目標(biāo)節(jié)點(diǎn)本身的度是具有最高優(yōu)先級(jí)的考慮因素。因此，本文制定排序局部調(diào)整策略如下：在對(duì)網(wǎng)絡(luò)各節(jié)點(diǎn)的影響力進(jìn)行度量時(shí)，若出現(xiàn)多個(gè)節(jié)點(diǎn)NewCI相等的情況，將根據(jù)鄰居數(shù)目對(duì)這部分節(jié)點(diǎn)進(jìn)行降序排列，以強(qiáng)化結(jié)果的整體合理性。注意，該策略只為實(shí)驗(yàn)中確定影響力節(jié)點(diǎn)的相對(duì)排名而用，并不作為節(jié)點(diǎn)影響力度量方法。

2.4 時(shí)間復(fù)雜度分析

給定復(fù)雜網(wǎng)絡(luò)G=(V,E)，這里V和E={(u,v)|u,v∈V}分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集和邊集，n和m依次代表V和E的規(guī)模。NewCI中心性影響力度量方法的計(jì)算復(fù)雜度主要由節(jié)點(diǎn)的CI中心性度量、l階鄰域度均衡性、l階鄰域簇間連接強(qiáng)度以及鄰域魯棒性等4部分計(jì)算復(fù)雜度組成。其中，節(jié)點(diǎn)CI的計(jì)算復(fù)雜度與該節(jié)點(diǎn)l階鄰域節(jié)點(diǎn)的數(shù)量有關(guān)。由于網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度為〈k〉，則任意節(jié)點(diǎn)的l階鄰域的平均節(jié)點(diǎn)數(shù)量為〈k〉*〈k〉l-1，則計(jì)算網(wǎng)絡(luò)所有節(jié)點(diǎn)CI的復(fù)雜度為O(n*〈k〉*〈k〉l-1)。對(duì)于目標(biāo)節(jié)點(diǎn)l階鄰域度均衡性和l階鄰域簇間連接強(qiáng)度的計(jì)算，復(fù)雜度均為O(〈k〉*〈k〉l-1)，節(jié)點(diǎn)的鄰域魯棒性的計(jì)算復(fù)雜度為O(1/2*〈k〉*(〈k〉-1))。所以，NewCI中心性影響力度量方法的最終時(shí)間復(fù)雜度為O(n*(3*〈k〉*〈k〉l-1+1/2*〈k〉*(〈k〉-1)))。又由于真實(shí)世界的復(fù)雜網(wǎng)絡(luò)通常是稀疏的，節(jié)點(diǎn)的數(shù)量n和邊數(shù)量m存在著m=O(n)的相關(guān)關(guān)系，所以〈k〉=2m/n可以記為一個(gè)常數(shù)，故算法的時(shí)間復(fù)雜度可近似為O(n*(3*〈k〉l+1/2*〈k〉2))，而l的取值一般較小。因此，NewCI中心性影響力度量方法具有較低的時(shí)間復(fù)雜度，符合基于網(wǎng)絡(luò)局部的中心性方法所具有的優(yōu)勢(shì)。

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

節(jié)點(diǎn)的影響力大小主要通過免疫該節(jié)點(diǎn)給網(wǎng)絡(luò)帶來的破壞程度來體現(xiàn)，本節(jié)即從該角度對(duì)NewCI中心性的性能進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)中l(wèi)的取值一般為2，與CC、BC、EC、k-core以及CI等5個(gè)代表性方法進(jìn)行對(duì)比。

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集介紹

實(shí)驗(yàn)的硬件環(huán)境為Intel(R) Core(TM) i5-3210 CPU @ 2.50GHz，8 GB的內(nèi)存。操作系統(tǒng)為window7。開發(fā)環(huán)境Visual Studio Code 1.15.1，開發(fā)語言為python 2.7。網(wǎng)絡(luò)分析工具包括snap-4.0.1版本、networkx-1.11版本、Gephi 0.8.1beta等。

為充分評(píng)估NewCI中心性的性能，本文選取了6個(gè)領(lǐng)域不同的真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集，包括：1)Celegans[18]：秀麗隱桿線蟲神經(jīng)元網(wǎng)絡(luò)；2)Power[18]：美國西部電力網(wǎng)絡(luò)，以發(fā)電站或中轉(zhuǎn)站為節(jié)點(diǎn)，高壓傳輸線路為邊；3)Citeseer[19]：由科學(xué)出版物和引用鏈接組成的引文網(wǎng)絡(luò)；4)Literature_1976[20][21]：荷蘭文學(xué)評(píng)論數(shù)據(jù)集，節(jié)點(diǎn)為文學(xué)作者或評(píng)論家，邊表示評(píng)論家對(duì)文學(xué)作者工作的評(píng)價(jià)；5)Sawmill[21][22]：某企業(yè)內(nèi)部員工的通信關(guān)系網(wǎng)絡(luò)；6)ModMath[21]：現(xiàn)代數(shù)學(xué)方法在美國賓夕法尼亞州Allegheny縣的小學(xué)和中學(xué)課程中的傳播網(wǎng)絡(luò)。網(wǎng)絡(luò)中的節(jié)點(diǎn)表示學(xué)校的主管領(lǐng)導(dǎo)，邊則表示管理者之間的友誼關(guān)系。

各數(shù)據(jù)集的基本網(wǎng)絡(luò)拓?fù)涮卣魅绫?，依次為節(jié)點(diǎn)數(shù)量(n)、網(wǎng)絡(luò)邊數(shù)(m)、平均度(〈k〉)、最大度(kmax)、網(wǎng)絡(luò)中節(jié)點(diǎn)的平均聚類系數(shù)(C)、節(jié)點(diǎn)間的平均最短路徑(〈d〉)、同配系數(shù)(r)、節(jié)點(diǎn)度分布的異質(zhì)性(H)[23-24]以及傳播閾值[6,25](λc)。其中，H=〈d2〉/〈d〉2，λc=〈k〉/(〈k2〉-〈k〉)。

表1 實(shí)驗(yàn)數(shù)據(jù)集的基本拓?fù)涮卣鱐ab.1 Basic topological features of the experimental datasets

3.2 節(jié)點(diǎn)免疫的網(wǎng)絡(luò)破壞性實(shí)驗(yàn)

本節(jié)對(duì)最終的NewCI中心性方法在6個(gè)真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)和結(jié)果分析。其中，各真實(shí)網(wǎng)絡(luò)中G(q)、C(q)隨著q值變化的情況描述如圖2，各方法在6個(gè)實(shí)驗(yàn)數(shù)據(jù)集中的執(zhí)行效率記錄如表2。

圖2 不同中心性方法在節(jié)點(diǎn)免疫的網(wǎng)絡(luò)破壞性實(shí)驗(yàn)中的表現(xiàn)Fig.2 Performance of different centralities in network destructive experiments of node immunity

表2 各中心性方法在真實(shí)數(shù)據(jù)集中的執(zhí)行效率Tab.2 Execution efficiency of each centrality in real datasets

顯然，NewCI中心性度量方法的表現(xiàn)穩(wěn)定優(yōu)于CI中心性方法。如在圖2a Celegans網(wǎng)絡(luò)中，NewCI中心性在q約等于0.576時(shí)，網(wǎng)絡(luò)中G(q)的規(guī)模從43直接減小為22。而CI中心性方法完成這一變化，即達(dá)到相同的網(wǎng)絡(luò)破壞程度，網(wǎng)絡(luò)中刪除節(jié)點(diǎn)的比例q須達(dá)到0.623，可見NewCI方法較CI提高了約7.5%的性能。在圖2b power網(wǎng)絡(luò)中，q為0.10時(shí)，NewCI中心性使該網(wǎng)絡(luò)中G(q)的規(guī)模從1 088個(gè)節(jié)點(diǎn)急劇減小為629。而CI中心性的最優(yōu)分裂點(diǎn)在q=0.151處，此時(shí)網(wǎng)絡(luò)中G(q)的規(guī)模僅從856個(gè)節(jié)點(diǎn)減少到515個(gè)節(jié)點(diǎn)。同樣是使目標(biāo)網(wǎng)絡(luò)中的G(q)的規(guī)模達(dá)到網(wǎng)絡(luò)規(guī)模的10%，NewCI的性能相比CI大約提升了34%。在其他的實(shí)驗(yàn)數(shù)據(jù)集中的結(jié)論與此類似。

整體而言，在節(jié)點(diǎn)刪除的最初階段，G(q)隨著節(jié)點(diǎn)的刪除會(huì)劇烈減小，當(dāng)超過一個(gè)最優(yōu)的比例q之后，刪除節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的破壞作用減弱。而NewCI相比其他方法，曲線的下降趨勢(shì)更為快速。其中，該方法在Celegans、Power、Literature_1976以及Sawmill 4個(gè)網(wǎng)絡(luò)集中均為最佳；在Citeseer和ModMath中的表現(xiàn)也僅以微弱差距次于BC中心性方法；在所有數(shù)據(jù)集上都領(lǐng)先于CI，充分證明了其對(duì)節(jié)點(diǎn)影響力大小評(píng)估的有效性和準(zhǔn)確性。與G(q)相對(duì)應(yīng)，C(q)在最初階段隨著q的增加急劇增加，達(dá)到極值之后，呈現(xiàn)減小趨勢(shì)。在該指標(biāo)之下，本文的NewCI中心性在Power、Literature_1976、Sawmill以及ModMath 4個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上的表現(xiàn)同樣明顯優(yōu)于CI中心性，在其他兩個(gè)數(shù)據(jù)集中，也能取得和CI相當(dāng)?shù)男Ч?/p>

從表2各方法的執(zhí)行效率來看，NewCI中心性的執(zhí)行時(shí)間比與經(jīng)典的BC、CC方法更短，與其他方法的執(zhí)行時(shí)間同處一個(gè)數(shù)量級(jí)。

綜上所析，在所有中心性方法的對(duì)比中，以NewCI中心性方法與BC中心性方法的表現(xiàn)最好。NewCI中心性于各個(gè)類型的網(wǎng)絡(luò)中的表現(xiàn)均能穩(wěn)定地優(yōu)于CI中心性，肯定了該方法對(duì)CI中心性方法性能的提升，同時(shí)也驗(yàn)證了其在度量節(jié)點(diǎn)影響力問題上的有效性，以及在應(yīng)用網(wǎng)絡(luò)方面的普適性。較短的執(zhí)行時(shí)間，使得其在較大規(guī)模的網(wǎng)絡(luò)中依然可行。

4 總結(jié)與展望

從節(jié)點(diǎn)免疫的網(wǎng)絡(luò)破壞性角度來看，NewCI中心性較CI中心性表現(xiàn)出更高的有效性和普適性，打破了CI中心性方法僅適用于樹狀網(wǎng)絡(luò)的局限。與各中心性方法相比，該方法與BC中心性方法展示出最佳的性能。綜合有效性、時(shí)間復(fù)雜度及執(zhí)行效率三者考慮，NewCI中心性則優(yōu)于其他中心性方法。

近年來，網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)興起，逐步成為解決大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)網(wǎng)絡(luò)數(shù)據(jù)的有效手段。基于網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力更為準(zhǔn)確和快速的評(píng)估，以適用于多關(guān)系網(wǎng)絡(luò)等新型網(wǎng)絡(luò)，將是本文下一步的研究任務(wù)。