復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法綜述

楊國軍

摘?要：文章基于國內(nèi)外學(xué)者對復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別的研究，對其方法進(jìn)行了分析總結(jié)。根據(jù)針對的網(wǎng)絡(luò)類型不同，將其分為四大類，分別為：無向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法、無向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法、有向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法和有向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法。通過梳理得知目前對復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別的研究已經(jīng)相當(dāng)成熟尤其是針對無向無權(quán)網(wǎng)絡(luò)，但是對于有向加權(quán)網(wǎng)絡(luò)的識別方法還相對較少。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；關(guān)鍵節(jié)點識別；梳理

中圖分類號：TB?????文獻(xiàn)標(biāo)識碼：A??????doi：10.19311/j.cnki.16723198.2023.12.087

0?引言

近年來，隨著復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點方法研究的不斷深入以及國內(nèi)外研究人員的不斷努力，針對如何有效識別關(guān)鍵節(jié)點提出了很多經(jīng)典的指標(biāo)和方法，根據(jù)不同網(wǎng)絡(luò)類型，可將其大致分為四大類。

（1）無向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別研究。

（2）無向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別研究。

（3）有向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別研究。

（4）有向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別研究。

1?無向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法研究

起初Freeman等人首先對社會網(wǎng)絡(luò)開展研究并做了大量的相關(guān)試驗，此后隨著研究的逐漸成熟，又將復(fù)雜網(wǎng)絡(luò)的節(jié)點重要性研究進(jìn)一步擴(kuò)展至科學(xué)領(lǐng)域和網(wǎng)絡(luò)搜索領(lǐng)域，并對該領(lǐng)域研究做出了巨大的貢獻(xiàn)。目前，對無向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法的研究相對成熟，國內(nèi)外學(xué)者從不同角度出發(fā)提出了很多方法。根據(jù)方法針對性的不同主要可以分為以下三類：社會網(wǎng)絡(luò)分析方法、系統(tǒng)科學(xué)分析方法、信息搜索分析方法。

1.1?基于社會網(wǎng)絡(luò)分析方法

基于社會網(wǎng)絡(luò)的分析方法的特點是，其在進(jìn)行節(jié)點重要性評估時主要強(qiáng)調(diào)的是將其重要性等價于其顯著性，同時，該類方法是以不破壞網(wǎng)絡(luò)結(jié)構(gòu)，保證網(wǎng)絡(luò)的完整性為前提的。例如葉春森等人利用賦權(quán)求和的方法，結(jié)合聚類系數(shù)和平均路徑來求得節(jié)點的重要值。但是由于在賦權(quán)時采用的是層次分析法，所以具有很強(qiáng)的人的主觀性，得到的結(jié)果會有一定的誤差。陳靜等人在評估網(wǎng)絡(luò)節(jié)點重要性時，同時考慮了局部和全局的信息流動。

在社會網(wǎng)絡(luò)分析法中，經(jīng)常用到節(jié)點的度、介數(shù)、緊密度等統(tǒng)計特性指標(biāo)。但Jin等人認(rèn)為這些指數(shù)只是節(jié)點某一個特性的表現(xiàn)，較為單一且不夠全面。比如度指數(shù)，節(jié)點的度反映的是與該節(jié)點直接相連的節(jié)點數(shù)量，而沒有考慮網(wǎng)絡(luò)中整體信息的流動。其后，F(xiàn)reeman又給出了一個考慮全局意義的指標(biāo)介數(shù)。該指標(biāo)通過計算最短路徑數(shù)來評價節(jié)點在全局的重要度。但是一旦研究的網(wǎng)絡(luò)為大型的復(fù)雜網(wǎng)絡(luò)，因為要計算網(wǎng)絡(luò)中任意節(jié)點相互之間的最短路徑數(shù)，其計算復(fù)雜性是相當(dāng)高的，這也導(dǎo)致了該指標(biāo)的使用受到限制。

1.2?基于系統(tǒng)科學(xué)分析方法

