Spectral complexity of directed graphs and application to structural decomposition.

*(English)*Zbl 1417.05121Summary: We introduce a new measure of complexity (called spectral complexity) for directed graphs. We start with splitting of the directed graph into its recurrent and nonrecurrent parts. We define the spectral complexity metric in terms of the spectrum of the recurrence matrix (associated with the reccurent part of the graph) and the Wasserstein distance. We show that the total complexity of the graph can then be defined in terms of the spectral complexity, complexities of individual components, and edge weights. The essential property of the spectral complexity metric is that it accounts for directed cycles in the graph. In engineered and software systems, such cycles give rise to subsystem interdependencies and increase risk for unintended consequences through positive feedback loops, instabilities, and infinite execution loops in software. In addition, we present a structural decomposition technique that identifies such cycles using a spectral technique. We show that this decomposition complements the well-known spectral decomposition analysis based on the Fiedler vector. We provide several examples of computation of spectral and total complexities, including the demonstration that the complexity increases monotonically with the average degree of a random graph. We also provide an example of spectral complexity computation for the architecture of a realistic fixed wing aircraft system.

##### MSC:

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

05C20 | Directed graphs (digraphs), tournaments |

##### References:

[1] | Eppinger, D. S.; Browning, R. T., Design Structure Matrix Methods and Applications, (2012), MIT press |

[2] | Pugliese, A.; James, E.; Nilchiani, R., Acquisition and development programs through the lens of system complexity, 2018 |

[3] | Robbins, D.; Bobalik, J.; Stena, D. D.; Martin, N.; Plag, K.; Keith, R.; Wall, K., F-35 subsystems design, development and verification, Proceedings of the Aviation Technology, Integration, and Operations Conference |

[4] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Application, 87, (1980), New York, NY, USA: Academic Press, New York, NY, USA · Zbl 0458.05042 |

[5] | Chung, R. K. F.; Graham, F. C., Spectral graph theory, Number 92, American Mathematical Soc., 1997 |

[6] | von Luxburg, U., A tutorial on spectral clustering, Statistics and Computing, 17, 4, 395-416, (2007) |

[7] | Sahai, T.; Speranzon, A.; Banaszuk, A., Hearing the clusters of a graph: a distributed algorithm, Automatica, 48, 1, 15-24, (2012) · Zbl 1244.93016 |

[8] | Klus, S.; Sahai, T., A spectral assignment approach for the graph isomorphism problem, Information and Inference: A Journal of the IMA, (2018) |

[9] | McCabe, T. J., A complexity measure, IEEE Transactions on Software Engineering, SE-2, 4, 308-320, (1976) · Zbl 0352.68066 |

[10] | McCabe, T. J.; Butler, C. W., Design complexity measurement and testing, Communications of the ACM, 32, 12, 1415-1425, (1989) |

[11] | Navlakha, J. K., A survey of system complexity metrics, The Computer Journal, 30, 3, 233-238, (1987) |

[12] | Shepperd, M.; Ince, D. C., A critique of three metrics, The Journal of Systems and Software, 26, 3, 197-210, (1994) |

[13] | Aström, K. J.; Murray, R. M., Feedback Systems: An Introduction for Scientists and Engineers, (2010), Princeton University Press |

[14] | Moshagen, T., Convergence of explicitely coupled Simulation Tools (Co-simulations), Journal of Numerical Mathematics, (2017) |

[15] | Klus, S.; Sahai, T.; Liu, C.; Dellnitz, M., An efficient algorithm for the parallel solution of high-dimensional differential equations, Journal of Computational and Applied Mathematics, 235, 9, 3053-3062, (2011) · Zbl 1210.65145 |

[16] | Dehmer, M.; Mowshowitz, A., A history of graph entropy measures, Information Sciences, 181, 1, 57-78, (2011) · Zbl 1204.94050 |

[17] | Dehmer, M.; Li, X.; Shi, Y., Connections between generalized graph entropies and graph energy, Complexity, 21, 1, 35-41, (2015) |

[18] | Mezic, I.; Runolfsson, T., Uncertainty propagation in dynamical systems, Automatica, 44, 12, 3003-3013, (2008) · Zbl 1153.93446 |

[19] | Cohen, M. B.; Kelner, J.; Peebles, J.; Peng, R.; Rao, A. B.; Sidford, A.; Vladu, A., Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM · Zbl 1370.60115 |

