基于快速密度聚類的電力通信網(wǎng)節(jié)點重要性評估

狄 立，鄭 征，夏 旻，胡 凱

?

基于快速密度聚類的電力通信網(wǎng)節(jié)點重要性評估

狄 立1，鄭 征1，夏 旻2，胡 凱2

(1.國網(wǎng)河南省電力公司經(jīng)濟技術研究院，河南 鄭州 450052；2.江蘇省大數(shù)據(jù)分析技術重點實驗室，南京信息工程大學，江蘇 南京 210044)

電力通信網(wǎng)的節(jié)點重要性評估是電力通信研究的一個重要議題。針對目前電力通信網(wǎng)節(jié)點重要性評估存在的連接權值單一以及評價指標單一等問題，利用電力通信網(wǎng)的帶寬和距離作為權值，計算電力通信網(wǎng)節(jié)點的多種評價指標：節(jié)點強度、節(jié)點緊密度以及節(jié)點的介數(shù)。基于電力通信網(wǎng)節(jié)點的多種評價指標，利用快速密度聚類方法建立電力通信網(wǎng)的節(jié)點重要性評估模型，為電網(wǎng)通信的規(guī)劃做支撐。通過快速密度聚類方法進行無監(jiān)督的分類，將節(jié)點分為若干個重要性等級。該方法可以有效地改善基于距離的無監(jiān)督分類方法的不足。利用某省的實際電網(wǎng)通信數(shù)據(jù)進行檢驗，驗證了該方法在電力通信網(wǎng)中的實用性。

電力通信網(wǎng)；節(jié)點重要性；快速密度聚類；無監(jiān)督分類；節(jié)點特性

0 引言

電力通信網(wǎng)是專門為電力行業(yè)服務的專用網(wǎng)絡，由電廠、變電站以及各級電力系統(tǒng)相互通信傳輸系統(tǒng)組成，目前已經(jīng)成為電網(wǎng)的重要組成部分。由于電力系統(tǒng)的不斷發(fā)展壯大，電力通信網(wǎng)承載的業(yè)務量也變得越來越多，增長速度驚人。隨著電力通信網(wǎng)絡規(guī)模的不斷擴大，電力通信網(wǎng)的安全性、可靠性研究也變得越來越重要[1]。而電力通信網(wǎng)中的重要節(jié)點在很大程度上決定了電力通信網(wǎng)的穩(wěn)定性和安全性[2-4]，對重要節(jié)點的重點維護和管理成為電力通信網(wǎng)的一個重要任務[5]。因此，如何在復雜的電力通信網(wǎng)中尋找到關鍵節(jié)點成為電力通信網(wǎng)研究的一個重要議題。

電力通信網(wǎng)中的重要節(jié)點決定了網(wǎng)絡的穩(wěn)定性和安全性，電力通信網(wǎng)中節(jié)點的重要性表明了該節(jié)點在可能的故障情況下對網(wǎng)絡性能的影響，使用定量的方法來對網(wǎng)絡節(jié)點進行評估已經(jīng)成為電力通信網(wǎng)研究的熱點。目前國內外對電力通信網(wǎng)節(jié)點的重要性評估主要使用以下幾種方法[6-10]：1)利用節(jié)點的度作為節(jié)點重要性的指標。該方法中某節(jié)點連接的邊越多，那么該節(jié)點的重要性就越大。2)基于節(jié)點刪除的評價。該方法通過刪除某個節(jié)點，看網(wǎng)絡連通性的變化來分析節(jié)點的重要性。3)基于節(jié)點的介數(shù)的評價，如果該節(jié)點的介數(shù)越大那么該節(jié)點越重要。4)通過節(jié)點緊密度來對節(jié)點進行評價，緊密度越大則節(jié)點的重要性越強。目前的電力通信網(wǎng)節(jié)點重要性評估主要采用以上幾種方法，但是以上的方法都具有一些缺陷[11-12]：以節(jié)點的度作為評價指標存在一定的片面性，例如橋節(jié)點的度雖然不大，但重要性卻很強；基于節(jié)點刪除的方式中如果刪除的是末梢節(jié)點，那么就不能實現(xiàn)節(jié)點重要性的客觀評估；介數(shù)和緊密度體現(xiàn)的是節(jié)點對于全局的影響。節(jié)點介數(shù)定義為網(wǎng)絡中所有最短路徑中經(jīng)過該節(jié)點的路徑的數(shù)目占最短路徑總數(shù)的比例。緊密度指標用于刻畫網(wǎng)絡中的節(jié)點通過網(wǎng)絡到達其他節(jié)點的難易程度。介數(shù)和緊密度沒有體現(xiàn)出該節(jié)點對局域網(wǎng)絡的影響，因此基于節(jié)點的介數(shù)和緊密度的方法的評估不能全面反映節(jié)點的重要性。而節(jié)點度的指標能夠刻畫節(jié)點對局部網(wǎng)絡的影響。因此，本文中綜合利用節(jié)點的度、介數(shù)和緊密度作為節(jié)點重要性的評價指標。

