Hierarchical Modeling by Recursive Unsupervised Spectral Clustering and Network Extended Importance Measures to Analyze the Reliability Characteristics of Complex Network Systems
Affiliation(s)
Chair on Systems Science and the Energetic Challenge, Ecole Centrale Paris and Supelec, Paris, France. Chair on Systems Science and the Energetic Challenge, Ecole Centrale Paris and Supelec, Paris, France&Energy Department, Politecnico di Milano, Milano, Italy.
Chair on Systems Science and the Energetic Challenge, Ecole Centrale Paris and Supelec, Paris, France. Chair on Systems Science and the Energetic Challenge, Ecole Centrale Paris and Supelec, Paris, France&Energy Department, Politecnico di Milano, Milano, Italy.
ABSTRACT
The complexity of large-scale network systems made of a large number of nonlinearly interconnected components is a restrictive facet for their modeling and analysis. In this paper, we propose a framework of hierarchical modeling of a complex network system, based on a recursive unsupervised spectral clustering method. The hierarchical model serves the purpose of facilitating the management of complexity in the analysis of real-world critical infrastructures. We exemplify this by referring to the reliability analysis of the 380 kV Italian Power Transmission Network (IPTN). In this work of analysis, the classical component Importance Measures (IMs) of reliability theory have been extended to render them compatible and applicable to a complex distributed network system. By utilizing these extended IMs, the reliability properties of the IPTN system can be evaluated in the framework of the hierarchical system model, with the aim of providing risk managers with information on the risk/safety significance of system structures and components.
KEYWORDS
Complex Network System; Hierarchical Modeling; Spectral Clustering; Extended Importance Measure
Complex Network System; Hierarchical Modeling; Spectral Clustering; Extended Importance Measure
Cite this paper
Y. Fang and E. Zio, "Hierarchical Modeling by Recursive Unsupervised Spectral Clustering and Network Extended Importance Measures to Analyze the Reliability Characteristics of Complex Network Systems," American Journal of Operations Research, Vol. 3 No. 1, 2013, pp. 101-112. doi: 10.4236/ajor.2013.31A010.
Y. Fang and E. Zio, "Hierarchical Modeling by Recursive Unsupervised Spectral Clustering and Network Extended Importance Measures to Analyze the Reliability Characteristics of Complex Network Systems," American Journal of Operations Research, Vol. 3 No. 1, 2013, pp. 101-112. doi: 10.4236/ajor.2013.31A010.
References
[1] W. Kroger, “Critical Infrastructures at Risk: A Need for a New Conceptual Approach and Extended Analytical Tools,” Reliability Engineering & System Safety, Vol. 93, No. 12, 2008, pp. 1781-1787. doi:10.1016/j.ress.2008.03.005 [2] E. Zio, “Reliability Engineering: Old Problems and New Challenges,” Reliability Engineering & System Safety, Vol. 94, No. 2, 2009, pp. 125-141. doi:10.1016/j.ress.2008.06.002 [3] W. Kroger and E. Zio, “Vulnerable Systems,” Springer, Berlin, 2011. doi:10.1007/978-0-85729-655-9 [4] A. Mason, J. Onnela and P. Mucha, “Communities in Networks,” Notices of the American Mathematical Society, Vol. 56, No. 9, 2009, pp. 1082-1166. [5] S. Fortunato, “Community Detection in Graphs,” Physics Reports, Vol. 486, No. 3, 2010, pp. 75-174. doi:10.1016/j.physrep.2009.11.002 [6] B. Karrer, E. Levina and M. Newman, “Robustness of Community Structure in Networks,” Physical Review E, Vol. 77, No. 4, 2008, Article ID: 046119. doi:10.1103/PhysRevE.77.046119 [7] A. Clauset, C. Moore and M. E. J. Newman, “Hierarchical Structure and the Prediction of Missing Links in Networks,” Nature, Vol. 453, No. 7191, 2008, pp. 98-101. doi:10.1038/nature06830 [8] M. Sales-Pardo, R. Guimerá, A. Moreira, A. Moreira and L. A. N. Amaral, “Extracting the Hierarchical Organization of Complex Systems,” Proceedings of the National Academy of Sciences, Vol. 104, No. 39, 2007, pp. 15224-15229. doi:10.1073/pnas.0703740104 [9] C. Gómez, M. Sánchez-Silva and L.Duenas-Osorio, “Clustering Methods for Risk Assessment of Infrastructure Network Systems,” In: Faber, Kohler and Nishijima, Eds., Applications of Statistics and Probability in Civil Engineering, CRC Press, Boca Raton, 2011. [10] M. Van der Borst and H. Schoonakker, “An Overview of PSA Importance Measures,” Reliability Engineering & System Safety, Vol. 72, No. 3, 2001, pp. 241-245. doi:10.1016/S0951-8320(01)00007-2 [11] I. Gertsbakh and Y. Shpungin, “Network Reliability Importance Measures: Combinatorics and Monte Carlo Based Computations,” WSEAS Transactions on Computers, Vol. 7, No. 4, 2008, pp. 216-227. [12] E. Zio, “Computational Methods for Reliability and Risk Analysis,” World Scientific Publishing, Singapore, 2009. doi:10.1142/7190 [13] E. Zio, “Risk Importance Measures,” In: Safety and Risk Modeling and its Applications, Springer, Berlin, 2011. [14] Z. W. Birnbaum, “On the Importance of Different Components in a Multicomponent System,” In: P. R. Krishnaiah, Ed., Multivariate Analysis II, Academic Press, New York, 1969. [15] J. B. Fussell, “How to Hand-Calculate System Reliability and Safety Characteristics,” IEEE Transactions on Reliability, Vol. 24, No. 3, 1975, pp. 169-174. doi:10.1109/TR.1975.5215142 [16] M. C. Cheok, W. P. Gareth and R. Sherry, “Use of Importance Measures in Risk-informed Regulatory Applications,” Reliability Engineering & System Safety, Vol. 60, No. 3, 1998, pp. 213-226. doi:10.1016/S0951-8320(97)00144-0 [17] J. F. Espiritu, D. W. Coit and U. Prakash, “Component Criticality Importance Measures for the Power Industry,” Electric Power Systems Research, Vol. 77, No. 5, 2007, pp. 407-420. doi:10.1016/j.epsr.2006.04.003 [18] V. Latora and M. Marchiori, “Economic Small-World Behavior in Weighted Networks,” The European Physical Journal B—Condensed Matter and Complex Systems, Vol. 32, No. 2, 2003, pp. 249-263. doi:10.1140/epjb/e2003-00095-5 [19] U. Brandes and T. Erlebach, “Network Analysis: Methodological Foundations,” Springer, Berlin, 2005. [20] E. Zio and G. Sansavini, “Component Criticality in Failure Cascade Processes of Network Systems,” Risk Analysis, Vol. 31, No. 8, 2011, pp. 1196-1210. doi:10.1111/j.1539-6924.2011.01584.x [21] V. Rosato, S. Bologna and F. Tiriticco “Topological Properties of High-Voltage Electrical Transmission Networks,” Electric Power Systems Research, Vol. 77, No. 2, 2007, pp. 99-105. doi:10.1016/j.epsr.2005.05.013 [22] E. Ravasz and B. Albert-László, “Hierarchical Organization in Complex Networks,” Physical Review E, Vol. 67, No. 2, 2003, Article ID: 026112. doi:10.1103/PhysRevE.67.026112 [23] Von Luxburg and Ulrike, “A Tutorial on Spectral Clustering,” Statistics and Computing, Vol. 17, No. 4, 2007, pp. 395-416. doi:10.1007/s11222-007-9033-z [24] A. K. Jain, M. Narasimha Murty and P. J. Flynn, “Data Clustering: A Review,” ACM Computing Surveys, Vol. 31, No. 3, 1999, pp. 264-323. [25] M. Filippone, F. Camastra, F. Masulli and S. Rovetta, “A Survey of Kernel and Spectral Methods for Clustering,” Pattern Recognition, Vol. 41, No. 1, 2008, pp. 176-190. doi:10.1016/j.patcog.2007.05.018 [26] S. E. Schaeffer, “Graph Clustering,” Computer Science Review, Vol. 1, No. 1, 2007, pp. 27-64. doi:10.1016/j.cosrev.2007.05.001 [27] S. Leguizemón, H. Pelgrum and S. Azzali, “Unsupervised Fuzzy C-means Classification for the Determination of Dynamically Homogeneous Areas,” Revista SELPER, Vol. 12, No. 12, 1996, pp. 20-24. [28] M. Alata, M. Molhim and A. Ramini, “Optimizing of Fuzzy C-Means Clustering Algorithm Using GA,” World Academy of Science, Engineering and Technology, Vol. 1, No. 5, 2008, pp. 224-229. [29] W. Dotson and J. Gobien, “A New Analysis Technique for Probabilistic Graphs,” IEEE Transactions on Circuits and Systems, Vol. 26, No. 10, 1979, pp. 855-865. doi:10.1109/TCS.1979.1084573 [30] Y. B. Yoo and N. Deo., “A Comparison of Algorithms for Terminal-pair Reliability,” IEEE Transactions on Reliability, Vol. 37, No. 2, 1988, pp. 210-215. [31] C.-C. Jane, W.-H. Shen and Y.-W. Laih, “Practical Sequential Bounds for Approximating Two-Terminal Reliability,” European Journal of Operational Research, Vol. 195, No. 2, 2009, pp. 427-441. doi:10.1016/j.ejor.2008.02.022 [32] A. A. Chowdhury and D. O. Koval, “High Voltage Transmission Equipment Forced Outage Statistics Including Different Fault Types,” Proceedings of the 10th International Conference on Probabilistic Methods Applied to Power Systems, 25-29 May 2008, pp.1-8, 25-29.
[1] W. Kroger, “Critical Infrastructures at Risk: A Need for a New Conceptual Approach and Extended Analytical Tools,” Reliability Engineering & System Safety, Vol. 93, No. 12, 2008, pp. 1781-1787. doi:10.1016/j.ress.2008.03.005 [2] E. Zio, “Reliability Engineering: Old Problems and New Challenges,” Reliability Engineering & System Safety, Vol. 94, No. 2, 2009, pp. 125-141. doi:10.1016/j.ress.2008.06.002 [3] W. Kroger and E. Zio, “Vulnerable Systems,” Springer, Berlin, 2011. doi:10.1007/978-0-85729-655-9 [4] A. Mason, J. Onnela and P. Mucha, “Communities in Networks,” Notices of the American Mathematical Society, Vol. 56, No. 9, 2009, pp. 1082-1166. [5] S. Fortunato, “Community Detection in Graphs,” Physics Reports, Vol. 486, No. 3, 2010, pp. 75-174. doi:10.1016/j.physrep.2009.11.002 [6] B. Karrer, E. Levina and M. Newman, “Robustness of Community Structure in Networks,” Physical Review E, Vol. 77, No. 4, 2008, Article ID: 046119. doi:10.1103/PhysRevE.77.046119 [7] A. Clauset, C. Moore and M. E. J. Newman, “Hierarchical Structure and the Prediction of Missing Links in Networks,” Nature, Vol. 453, No. 7191, 2008, pp. 98-101. doi:10.1038/nature06830 [8] M. Sales-Pardo, R. Guimerá, A. Moreira, A. Moreira and L. A. N. Amaral, “Extracting the Hierarchical Organization of Complex Systems,” Proceedings of the National Academy of Sciences, Vol. 104, No. 39, 2007, pp. 15224-15229. doi:10.1073/pnas.0703740104 [9] C. Gómez, M. Sánchez-Silva and L.Duenas-Osorio, “Clustering Methods for Risk Assessment of Infrastructure Network Systems,” In: Faber, Kohler and Nishijima, Eds., Applications of Statistics and Probability in Civil Engineering, CRC Press, Boca Raton, 2011. [10] M. Van der Borst and H. Schoonakker, “An Overview of PSA Importance Measures,” Reliability Engineering & System Safety, Vol. 72, No. 3, 2001, pp. 241-245. doi:10.1016/S0951-8320(01)00007-2 [11] I. Gertsbakh and Y. Shpungin, “Network Reliability Importance Measures: Combinatorics and Monte Carlo Based Computations,” WSEAS Transactions on Computers, Vol. 7, No. 4, 2008, pp. 216-227. [12] E. Zio, “Computational Methods for Reliability and Risk Analysis,” World Scientific Publishing, Singapore, 2009. doi:10.1142/7190 [13] E. Zio, “Risk Importance Measures,” In: Safety and Risk Modeling and its Applications, Springer, Berlin, 2011. [14] Z. W. Birnbaum, “On the Importance of Different Components in a Multicomponent System,” In: P. R. Krishnaiah, Ed., Multivariate Analysis II, Academic Press, New York, 1969. [15] J. B. Fussell, “How to Hand-Calculate System Reliability and Safety Characteristics,” IEEE Transactions on Reliability, Vol. 24, No. 3, 1975, pp. 169-174. doi:10.1109/TR.1975.5215142 [16] M. C. Cheok, W. P. Gareth and R. Sherry, “Use of Importance Measures in Risk-informed Regulatory Applications,” Reliability Engineering & System Safety, Vol. 60, No. 3, 1998, pp. 213-226. doi:10.1016/S0951-8320(97)00144-0 [17] J. F. Espiritu, D. W. Coit and U. Prakash, “Component Criticality Importance Measures for the Power Industry,” Electric Power Systems Research, Vol. 77, No. 5, 2007, pp. 407-420. doi:10.1016/j.epsr.2006.04.003 [18] V. Latora and M. Marchiori, “Economic Small-World Behavior in Weighted Networks,” The European Physical Journal B—Condensed Matter and Complex Systems, Vol. 32, No. 2, 2003, pp. 249-263. doi:10.1140/epjb/e2003-00095-5 [19] U. Brandes and T. Erlebach, “Network Analysis: Methodological Foundations,” Springer, Berlin, 2005. [20] E. Zio and G. Sansavini, “Component Criticality in Failure Cascade Processes of Network Systems,” Risk Analysis, Vol. 31, No. 8, 2011, pp. 1196-1210. doi:10.1111/j.1539-6924.2011.01584.x [21] V. Rosato, S. Bologna and F. Tiriticco “Topological Properties of High-Voltage Electrical Transmission Networks,” Electric Power Systems Research, Vol. 77, No. 2, 2007, pp. 99-105. doi:10.1016/j.epsr.2005.05.013 [22] E. Ravasz and B. Albert-László, “Hierarchical Organization in Complex Networks,” Physical Review E, Vol. 67, No. 2, 2003, Article ID: 026112. doi:10.1103/PhysRevE.67.026112 [23] Von Luxburg and Ulrike, “A Tutorial on Spectral Clustering,” Statistics and Computing, Vol. 17, No. 4, 2007, pp. 395-416. doi:10.1007/s11222-007-9033-z [24] A. K. Jain, M. Narasimha Murty and P. J. Flynn, “Data Clustering: A Review,” ACM Computing Surveys, Vol. 31, No. 3, 1999, pp. 264-323. [25] M. Filippone, F. Camastra, F. Masulli and S. Rovetta, “A Survey of Kernel and Spectral Methods for Clustering,” Pattern Recognition, Vol. 41, No. 1, 2008, pp. 176-190. doi:10.1016/j.patcog.2007.05.018 [26] S. E. Schaeffer, “Graph Clustering,” Computer Science Review, Vol. 1, No. 1, 2007, pp. 27-64. doi:10.1016/j.cosrev.2007.05.001 [27] S. Leguizemón, H. Pelgrum and S. Azzali, “Unsupervised Fuzzy C-means Classification for the Determination of Dynamically Homogeneous Areas,” Revista SELPER, Vol. 12, No. 12, 1996, pp. 20-24. [28] M. Alata, M. Molhim and A. Ramini, “Optimizing of Fuzzy C-Means Clustering Algorithm Using GA,” World Academy of Science, Engineering and Technology, Vol. 1, No. 5, 2008, pp. 224-229. [29] W. Dotson and J. Gobien, “A New Analysis Technique for Probabilistic Graphs,” IEEE Transactions on Circuits and Systems, Vol. 26, No. 10, 1979, pp. 855-865. doi:10.1109/TCS.1979.1084573 [30] Y. B. Yoo and N. Deo., “A Comparison of Algorithms for Terminal-pair Reliability,” IEEE Transactions on Reliability, Vol. 37, No. 2, 1988, pp. 210-215. [31] C.-C. Jane, W.-H. Shen and Y.-W. Laih, “Practical Sequential Bounds for Approximating Two-Terminal Reliability,” European Journal of Operational Research, Vol. 195, No. 2, 2009, pp. 427-441. doi:10.1016/j.ejor.2008.02.022 [32] A. A. Chowdhury and D. O. Koval, “High Voltage Transmission Equipment Forced Outage Statistics Including Different Fault Types,” Proceedings of the 10th International Conference on Probabilistic Methods Applied to Power Systems, 25-29 May 2008, pp.1-8, 25-29.