一種基于局部中心性的網(wǎng)絡(luò)關(guān)鍵節(jié)點識別算法

鄭文萍 吳志康 楊 貴

1(山西大學計算機與信息技術(shù)學院 太原 030006)2(計算智能與中文信息處理教育部重點實驗室(山西大學) 太原 030006)3(山西大學大數(shù)據(jù)科學與產(chǎn)業(yè)研究院 太原 030006)

近年來,對各種復(fù)雜網(wǎng)絡(luò)的研究是許多領(lǐng)域關(guān)注的熱點之一,如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等已成為眾多學者的主要研究對象[1-4].研究發(fā)現(xiàn)網(wǎng)絡(luò)機能往往受網(wǎng)絡(luò)中一小部分節(jié)點的影響,這部分節(jié)點的功能失效會導(dǎo)致網(wǎng)絡(luò)性能下降.并且這部分節(jié)點的失效影響會快速波及到整個網(wǎng)絡(luò),并最終使網(wǎng)絡(luò)陷入癱瘓.基于此，對網(wǎng)絡(luò)連通性至關(guān)重要的那部分節(jié)點被稱為關(guān)鍵節(jié)點.此外,關(guān)鍵節(jié)點識別是分析與理解網(wǎng)絡(luò)特性、結(jié)構(gòu)以及功能的重要方式[5-6],且在發(fā)現(xiàn)藥物靶點、發(fā)現(xiàn)關(guān)鍵蛋白質(zhì)、控制傳染病的爆發(fā)以及快速定位恐怖組織等方面意義重大[7-9].因此如何在大規(guī)模網(wǎng)絡(luò)中快速搜索關(guān)鍵節(jié)點,并加強對關(guān)鍵節(jié)點的監(jiān)控和保護,對維持網(wǎng)絡(luò)性能、確保復(fù)雜系統(tǒng)功能可靠性與健壯性十分重要.

本文提出一種基于節(jié)點中心性的網(wǎng)絡(luò)關(guān)鍵節(jié)點識別算法框架(greedy algorithm for critical node problem, GCNP): 根據(jù)某種中心性指標得到網(wǎng)絡(luò)的點覆蓋集;從網(wǎng)絡(luò)中刪除點覆蓋集,并迭代選擇點覆蓋集中使網(wǎng)絡(luò)連通的節(jié)點對增加最少的節(jié)點向原網(wǎng)絡(luò)回添,直至點覆蓋集中節(jié)點滿足用戶給定的待刪除關(guān)鍵節(jié)點數(shù).為了更好地選擇初始的點覆蓋集,本文還提出了一種基于局部拓撲結(jié)構(gòu)特征的節(jié)點中心性度量(local neighbor centrality, LNC).實驗結(jié)果表明,采用合理的中心性度量指標選擇初始點覆蓋集可以有效提高關(guān)鍵節(jié)點識別性能,且本文所提的LNC指標能更準確地評估節(jié)點的重要性.

1 相關(guān)工作

網(wǎng)絡(luò)關(guān)鍵節(jié)點識別問題(critical node problem, CNP)形式化定義為:對于圖G=(V,E)和正整數(shù)k,確定節(jié)點子集S?V且|S|=k,使得導(dǎo)出子圖G[VS]中連通的節(jié)點對最少.確定一個網(wǎng)絡(luò)的包含k個節(jié)點的最優(yōu)子集S是NP困難問題[10].

節(jié)點中心性是刻畫節(jié)點關(guān)鍵性的重要指標.目前已經(jīng)提出許多節(jié)點重要性度量指標,包括度中心性(degree centrality, DC)[11]、介數(shù)中心性(between-ness centrality, BC)[12]、接近中心性(closeness centrality, CC)[13]、PageRank[14]等.其中度中心性是刻畫節(jié)點重要性最簡單的指標,文獻[15]表明在無標度網(wǎng)絡(luò)或指數(shù)網(wǎng)絡(luò)中,只存在小部分大度節(jié)點,這些節(jié)點具有較高的重要性;然而網(wǎng)絡(luò)中大多數(shù)節(jié)點都是小度節(jié)點,為了對這些節(jié)點重要性進行度量,需要考慮其更廣泛的拓撲結(jié)構(gòu)信息.介數(shù)中心性[6,12]定義為經(jīng)過一個節(jié)點的最短路徑占網(wǎng)絡(luò)所有最短路徑的比值,通常一個節(jié)點介數(shù)中心性越高,越有可能位于多個社區(qū)的“橋接”處,其對保證網(wǎng)絡(luò)連通性也越重要.接近中心性[13]通過計算節(jié)點到網(wǎng)絡(luò)其他所有節(jié)點的最短路徑長度來刻畫節(jié)點到網(wǎng)絡(luò)中心的趨近程度.通常節(jié)點的接近度中心性越高,表明該節(jié)點越趨近網(wǎng)絡(luò)的中心.盡管介數(shù)中心性和接近中心性較好地考慮了節(jié)點在網(wǎng)絡(luò)連通性方面的重要性,然而由于需要預(yù)先知道網(wǎng)絡(luò)的全局信息,計算復(fù)雜度高,不適用于大型復(fù)雜網(wǎng)絡(luò).

