□布英塔

一、領(lǐng)域研究的背景

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

二、相關(guān)概念和理論

(一)復(fù)雜網(wǎng)絡(luò)節(jié)點重要性分析與表示。網(wǎng)絡(luò)是節(jié)點與節(jié)點相互連接形成的，所以節(jié)點也是網(wǎng)絡(luò)的核心元素。節(jié)點的重要性主要體現(xiàn)在節(jié)點在網(wǎng)絡(luò)中的所處的位置和連接方式體現(xiàn)。目前，對網(wǎng)絡(luò)節(jié)點重要性的測度指標(biāo)主要包括節(jié)點局部連接屬性測度和節(jié)點全局位置屬性測度。

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

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

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

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

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

三、評估方法簡述

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

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

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

(四)評價結(jié)果和模型分析討論。經(jīng)過詳細(xì)的分析驗證，基于度的評價結(jié)果和模型的角度，按節(jié)點的度值大小排列，也反映了節(jié)點的重要性。提出方案綜合考慮了節(jié)點在網(wǎng)絡(luò)中的整體和局部的重要性，目標(biāo)節(jié)點和各階鄰居節(jié)點對節(jié)點的重要度貢獻(xiàn)，方法具有較高的評估精度，做到了區(qū)分各節(jié)點的重要度差別。基于度和介數(shù)的評估結(jié)果和模型的角度，節(jié)點介數(shù)給出了網(wǎng)絡(luò)中通過某節(jié)點的最短路徑，體現(xiàn)了節(jié)點連通性能的聚集度。評估算法做到了有效評估網(wǎng)絡(luò)節(jié)點重要度，同時精確提取關(guān)鍵節(jié)點的地步。

四、結(jié)語

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

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

［2］董立珉，劉源，徐國棟．衛(wèi)星系統(tǒng)網(wǎng)絡(luò)節(jié)點的智能化設(shè)計［J］．光學(xué)精密工程，2013，4

［3］黃新波，羅兵，劉存孝．采用ZigBee 芯片的無線加速度傳感器網(wǎng)絡(luò)節(jié)點的實現(xiàn)［J］．高電壓技術(shù)，2010，8

［4］韋相和，印杰，李千目．天地一體化網(wǎng)絡(luò)節(jié)點的移動認(rèn)證協(xié)議設(shè)計［J］．南京理工大學(xué)學(xué)報(自然科學(xué)版)，2010，4

［5］肖衛(wèi)東，譚文堂，葛斌．網(wǎng)絡(luò)節(jié)點重要度的快速評估方法［J］．系統(tǒng)工程理論與實踐，2013，7