[20] | Kottak, C., Cultural Anthropology, (1991), New York, NY, USA: McGraw Hill, New York, NY, USA |

[21] | Speer, N.; Fröhlich, H.; Spieth, C.; Zell, A., Functional grouping of genes using spectral clustering and gene ontology, Proceedings of the International Joint Conference on Neural Networks, IJCNN 2005 |

[22] | Paccanaro, A.; Casbon, J. A.; Saqi, M. A. S., Spectral clustering of protein sequences, Nucleic Acids Research, 34, 5, 1571-1580, (2006) |

[23] | Muhammad, A.; Jadbabaie, A., Decentralized computation of homology groups in networks by gossip, Proceedings of the 2007 American Control Conference, ACC |

[24] | Herman, I.; Melançon, G.; Marshall, M. S., Graph visualization and navigation in information visualization: a survey, IEEE Transactions on Visualization and Computer Graphics, 6, 1, 24-43, (2000) |

[25] | Kempe, D.; McSherry, F., A decentralized algorithm for spectral analysis, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, ACM · Zbl 1192.68848 |

[26] | Fiedler, M., Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23(98), 298-305, (1973) · Zbl 0265.05119 |

[27] | Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Mathematical Journal, 25(100), 4, 619-633, (1975) · Zbl 0437.15004 |

[28] | Biggs, N., Norman Linstead Biggs, and Emeritus Norman Biggs, Algebraic graph theory, 67, (1993), Cambridge, UK: Cambridge University Press, Cambridge, UK |

[29] | Everitt, B. S.; Landau, S.; Leese, M., Cluster analysis, (2001), Arnold · Zbl 1205.62076 |

[30] | Jain, A. K.; Dubes, R. C., Algorithms for Clustering Data, (1988), Prentice Hall · Zbl 0665.62061 |

[31] | Sahai, T.; Speranzon, A.; Banaszuk, A., Wave equation based algorithm for distributed eigenvector computation, Proceedings of the 49th IEEE Conference on Decision and Control (CDC ’10), 2010 |

[32] | Schaeffer, S. E., Graph clustering, Computer Science Review, 1, 1, 27-64, (2007) · Zbl 1302.68237 |

[33] | Zeidner, L. E.; Banaszuk, A.; Becz, S., System complexity reduction via spectral graph partitioning to identify hierarchical modular clusters, Proceedings of the 10th AIAA Aviation Technology, Integration and Operations Conference ATIO ’10 |

[34] | Leskovec, J.; Krevl, A., SNAP Datasets: Stanford large network dataset collection, 2015 |

[35] | Brualdi, R. A., Spectra of digraphs, Linear Algebra and its Applications, 432, 9, 2181-2213, (2010) · Zbl 1221.05177 |

[36] | Chung, F., Laplacians and the Cheeger inequality for directed graphs, Annals of Combinatorics, 9, 1, 1-19, (2005) · Zbl 1059.05070 |

[37] | Gleich, D., Hierarchical directed spectral graph partitioning, Information Networks, (2006) |

[38] | Capocci, A.; Servedio, V. D. P.; Caldarelli, G.; Colaiori, F., Detecting communities in large networks, Physica A: Statistical Mechanics and its Applications, 352, 2-4, 669-676, (2005) |

[39] | Meila, M.; Pentney, W., Clustering by weighted cuts in directed graphs, Proceedings of the 7th SIAM International Conference on Data Mining (SDM ’07), SIAM |

[40] | Leicht, E. A.; Newman, M. E. J., Community structure in directed networks, Physical Review Letters, 100, 11, (2008) |

[41] | Yin, H.; Benson, A. R.; Leskovec, J.; Gleich, D. F., Local higher-order graph clustering, Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017 |

[42] | Van Lierde, H.; Chow, T. W.; Delvenne, J., Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs, Journal of Complex Networks, (2018) |

[43] | Christine, K.; Sanders, G., Detecting highly cyclic structure with complex eigenpairs, 2016, https://arxiv.org/abs/1609.05740 |

[44] | Mezic, I.; Fonoberov, V. A.; Fonoberova, M.; Sahai, T., Complexity and clustering metrics, Proceedings of the DARPA METAII PI meeting |

[45] | Mezic, I., Coupled nonlinear dynamical systems: asymptotic behavior and uncertainty propagation, Proceedings of the 2004 43rd IEEE Conference on Decision and Control (CDC), IEEE |