Chen等人[16]提出了LR中心性(LocalRank),通過考慮節(jié)點4階鄰域信息來衡量節(jié)點重要性.王建偉等人[17]綜合考慮節(jié)點自身度與鄰居節(jié)點的度數(shù)和來衡量節(jié)點重要性,稱為局部度和中心性(local degree sum centrality, LDS).LocalRank中心性僅考慮鄰域中節(jié)點個數(shù),局部度和中心性只考慮節(jié)點的度信息,兩者都忽略了鄰域中節(jié)點間的拓撲結(jié)構(gòu),無法有效識別網(wǎng)絡(luò)中關(guān)鍵節(jié)點的重要性.任卓明等人[18]綜合考慮節(jié)點的度數(shù)和聚集系數(shù),提出了一種基于鄰居信息與聚集系數(shù)的節(jié)點重要性評價算法.Kitsak等人[19]提出節(jié)點重要性取決于其在網(wǎng)絡(luò)中的位置,并指出經(jīng)過K殼(K-Shell, KS)分解得到的節(jié)點的殼值可以較好地刻畫了節(jié)點的重要性.目前已經(jīng)提出一系列擴展和改進的K殼指標[20-22].

Arulselvan等人[10]提出了一種基于貪心策略的關(guān)鍵節(jié)點識別算法,首先從網(wǎng)絡(luò)G=(V,E)中隨機選取節(jié)點構(gòu)成網(wǎng)絡(luò)的一個極大獨立集M,從其余節(jié)點中選擇添加后使導(dǎo)出子圖G[M]中連通節(jié)點對數(shù)增量最小的節(jié)點加入M,直到|M|=|V|-k為止.Addis等人[23]提出了一種基于貪心策略的多啟動關(guān)鍵節(jié)點識別算法,從網(wǎng)絡(luò)中刪除一個隨機選擇的點覆蓋集S(|S|>k);再從S中選擇使得網(wǎng)絡(luò)中連通節(jié)點對數(shù)增加最小的節(jié)點向原網(wǎng)絡(luò)回添.

基于貪心策略的關(guān)鍵節(jié)點識別方法可以在較短時間內(nèi)得到網(wǎng)絡(luò)中對連通性影響最大的k個關(guān)鍵節(jié)點,適用于大規(guī)模網(wǎng)絡(luò)中的關(guān)鍵節(jié)點識別問題.然而,上述基于貪心策略的算法中,隨機選擇初始節(jié)點獨立集或覆蓋集,結(jié)果存在較大的隨機性.同時隨機選擇的初始集合規(guī)模與最終目標集合規(guī)模相差較大,導(dǎo)致算法需要進行更多的回添節(jié)點操作.

采用合理的中心性指標選擇初始節(jié)點集合,可以有效解決貪心算法結(jié)果隨機性較大的問題.基于此,本文提出一種基于節(jié)點中心性的網(wǎng)絡(luò)關(guān)鍵節(jié)點識別算法框架GCNP:根據(jù)某種節(jié)點中心性指標選擇網(wǎng)絡(luò)的節(jié)點覆蓋集S;從網(wǎng)絡(luò)中刪除S,并迭代選擇S中使網(wǎng)絡(luò)連通的節(jié)點對增加最少的節(jié)點向原網(wǎng)絡(luò)回添,直到|S|=k為止.為了更好地選擇初始的節(jié)點覆蓋集,本文還提出了一種基于局部拓撲結(jié)構(gòu)特征的節(jié)點中心性度量指標LNC.在真實網(wǎng)絡(luò)數(shù)據(jù)集和人工網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果表明,采用合理的中心性指標選擇初始點覆蓋集可以有效提高關(guān)鍵節(jié)點識別性能.在GCNP算法框架下,將本文所提的LNC指標與度中心性(DC)、LocalRank中心性(LR)、K殼中心性(KS)、局部度和中心性(LDS)相比較,發(fā)現(xiàn)LNC指標能更準確地評估節(jié)點的重要性.