基于系統(tǒng)科學(xué)分析的方法是目前比較典型的一種識別方法。它是通過刪除網(wǎng)絡(luò)中的節(jié)點來觀察網(wǎng)絡(luò)連通性的變化，即網(wǎng)絡(luò)的連通性越差證明被刪除的節(jié)點越重要。即刪除該節(jié)點之后對網(wǎng)絡(luò)的損害范圍越大那么這個節(jié)點就更重要，反之則重要程度越低。其中節(jié)點刪除方法是最典型的系統(tǒng)科學(xué)分析類型，它避免了社交中不合理選擇屬性和指標(biāo)而導(dǎo)致的一些問題逆向思維的網(wǎng)絡(luò)分析。

這類方法還有很多，例如基于級聯(lián)失效的方法、“核和核度”理論、最小生成樹數(shù)目的節(jié)點刪除法等。張海艦提出基于級聯(lián)失效的方法，該方法是以網(wǎng)絡(luò)的完整性為前提的，將網(wǎng)絡(luò)發(fā)生級聯(lián)失效后的網(wǎng)絡(luò)狀態(tài)分為正常、過載、失效三個狀態(tài)，然后通過網(wǎng)絡(luò)效率的變化來評價節(jié)點重要性。“核和核度”理論是由許進(jìn)等人提出的，該理論將節(jié)點的集合看作為網(wǎng)絡(luò)中的一個“核”。而網(wǎng)絡(luò)中所有的核組成網(wǎng)絡(luò)“核度”，其代表著網(wǎng)絡(luò)的連通性，如果該“核”中的節(jié)點被損壞，就會引起網(wǎng)絡(luò)“核度”產(chǎn)生問題，進(jìn)而造成整體系統(tǒng)癱瘓。2004年，陳勇等人根據(jù)最小生成樹，給出了一個新的評價方法。這種方法在評價網(wǎng)絡(luò)中節(jié)點的重要度時，同樣是通過刪除節(jié)點的方式，但不同的是，這種評估方法要在刪除節(jié)點的同時，也要考慮最小生成樹隨著刪除節(jié)點數(shù)量是如何變化的，最小生成樹的數(shù)量變動越小，那么節(jié)點越重要在網(wǎng)絡(luò)中的重要性就越高。同年，李鵬翔等人根據(jù)刪除節(jié)點后，網(wǎng)絡(luò)結(jié)構(gòu)被破環(huán)的程度將其進(jìn)一步分為直接和間接。張品等人在對此進(jìn)一步進(jìn)行了優(yōu)化，將生成樹和度等特性相結(jié)合引入指標(biāo)評估體系中。

1.3?基于信息搜索分析方法

基于信息搜索分析的方法是根據(jù)互聯(lián)網(wǎng)中信息流動提出的，其比較常用的評價算法有兩種。其中一個是1998年Google創(chuàng)始人Brin和Page提出的PageRank算法，另一個是同年Kleinberg提出的HITS算法。這兩種方法不僅考慮了節(jié)點自身的特性，同時也考慮了鄰居節(jié)點對其的影響，通過驗證表明這兩種方法能夠很好的識別出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點。后人在這兩個經(jīng)典評估方法的基礎(chǔ)上，進(jìn)一步給出改善意見，進(jìn)而提出了多種有效的評估方法。其中，Lü等人以PageRank算法為基礎(chǔ)，將背景節(jié)點加入其中，解決了參數(shù)的影響。因為關(guān)鍵節(jié)點在數(shù)據(jù)傳播中扮演了至關(guān)重要的角色，基于此，近年來產(chǎn)生了許多新的評估方法。例如Kitsak等人提出的ks指標(biāo)，這種方法是通過將網(wǎng)絡(luò)中的節(jié)點按節(jié)點的度值進(jìn)行分層，度值相同的節(jié)點為同一層。節(jié)點的ks值就是層的表示，按節(jié)點度值分的層數(shù)越多ks值也就越大，那么該層內(nèi)的節(jié)點的重要性就越大。但是該指標(biāo)不具有一定的適用性，由于該方法按照度值進(jìn)行分層，雖然可以區(qū)別層間的節(jié)點重要性，但是層內(nèi)的節(jié)點重要性都是一樣的，而且該方法僅能應(yīng)用于無向無權(quán)網(wǎng)絡(luò)。

