Abstract
This paper presents machine learning based approximations for the minimum number of driver nodes needed for structural controllability of networks under link-based random and targeted attacks. We compare our approximations with existing analytical approximations and show that our machine learning based approximations significantly outperform the existing closed-form analytical approximations in case of both synthetic and real-world networks. Apart from targeted attacks based upon the removal of so-called critical links, we also propose analytical approximations for out-in degree-based attacks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Sun, P., Kooij, R. E., He, Z., Van Mieghem, P.: Quantifying the robustness of network controllability. In 2019 4th International Conference on System Reliability and Safety (ICSRS), pp. 66–76. IEEE, November 2019
Liu, Y.Y., Slotine, J.J., Barabási, A.L.: Controllability of complex networks. Nature 473(7346), 167–173 (2011)
Kalman, R.E.: Mathematical description of linear dynamical systems. J. SIAM Ser. A Control 1(2), 152–192 (1963)
Dhiman, A.K.: Measuring the robustness of network controllability. M.Sc. Thesis, Delft University of Technology (2020)
Cowan, N.J., Chastain, E.J., Vilhena, D.A., Freudenberg, J.S., Bergstrom, C.T.: Nodal dynamics, not degree distributions, determine the structural controllability of complex networks. PloS ONE 7(6), e38398 (2012)
Socievole, A., De Rango, F., Scoglio, C., Van Mieghem, P.: Assessing network robustness under SIS epidemics: the relationship between epidemic threshold and viral conductance. Comput. Netw. 103, 196–206 (2016)
Trajanovski, S., Martín-Hernández, J., Winterbach, W., Van Mieghem, P.: Robustness envelopes of networks. J. Complex Netw. 1(1), 44–62 (2013)
Wang, X., Pournaras, E., Kooij, R.E., Van Mieghem, P.: Improving robustness of complex networks via the effective graph resistance. Eur. Phys. J. B 87(9), 221 (2014). https://doi.org/10.1140/epjb/e2014-50276-0
Koç, Y., Warnier, M., Van Mieghem, P., Kooij, R.E., Brazier, F.M.: The impact of the topology on cascading failures in a power grid model. Phys. A Stat. Mech. Appl. 402, 169–179 (2014)
Lin, C.T.: Structural controllability. IEEE Trans. Autom. Control 19(3), 201–208 (1974)
Hopcroft, J.E., Karp, R.M.: An n\(\hat{}\)5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)
Nie, S., Wang, X., Zhang, H., Li, Q., Wang, B.: Robustness of controllability for networks based on edge-attack. PloS One 9(2), e89066 (2014)
Pu, C.L., Pei, W.J., Michaelson, A.: Robustness analysis of network controllability. Physica A Stat. Mech. Appl. 391(18), 4420–4425 (2012)
Knight, S., Nguyen, H.X., Falkner, N., Bowden, R., Roughan, M.: The internet topology zoo. IEEE J. Sel. Areas Commun. 29(9), 1765–1775 (2011)
Himsolt, M.: GML: a portable graph file format, p. 35. Technical report 94030, Universitat Passau (1997)
Brandes, U., Eiglsperger, M., Herman, I., Himsolt, M., Marshall, M.S.: GraphML progress report structural layer proposal. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 501–512. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45848-4_59
NetworkX. Network analysis in python. https://networkx.github.io/
Tirpak, T.M.: Telecommunication network resource management based on social network characteristics. U.S. Patent Application No. 12/463,445 (2010)
Harary, F.: The determinant of the adjacency matrix of a graph. SIAM Rev. 4(3), 202–210 (1962)
van der Hofstad, R.: Random graphs models for complex networks, and the brain. Complex. Sci. 1, 199–246 (2019)
Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5(1), 17–60 (1960)
Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47 (2002)
Barabási, A.L., Ravasz, E., Vicsek, T.: Deterministic scale-free networks. Phys. A Stat. Mech. Appl. 299(3–4), 559–564 (2001)
Cohen, R., Erez, K., Ben-Avraham, D., Havlin, S.: Resilience of the internet to random breakdowns. Phys. Rev. Lett. 85(21), 4626 (2000)
Cetinay, H., Devriendt, K., Van Mieghem, P.: Nodal vulnerability to targeted attacks in power grids. Appl. Netw. Sci. 3(1), 34 (2018)
Holme, P., Kim, B.J., Yoon, C.N., Han, S.K.: Attack vulnerability of complex networks. Phys. Rev. E 65(5), 056109 (2002)
Huang, X., Gao, J., Buldyrev, S.V., Havlin, S., Stanley, H.E.: Robustness of interdependent networks under targeted attack. Phys. Rev. E 83(6), 065101 (2011)
Mengiste, S.A., Aertsen, A., Kumar, A.: Effect of edge pruning on structural controllability and observability of complex networks. Sci. Rep. 5(1), 1–14 (2015)
Van Mieghem, P., et al.: A framework for computing topological network robustness. Delft University of Technology, Report 20101218 (2010)
Lou, Y., He, Y., Wang, L., Chen, G.: Predicting network controllability robustness: a convolutional neural network approach. IEEE Trans. Cybern. 2, 1–12 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Dhiman, A., Sun, P., Kooij, R. (2021). Using Machine Learning to Quantify the Robustness of Network Controllability. In: Renault, É., Boumerdassi, S., Mühlethaler, P. (eds) Machine Learning for Networking. MLN 2020. Lecture Notes in Computer Science(), vol 12629. Springer, Cham. https://doi.org/10.1007/978-3-030-70866-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-70866-5_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-70865-8
Online ISBN: 978-3-030-70866-5
eBook Packages: Computer ScienceComputer Science (R0)