Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate Networks
A number of real-world complex networks can be modeled as multistate networks for performance analysis. A multistate network consists of multistate components and possesses multiple different performance levels. For such a network, reliability is concerned with the probability of the network capacit...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/4561845 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832560413286334464 |
|---|---|
| author | Xiu-Zhen Xu Yi-Feng Niu Qing Li |
| author_facet | Xiu-Zhen Xu Yi-Feng Niu Qing Li |
| author_sort | Xiu-Zhen Xu |
| collection | DOAJ |
| description | A number of real-world complex networks can be modeled as multistate networks for performance analysis. A multistate network consists of multistate components and possesses multiple different performance levels. For such a network, reliability is concerned with the probability of the network capacity level greater than or equal to a predetermined demand level d. One major method for multistate network reliability evaluation is using d-minimal paths. This paper proposes an efficient algorithm to find d-minimal paths. First, a new concept of qualified state vector is defined so as to fix a relatively smaller search space of d-minimal paths, and a sufficient and necessary condition for a qualified state vector to be d-minimal path is established. Then, the max-flow algorithm and the enumeration algorithm are integrated to search for d-minimal paths in the determined search space that is recursively divided into subspaces such that the searching efficiency can be increased as much as possible. Both analytical and numerical results show that the proposed algorithm is more efficient in finding all d-minimal paths. In addition, a case study related to power transmission network is performed to demonstrate the implication of network reliability. |
| format | Article |
| id | doaj-art-c52f017e86dd49d7974b7fd6263eca26 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-c52f017e86dd49d7974b7fd6263eca262025-02-03T01:27:44ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/45618454561845Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate NetworksXiu-Zhen Xu0Yi-Feng Niu1Qing Li2School of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaSchool of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaCollege of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao 266590, ChinaA number of real-world complex networks can be modeled as multistate networks for performance analysis. A multistate network consists of multistate components and possesses multiple different performance levels. For such a network, reliability is concerned with the probability of the network capacity level greater than or equal to a predetermined demand level d. One major method for multistate network reliability evaluation is using d-minimal paths. This paper proposes an efficient algorithm to find d-minimal paths. First, a new concept of qualified state vector is defined so as to fix a relatively smaller search space of d-minimal paths, and a sufficient and necessary condition for a qualified state vector to be d-minimal path is established. Then, the max-flow algorithm and the enumeration algorithm are integrated to search for d-minimal paths in the determined search space that is recursively divided into subspaces such that the searching efficiency can be increased as much as possible. Both analytical and numerical results show that the proposed algorithm is more efficient in finding all d-minimal paths. In addition, a case study related to power transmission network is performed to demonstrate the implication of network reliability.http://dx.doi.org/10.1155/2019/4561845 |
| spellingShingle | Xiu-Zhen Xu Yi-Feng Niu Qing Li Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate Networks Complexity |
| title | Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate Networks |
| title_full | Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate Networks |
| title_fullStr | Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate Networks |
| title_full_unstemmed | Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate Networks |
| title_short | Efficient Enumeration of d-Minimal Paths in Reliability Evaluation of Multistate Networks |
| title_sort | efficient enumeration of d minimal paths in reliability evaluation of multistate networks |
| url | http://dx.doi.org/10.1155/2019/4561845 |
| work_keys_str_mv | AT xiuzhenxu efficientenumerationofdminimalpathsinreliabilityevaluationofmultistatenetworks AT yifengniu efficientenumerationofdminimalpathsinreliabilityevaluationofmultistatenetworks AT qingli efficientenumerationofdminimalpathsinreliabilityevaluationofmultistatenetworks |