在特定的網(wǎng)絡(luò)環(huán)境下，以上的關(guān)鍵節(jié)點評估方法都能取得良好的評估效果，為復(fù)雜網(wǎng)絡(luò)節(jié)點重要性的研究打下了堅實的基礎(chǔ)。

2?無向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法研究

2.1?按對網(wǎng)絡(luò)邊信息的利用程度劃分

首先，Newman提出了一種針對于于無向有權(quán)網(wǎng)絡(luò)的評價指標(biāo)，而后LouXuyang等人在此基礎(chǔ)上，提出了一種基于同步的加權(quán)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，這種算法首先使網(wǎng)絡(luò)中的一部分節(jié)點開始震蕩，應(yīng)用矩陣來記錄被其影響的鄰居節(jié)點的震動情況，當(dāng)矩陣不再對稱時停止震蕩，記錄得到的最終結(jié)果。Biondel等人提出了一種基于模塊度的適用于較大規(guī)模加權(quán)復(fù)雜網(wǎng)絡(luò)的關(guān)鍵節(jié)點識別方法。除了對模塊度的擴(kuò)展外，Hoffman等人提出了將貝葉斯以及受約束的SBM相結(jié)合，提出一種適用于無向無權(quán)網(wǎng)絡(luò)的方法，隨后Jiang?Qixia等人將此方法進(jìn)一步擴(kuò)展到無向加權(quán)網(wǎng)絡(luò)中。隨著研究的進(jìn)一步深入，更多針對于加權(quán)網(wǎng)絡(luò)的方法涌現(xiàn)，比如Lu?Zongqin等人提出了一種基于Conductance的加權(quán)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法；Saha?Tanwistha等人提出了一種基于模糊聚類的識別方法；Cui?Aixiang等人利用加權(quán)的情感網(wǎng)絡(luò)提出了一種新的識別方法。

2.2?按能否發(fā)現(xiàn)重疊社區(qū)的劃分

前面所提到的大多數(shù)算法都屬于非重疊情況，因為這些算法考慮的因素比較單一，而現(xiàn)實中的網(wǎng)絡(luò)的節(jié)點一般包含多重信息，所以所取得的效果不是很明顯，為了使得算法更加有效，就需要考慮多重信息是否造成了重疊社區(qū)，以減少計算過程中所產(chǎn)生的誤差。

為了更加全面的考慮網(wǎng)絡(luò)中的信息，同時考慮重疊社區(qū)存在與否，國內(nèi)外學(xué)者提出了多種針對于此的關(guān)鍵節(jié)點識別方法。Palla等人提出的CPM算法是一種比較典型的算法。CPM算法是以參數(shù)k來表示子圖規(guī)模，然后從網(wǎng)絡(luò)中抽取所有的子圖，通過參數(shù)k來約束網(wǎng)絡(luò)中的社團(tuán)數(shù)量，根據(jù)約束條件對進(jìn)行矩陣多次迭代，看是否滿足約束條件，根據(jù)約束條件擴(kuò)大或者結(jié)合，直到最終達(dá)到穩(wěn)定的狀態(tài)。

3?有向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法研究