目前有關電力通信網(wǎng)節(jié)點重要性評估的工作基本上都是以單一連接權值為主，將距離和帶寬都考慮進評估模型的還沒有[13-14]。而且以往的電力通信網(wǎng)的節(jié)點重要性評估往往只利用單個的評價指標，而沒有有效地綜合多種評價指標，并且很多方法只針對網(wǎng)絡結構本身，而忽略了網(wǎng)絡的連接權重[15-16]。針對目前電力通信網(wǎng)評估存在的各種問題，本文利用網(wǎng)絡帶寬和距離作為加權，通過多種評價指標的綜合來對節(jié)點的重要性進行評估。采用多指標的方式進行節(jié)點重要性的評估分類，并且這種分類是一種無監(jiān)督的分類[17]。目前針對電力通信網(wǎng)節(jié)點重要性評估的無監(jiān)督分類主要為K-means方法。K-means方法為無監(jiān)督分類中的主要傳統(tǒng)方法，但是因為該方法基于距離，故結果是圓形的聚類形狀，并不能很好地對復雜特征的融合進行分類。針對該問題，本文采用了一種快速密度聚類的方法[18]，該方法發(fā)表在2014年的《science》期刊上，該方法不僅利用距離作為分類的度量，還利用密度作為分類的指標，有效解決了K-means方法的不足。在加權網(wǎng)絡的基礎上，本文基于快速密度聚類的方法，采用節(jié)點度、節(jié)點緊密度以及節(jié)點的介數(shù)作為評價指標，對電力通信網(wǎng)的節(jié)點重要性進行評估。利用某省的實際電網(wǎng)通信數(shù)據(jù)進行檢驗，驗證了本文方法在電力通信網(wǎng)中的實用性。

1 節(jié)點重要性相關指標分析

節(jié)點數(shù)為，邊數(shù)為的通信網(wǎng)有權網(wǎng)絡數(shù)學模型可以用一個加權矩陣來描述。

邊權鄰接矩陣的矩陣元為：如果節(jié)點和節(jié)點之間有連接，那么；如果節(jié)點和節(jié)點之間沒有連接，就有。式中，為節(jié)點與節(jié)點之間線路的權值。邊權代表節(jié)點間相互作用的強度或難易程度。如果節(jié)點之間的距離作為權值，權值越大表示兩點間的距離越大，作用越弱。如果節(jié)點之間的帶寬作為權值，則權值越大作用越大。在本研究中將距離和帶寬的權值進行歸一化整合，距離和帶寬的權值各為50%。

網(wǎng)絡中節(jié)點的重要性不但與節(jié)點本身的度有一定關系，而且與節(jié)點的鄰居節(jié)點的度大小、節(jié)點的緊密度、節(jié)點的介數(shù)也存在一定的關聯(lián)，這些指標體現(xiàn)了節(jié)點的影響力。節(jié)點的影響力包括直接影響力和間接影響力。直接影響力反映節(jié)點本身影響其他節(jié)點的能力，如節(jié)點的度。間接影響力反映節(jié)點通過網(wǎng)絡對其他節(jié)點施加影響的能力，如緊密度和介數(shù)。本文利用節(jié)點度、節(jié)點緊密度、節(jié)點的介數(shù)作為節(jié)點重要性的評價指標。

