邵鐵林

(沈陽理工大學 信息科學與工程學院，遼寧 沈陽 110159)

基于復雜網絡拓撲結構的評估體系研究

邵鐵林

(沈陽理工大學 信息科學與工程學院，遼寧 沈陽 110159)

對復雜網絡拓撲結構中特定屬性的計算和評估進行了研究。層次分析法和熵權法被用來計算復雜網絡拓撲結構的權重，這樣既可以防止在主觀賦權法上因專家經驗不足使得對方案的排序造成很大的隨意性，又可以避免客觀賦權法的結果與實際情況不一致的現(xiàn)象發(fā)生。選取了規(guī)則網絡模型、隨機網絡模型、小世界網絡模型和BA無標度網絡模型進行加權計算，并計算出它們各自相應的綜合權重。從綜合權重的角度來看，實驗結果表明，隨機網絡效能最好，接下來是小世界網絡、無標度網絡，最后是規(guī)則網絡。該評估體系和算法可以被廣泛地用于需要對網絡性能進行定量評估的情況下。

主觀賦權法；客觀賦權法；組合賦權法；網絡性能評價

0 引言

目前對多屬性決策問題的權重確立已有許多方法，如何準確地對各個指標賦值，會直接影響到最終復雜網絡系統(tǒng)綜合權重結果的正確性。根據(jù)確定指標權重方法的不同，可以分為主觀賦權法、客觀賦權法和主客觀相結合的組合賦權法。主觀賦權法是由決策者的偏好給出的方法，如專家調查法[1-2]、層次分析法[3-4]、二項系數(shù)法[3]等都可以用來對復雜網絡進行系統(tǒng)評估。但是主觀賦權法有它自身的缺陷。比如由專家根據(jù)自己的經驗和判斷對目標賦以權值時，得到的不同方案之間的排序會出現(xiàn)一個很大的隨意性?？陀^賦權法是一種基于目標矩陣信息的方法，如熵權法[4]、離差及均方差法[5]等。但由于該方法沒有體現(xiàn)出決策者對諸多目標的重視程度，因此一些可以使不同方案顯示出明顯差異的目標，并沒有體現(xiàn)其重要性，甚至會出現(xiàn)截然相反的結果。

本文運用了第三種賦權方法：主客觀組合賦權法[6]。主客觀組合賦權法正好可以克服主觀的隨意性并避免客觀所得結果與實際不符的現(xiàn)象發(fā)生，可以使復雜網絡系統(tǒng)最終得到的綜合權重結果科學合理。在本文中，綜合了主觀賦權法中的層次分析法和客觀賦權法中的熵權法。列舉四種基本的復雜網絡模型：規(guī)則網絡模型[7]、隨機網絡模型[8]、小世界網絡模型[9]和BA無標度網絡模型[10]。在同樣目標條件下根據(jù)最終所得的綜合權值的大小對不同的復雜網絡模型進行排序。

1 復雜網絡拓撲結構模型的指標確立[11]

影響復雜網絡模型的因素有許多，應該盡可能選取少量但具有關鍵性的指標。在這里選取了魯棒性、可靠性、適應性和品質因素作為復雜網絡模型的評估指標。各指標的建立如圖1～圖4所示。

圖1 魯棒性評價指標圖

圖2 可靠性評價指標圖

圖3 適應性評價指標圖

圖4 品質因素評價指標圖

2 基于AHP層次分析法的指標權重計算方法

層次分析法其主要思想是將要達到的目標分解為多個具有代表性的指標，根據(jù)指標間的從屬性關系建立一個遞接層次結構模型，按層進行分析，最終獲得底端層指標相對于目標層的最終權重。

AHP法可分為4個步驟：

(1)根據(jù)復雜網絡系統(tǒng)中各因素之間的關系，將網絡分為3個層次，即目標層、準則層和措施層，并建立層次結構。

(2)對于同一層中各因素相對于上一層因素的重要性進行兩兩比較，構造權重判斷矩陣。

