Literature on the controllability of networks under attack

Question

I would like to request your advice on a problem arising from my research in the life sciences. Consider a modular, sparse weighted network which is partially controllable in the sense that some modules of interest within it are fully controllable. The network experiences an attack which leads to edge weight alterations throughout the entire network and to loss of control over the network modules of interest. I am broadly interested in the problem of determining what network inputs can lead to regaining control of those modules which are fully controllable. If you can recommend any references on this or on related problems, I would greatly appreciate it. Thank you in advance for your assistance!

Answer 1

This paper by Menichetti, Dall’Asta and Bianconi specifically talks about sparse networks, and shows minimum degree conditions for networks to be controllable by a small fraction of nodes, and discusses a maximum matching based algorithm (which I think is the common approach as in this original paper that you're probably aware of). These maximum matching algorithms usually work incrementally, so in your setting that is a good thing. As I understand it you have a good matching and then some of it breaks, so you can use that partial solution as input.

Since you are interested in the problem of determining controllability: it seems that the minimum degree of the network is crucial, and you are only interested in a subset of the nodes being controllable. Perhaps you can do a $k$-core decomposition, and then look at which $k$-cores still contain your nodes of interest. A $k$-core of a graph is a maximal subgraph of minimum degree $k$ (to other nodes in that subgraph). These are very cheap to find computationally (linear time): for example, to find a 2-core you delete vertices of degree 1 until none are left. You can do this for a directed network, too, and consider both in- and out-degree separately. If your nodes of interest all lie in the 2-core, then you know that they are controllable by a small fraction of nodes also in that 2-core, by the Menichetti paper.

Of course, what is small in theory may not be good enough for your practical purposes, so I can't say whether this would give a satisfying yes/no answer to your question.