節(jié)點的度：節(jié)點的度數(shù)是指與該節(jié)點直接連接的邊數(shù)，反映的是一個節(jié)點對于網(wǎng)絡中其他節(jié)點的直接影響力。具有個節(jié)點的網(wǎng)絡中，節(jié)點的度不會超過–1。通常情況下，加權后節(jié)點的強度定義為

節(jié)點的緊密度：緊密度指標用于刻畫網(wǎng)絡中的節(jié)點通過網(wǎng)絡到達其他節(jié)點的難易程度，反映節(jié)點的間接影響力。其值定義為該節(jié)點到達所有其他節(jié)點的距離之和的倒數(shù)。具有個節(jié)點的網(wǎng)絡中，節(jié)點到達所有其他節(jié)點的距離之和不會小于–1，則歸一化的緊密度指標為

(3)

介數(shù)：選取復雜網(wǎng)絡理論中合適的靜態(tài)幾何參量進行網(wǎng)絡拓撲脆弱性的計算。本文采用的是介數(shù)指標。節(jié)點介數(shù)定義為網(wǎng)絡中所有最短路徑中經(jīng)過該節(jié)點的路徑的數(shù)目占最短路徑總數(shù)的比例。每個節(jié)點的介數(shù)用參數(shù)表示，反映節(jié)點在網(wǎng)絡連通中的重要程度。也反映了節(jié)點拓撲脆弱性，表示節(jié)點在整個網(wǎng)絡中的脆弱程度。代表的是節(jié)點的相對拓撲重要度，測度了故障造成的潛在影響程度，能夠直接找到最脆弱點。

本文中以中國某省的電網(wǎng)通信實際數(shù)據(jù)作為分析來源，實現(xiàn)節(jié)點重要性的評估。

2 快速密度聚類

針對目前非監(jiān)督聚類存在的一些問題，本文采用快速密度聚類的方法來進行電力通信網(wǎng)的節(jié)點重要性評估分類?？焖倜芏染垲愃惴ǖ暮诵乃枷胧牵侯惔刂行谋痪哂休^低局部密度的鄰居點包圍，且與具有更高密度的任何點有相對較大的距離?；谶@種思想，對于任意數(shù)據(jù)點，需要計算兩個量：局部密度值以及點到具有更高局部密度點的距離。和的值都與數(shù)據(jù)點之間的距離有關(代表點和點之間的距離，本文中用歐式距離表示)。任意數(shù)據(jù)點的局部密度定義如式(4)。

(5)

圖1 算法實例展示

3 節(jié)點重要性分類結果

本文利用節(jié)點度、節(jié)點緊密度、節(jié)點的介數(shù)作為節(jié)點重要性的評價指標。節(jié)點度的大小非常直觀，反映了節(jié)點本身影響其他節(jié)點的能力。一般情況，度越大的節(jié)點重要性越大，但是對于某些橋節(jié)點來說不正確。間接影響力反映節(jié)點通過網(wǎng)絡對其他節(jié)點施加影響的能力，如緊密度和介數(shù)。本文利用節(jié)點度、節(jié)點緊密度、節(jié)點的介數(shù)這三個要素，基于快速密度聚類方法對通信網(wǎng)節(jié)點的重要性進行評估。本文中的要素為3個，那么分類空間為三維。在分類過程中，點和點之間的距離利用歐式距離表示。然后按照式(4)和式(5)分別計算節(jié)點的局部密度值以及點到具有更高局部密度點的距離。然后尋找和都大的節(jié)點作為聚類中心。本文中利用來作為尋找聚類中心的依據(jù)。由于本文將節(jié)點的重要性分為4類，因此本文尋找最大的4個點作為聚類中心，然后進行聚類。