[46] | Koopman, B. O., Hamiltonian Systems and Transformation in Hilbert Space, Proceedings of the National Acadamy of Sciences of the United States of America, 17, 5, 315-318, (1931) · Zbl 0002.05701 |

[47] | Mezic, I.; Banaszuk, A., Comparison of systems with complex behavior, Physica D: Nonlinear Phenomena, 197, 1-2, 101-133, (2004) · Zbl 1059.37072 |

[48] | Grimmett, G.; Stirzaker, D., Probability and random processes, (2001), Oxford university press · Zbl 1015.60002 |

[49] | Katok, A.; Hasselblatt, B., Introduction to the modern theory of dynamical systems, 54, (1997), New York, NY, USA: Cambridge University Press, New York, NY, USA · Zbl 0878.58019 |

[50] | Huisinga, W.; Schmidt, B., Advances in Algorithms for Macromolecular Simulation, Chapter Metastability and Dominant Eigenvalues of Transfer Operators. Advances in Algorithms for Macromolecular Simulation, Chapter Metastability and Dominant Eigenvalues of Transfer Operators, Lecture Notes in Computational Science and Engineering, (2005), Berlin, Germany: Springer, Berlin, Germany |

[51] | Bordenave, C.; Caputo, P.; Chafa, D., Circular law theorem for random Markov matrices, Probability Theory and Related Fields, 152, 3-4, 751-779, (2012) · Zbl 1242.15034 |

[52] | Gutman, I., The energy of a graph. 10, steiermrkisches mathematisches symposium (stift rein, graz, 1978), Ber. Math.-Statist. Sekt. Forsch. Graz, (100-105), 1978 |

[53] | Gutman, I., The energy of a graph: old and new results, Algebraic Combinatorics and Applications, 196-211, (2001), Berlin, Germany: Springer, Berlin, Germany · Zbl 0974.05054 |

[54] | Estrada, E., Characterization of 3D molecular structure, Chemical Physics Letters, 319, 5-6, 713-718, (2000) |

[55] | Gutman, I.; Soldatović, T.; Vidović, D., The energy of a graph and its size dependence. A Monte Carlo approach, Chemical Physics Letters, 297, 5-6, 428-432, (1998) |

[56] | Berwanger, D.; Gradel, E.; Kaiser, L.; Rabinovich, R., Entanglement and the complexity of directed graphs, Theoretical Computer Science, 463, 2-25, (2012) · Zbl 1256.05086 |

[57] | Mucha, P. J.; Richardson, T.; Macon, K.; Porter, M. A.; Onnela, J.-P., Community structure in time-dependent, multiscale, and multiplex networks, Science, 328, 5980, 876-878, (2010) · Zbl 1226.91056 |

[58] | Reichardt, J.; White, D. R., Role models for complex networks, The European Physical Journal B, 60, 2, 217-224, (2007) · Zbl 1189.91127 |

[59] | Karrer, B.; Newman, M. E. J., Stochastic blockmodels and community structure in networks, Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 83, 1, (2011) |

[60] | Jacobi, M. N.; Gornerup, O., A spectral method for aggregating variables in linear dynamical systems with application to cellular automata renormalization, Advances in Complex Systems, 12, 2, 131-155, (2009) · Zbl 1187.37012 |

[61] | Jacobi, M. N.; Goernerup, O., A dual eigenvector condition for strong lumpability of Markov chains, 2007, https://arxiv.org/abs/0710.1986 |

[62] | Arena, M. V.; Younossi, O.; Brancato, K., Why has the cost of fixed-wing aircraft risen? a macroscopic examination of the trends in us military aircraft costs over the past several decades, (2008), Rand national defense research Inst santa monica CA |

[63] | Rosero, J. A.; Ortega, J. A.; Aldabas, E.; Romeral, L., Moving towards a more electric aircraft, IEEE Aerospace and Electronic Systems Magazine, 22, 3, 3-9, (2007) |

[64] | Xu, J.; Lan, Y., Hierarchical feedback modules and reaction hubs in cell signaling networks, PLoS ONE, 10, 5, (2015) |

[65] | Budisic, M.; Mohr, R.; Mezic, I., Applied Koopmanism, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22, 4, (2012) · Zbl 1319.37013 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.