K-Terminal Network Permutation Importance Measure Based on Mixture C-Spectrum

基于混合C-谱的K-终端网络置换重要度计算方法

¹ School of Science, Lanzhou University of Technology, Lanzhou 730050, China
² School of Mechatronics, Northwestern Polytechnical University, Xi'an 710072, China

Received: 22 October 2018

Abstract

The construction spectrum(C-spectrum) is often used to exploit the network reliability and importance measure. It depends only on the network structure and hence called structure invariant. Importance measure can be used to quantify the criticality of edge within a network. This paper aim at generalizing the traditional permutation importance measure to accommodate the case of K-terminal network in which all the edges fail with independent and equal probability. A concept for mixture C-spectrum is introduced to evaluate the permutation importance measure of edges. It is proved that the rankings according to the permutation importance measure depend only on the network structure through the mixture C-spectrum when the network has special structure or the reliability of edge is sufficient large. Finally, numerical experiment show that the Monte Carlo algorithm based on the mixture C-spectrum can be efficiently used to evaluate the permutation importance measure.

摘要

重要度可以量化网络边对整个网络可靠性（故障）的影响程度，而C-谱是研究网络可靠性及重要度的一个有力工具。假设网络中每条边具有相同的可靠性，将二态关联系统中的传统置换重要度推广到K-终端网络，设计了基于混合C-谱的蒙特卡罗算法来评估该重要度。理论分析表明：当网络具有某种特殊结构或者边的可靠性足够大时，网络边的置换重要度排序仅依赖于网络结构，而与边的可靠性无关。最后，结合算例演示了如何利用传统置换重要度评估K-终端网络中网络边的重要程度。