圖2是網(wǎng)絡節(jié)點的緊密度分析，從圖2可以看出，緊密度大的點它的度未必很大，但是該點在數(shù)據(jù)傳輸中的作用卻很大。圖3為網(wǎng)絡節(jié)點的脆弱性分析，節(jié)點的脆弱性代表了該節(jié)點在網(wǎng)絡連通方面的能力，如果連通能力強，那么該節(jié)點遭到損毀后對網(wǎng)絡的影響就越大，即認為脆弱性強。從圖3可以看出，節(jié)點的脆弱性并不和節(jié)點的度分布和緊密度成完全的正相關關系。

圖2 節(jié)點緊密度分析圖

圖3 節(jié)點脆弱性分析圖

圖4給出了本文各種因素的分布。表1給出了這三種要素之間的相關性。從圖4和表1中可以看出這三種因素之間并不完全是正相關的關系。因此在節(jié)點重要性的度量上，需要綜合考慮這三種因素。

表1 各要素之間的相關關系

圖4 節(jié)點度、緊密度以及介數(shù)之間的相關關系

本文利用快速密度聚類的方法對節(jié)點重要性進行評估。本文中的要素為3個，那么分類空間為三維。因此本文將快速密度聚類的方法由二維推廣至三維，應用于節(jié)點重要性分類中。圖5給出了基于三種因素的聚類中心選擇圖，圖中大的4個方塊即為我們所需的聚類中心，按照這4個聚類中心將所有節(jié)點進行聚類。聚類結果圖為圖6所示。圖6中三個維度代表三個聚類因素，即節(jié)點度、緊密度以及脆弱性。從圖5中可以看出，本文的方法可以很好地將節(jié)點進行重要性分類。圖6中方形的節(jié)點代表重要性很強，“*”代表該節(jié)點重要性比較強，三角形代表該節(jié)點重要性一般，圓形代表該節(jié)點重要性很弱。在實際應用中，方形代表的節(jié)點要引起足夠的重視。

圖5 基于快速密度聚類的聚類中心選擇圖

圖6 節(jié)點的重要性聚類分布圖

圖7給出了電力通信網(wǎng)骨干網(wǎng)的節(jié)點重要性分類結果，從圖中可以很直觀地看出我們采用的方法可以比較好地對重要節(jié)點進行分類。在本研究中將距離和帶寬的權值進行歸一化整合，距離和帶寬的權值各為50%。因此節(jié)點重要性的評估能夠反映出距離和帶寬的影響。對于重要性一般的節(jié)點和重要性比較弱的節(jié)點來說，由于本文中采用了距離和帶寬作為權值的一部分，因此一般重要性節(jié)點在距離和帶寬的加權值比重要性比較弱的節(jié)點大。這也就是圖7中一般重要性節(jié)點和重要性比較弱的節(jié)點的區(qū)別。

圖7 電力通信網(wǎng)節(jié)點的重要性分類圖

4 結論

電力通信網(wǎng)的節(jié)點重要性評估是電力通信研究的一個重要議題[19]。本文針對以往電力通信網(wǎng)節(jié)點重要性評估中存在使用單一因素的問題，采用節(jié)點強度、節(jié)點精密度以及節(jié)點的介數(shù)作為節(jié)點重要性的評價指標，并以電力通信網(wǎng)的帶寬和距離作為權值，基于快速密度聚類方法建立電力通信網(wǎng)的節(jié)點重要性評估模型，為電網(wǎng)通信的規(guī)劃做支撐。本文通過快速密度聚類方法進行無監(jiān)督的分類，將節(jié)點分為4個重要性等級。本文利用某省的實際電網(wǎng)通信數(shù)據(jù)進行檢驗，驗證了本文方法在電力通信網(wǎng)中的實用性，證明本文方法可以有效地應用于實際電力通信網(wǎng)評估當中。

[1] 李瑞生. 一種基于虛擬節(jié)點網(wǎng)絡拓樸結構適用于架空線路主動配電網(wǎng)的縱聯(lián)保護方案[J]. 電力系統(tǒng)保護與控制, 2015, 43(2): 70-75.

LI Ruisheng. An aerial line active distribution network pilot protection scheme based on topology of virtual node[J]. Power System Protection and Control, 2015, 43(2): 70-75.