(3)由判斷矩陣計算得到各指標的權重，并進行一致性檢驗。其具體步驟如下：

①計算判斷矩陣的每一列，并進行規(guī)劃處理

②對判斷矩陣每一行進行求和

W=[W1，W2，…，Wn]T,即為所求特征向量。

④計算判斷矩陣的最大特征根

其中A是權重比矩陣。

(4)措施層的權重計算：

①準則層的權重為：w=(w1,w2,w3...wk)T，其中，wi為準則層指標i在準則層中所占有的相對權重。

②措施層指標權重為：wk=(wk1,wk2,wks…wkp)T，再以wk為列向量構成矩陣W=[w1,w2,…wn]。

③措施層的權重為：c=W·w,其中c為最終的權重值。

3 基于熵權法的指標權重計算方法

熵最早是用來描述熱力學第二定律，在1865年由克勞休斯引入。信息熵值反映了信息的不確定程度，可以度量信息量的多少。在復雜網絡效能評估時某一項指標帶有的信息量越多，表明該項指標對決策的作用越大，此時信息熵值越小。因此，可用信息熵評價所獲信息的有序度及其效用，即各評價指標的權重大小由評價指標值構成的判斷矩陣來確定。

熵權法的具體計算步驟如下：

(1)設一共有M個方案，本文中共有4個復雜網絡模型M=(M1,M2,M3,M4)。評價指標D=(D1,D2,D3,D4)，被評價的對象Mi對指標Dj的值記為Xij(i=1,2,3,4;j=1,2,3,4)。則形成的原始數(shù)據(jù)矩陣如下：

其中Xij為第j個指標下的第i個評價對象的值。

(2)對原始矩陣進行無量綱化處理，所得到的指標值越大表明評價對象在該項目上表現(xiàn)越好：

(4)計算第j項指標的熵值ej

其中，m為方案的個數(shù)，本文中共有4個方案，所以m=4。

(5)計算第j項指標的差異系數(shù)dj

dj=1-ej

dj越大，該指標所提供的信息量越大，越應該給予較大的指標權重。

(6)確定各指標的熵權

(7)分別計算各個評價對象的綜合評價值

4 組合賦權法計算權重

采用拉格朗日乘子法解決上述優(yōu)化問題:

5 應用實例

本文采用4種復雜網絡模型，它們對應著4個方案。分別是A：無標度網絡;B：小世界網絡;C：隨機網絡;D：規(guī)則網絡。

基于層次分析法的效能評估，根據(jù)第2節(jié)中所提到的方法，通過MATLAB來進行計算。以4種不同的復雜網絡模型為4種方案得到的各自指標權重，見表1～表4。

表1 實驗A的仿真結果(無標度網絡模型)

表2 實驗B的仿真結果(小世界網絡模型)

表3 實驗C 的仿真結果(隨機網絡模型)

表4 實驗D 的仿真結果(規(guī)則網絡模型)

最終通過層次分析法得到的4種方案的綜合權重為：Wi=[0.076 84,0.077 07,0.077 53,0.075 07]。

根據(jù)第3節(jié)介紹的熵權法，將魯棒性、可靠性、適應性、品質因素設為4個評價指標D=(D1,D2,D3,D4)，對于4種復雜網絡模型設定為4個不同的評價對象M=(M1,M2,M3,M4)。形成的判斷矩陣為：

最后得到的4種復雜網絡模型的權值向量為：

Vi=[0.240 42,0.256 04,0.276 52,0.227 02]

根據(jù)第4節(jié)介紹的組合賦權法，將層次分析法和熵權法的權重帶入組合賦權法的公式得到4種復雜網絡模型的效能權重。

A:W1=0.438 84

B:W2=0.524 27

C:W3=0.639 87

D:W4=0.350 89

