第一節 網絡節點重要性指標國內外研究進展

網絡節點重要性的度量，是社會網絡分析和系統科學研究領域一個引人關注的問題，許多學者從不同角度對此問題進行了研究，提出了各種指標對此進行了度量。文獻中常見的無尺度網絡（Baratasi, A. L., 1999）、“小世界”理論（Watts, D. J., 1998）、社交網絡（Dodds, P. S., et al., 2003）、生物網絡（Girvan, M., 2002）、交通網絡（Holms, P., 2003;Crucitti, P., et al., 2005; Porta, S., et al., 2005）、恐怖分子組織網絡（Drˇazen, P., 2005）等研究領域，都從不同角度討論了節點對網絡的影響。

社會網絡分析對這一問題的研究始于20世紀40年代末，其主流方法均基于這樣一個假設，即節點的重要性等價于該節點與其他節點的連接而使其具有的顯著性（Knoke, D., et al., 1983）。這些方法的基本思路是從網絡中尋找某種有用的屬性信息（如度、最短路、路徑中包含的信息量等）來凸顯網絡節點間的差異，也就是說，充分地反映出節點在網絡中的位置特性，放大網絡節點的顯著性以定義節點的重要性。

已提出的指標分為節點中心度（Centrality）和聲望（Prestige）兩大類，度量方法主要包括節點的度（Degree）、接近度（Closeness）、介數（Betweenness）、信息中心度（Information Centrality）、特征向量（Eigen-vector）和累計提名（Cumulated Nomination）等。

最簡單的節點中心度指標是節點的度，直接利用與節點相鄰接的邊數來度量節點的重要性，這顯然存在很多不足之處；節點的接近度被定義為該節點到其他所有節點距離之和的倒數，反映了節點在網絡中的居中程度（Wasserman, S., 1994）; Freeman, L. C.（1979）提出的介數指標反映了節點對其他節點的控制作用；Stephenson, K．和Zelen, M.（1989）提出的信息中心度指標類似于節點的接近度，但在計算時充分考慮了所有路徑中傳遞的信息流；Bonacich, P.（1972, 1987）提出的特征向量指標則是從網絡成員的地位或名望角度考慮，將單個成員的名望看成所有其他成員名望的線性組合從而得到一個線性方程組，該方程組的最大特征值所對應的特征向量就是各個節點的重要性指標；Poulin, R．等（2000）在對Bonacichi, P．求解特征向量的映射迭代方法改進的基礎上，提出了收斂速度更快、更穩定而且適用于大網絡和多分支網絡的累計提名指標。

以上指標中，特別值得關注的是介數指標，由于其在復雜網絡、社會網絡分析等領域的重要作用，與其相關的指標已經發展成了一個介數指標族。最早的介數指標被定義為網絡中通過節點的最短路數目占所有最短路的百分比。在信息完全按照最短路徑傳播的網絡中，介數指標刻畫了信息流經給定節點的可能性，可以用來度量節點對網絡中信息傳播的控制和影響；Newman, M. E. J.（2001）和Brandes, U.（2001）分別提出了計算介數的有效算法，對于具有m條邊和n個節點的網絡，所有節點的介數都可以在O（mn）的時間內求得，這也大大拓寬了介數的應用范圍。但在大多數現實世界的網絡中，信息并不是沿最短路徑傳播的（Stephenson, K. A., 1989），由于無法獲得網絡的所有結構信息，信息往往只是根據傳遞節點周圍的部分結構信息選擇路徑，因此路徑的選擇具有一定的隨機性（Milgram, S., 1967; Travers, J., 1969）。針對此問題，Freeman, L. C.等（1991）又提出了流介數指標（flow betweenness），利用最大流的概念來度量所有傳播路徑的貢獻；Newman, M. E. J.（2005）提出了隨機行走介數指標（random-walk betweenness），利用統計方法來研究部分結構信息下網絡節點重要性的度量；Noh, J. D．和Rieger, H.（2002）提出了隨機行走中心度（random-walk centrality），通過度量消息在網絡中傳播的速度來反映網絡節點的重要性。