[2] 薛浩然, 張珂珩, 李斌, 等. 基于布谷鳥算法和支持向量機的變壓器故障診斷[J]. 電力系統(tǒng)保護與控制, 2015, 43(8): 8-13.

XUE Haoran, ZHANG Keheng, LI Bin, et al. Fault diagnosis of transformer based on the cuckoo search and support vector machine[J]. Power System Protection and Control, 2015, 43(8): 8-13.

[3] 李蓉蓉, 陳曦, 吳延琳, 等. 基于狀態(tài)轉移的高壓直流輸電系統(tǒng)可靠性分析[J]. 高壓電器, 2015(12): 66-71.

LI Rongrong, CHEN Xi, WU Yanlin, et al. Reliability analysis of HVDC transmission system based on state transition[J]. High Voltage Apparatus, 2015(12): 66-71.

[4] 班淑珍, 韓俊峰. 改進關聯(lián)規(guī)則方法在電力設備故障預測中的應用[J]. 電網(wǎng)與清潔能源, 2015, 31(10): 83-88.

BAN Shuzhen, HAN Junfeng. Application of improved association rules method in prediction of electric power equipment faults[J]. Power System and Clean Energy, 2015, 31(10): 83-88.

[5] 國家能源局. DL/T光纖通道傳輸保護信息通用技術條件[S]. 2010.

粵菜主要由以廣州菜、潮州菜、東江菜發(fā)展而來。其菜系集南海、番禺、東莞、順德、香山、四邑、寶安等地方風味特色，兼京、蘇、浙等外省菜以及西菜之所長融為一體，自成一家。其菜系雖然起步較晚，但發(fā)展迅猛，影響深遠。在海外，粵菜與法國大餐齊名，因此粵菜被眾多食客認為是海外中國菜的代表菜系。

[6] GUNGOR V C, LAMBERT F C. A survey on communication networks for electric system automation[J]. Computer Networks, 2006, 50(7): 877-897.

[7] GAO Huisheng, RAN Jingxue, SUN Yiqun. Risk evaluation of communication network of electric power based on restriction coefficient[C] // International Conference on Wireless Communications, Networking and Mobile Computing, 2007: 3127-3134.

[8] 謝瓊瑤, 鄧長虹, 趙紅生, 等. 基于有權網(wǎng)絡模型的電力網(wǎng)節(jié)點重要度評估[J]. 電力系統(tǒng)自動化, 2009, 33(4): 21-24.

XIE Qiongyao, DENG Changhong, ZHAO Hongsheng, et al. Evaluation method for node importance of power grid based on the weighted network model[J]. Automation of Electric Power Systems, 2009, 33(4): 21-24.

[9] 張愷倫, 江全元. 基于攻擊樹模型的WAMS通信系統(tǒng)脆弱性評估[J]. 電力系統(tǒng)保護與控制, 2013, 41(7): 116-122.

ZHANG Kailun, JIANG Quanyuan. Vulnerability assessment on WAMS communication system based on attack tree model[J]. Power System Protection and Control, 2013, 41(7): 116-122.

[10]蔣康明, 曾瑛, 鄧博仁, 等. 基于業(yè)務的電力通信網(wǎng)風險評價方法[J]. 電力系統(tǒng)保護與控制, 2013, 41(24): 101-106.

JIANG Kangming, ZENG Ying, DENG Boren, et al. Risk evaluation method of electric power communication network based on services[J]. Power System Protection and Control, 2013, 41(24): 101-106.

GUO Jing, WANG Dongrui. Vulnerability analysis on power communication network based on complex network theory[J]. Telecommunications for Electric Power System, 2009, 30(9): 6-10.

[12]程文清, 馬慶峰, 趙建之. 電力光纖傳輸網(wǎng)可靠性評估方法的研究[J]. 電力系統(tǒng)通信, 2011, 32(9): 11-15.

CHENG Wenqing, MA Qingfeng, ZHAO Jianzhi. Research on the reliability evaluation of power optical fiber transmission network[J]. Telecommunications for Electric Power System, 2011, 32(9): 11-15.