最終根據(jù)組合賦權法得到了4種復雜網絡模型的權重，充分利用了兩種方法的優(yōu)點，同時又最大程度地避免了人為主觀性和客觀單一權重的片面性，使得綜合評價既合理又科學。根據(jù)組合賦權法得到4種方案各自的權重大小，對4種復雜網絡模型的效能進行排序，得到的結果是：C>B>A>D。即隨機網絡的效能要好于小世界網絡，小世界網絡要好于無標度網絡，而規(guī)則網絡的效能最差。結論符合實際情況，因此該評估系統(tǒng)可靠有效。

6 結論

在對復雜網絡拓撲結構進行效能評估時，利用將主觀賦權法和客觀賦權法相結合的思想，把層次分析法和熵權法的各自權重進行了科學、合理的結合。這既反映了專家對各評價指標的主觀意向，又包含了科學嚴謹?shù)臄?shù)學理論依據(jù)，便于計算處理。組合賦權法使得主觀判斷和客觀計算有了一個很好的結合。

[1] 聶相田,王博,駱原. Delphi專家法在施工監(jiān)理規(guī)范修訂中的應用[J]. 人民黃河,2010,32(12):240-242,247.

[2] 房鑫,郝艷華,吳群紅,等. 基于Delphi法的完善全民醫(yī)保制度要素設計專家意見分析[J]. 中國衛(wèi)生經濟,2016,35(2):29-31.

[3] 肖滿生,陽娣蘭,張居武,等. 基于模糊相關度的模糊C均值聚類加權指數(shù)研究[J]. 計算機應用,2010,30(12):3388-3390.

[4] 毛毅鋼. 基于熵權法的高校體育教師評價指標體系的建立[J]. 重慶理工大學學報(自然科學版),2015,29(1):150-154.

[5] 雷勛平,劉晨. 熵權法在高校實踐教學質量評價中的應用[J]. 蚌埠學院學報,2015,4(6):125-128.

[6] 謝軼. 組合賦權法確定清河流域總量減排績效評估指標權重[J]. 環(huán)境保護科學,2014,40(1):28-31.

[7] 王晨晨,姚軍,楊永飛,等. 基于規(guī)則網絡的碳酸鹽巖多尺度網絡模型構建方法研究[J]. 計算力學學報,2013,30(2):231-235.

[8] 姜志宏,王暉,高超. 一種基于隨機行走和策略連接的網絡演化模型[J]. 物理學報,2011,60(5):824-832.

[9] 張浩. 基于小世界網絡的高校知識轉移機理及擴散模型研究[J]. 情報科學,2011(9):1294-1297,1312.

[10] 吳泓潤,覃俊,易云飛,等. 基于優(yōu)化理論的社區(qū)無標度網絡模型[J]. 計算機學報,2015,38(2):337-348.

[11] 劉建香. 復雜網絡及其在國內研究進展的綜述[J]. 系統(tǒng)科學學報,2009,17(4):31-37.

Research on the assessment system based on complex network topological structures

Shao Tielin

(College of Information Science and Engineering, Shenyang Ligong University, Shenyang 110159, China)

A quantitative way of measuring and evaluating specific properties in complex networks topology is studied. By determining the weight of the complex network topology structure, both hierarchy process and entropy weight method were introduced to avoid incorrect results out of great randomness caused by experts who are lacking of experiences in the subjective weighting method, as well as to avoid the inconsistent output of objective weighting method with that of the real situations. Weighting method was performed on four different complex networks models including regular network model, random network model, small world network model and BA scale-free network model, and comprehensive weights of corresponding networks were calculated. The experimental results show that on comprehensive performance point of view, random network is the best followed by small world network, scale free network rank next and the regular network at last. The assessment systems and algorithms could be widely used in circumstances where quantitative evaluations of networks performances are required.

subjective weighting method; objective weighting method; combined weighting method; network performance evaluation

TP302.7

A

10.19358/j.issn.1674- 7720.2017.01.021

邵鐵林. 基于復雜網絡拓撲結構的評估體系研究[J].微型機與應用，2017,36(1)：69-72.

2016-08-05)

邵鐵林(1990-),男,碩士研究生,主要研究方向：無線網絡信息處理技術。