2 背景知識

定義1.復(fù)雜網(wǎng)絡(luò).可以用圖G=(V,E)來表示,其中節(jié)點集V={v1,v2,…,vn},邊集E={(vi,vj)| 1≤i,j≤n}代表網(wǎng)絡(luò)個體間聯(lián)系的集合.|V|和|E|分別為圖G的節(jié)點數(shù)和邊數(shù).節(jié)點vi的鄰域Г(vi)={vj|(vi,vj)∈E,vj∈V}.Г(vi)中的節(jié)點稱為節(jié)點vi的鄰居節(jié)點,節(jié)點vi的度di=|Г(vi)|.除非特別指明,本文僅考慮簡單無向圖.

在無向圖G中,如果從節(jié)點vi到節(jié)點vj有路徑,則稱vi和vj是連通的.如果對于圖G中的任意2個節(jié)點vi,vj∈V,vi和vj都是連通的,則稱圖G是連通的.對于一個包含由m個節(jié)點的連通圖,連通節(jié)點對數(shù)為m(m-1)2.vi和vj之間的距離就是2個節(jié)點之間最短路徑的長度.

對圖G=(V,E)和G′=(V′,E′),如果V′?V且E′?E,則稱G′是G的子圖,記作G′?G.若G′是以V′為頂點集,以2個端點均在V′中邊的全體為邊集,則稱G′是G的導(dǎo)出子圖,并記為G[V′].

定義2.網(wǎng)絡(luò)關(guān)鍵節(jié)點識別問題[23].對于圖G=(V,E)和正整數(shù)k,確定包含k個節(jié)點的節(jié)點子集S?V,使得刪除子集S后,導(dǎo)出子圖G[VS]中的連通節(jié)點對最少.

LocalRank中心性[16]利用節(jié)點的4階鄰域內(nèi)所包含的信息刻畫節(jié)點在全局網(wǎng)絡(luò)中的重要性,是在權(quán)衡效率和性能的基礎(chǔ)上對度中心性的擴展.令N(vw)表示圖G中與節(jié)點vw的距離不超過2的節(jié)點集合,定義

(1)

則節(jié)點vi的LocalRank中心性定義為

(2)

其中,Г(vi)表示節(jié)點vi的鄰居節(jié)點集合.

3 基于節(jié)點中心性的關(guān)鍵節(jié)點識別算法

3.1 問題定義

定義3.關(guān)鍵節(jié)點問題(CNP).對無向圖G=(V,E),確定一個節(jié)點子集S?V,使得|S|≤k且從G中刪除S所得的導(dǎo)出子圖G[VS]中連通節(jié)點對數(shù)f(S)最小.其中

(3)

Ci表示刪除集合S后G[VS]中的第i個連通分量,δi是連通分量Ci中的節(jié)點數(shù).

3.2 GCNP算法框架

由于確定一個網(wǎng)絡(luò)的包含k個節(jié)點的最優(yōu)子集S是NP困難問題.為了在合理的時間得到一個較優(yōu)的大小為k的關(guān)鍵節(jié)點集合,本文提出一個基于局部中心性的關(guān)鍵節(jié)點識別算法框架 (greedy algorithm for critical node problem, GCNP).

GCNP迭代選擇中心性指標最高的節(jié)點加入集合S,直至S成為網(wǎng)絡(luò)的一個點覆蓋集,通常|S|>k.迭代地從S中選擇使得網(wǎng)絡(luò)連通節(jié)點對增加最小的節(jié)點回添至原網(wǎng)絡(luò),直到|S|=k.基于節(jié)點中心性指標的關(guān)鍵節(jié)點識別算法框架GCNP(σ)如算法1所示,其中σ代表某種中心性指標,如度中心性、介數(shù)中心性、LocalRank中心性等.

算法1.GCNP(σ)算法框架.

輸入:網(wǎng)絡(luò)G=(V,E)、正整數(shù)k、中心性指標σ;

輸出:節(jié)點子集S?V,且|S|=k.

Step1.S=?,V′=V;

Step2. 計算V′中每個節(jié)點的中心性指標值σ(vx);

