Before I discuss the above question, let me first ask, how desirable is it to control complex networks around us? This one is easily answerable. Think of the complex networks within our own bodies - the biological systems. It is not surprising to know that targeting certain 'spots' in the complex biological systems within us can give us a great control on governing metabolism, however sophisticated. Figuring out how bacterial metabolic networks are controlled could help biologists identify new and easy targets for antibiotics by determining which points in the network are the most vulnerable.
Ability to control networks also means that trouble could be caused more easily. Consider a situation where someone fond of mischief knows exactly what minimal set of power lines to trip to put off electricity for the whole city.
The proof of our understanding of complex systems is very much reflected in our ability to control them. In this post, I will talk about some basic jargon of network controllability and vulnerability.
The proof of our understanding of complex systems is very much reflected in our ability to control them. In this post, I will talk about some basic jargon of network controllability and vulnerability.
Control Theory
According to control theory, a system is controllable, if it can be driven from any intial state to any desired final state by varying certain inputs.
Assuming linear control systems, described by the following state equation,
Assuming linear control systems, described by the following state equation,
x˙(t) = A.x(t)+B.u(t)
C = [B AB A2B]
which is a NxNM matrix, has full rank, i.e. Rank(C) = N.
This controllability rank condition is given by Kalman.
The critical question here is how do we find out the minimum number M (M < N) of different signals that offer full control over the network? Kalman's theory is only feasible for small networks, while for large real networks, it is very hard to compute the rank of C, since C is an incredibly large matrix.
This is where Liu, Slotine and Barabasi come to rescue.
Liu, Slotine and Barabasi
Slotine, an MIT researcher has come up with a new computational model that can analyze a wide variety of complex networks, ranging from biological to social networks. His work was motivated to reveal the critical points that could be used in controlling the entire system, and ideally, this fraction of driver nodes is supposed to be low, for better ease and control.
Slotine and his co-authors devised a computer algorithm that can generate a controllability structure for any complex network. The red points are 'driver nodes,' which can control the rest of the nodes (green).
They showed that minimum number of nodes (driver nodes) can be found out in the 'maximum' matching of the network. In graph theory, the maximum matching of a directed network is the maximum set of links that do not share start and end nodes, and a node is matched if it is the end of a directed link in the maximum matching set, otherwise it is unmatched.
For sparse networks, such as gene regulatory networks, they found the number to be high, around 80%, implying the difficulty of control. For dense networks, such as neuronal networks, the number was about 10%.
Well, what determines the number of driver nodes? An intuitive guess would be our favorite property, the degree distribution, which describes the number of connections per node. This is indeed the case - the knowledge of degree distribution can very much help in estimating the number.
An example of maximum matching and network control, via driver nodes
Vulnerability
It is generally assumed that when a node is attacked, its edges are removed from the network, but the node itself is still in the network, so the size of the network is unchanged after attacks.
Intuitively, network controllability is supposed to decrease after attacks, which is reflected as increase in the number of driver nodes.
Intuitively, network controllability is supposed to decrease after attacks, which is reflected as increase in the number of driver nodes.
A single node attack may be a random one, or a degree-based attack. Degree-based attacks are
more efficient in attacking the network controllability rather than random attacks, reason being that degree based attacks have more edges removed from the network at each time step, which indicates that most likely more matched links are removed in the degree-based attacks at each time step, compared to that of the random attacks. As a result, the network controllability decreases faster which reflects in the need for more control signals or driver nodes to control the network. Interested readers should follow up the references.
A very good analogy could be that of power grids. The node with largest load will obviously cause greatest disruption on failure.
In conclusion, the area of control of networks is very important one, and although much work has been done in this area, there are a number of open problems of outstanding practical signifinance that budding network researchers can take up. For example, in context of vulnerability, defense strategies are very important and need further research.
References:
(1) MIT News: How to control complex networks - http://web.mit.edu/newsoffice/2011/network-control-0512.html
(2) Controllability of Complex Networks - Yang-Yu Liu, Jean-Jacques Slotine & Barabasi
(3) Robustness Analysis of Network Controllability - Cun-Lai Pua, Wen-Jiang Peib, Andrew Michaelsond
No comments:
Post a Comment