Finite-time distributed topology design for optimal network resilience
- Author(s): Dong Xue 1 and Sandra Hirche 1
-
-
View affiliations
-
Affiliations:
1:
Chair of Information-Oriented Control , Technische Universität München , D-80209 München , Germany
-
Affiliations:
1:
Chair of Information-Oriented Control , Technische Universität München , D-80209 München , Germany
- Source:
Volume 13, Issue 17,
26
November
2019,
p.
2792 – 2799
DOI: 10.1049/iet-cta.2018.6117 , Print ISSN 1751-8644, Online ISSN 1751-8652
The process of enhancing the ability of a complex network against various malicious attacks through link addition/rewiring has been the subject of extensive interest and research. The performance of existing methods often highly depends on full knowledge about the network topology. In this study, the authors devote ourselves to developing new distributed strategies to perform link manipulation sequentially using only local accessible topology information. This strategy is concerned with a matrix-perturbation-based approximation of the network-based optimisation problems and a distributed algorithm to compute eigenvectors and eigenvalues of graph matrices. In addition, the development of a distributed stopping criterion, which provides the desired accuracy on the distributed estimation algorithm, enables us to solve the link-operation problem in a finite-time manner. Finally, all results are illustrated and validated using numerical demonstrations and examples.
Inspec keywords: optimisation; eigenvalues and eigenfunctions; matrix algebra; network topology; distributed algorithms; estimation theory; approximation theory; graph theory; complex networks; network theory (graphs)
Other keywords: complex network; link-operation problem; eigenvectors and eigenvalues; distributed stopping criterion; extensive interest; link manipulation; graph matrices; distributed estimation algorithm; matrix-perturbation-based approximation; network-based optimisation problems; link addition-rewiring; optimal network resilience; local accessible topology information; network topology; finite-time distributed topology design; distributed strategies; malicious attacks; numerical demonstrations
Subjects: Optimisation techniques; Linear algebra (numerical analysis); Probability theory, stochastic processes, and statistics; Combinatorial mathematics; Optimisation; Combinatorial mathematics; Numerical approximation and analysis; Optimisation techniques; Algebra, set theory, and graph theory; Interpolation and function approximation (numerical analysis); Numerical analysis; Combinatorial mathematics; Linear algebra (numerical analysis); Interpolation and function approximation (numerical analysis)
References
-
-
1)
-
1. Su, H., Wu, H., Chen, X., et al: ‘Positive edge consensus of complex networks’, IEEE Trans. Syst. Man Cybern., Syst., 2017, 48, pp. 2242–2250.
-
-
2)
-
2. Wang, D., Zhou, J., Wang, Z., et al: ‘Random gradient-free optimization for multiagent systems with communication noise under a time-varying weight balanced digraph’, IEEE Trans. Syst. Man Cybern., Syst., 2017, doi: 10.1109/TSMC.2017.2757265, to appear.
-
-
3)
-
7. Gunderson, L.H.: ‘Ecological resilience - In theory and application’, Annual Rev. Ecol. Syst., 2000, 31, pp. 425–439.
-
-
4)
-
19. Yang, P., Freeman, R.A., Gordon, G.J., et al: ‘Decentralized estimation and control of graph connectivity for mobile sensor networks’, Automatica, 2010, 46, (2), pp. 390–396.
-
-
5)
-
3. Yang, T., Wan, Y., Wang, H., et al: ‘Global optimal consensus for discrete-time multi-agent systems with bounded controls’, Automatica, 2018, 97, pp. 182–185.
-
-
6)
-
6. Schneider, C., Moreira, A., Andrade, J., et al: ‘Mitigation of malicious attacks on networks’, Proc. Natl. Acad. Sci., 2011, 108, (10), pp. 3838–3841.
-
-
7)
-
26. Summers, T.H., Cortesi, F.L., Lygeros, J.: ‘On submodularity and controllability in complex dynamical networks’, IEEE Trans. Control Netw. Syst., 2016, 3, pp. 91–101.
-
-
8)
-
37. Liu, F., Xue, D., Hirche, S., et al: ‘Polarizability, consensusability and neutralizability of opinion dynamics on coopetitive networks’, IEEE Trans. Autom. Control, 2018, doi: 10.1109/TAC.2018.2879599, to appear.
-
-
9)
-
23. Liu, H., Cao, X., He, J., et al: ‘Distributed identification of the most critical node for average consensus’, IEEE Trans. Signal Process., 2015, 63, (16), pp. 4315–4328.
-
-
10)
-
4. Zhao, K., Kummar, A., Harrison, T.P., et al: ‘Analyzing the resilience of complex supply network topologies against random and targeted disruptions’, IEEE Syst. J., 2011, 5, (1), pp. 28–39.
-
-
11)
-
35. Long, M., Su, H., Liu, B.: ‘Group controllability of two-time-scale multi-agent networks’, J. Franklin Inst., 2018, 355, pp. 6045–6061.
-
-
12)
-
38. Ghosh, A., Boyd, S.: ‘Growing well-connected graphs’, Proc. of the 45th IEEE Conf. on Decision and Control, San Diego, USA, 2006, pp. 6605–6611.
-
-
13)
-
13. Blondel, V.D., Tsitsiklis, J.N.: ‘A survey of computational complexity results in systems and control’, Automatica, 2000, 36, pp. 1249–1274.
-
-
14)
-
36. Long, M., Su, H., Liu, B.: ‘Second-order controllability of two-time-scale multi-agent systems’, Appl. Math. Comput., 2019, 343, pp. 299–313.
-
-
15)
-
21. Liu, S., Chen, P., Hero, A.: ‘Acceleterat distributed dual averaging over evolving networks of growing connectivity’, IEEE Trans. Signal Process., 2017, 66, (7), pp. 1845–1859.
-
-
16)
-
12. Jalili, M., Yu, X.H.: ‘Enhancement of synchronizability in networks with community structure through adding efficient inter-community link’, IEEE Trans. Network Sci. Eng., 2016, 3, (2), pp. 106–116.
-
-
17)
-
34. Su, H., Wu, H., Lam, J.: ‘Positive edge-consensus for nodal networks via output feedback’, IEEE Trans. Autom. Control, 2018, doi: 10.1109/TAC.2018.2845694, to appear.
-
-
18)
-
22. Bertrand, A., Moonen, M.: ‘Distributed computation of the Fiedler vector with application to topology inference in ad hoc networks’, Signal Process., 2013, 93, (5), pp. 1106–1117.
-
-
19)
-
29. Golub, G.H., van Loan, C.F.: ‘Matrix computations’ (Johns Hopkins University Press, Baltimore, 2012, 4th edn.).
-
-
20)
-
17. Milanese, A., Sun, J., Nishikawa, T.: ‘Approximating spectral impact of structural perturbation in large networks’, Phys. Rev. E, 2010, 81, p. 046112.
-
-
21)
-
14. Bishop, A.N., Shames, I.: ‘Link operations for slowing the spread of disease in complex networks’, Europhys. Lett., 2011, 95, (1), p. 18005.
-
-
22)
-
25. Oreshkin, B.N., Coates, M.J., Rabbat, M.G.: ‘Optimization and analysis of distributed averaging with short node memory’, IEEE Trans. Signal Process, 2014, 58, (5), pp. 2850–2865.
-
-
23)
-
18. Kempe, D., McSherry, F.: ‘A decentralized algorithm for spectral analysis’, J. Comput. Syst. Sci., 2008, 74, (1), pp. 70–83.
-
-
24)
-
9. Asllani, M., Carletti, T.: ‘Topological resilience in non-normal networked systems’, Phys. Rev. E, 2018, 97, p. 042302.
-
-
25)
-
28. Asif, W., Lestas, M., Qureshi, H.K., et al: ‘Optimization based spectral partitioning for node criticality assessment’, J. Netw. Comput. Appl., 2016, 75, pp. 279–292.
-
-
26)
-
8. Simpson.Porco, J.W., Dörfler, F., Bullo, F.: ‘Voltage collapse in complex power grids’, Nature Commun., 2016, 7, pp. 1–8.
-
-
27)
-
39. Ramirez Llanos, E., Martinez, S.: ‘Distributed stopping criterion for the power iteration applied to virus mitigation’. Proc. of 49th Asilomar Conf. on Signals, Systems and Computers, Pacific Grove, USA, 2015, pp. 1328–1332.
-
-
28)
-
16. Schneider, C.M., Mihaljev, T., Havlin, S., et al: ‘Suppressing epidemics with a limited amount of immunization units’, Phys. Rev. E, 2011, 84, (6), p. 061911-6.
-
-
29)
-
11. Wang, H., Mieghem, P.V.: ‘Algebraic connectivity optimization via link addition’. Proceeding of the 3rd Int. Conf. on Bio-Inspired Models of Network, Information and Computing Systems, Hyogo, Japan, 2008.
-
-
30)
-
30. Borm, S., Mehl, C.: ‘Numerical methods for eigenvalue problems’ (De Gruyter Textbook, Berlin, 2012).
-
-
31)
-
10. Yang, T., Meng, Z., Shi, G., et al: ‘Network synchronization with nonlinear dynamics and switching interactions’, IEEE Trans. Autom. Control, 2016, 61, (10), pp. 3103–3108.
-
-
32)
-
31. Zhang, S., Tepedelenlioglu, C., Spanias, A.: ‘Distributed network center and size estimation’, IEEE Sens. J., 2018, 14, (15), pp. 6033–6045.
-
-
33)
-
24. Xue, D., Gusrialdi, A., Hirche, S.: ‘A distributed strategy for near-optimal network topology design’, Proc. of the 21st Int. Symp. on Mathematical Theory of Networks and Systems, Groningen, The Netherlands, 2014, pp. 7–14.
-
-
34)
-
5. Smith, P., Hutchison, D., Sterbenz, J., et al: ‘Network resilience: a systematic approach’, IEEE Commun. Mag., 2011, 49, (7), pp. 88–97.
-
-
35)
-
15. van Mieghem, P., Stevanović, D., Kuipers, F., et al: ‘Decreasing the spectral radius of a graph by link removals’, Phys. Rev. E, 2011, 84, (1), p. 016101-12.
-
-
36)
-
20. Xue, D., Gusrialdi, A., Hirche, S.: ‘Robust distributed control design for interconnected systems under topology uncertainty’, Proc. of the 2013 American Control Conf., Washington DC, USA, 2013, pp. 6556–6561.
-
-
37)
-
32. Su, H.S., Wan, X.F., Chen, G.R.: ‘A connectivity-preserving flocking algorithm for multi-agent systems based only on position measurements’, Int. J. Control, 2009, 82, pp. 1334–1343.
-
-
38)
-
27. Stewart, G.W., Sun, J.G.: ‘Matrix perturbation theory’ (Academic Press, Boston, 1990).
-
-
39)
-
33. Xue, D., Hirche, S.: ‘Distributed topology manipulation to control epidemic spreading over networks’, IEEE Trans. Signal Process., 2019, 67, (5), pp. 1163–1174.
-
-
1)