Step4. 令S=S∪{vi},V′=V′{vi};

Step5. 若G的導(dǎo)出子圖G[VS]中存在邊,轉(zhuǎn)Step2;

Step6. 根據(jù)式(3)計算f(S),若|S|≤k,轉(zhuǎn)Step10;

Step7. 對S中的每個節(jié)點計算f(S{vx});

Step9.S=S{vi},若|S|>k,轉(zhuǎn)Step7;

Step10. 輸出S.

任何一種節(jié)點中心性指標σ都是從不同角度衡量了節(jié)點在特定拓撲特征下的關(guān)鍵性.σ值越高,節(jié)點越有可能是關(guān)鍵節(jié)點.如果將網(wǎng)絡(luò)節(jié)點僅按照某種中心性指標σ值由高到低排序,并選擇前k個節(jié)點作為關(guān)鍵節(jié)點集,可能會遺漏一些σ值不高但對網(wǎng)絡(luò)連通性比較關(guān)鍵的節(jié)點.

為了提高關(guān)鍵節(jié)點識別性能,GCNP(σ)算法中按照某種中心性指標σ選擇網(wǎng)絡(luò)的一個初始點覆蓋集合S,并按照目標函數(shù)選擇S中對網(wǎng)絡(luò)連通性影響最小的節(jié)點回添.表1給出了在部分人工網(wǎng)絡(luò)數(shù)據(jù)[23]上分別采用σ指標和本文GCNP(σ)算法選擇k個關(guān)鍵節(jié)點,刪除這些節(jié)點后原網(wǎng)絡(luò)的連通點對數(shù),其中σ采用本文第1節(jié)給出的度中心性(DC)、LocalRank中心性(LR)、K殼中心性(KS)、局部度和中心性(LDS).從表1可以看出,GCNP(σ)在關(guān)鍵節(jié)點識別性能方面有非常大的改進.

網(wǎng)絡(luò)中節(jié)點的中心性與節(jié)點度及其鄰域拓撲結(jié)構(gòu)密切相關(guān).這使得度中心性不足以準確度量節(jié)點在網(wǎng)絡(luò)連通方面的重要性,LocalRank中心性統(tǒng)計了節(jié)點vi的4步鄰域中的節(jié)點數(shù),并沒有考慮其鄰域節(jié)點間的拓撲結(jié)構(gòu).K殼中心性通常將網(wǎng)絡(luò)中節(jié)點劃分為不同的層次,無法區(qū)分同一層次中包含的大量節(jié)點的中心性.局部度和中心性沒有考慮節(jié)點鄰域連接的緊密程度對其中心性的影響.

Table 1 Pairwise Connectivity of σ and GCNP(σ) 表1 σ與GCNP(σ)在各指標上的連通節(jié)點對數(shù)

為了更合理地對網(wǎng)絡(luò)節(jié)點的中心性進行度量,進一步利用節(jié)點的度和鄰域拓撲結(jié)構(gòu)提出基于節(jié)點局部中心性的度量指標LNC.

4 節(jié)點的局部中心性(LNC)度量

為了更好地利用節(jié)點度和鄰域拓撲結(jié)構(gòu)對節(jié)點中心性進行度量,本文提出一種節(jié)點的局部中心性度量指標LNC,衡量節(jié)點對網(wǎng)絡(luò)連通性的影響.如果一個節(jié)點對網(wǎng)絡(luò)連通性影響越大,則與該節(jié)點關(guān)聯(lián)的邊通常對局部網(wǎng)絡(luò)連通性影響越大.因而,可以通過節(jié)點所連邊對局部網(wǎng)絡(luò)連通性的影響來反映該節(jié)點在網(wǎng)絡(luò)連通性方面的重要性,節(jié)點所連邊的重要性越高,該節(jié)點往往越重要.基于此,本文首先考慮網(wǎng)絡(luò)中邊權(quán)重.對邊(vi,vj)∈E而言,節(jié)點vi和vj度越大,則該邊權(quán)重越大;節(jié)點vi和vj之間公共鄰居節(jié)點越少,則邊(vi,vj)對vi與vj之間的連通性影響越大,其權(quán)重也越大.式(4)給出了邊權(quán)重的定義.

令vi和vj是網(wǎng)絡(luò)中的2個節(jié)點,其權(quán)重wi,j定義為

(4)