起初，針對于有向無權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法大都考慮的比較片面，后來學(xué)者為了克服這一缺點提出了很多具有代表性的方法。比如于會等人將度中心性、接近中性性、介數(shù)中心性以及結(jié)構(gòu)洞相結(jié)合，很好的解決傳統(tǒng)方法考慮條件單一的不足。但是由于該方法在評估各個指標(biāo)權(quán)重時用的是層次分析法，而層次分析法具有很強(qiáng)的主觀性，所以會對結(jié)構(gòu)造成一定的誤差。此外，韓忠明等人采用結(jié)構(gòu)洞理論通過ListNet排序方法將節(jié)點效率、網(wǎng)絡(luò)規(guī)模、聚類系數(shù)等七個指標(biāo)綜合起來，提出了一種針對于有向無權(quán)網(wǎng)絡(luò)的節(jié)點重要性排序方法，雖然這種方法能很好的識別出網(wǎng)絡(luò)中的重要節(jié)點，但是該方法的計算量很大，復(fù)雜性比較高，不適用于大型復(fù)雜網(wǎng)絡(luò)且不具有一定的普遍性。

4?有向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法研究

根據(jù)已有的研究成果，大部分評估方法都是針對于無向無權(quán)網(wǎng)絡(luò)的，但對有向加權(quán)網(wǎng)絡(luò)的發(fā)展仍有一定的幫助。例如Xu等人提出的DWCN-NodeRank指標(biāo)，該評價指標(biāo)是對PageRank的進(jìn)一步擴(kuò)展，其在考慮節(jié)點重要性時，能夠應(yīng)用在有向加權(quán)網(wǎng)絡(luò)中，其不僅考慮了網(wǎng)絡(luò)邊的方向，而且同時考慮了邊的權(quán)值。不過，這種算法的復(fù)雜性很高，針對大型網(wǎng)絡(luò)計算，其估計準(zhǔn)確度時算法可能不收斂。Liu等人通過分析網(wǎng)絡(luò)的局部結(jié)構(gòu)，即認(rèn)為與目標(biāo)節(jié)點直接相連的鄰居節(jié)點之間能夠進(jìn)行信息的流動，利用節(jié)點間信息的交互作用來作為指標(biāo)，最終計算節(jié)點所包含的信息量評價節(jié)點的重要性。不過，這種方法不能直接應(yīng)用于加權(quán)網(wǎng)絡(luò)，因為其并沒有考慮權(quán)值對網(wǎng)絡(luò)節(jié)點重要性的影響。對此，王班等人對前者的評價方法進(jìn)行了改進(jìn)，即在網(wǎng)絡(luò)的連邊上增加了權(quán)重系數(shù)，所以該方法能用于有向加權(quán)網(wǎng)絡(luò)的節(jié)點重要性評估。但是這兩種評價方法都僅考慮了鄰居節(jié)點的影響。而網(wǎng)絡(luò)中的信息交互不僅只存在于鄰居節(jié)點，與網(wǎng)絡(luò)中的節(jié)點同樣有信息交互作用。

矩陣經(jīng)常被用來研究網(wǎng)絡(luò)中節(jié)點之間相互作用，許多專家學(xué)者借助矩陣制定出了許多有效的評價方法。例如，周漩等人用節(jié)點效率和節(jié)點度來描述節(jié)點之間相互影響的關(guān)聯(lián)度，并將其作為評價因素構(gòu)建矩陣，通過將二者結(jié)合評價節(jié)點重要性。該方法將節(jié)點效率和節(jié)點度矩陣中的貢獻(xiàn)比平均分配，且僅考慮了鄰居節(jié)點的影響，與實際情況不符，不能在實際網(wǎng)絡(luò)中廣泛應(yīng)用。因此許多學(xué)者根據(jù)這點不足，同時考慮到非相鄰節(jié)點間也可能出現(xiàn)相互作用的影響情況，提出了更加全面的節(jié)點評價方法。例如，Hu等人提出的重要度貢獻(xiàn)關(guān)聯(lián)矩陣，以及范文禮等人提出的網(wǎng)絡(luò)傳輸效率矩陣，這兩種方法都從全局的角度分析節(jié)點的重要性，并用最短路徑來衡量全網(wǎng)對各個節(jié)點之間的信息貢獻(xiàn)比。由此可見，該評估方法由于將最短路徑引入其中，所以在一定程度上克服了只考慮鄰居節(jié)點的缺點。而實際上，最短路徑只是其中的一個因素，最短路徑的條數(shù)對網(wǎng)絡(luò)中節(jié)點的節(jié)點重要性貢獻(xiàn)同樣有一定的影響。