近年的研究又有了新突破。Kitsak, M．等人（2010）提出同時考慮節點度數和位置的“k-殼分解法”（k-shell decomposition）, Hu, Q．等人（2013）將“k -殼分解法”與社區結構相結合，對其進行了改良；Chen, D. B．等人（2012, 2013）提出了一種基于半局部信息的半局部中心性節點重要性排序方法，其計算復雜度隨網絡規模線性增長，只需非常少的計算時間，就能夠得到遠好于度中心性和介數中心性的排序結果；Gao, C．等人（2013）用“D-S證據理論”將此方法推廣到了含權網絡；秦李等（2015）結合改進的主成分分析法和TOPSIS法提出了一種新復雜網絡中的節點重要性的綜合評價方法，并對ARPA網絡和美國航空網絡進行了實驗分析；任卓明等（2012）提出了基于度與集聚系數的網絡節點重要性度量方法，并分析了復雜網絡中最小K-核節點的傳播能力。

社會網絡分析方法是在保證網絡整體性的前提下進行指標研究的，而系統科學的研究方法則是用網絡的連通性來反映系統某種功能的完整性，通過度量節點刪除對網絡連通的破壞程度來反映網絡節點的重要性。

這種節點刪除的思想最早體現在圖論中反映圖的連通程度的指標連通度上（Bondy, J. A., 1981；吳望名、李念祖，1984），但具有相同連通度的兩個圖的連通程度實際上仍可能有相當的差異。為此，Chvatal, V.（1973）引入了圖的堅韌度（toughness）概念；歐陽克智等（1993）提出了圖的相對斷裂度；許進等（1993）提出的系統的核與核度理論是這方面主要的研究成果。該理論將系統抽象成網絡，定義系統的“核”為那些對系統功能來講具有重要的或支配性作用的，且一旦遭到破壞會使整個系統癱瘓或受到重大損失的節點或節點的集合，而“核度”的計算則通過點斷集和連通分支數來實現。其后，壽紀麟、李飛（1996）提出了針對節點加權連通網絡系統的點權核與點權核度；謝政、湯澤瑩（1997）提出了模糊連通度與模糊核度，對核與核度理論進行了擴展。這些參數較連通度而言更進了一步，但還存在不足，有些圖的這些參數相同，但連通程度不同。為了解決這個矛盾，許進等（1994）又提出了核冠與核能量的概念；Cozzens等（1995）提出了韌性度的概念；王志平、趙連昌等（1999, 2001）提出了離散度的概念；另外考慮到連通分支在大小和形狀上的差異，席酉民和唐方成（2002）提出了立體多核網絡的定義，將核度定義為立體多核網絡中核的拓撲勢的測度，但沒有給出核度的數學表達式或拓撲勢測度的具體方法；李鵬翔、任玉晴、席酉民（2004）用節點被刪除后形成的所有不連通節點對之間的距離（最短路）的倒數之和來計算指標的大小，對這一思想進行了量化。

綜上所述，研究節點重要性的方法主要有兩類。一類是社會網絡分析方法，將節點的“重要性等價為顯著性”，對指標的研究不破壞網絡的整體性且通常不考慮節點集的重要性；另一類是節點刪除的研究方法，將節點的“重要性等價為該節點被刪除后對網絡的破壞性”，指標的研究實際上考慮的是節點刪除前后圖的連通狀況發生的變化。

但以上這些方法考慮的都是節點對于整個網絡的重要性，沒有考慮節點對于某個目標節點集的重要性。因此所求解的問題只能是靜態的，這兩類方法關注的始終是整個網絡，而沒有考慮問題的動態特性，即在解決問題的過程中，在不同的階段或不同的子問題中關注的中心往往具有目標性和局域性。應急物流配送是這方面最典型的例子：在一次出救行車任務中，配送車輛不需要關注整個區域路網海量的道路細節，其關心的只是對于此次行車目標節點集重要的那部分道路地圖（即“出救點—應急物資儲備中心—災區需求點”及其沿線的道路網絡），而且突發事件中道路網絡節點常因次生衍生災害損毀無法通行，因此救援人員在應急物流配送的不同階段所關心的目標集也是動態變化的。為此，必須尋找度量節點對于目標節點集重要性的新指標，從而將節點對于目標節點的連通關系從節點對于整個網絡的連通關系中分離出來。