[13]高會生, 王旭蕊, 王慧芳. 一種基于貝葉斯網(wǎng)絡的電力通信網(wǎng)SDH設備綜合安全評估模型[J]. 現(xiàn)代電力, 2014, 31(3): 68-73.

GAO Huisheng, WANG Xurui, WANG Huifang. A comprehensive security evaluation model of SDH equipments in power communication network based on Bayesian network[J]. Modern Electric Power, 2014, 31(3): 68-73.

[14]梅魯海. 基于SDH光網(wǎng)絡的分層區(qū)域式保護通信系統(tǒng)的可靠性研究[J]. 電力系統(tǒng)保護與控制, 2014, 42(21): 81-85.

MEI Luhai. Reliability research of layered regional protective communication system based on SDH optical network[J]. Power System Protection and Control, 2014, 42(21): 81-85.

[15]蔡澤祥, 王星華, 任曉娜. 復雜網(wǎng)絡理論及其在電力系統(tǒng)中的應用研究綜述[J]. 電網(wǎng)技術, 2012, 32(11): 114-119.

CAI Zexiang, WANG Xinghua, REN Xiaona. A review of complex network theory and its application in power systems[J]. Power System Technology, 2012, 32(11): 114-119.

[16]楊蕾, 黃小慶, 曹麗華, 等. 考慮區(qū)域性的復雜電力網(wǎng)絡演化模型[J]. 電力系統(tǒng)及其自動化學報, 2012, 24(2): 5-10.

YANG Lei, HUANG Xiaoqing, CAO Lihua. Novel evolving network model for complex power grid considering rationality[J]. Proceedings of the CSU-EPSA, 2012, 24(2): 5-10.

[17] HE Xi, WANG Wei, LIU Xinyu, et al. Risk assessment of communication network of power company based on rough set theory and multiclass SVM[J]. Physics Procedia, 2012, 24: 1226-1231.

[18] ALEX R, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014: 1492-1496.

[19]姚致清, 于飛, 趙倩, 等. 基于模塊化多電平換流器的大型光伏并網(wǎng)系統(tǒng)仿真研究[J]. 中國電機工程學報, 2013, 33(36): 27-33.

YAO Zhiqing, YU Fei, ZHAO Qian, et al. Simulation research on large-scale PV grid-connected systems based on MMC[J]. Proceedings of the CSEE, 2013, 33(36): 27-33.

(編輯 葛艷娜)

Node importance evaluation of electric power communication network based on fast density clustering

DI Li1, ZHENG Zheng1, XIA Min2, HU Kai2

(1. Economics and Technology Research Institute of State Grid Henan Electric Power Company, Zhengzhou 450052, China; 2. Jiangsu Key Laboratory of Big Data Analysis Technology, Nanjing University of Information Science and Technology, Nanjing 210044, China)

Node importance evaluation of electric power communication network is an important topic of power communication studies. For the problem of single connection weights and single evaluation index, the bandwidth and the distance of the electric power communication network are used for the network's weight, computing the evaluating indicators of power communication network node, including joint strength, precision and node betweenness. Evaluation based on a variety of power communication network node and the fast density clustering method are used to establish the importance of the assessment model for power node communication network, supporting for the planning of grid communications. Using unsupervised classification by fast density clustering method, the node is divided into several fragile levels. This method can effectively improve the unsupervised classification method. The actual data grid communications are tested to verify the usefulness of this method in electric power communication network. This work is supported by National Natural Science Foundation of China (No. 61105115).

electric power communication networks; node importance; fast density clustering; unsupervised classification; node characteristic

10.7667/PSPC151377

國家自然科學基金(61105115)

2015-08-06；

2015-10-19

狄 立(1987-)，男，碩士，工程師，研究方向為電力通信網(wǎng)絡評估；E-mail: 137886399@qq.com 鄭 征(1979-)，男，碩士，工程師，研究方向為電力通信系統(tǒng)規(guī)劃等；E-mail: 342100300@qq.com 夏 旻(1983-)，男，通信作者，博士，副教授，研究方向為大數(shù)據(jù)分析及機器學習理論，電力通信網(wǎng)評估等。E-mail: xiamin@nuist.edu.cn