5?結(jié)語

通過對復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法的梳理和分析可知，目前對于復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點方法的研究已經(jīng)逐漸趨于成熟，尤其是針對于無向無權(quán)網(wǎng)絡(luò)的方法，而現(xiàn)實中大部分網(wǎng)絡(luò)是有向加權(quán)的，但目前對其研究的關(guān)鍵節(jié)點識別方法還不是很多，所以今后應(yīng)當(dāng)對有向加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法進(jìn)行研究補(bǔ)充，以解決現(xiàn)實生產(chǎn)生活中的實際問題。

參考文獻(xiàn)

[1]Freeman?L?C.A?set?of?measures?of?centrality?based?on?betweenness[J].Sociometry，1977：3541.

[2]葉春森，汪傳雷，劉宏偉，等.網(wǎng)絡(luò)節(jié)點重要度評價方法研究[J].統(tǒng)計與決策，2010，（01）：2224.

[3]Jin?J，Xu?K，Xiong?N，et?al.Multiindex?evaluation?algorithm?based?on?principal?component?analysis?for?node?importance?in?complex?networks[J].IET?networks，2012，1（3）：108115.

[4]陳勇，胡愛群，胡嘯，等.通信網(wǎng)中節(jié)點重要性的評價方法[J].通信學(xué)報，2004，（08）：129134.

[5]李鵬翔，任玉晴，席酉民，等.網(wǎng)絡(luò)節(jié)點（集）重要性的一種度量指標(biāo)[J].系統(tǒng)工程，2004，（04）：1320.

[6]張品，董志遠(yuǎn)，沈政，等.用于評價通信網(wǎng)節(jié)點重要性的多參數(shù)優(yōu)化算法[J].計算機(jī)工程，2013，39（06）：9598.

[7]Lü?L，Zhang?Y?C，Yeung?C?H，et?al.Leaders?in?social?networks，the?delicious?case[J].PloS?one，2011，6（6）：21202.

[8]Kitsak?M，Gallos?L?K，Havlin?S，et?al.Identification?of?influential?spreaders?in?complex?networks[J].Nature?physics，2010，6（11）：888893.

[9]Lou?X，Suykens?J?A?K.Finding?communities?in?weighted?networks?through?synchronization[J].Chaos：?An?Interdisciplinary?Journal?of?Nonlinear?Science，2011，21（4）：04311610431169.

[10]Jiang?Qixia，Zhang?Yan，Sun?Maosong.Community?detection?on?weighted?networks.avariational?Bayesian?method[A].Zhou?Z.H.and?Washio?T，ACML，2009，（5828）：176190.

[11]Lu?Zongqing，Wen?Yonggang，Cao?Guohong.Community?detection?in?weighted?networks：algorithms?and?applications[A].IEEE?International?Conference?on?Pervasive?Computing?and?Communications（PerCom）[C].San?Diego，USA：IEEE，2013，179184.

[12]于會，劉尊，李勇軍，等.基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性綜合評價方法[J].物理學(xué)報，2013，62（02）：5462.

[13]韓忠明，吳楊，譚旭升，等.面向結(jié)構(gòu)洞的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點排序[J].物理學(xué)報，2015，64（05）：429437.

[14]Xu?J，Li?J，Xu?S.Quantized?innovations?Kalman?filter：?stability?and?modificationwith?scaling?quantization[J].Journal?of?Zhejiang?University?SCIENCE?C，2012，13（2）：118130.

[15]Liu?Y，Jin?J，Zhang?Y，et?al.A?new?clustering?algorithm?based?on?data?field?in?complex?networks[J].The?Journal?of?Supercomputing，2014，67（3）：723737.