其中Г(vi)是節(jié)點vi的鄰居節(jié)點集合,di為節(jié)點vi的度數(shù),|Γ(vi)∩Γ(vj)|表示節(jié)點vi和節(jié)點vj之間的公共鄰居節(jié)點數(shù).

如圖1所示網(wǎng)絡(luò)[24]中的2條邊(v10,v20)和(v19,v17),其中d10=d19=4且d20=d17=3.盡管2條邊對應(yīng)度相同,但由于|Γ(v10)∩Γ(v20)|=0,而|Γ(v19)∩Γ(v17)|=1,且v15的度數(shù)較大,因而有w10,20>w19,17,即邊(v10,v20)對網(wǎng)絡(luò)連通性的重要性大于邊(v19,v17).

Fig. 1 The topological structure of an example network圖1 示例網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

(5)

其中Г(vi)是節(jié)點vi的鄰居節(jié)點集合,di為節(jié)點vi的度數(shù),wi,j為式(4)給出的(vi,vj)的權(quán)重.可以看出,一條邊對其關(guān)聯(lián)度數(shù)較高的節(jié)點權(quán)重貢獻更大.

式(5)所定義的局部鄰域中心性指標LNC，綜合考慮了節(jié)點的度信息及其鄰域節(jié)點間的拓撲結(jié)構(gòu).

表2給出了圖1所示網(wǎng)絡(luò)在一些經(jīng)典中心性度量指標下排名最高的4個重要節(jié)點集合S,以及從網(wǎng)絡(luò)中刪除S后對應(yīng)的連通分支數(shù)和連通節(jié)點對數(shù)f(S),可以看出本文給出的LNC指標表現(xiàn)出良好的性能.

在第5節(jié),將利用度中心性、LocalRank中心性、 K殼中心性、局部度和中心性與本文所提的LNC指標在GCNP(σ)算法框架下生成初始點覆蓋集S,比較它們在人工網(wǎng)絡(luò)和真實網(wǎng)絡(luò)上對網(wǎng)絡(luò)連通性的影響.

Table 2 Critical Node Sets Determined by Index σ onExample Network表2 示例網(wǎng)絡(luò)上按指標σ選取關(guān)鍵節(jié)點集結(jié)果

Note:S—the critical node set;p—connected component number in the residual graphG[VS];f(S)—the pairwise connectivity ofG[VS].

5 實驗與結(jié)果

在人工網(wǎng)絡(luò)數(shù)據(jù)集[23]和真實網(wǎng)絡(luò)數(shù)據(jù)集上對本文所提算法框架GCNP和LNC指標做有效性驗證.人工網(wǎng)絡(luò)數(shù)據(jù)集包括16個人工網(wǎng)絡(luò),依據(jù)不同的網(wǎng)絡(luò)結(jié)構(gòu)可以分為4種類型,網(wǎng)絡(luò)節(jié)點數(shù)為250～5 000不等,具體信息見表3.參數(shù)k的選取范圍是k∈{5,10,20,30,50,75,100,150,200,300,500,1 000,1 500,3 000}且k<|V|.排除掉刪除k個節(jié)點后所得的網(wǎng)絡(luò)中不存在連通的點對的情況,可以得到人工網(wǎng)絡(luò)與不同k組合共156個案例.

Table 3 Artificial Network Datasets[23]表3 人工網(wǎng)絡(luò)數(shù)據(jù)集[23]

Notes:|V|—node number; |E|—edge number;k—a preset integer, it determines the size of the critical node setS.

真實網(wǎng)絡(luò)數(shù)據(jù)集包括9個真實世界網(wǎng)絡(luò),具體網(wǎng)絡(luò)信息見表4.考慮到真實網(wǎng)絡(luò)的復(fù)雜性,在此根據(jù)刪除節(jié)點占網(wǎng)絡(luò)節(jié)點總數(shù)的比值確定參數(shù)k,具體為:k∈{0.01|V|,0.05|V|,0.1|V|,0.15|V|,0.2|V|,0.25|V|,0.3|V|}.排除掉刪除k個節(jié)點后所得的網(wǎng)絡(luò)中不存在連通的點對的情況,可以得到真實網(wǎng)絡(luò)與不同k組合共72個案例.

Table 4 Real Network Datasets表4 真實網(wǎng)絡(luò)數(shù)據(jù)集

Notes:|V|—node number; |E|—edge number;d—average degree;C—clustering coefficient;r—degree assortativity.

