楊國軍

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

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

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

0?引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5?結(jié)語

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

參考文獻(xiàn)

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

[2]葉春森，汪傳雷，劉宏偉，等.網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)價(jià)方法研究[J].統(tǒng)計(jì)與決策，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é)點(diǎn)重要性的評(píng)價(jià)方法[J].通信學(xué)報(bào)，2004，（08）：129134.

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

[6]張品，董志遠(yuǎn)，沈政，等.用于評(píng)價(jià)通信網(wǎng)節(jié)點(diǎn)重要性的多參數(shù)優(yōu)化算法[J].計(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]于會(huì)，劉尊，李勇軍，等.基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性綜合評(píng)價(jià)方法[J].物理學(xué)報(bào)，2013，62（02）：5462.

[13]韓忠明，吳楊，譚旭升，等.面向結(jié)構(gòu)洞的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)排序[J].物理學(xué)報(bào)，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.