復雜網絡關鍵節點識別方法綜述

楊國軍

摘?要：文章基于國內外學者對復雜網絡關鍵節點識別的研究，對其方法進行了分析總結。根據針對的網絡類型不同，將其分為四大類，分別為：無向無權網絡關鍵節點識別方法、無向加權網絡關鍵節點識別方法、有向無權網絡關鍵節點識別方法和有向加權網絡關鍵節點識別方法。通過梳理得知目前對復雜網絡關鍵節點識別的研究已經相當成熟尤其是針對無向無權網絡，但是對于有向加權網絡的識別方法還相對較少。

關鍵詞：復雜網絡；關鍵節點識別；梳理

中圖分類號：TB?????文獻標識碼：A??????doi：10.19311/j.cnki.16723198.2023.12.087

0?引言

近年來，隨著復雜網絡關鍵節點方法研究的不斷深入以及國內外研究人員的不斷努力，針對如何有效識別關鍵節點提出了很多經典的指標和方法，根據不同網絡類型，可將其大致分為四大類。

（1）無向無權網絡關鍵節點識別研究。

（2）無向加權網絡關鍵節點識別研究。

（3）有向無權網絡關鍵節點識別研究。

（4）有向加權網絡關鍵節點識別研究。

1?無向無權網絡關鍵節點識別方法研究

起初Freeman等人首先對社會網絡開展研究并做了大量的相關試驗，此后隨著研究的逐漸成熟，又將復雜網絡的節點重要性研究進一步擴展至科學領域和網絡搜索領域，并對該領域研究做出了巨大的貢獻。目前，對無向無權網絡關鍵節點識別方法的研究相對成熟，國內外學者從不同角度出發提出了很多方法。根據方法針對性的不同主要可以分為以下三類：社會網絡分析方法、系統科學分析方法、信息搜索分析方法。

1.1?基于社會網絡分析方法

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

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

1.2?基于系統科學分析方法

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

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

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

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

在特定的網絡環境下，以上的關鍵節點評估方法都能取得良好的評估效果，為復雜網絡節點重要性的研究打下了堅實的基礎。

2?無向加權網絡關鍵節點識別方法研究

2.1?按對網絡邊信息的利用程度劃分

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

2.2?按能否發現重疊社區的劃分

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

為了更加全面的考慮網絡中的信息，同時考慮重疊社區存在與否，國內外學者提出了多種針對于此的關鍵節點識別方法。Palla等人提出的CPM算法是一種比較典型的算法。CPM算法是以參數k來表示子圖規模，然后從網絡中抽取所有的子圖，通過參數k來約束網絡中的社團數量，根據約束條件對進行矩陣多次迭代，看是否滿足約束條件，根據約束條件擴大或者結合，直到最終達到穩定的狀態。

3?有向無權網絡關鍵節點識別方法研究

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

4?有向加權網絡關鍵節點識別方法研究

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

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

5?結語

通過對復雜網絡關鍵節點識別方法的梳理和分析可知，目前對于復雜網絡關鍵節點方法的研究已經逐漸趨于成熟，尤其是針對于無向無權網絡的方法，而現實中大部分網絡是有向加權的，但目前對其研究的關鍵節點識別方法還不是很多，所以今后應當對有向加權網絡關鍵節點識別方法進行研究補充，以解決現實生產生活中的實際問題。

參考文獻

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

[2]葉春森，汪傳雷，劉宏偉，等.網絡節點重要度評價方法研究[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]陳勇，胡愛群，胡嘯，等.通信網中節點重要性的評價方法[J].通信學報，2004，（08）：129134.

[5]李鵬翔，任玉晴，席酉民，等.網絡節點（集）重要性的一種度量指標[J].系統工程，2004，（04）：1320.

[6]張品，董志遠，沈政，等.用于評價通信網節點重要性的多參數優化算法[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]于會，劉尊，李勇軍，等.基于多屬性決策的復雜網絡節點重要性綜合評價方法[J].物理學報，2013，62（02）：5462.

[13]韓忠明，吳楊，譚旭升，等.面向結構洞的復雜網絡關鍵節點排序[J].物理學報，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.