采用文獻[31]給出的效能函數(shù)對算法性能進行評價.算法A在測試數(shù)據(jù)集所有案例集合T上的效能函數(shù)定義為

(6)

其中,A(I)表示算法A在某一案例I上的結(jié)果,在本文中A代指在GCNP框架下所對應(yīng)的各個指標,BEST(I)表示在案例I上所有對比算法中獲得的最好結(jié)果.效能函數(shù)曲線上的點(n,PA(n))表示算法A的計算結(jié)果與最優(yōu)結(jié)果的相對誤差不超過2n-1的情況下測試案例所占比例.可以看出相對誤差是關(guān)于n的指數(shù)函數(shù),表5列出了n∈[0,0.6]時相對誤差的取值.

Table 5 Relative Errors of Performance Profile (n∈[0,0.6])表5 效能函數(shù)相對誤差(n∈[0,0.6])

當評價算法A和A′的性能時,如果算法A的效能函數(shù)曲線位于A′效能函數(shù)曲線的左上方,則認為算法A優(yōu)于算法A′.

圖2給出了GCNP(σ)算法分別在人工網(wǎng)絡(luò)數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集上的效能函數(shù)曲線圖.從圖2(a)所示人工網(wǎng)絡(luò)數(shù)據(jù)集上的函數(shù)曲線,可以看出本文所提局部中心性指標LNC在關(guān)鍵節(jié)點識別方面表現(xiàn)良好.當n=0(相對誤差為0%)時,算法GCNP(LNC)在49%的人工網(wǎng)絡(luò)案例上達到最好的效果,明顯優(yōu)于其他指標.當n=0.14(相對誤差為10%)時,GCNP(LNC)在將近91%的案例上達到較好的效果,也明顯優(yōu)于其他指標.

Fig. 2 The curves of performance profiles of GCNP(σ) under 5 centralities圖2 GCNP(σ)在不同指標下的效能函數(shù)曲線

在真實網(wǎng)絡(luò)數(shù)據(jù)集上也可以得到類似的結(jié)論.如圖2(b),當n=0(相對誤差為0%)時,算法GCNP(LNC)在26%的人工網(wǎng)絡(luò)案例上達到最好的效果,明顯優(yōu)于其他指標.當n=0.14(相對誤差為10%)時,GCNP(LNC)在將近76%的案例上達到較好的效果,也明顯優(yōu)于其他指標.

表6給出了算法GCNP(σ)在人工網(wǎng)絡(luò)數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集部分案例上對應(yīng)的5個中心性指標上重復(fù)實驗30次所得的最佳結(jié)果.可以看出,通過刪除由算法GCNP(LNC)所得到的關(guān)鍵節(jié)點集合能夠使大多數(shù)網(wǎng)絡(luò)上剩余圖上連通節(jié)點對數(shù)達到最小.

Table 6 Pairwise Connectivity of GCNP(σ) on 5 Centralities表6 GCNP(σ)算法在各中心性指標下所得的連通節(jié)點對數(shù)

Note： The best results are in bold.

6 總 結(jié)

本文提出了一種基于節(jié)點中心性的網(wǎng)絡(luò)關(guān)鍵節(jié)點識別搜索框架GCNP,根據(jù)某種中心性指標選擇網(wǎng)絡(luò)的初始點覆蓋集;從網(wǎng)絡(luò)中刪除該點覆蓋集,迭代選擇點覆蓋集中使網(wǎng)絡(luò)連通節(jié)點對增加最小的節(jié)點向原網(wǎng)絡(luò)回添,直至點覆蓋集中節(jié)點滿足用戶給定的待刪除關(guān)鍵節(jié)點數(shù).為了更好地選擇初始的節(jié)點覆蓋集,本文還提出了一種基于局部拓撲結(jié)構(gòu)特征的節(jié)點中心性度量指標LNC.在16個人工網(wǎng)絡(luò)和9個真實網(wǎng)絡(luò)上的實驗結(jié)果表明,采用GCNP算法可以提高算法性能.本文所提的節(jié)點中心性度量指標LNC較度中心性、LocalRank中心性、K殼中心性、局部度和中心性更能準確地評估節(jié)點的重要性.

近年來,復(fù)雜網(wǎng)絡(luò)呈現(xiàn)出大規(guī)模和動態(tài)性的特點,如何設(shè)計合理的算法以有效識別大規(guī)模動態(tài)復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點是CNP問題面臨的一大挑戰(zhàn).我們也將就這一問題開展深入探索.