網絡節點重要度的快速評估方法探索

□布英塔

一、領域研究的背景

對于網絡節點重要度的快速評估的問題上，國內外大量專家學者做了大量的研究。分析社會網絡時，認為節點的重要性與目標節點和剩余節點的連接而具有的顯著性是可以等同認知的。隨后又有學者提出研究網絡核度與節點數、邊數的關系的核度測量方法。之后的研究綜合了多方面的因素，包括介數、節點度、鄰接節點度數等，加權求得節點的重要度評估。當前關于復雜網絡節點重要度的研究，還是集中在特定結構網絡中重要性指標的選取上;在節點重要性內涵以及重要性影響因素等方面還沒有形成一致的認知;而且對節點重要度的指標的信度測量方面的研究相對較少。

二、相關概念和理論

(一)復雜網絡節點重要性分析與表示。網絡是節點與節點相互連接形成的，所以節點也是網絡的核心元素。節點的重要性主要體現在節點在網絡中的所處的位置和連接方式體現。目前，對網絡節點重要性的測度指標主要包括節點局部連接屬性測度和節點全局位置屬性測度。

(二)節點度。假設G = {V，L}，是一個無向連通的網絡，V 代表網絡中所有節點的集合;L 代表該網絡中鏈接所有節點的邊的集合，同時滿足。節點度是指和該節點相關聯的邊的數量，記作k。其中節點的入度是指進入該節點的邊的數量;節點的出度是指從該節點出發的邊的數量。節點的度值能夠直接反映節點的重要度的觀點得到了廣泛的認知，而且存在一定的規律:節點的度值越高，說明該店的重要程度越高。

(三)節點介數。節點介數是指網絡中所有最短路徑中經過該節點的路徑的數目占最短路徑總數的比例。主要用來描述網絡節點重要性程度，可以給出網絡之中通過某一節點的最短路徑。目前，研究表明，節點的介數越大，其影響力和重要程度就會越大。

(四)階鄰居節點。鄰居節點是相對于傳輸距離或傳輸跳數而言的，在一定范圍內的就可以稱之為鄰居節點。一個復雜的網絡，例如G={V，L}，對于其中的任意一個節點，它的1 階鄰居節點是與該節點距離為1 的節點，此類節點的集合就是1 階鄰居節點的集合。同理可以類推，與該節點距離為m 的節點稱為m 階鄰居節點。

(五)最短路徑。最短路徑主要是用來計算一個節點到其他所有節點的距離中最近的路徑。通常情況下，采用Dijkstra 算法算出最短路徑的最優解，但是因為它計算的節點比較多，效率偏低。

(六)節點對數目。節點對數目是指刪除任意節點后，網絡中該節點的鄰居節點集合中能保持連通的節點對數。依據在網絡中節點和邊的關系，此數值為正整數。當其數值比較大時，說明刪除該節點后網絡的連通性能依舊保持良好，則可以說明該節點自己本身的重要性很小。其主要反映了節點的局部聯通情況，可以用來描述網絡節點的重要性。

三、評估方法簡述

(一)節點重要度評估方法。從另一個領域，空間自相關的方向上來講，兩個對象之間的距離越接近，其之間的依賴就會越強。所以可以認為:距離目標節點越近的節點對目標節點重要性的貢獻就會越大。現在既有的研究發現，存在很大一部分的復雜系統的一些特性會隨著距離的增加表現出衰減的趨勢，基本上符合指數衰減的規律。本文也假設在節點的重要度評估過程中，其鄰居節點的重要度貢獻隨距離的增加出現指數遞減的走向。當只考慮節點單一性質對重要性的影響時，對于任意節點，引入相應的蟲藥都測評函數。所用的評價函數要綜合考慮到節點本身和它的從1 到m 階的鄰居節點的重要度貢獻，此外，距離節點越遠，其重要度就會越小。一般來說，現實生活中評估目標的重要性時，基本上都會綜合全方面的影響。但是，網絡節點的重要性并不完完全全取決于節點的度、介數等特性指標，在涵蓋這些因素后做出的重要程度評估才更為精準，據此可以定義重要度評價模型。模型要包括用來表示節點以及各階鄰居節點對目標節點重要性貢獻程度的評估系數矩陣，包含節點和各階鄰居節點指標值的評估指標矩陣，以及權重矩陣。

(二)算法流程概述。考慮目標節點以及m 階鄰居節點對目標節點對節點的重要度貢獻，才會得到較為準確的評價結果。評估最關鍵的是意識到目標節點的度值等相關信息對評估的重要性，度值甚至可以表現節點的重要性。所以，在已知網絡，目標節點的鄰居節點深度，評估的指標集和權重矩陣，采用了下面的算法:一是根據網絡的結構關系，提取出節點的各階鄰居節點集。二是計算目標節點的鄰居節點集的指標數值，然后確定目標節點的評估指標矩陣。三是根據評估指標矩陣中每一類指標做出歸一化的處理，計算歸一化處理后的評估指標矩陣。四是根據選取的公式，計算各個節點的重要度。

(三)評估算法的分析。節點重要度評估方法，評估指標以及另據節點的深度都是影響評價結果的重要因素。展開來說，如果鄰居節點深度值太小，會出現過分依賴節點本身屬性的評價過程，導致忽略網絡位置信息對節點的影響，結果將會與傳統連接度的方法沒有太大差別。相反，取值太大的話，不僅會增加算法復雜程度，還會造成負面的影響。在評價指標的選擇問題上，反映節點重要性最主要的兩個參數分別為:節點的度和節點介數，本文也是以這兩個參數為評價指標建立的整個評價模型。

(四)評價結果和模型分析討論。經過詳細的分析驗證，基于度的評價結果和模型的角度，按節點的度值大小排列，也反映了節點的重要性。提出方案綜合考慮了節點在網絡中的整體和局部的重要性，目標節點和各階鄰居節點對節點的重要度貢獻，方法具有較高的評估精度，做到了區分各節點的重要度差別?；诙群徒閿档脑u估結果和模型的角度，節點介數給出了網絡中通過某節點的最短路徑，體現了節點連通性能的聚集度。評估算法做到了有效評估網絡節點重要度，同時精確提取關鍵節點的地步。

四、結語

在現實世界中，網絡形式的系統無處不在，從因特網、社會網絡到客戶關系網絡等，諸多的網絡環境，能夠盡可能地保證網絡的穩定性和可靠性，對我們的生活帶了頗多的益處。例如，當網絡中有多個節點同時發生故障時，需要考慮如何確定維修的先后順序，使網絡遭受的損失最小;因此，本文從基本理論和評估方法的現狀對快速評估網絡節點重要度提出了自己的看法，希望對提高復雜網絡中節點的可靠性和重要度有所幫助，也希望從業人員之間相互學習，共同成長。

［1］李海艦，董宏輝，張鵬飛．一種適用于道路交通的傳感器網絡節點語義編碼設計［J］．中南大學學報(自然科學版)，2013，6

［2］董立珉，劉源，徐國棟．衛星系統網絡節點的智能化設計［J］．光學精密工程，2013，4

［3］黃新波，羅兵，劉存孝．采用ZigBee 芯片的無線加速度傳感器網絡節點的實現［J］．高電壓技術，2010，8

［4］韋相和，印杰，李千目．天地一體化網絡節點的移動認證協議設計［J］．南京理工大學學報(自然科學版)，2010，4

［5］肖衛東，譚文堂，葛斌．網絡節點重要度的快速評估方法［J］．系統工程理論與實踐，2013，7