Estimating the all-terminal network reliability by using artificial neural networks (ANNs) has emerged as a promissory alternative to classical exact NP-hard algorithms. Approaches based on traditional ANNs have usually considered the network reliability upper bound as part of the inputs, which implies additional time-consuming calculations during both training and testing phases. This paper proposes the use of Convolutional Neural Networks (CNNs), without the reliability upper-bound as an input, to address the all-terminal network reliability estimation problem. The present study introduces a multidimensional matrix format to embed the topological and link reliability information of networks. The unique contribution of this article is the method to capture the topology of a network in terms of its adjacency matrix, link reliability, and topological attributes providing a novel use of CNN beyond image classification. Since CNNs have been successful for image classification, appropriate modifications are needed and introduced to use them in the estimation of network reliability. A regression output layer is proposed, preceded by a sigmoid layer to achieve predictions within the range of reliability characteristic, a feature that some previous ANN-based works lack. Several training parameters together with a filter multiplier (CNN architecture parameter) were investigated. The actual values and the ones predicted with the best trained CNN were compared in the light of RMSE (0.04406) and p-value (0.3) showing non-significant difference. This study provides evidence supporting the hypothesis that the network reliability can be estimated by CNNs from its topology and link reliability information, embedded as an image-like multidimensional matrix. Another important result of the proposed approach is the significant reduction in computational time. An average of 1.18 ms/network was achieved by the CNN, whereas backtracking exact algorithm took around 500 s/network.
WangYnLinZyLiangX, et al. On modeling of electrical cyber-physical systems considering cyber security. Front Inform Tech El2016; 17: 465–478.
6.
ParandehgheibiMModianoEHayD. Mitigating cascading failures in interdependent power grids and communication networks. In: 2014 IEEE international conference on smart grid communications (SmartGridComm), Venice, Italy, 3–6 November 2014, pp.242–247. IEEE.
7.
KimJTongL. On topology attack of a smart grid: Undetectable attacks and countermeasures. IEEE J Sel Area Comm2013; 31: 1294–1305.
8.
ZhangZAnWShaoF. Cascading failures on reliability in cyber-physical system. IEEE T Reliab2016; 65: 1745–1754.
9.
ShoomanAMKershenbaumA. Exact graph-reduction algorithms for network reliability analysis. In: IEEE global telecommunications conference GLOBECOM’91: countdown to the new millennium conference record, Phoenix, AZ, 2–5 December 1991, pp.1412–1420. IEEE.
GhoshJNgoHQYoonS, et al. On a routing problem within probabilistic graphs and its application to intermittently connected networks. In: IEEE INFOCOM 2007-26th IEEE international conference on computer communications, Barcelona, Spain, 6–12 May 2007, pp.1721–1729. IEEE.
12.
JinRLiuLDingB, et al. Distance-constraint reachability computation in uncertain graphs. Proc VLDB Endow2011; 4: 551–562.
13.
HuaMPeiJ. Probabilistic path queries in road networks: traffic uncertainty aware path selection. In: Proceedings of the 13th international conference on extending database technology, Lausanne, Switzerland, 22–26 March 2010, pp.347–358.
14.
KhanABonchiFGulloF, et al. Conditional reliability in uncertain graphs. IEEE T Knowl Data En2018; 30: 2078–2092.
15.
BellavistaP. Telecommunication systems and technologies-Volume II. Oxford: EOLSS Publications, 2009.
16.
CancelaHRubinoGUrquhartME. An algorithm to compute the all-terminal reliability measure. OpSearch2001; 38: 567–579.
17.
Srivaree-RatanaCKonakASmithAE. Estimation of all-terminal network reliability using an artificial neural network. Comput Oper Res2002; 29: 849–868.
18.
ParkJ-H. All-terminal reliability analysis of wireless networks of redundant radio modules. IEEE Internet Things2015; 3: 219–230.
19.
PeiraviAKheibariHT. Fast estimation of network reliability using modified Manhattan distance in mobile wireless networks. J Appl Sci2008; 8: 4303–4311.
20.
HardyGLucetCLimniosN. K-terminal network reliability measures with binary decision diagrams. IEEE T Reliab2007; 56: 506–515.
21.
AyoubJSaafinWKahhalehB. K-terminal reliability of communication networks. In: ICECS 2000 7th IEEE international conference on electronics, circuits and systems (Cat No 00EX445), Jounieh, Lebanon, 7–20 December 2000, pp.374–377. IEEE.
22.
SatyanarayanaAWoodRK. A linear-time algorithm for computing k-terminal reliability in series-parallel networks. SIAM J Comput1985; 14: 818–832.
23.
WoodRK. Factoring algorithms for computing K-terminal network reliability. IEEE T Reliab1986; 35: 269–278.
24.
ZioE. Solving advanced network reliability problems by means of cellular automata and Monte Carlo sampling. Reliab Eng Syst Safe2005; 89: 219–226.
25.
WonJ-MKarrayF. Cumulative update of all-terminal reliability for faster feasibility decision. IEEE T Reliab2010; 59: 551–562.
26.
KargerDR. A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Rev2001; 43: 499–522.
27.
Ramirez-MarquezJERoccoCM. All-terminal network reliability optimization via probabilistic solution discovery. Reliability Eng Syst Safe2008; 93: 1689–1697.
28.
AltiparmakFDengizBSmithAE. A general neural network model for estimating telecommunications network reliability. IEEE T Reliab2009; 58: 2–9.
29.
YehM-S. A new Monte Carlo method for estimating network reliability. In: Proceedings of the 16th international conference on computers & industrial engineering, Ashikaga, Japan, 7–9 March 1994.
30.
Ramirez-MarquezJECoitDW. A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability. Reliab Eng Syst Safe2005; 87: 253–264.
31.
FishmanGS. A Monte Carlo sampling plan for estimating network reliability. Oper Res1986; 34: 581–594.
32.
KruskalJB. The number of simplices in a complex. Math Optim Tech1963; 10: 251–278.
33.
KatonaG. A theorem of finite sets, theory of graphs (Proc. Colloq., Tihany, 1966). New York: Academic Press, 1968.
34.
RossSM. Introduction to probability models. Oxford: Academic press, 2014.
35.
GaurVYadavOSoniG, et al. A review of metrics, algorithms and methodologies for network reliability. In: 2019 IEEE international conference on industrial engineering and engineering management (IEEM), Macao, China, 15–18 December 2019, pp.1129–1133. IEEE.
36.
DashRBarpandaNTripathyP, et al. Network reliability optimization problem of interconnection network under node-edge failure model. Appl Soft Comput2012; 12: 2322–2328.
37.
JanR. Design of reliable networks. Comput Oper Res1993; 20: 25–34.
38.
ZhaoGZhangGGeQ, et al. Research advances in fault diagnosis and prognostic based on deep learning. In: 2016 Prognostics and system health management conference (PHM-Chengdu)Chengdu, China, 19–21 October 2016, pp.1–6. IEEE.
39.
LiuWWangZLiuX, et al. A survey of deep neural network architectures and their applications. Neurocomputing2017; 234: 11–26.
40.
GuoLLiNJiaF, et al. A recurrent neural network based health indicator for remaining useful life prediction of bearings. Neurocomputing2017; 240: 98–109.
41.
LiuJSaxenaAGoebelK, et al. An adaptive recurrent neural network for remaining useful life prediction of lithium-ion batteries. 2010. National aeronautics and space administration moffett field ca ames research.
42.
KhumpromPYodoN. A data-driven predictive prognostic model for lithium-ion batteries based on a deep learning algorithm. Energies2019; 12: 660.
43.
RenLZhaoLHongS, et al. Remaining useful life prediction for lithium-ion battery: a deep learning approach. IEEE Access2018; 6: 50587–50598.
44.
RenLSunYCuiJ, et al. Bearing remaining useful life prediction based on deep autoencoder and deep neural networks. J Manuf Syst2018; 48: 71–77.
45.
WangHYangZYuQ, et al. Online reliability time series prediction via convolutional neural network and long short term memory for service-oriented systems. Knowl-Based Syst2018; 159: 132–147.
46.
LiJHePZhuJ, et al. Software defect prediction via convolutional neural network. In: 2017 IEEE international conference on software quality, reliability and security (QRS), Prague, The Czech Republic, 25–29 July 2017, pp.318–328. IEEE.
47.
AkaiNMoralesLYMuraseH. Simultaneous pose and reliability estimation using convolutional neural network and Rao–Blackwellized particle filter. Adv Robotics2018; 32: 930-944.
48.
WangQZhaoBMaH, et al. A method for rapidly evaluating reliability and predicting remaining useful life using two-dimensional convolutional neural network with signal conversion. J Mech Sci Technol2019; 33: 2561–2571.
49.
AbiodunOIJantanAOmolaraAE, et al. State-of-the-art in artificial neural network applications: a survey. Heliyon2018; 4: e00938.
50.
AlbawiSMohammedTAAl-ZawiS. Understanding of a convolutional neural network. In: 2017 international conference on engineering and technology (ICET)Antalya, Turkey, 21–23 August 2017, pp.1–6. IEEE.
51.
ProvanJSBallMO. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J Comput1983; 12: 777–788.
52.
IoannouYRobertsonDCipollaR, et al. Deep roots: improving cnn efficiency with hierarchical filter groups. In: Proceedings of the IEEE conference on computer vision and pattern recognition, Honolulu, HI, 21–26 July 2017, pp.1231–1240.
53.
YaseenAFSaudLJ. A survey on the layers of convolutional neural networks. IJCSMC 2018; 7: 191–196.
54.
GoodfellowIBengioYCourvilleA. Deep learning. Cambridge, MA: MIT press, 2016.
55.
ArunnehruJKumarAVermaJ. Early prediction of brain tumor classification using convolution neural networks. In: International conference on computational intelligence, security and internet of things, Agartala, India, 13–14 December 2019, pp.16–25. Springer.
56.
Van SlykeRFrankH. Network reliability analysis: part I. Networks1971; 1: 279–290.
57.
WilkovR. Analysis and design of reliable computer networks. IEEE T Commun1972; 20: 660–678.
58.
ColbournCJHarmsDD. Bounding all-terminal reliability in computer networks. Networks1988; 18: 1–12.
59.
AltiparmakFDengizBSmithAE. Reliability optimization of computer communication networks using genetic algorithms. In: SMC’98 conference proceedings 1998 IEEE international conference on systems, man, and cybernetics (Cat No 98CH36218), San Diego, CA, 1998, pp.4676–4681. IEEE.
60.
GareyMRDavidS. Johnson Computers and Intractability. A guide to the theory of np-completeness WH freeman and company New York1979.
61.
BallMVan SlykeRM. Backtracking algorithms for network reliability analysis. In: HammerPLJohnsonELKorteBH, et al. (eds) Annals of discrete mathematics. Glen Cove, NY: Elsevier, 1977, pp.49–64.
62.
ZakiMJMeiraWJrMeiraW.Data mining and analysis: fundamental concepts and algorithms. New York: Cambridge University Press, 2014.
63.
ChuiKTShenC-w. Tolerance analysis in scale-free social networks with varying degree exponents. Library Hi Tech2019; 37(1): 57–71.
64.
AlbertRBarabásiA-L. Statistical mechanics of complex networks. Rev Mod Phys2002; 74: 47.
65.
CrucittiPLatoraVMarchioriM, et al. Efficiency of scale-free networks: error and attack tolerance. Physica A2003; 320: 622–642.
66.
SrivastavaNHintonGKrizhevskyA, et al. Dropout: a simple way to prevent neural networks from overfitting. J Mach Learn Res2014; 15: 1929–1958.
67.
TwomeyJMSmithAE. Bias and variance of validation methods for function approximation neural networks under conditions of sparse data. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)1998; 28: 417–430.
68.
VedaldiALencK. Matconvnet. Convolutional neural networks for matlab. In: Proceedings of the 23rd ACM international conference on Multimedia, Brisbane Australia, 26–30 October 2015, pp.689–692.
69.
MastersDLuschiC. Revisiting small batch training for deep neural networks. arXiv preprint arXiv:1804076122018.
