Network Controllability
IV124
Josef Spurný & Eva Výtvarová
Faculty of Informatics, Masaryk University
May 12, 2023
Introduction
Studying complex networks
1. Understand & Describe (Quantify)
2. Predict
3. Control
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 2 / 26
Introduction
Research Questions
Which nodes to target?
How many nodes do we need to control the network?
Are some networks easier to control than others?
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 3 / 26
Introduction
Controllability
Controllability
A system is controllable if it can be driven from any initial state to
any desired final state.
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 4 / 26
Introduction
Controllability
Even a simple oldtimer car can have several thousands of
components.
Yet you only need to manipulate three components to control the car
(gas, brake, steering wheel).
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 5 / 26
Introduction
Controllability
With real-world networks, we are facing a inverse problem:
We have a network, but we do not know which components
control the system
We need to identify the driver nodes (ND)
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 6 / 26
Introduction
Case study
Control of Neuronal Network in C. elegans1
body ≈ 1000 cells
brain: N ≈ 300; E ≈ 2500
scale-free structure
16 % driver nodes (≈ 50 neurons)
driver nodes avoid hubs
1
Badhwar R, Bagler G. 2015. Control of Neuronal Network in
Caenorhabditis elegans.
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 7 / 26
Control Theory
Controlling simple linear system
dX
dt = A × X(t) + B × u(t)
A ∈ RN×N: adjacency matrix
X(t) ∈ RN×1: state vector
u(t) ∈ RM×1: input vector
(signal)
B ∈ RN×M: input matrix
Note: Oriented network, only incoming links count
Transpose of the weighted adjacency matrix.
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 8 / 26
Control Theory
Kalman’s Rank Condition2
Kalman’s Rank Condition:
A system is controllable if its controllability matrix has full rank.
rank C = N
C = [B, A × B, A2 × B, · · · , AN−1 × B]
Informally, every row (column) is linearly independent of one another.
2
Kalman, R.E. 1963. Mathematical description of linear dynamical
systems
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 9 / 26
Control Theory
Example 1: Controllable
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 10 / 26
Control Theory
Example 2: Uncontrollable
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 11 / 26
Control Theory
Example 2: How to control it?
We cannot change the topology, so we need to send a signal to an
additional node.
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 12 / 26
Driver Nodes
Driver Nodes – ND
What’s the minimum number of ND?
How to efficiently identify them?
Which network characteristics determine ND?
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 13 / 26
Driver Nodes
Challenges with identification of ND
Link weights of real-world networks are usually unknown
Brute-force search is not feasible, as there are 2N − 1
combinations
Kalman’s rank condition is hard to check for large systems, as it
has a dimension of N × NM
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 14 / 26
Driver Nodes
Solution: Graph Matching theory
Matching M ⊆ E is a set of links that don’t have common nodes
Maximal matching – a matching with the highest link count
(more than one can be identified)
Perfect matching – a matching that covers all nodes (there are
no unmatched nodes)
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 15 / 26
Driver Nodes
Matching in Directed Network3
The bipartite graph is built by splitting the node set N into two node
sets Nin and Nout
3
Zhang, Han & Zhang. 2015. An efficient algorithm for finding all
possible input nodes for controlling complex networks
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 16 / 26
Driver Nodes
Matching in Directed Network4
4
Zhang, Han & Zhang. 2015. An efficient algorithm for finding all
possible input nodes for controlling complex networks
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 17 / 26
Driver Nodes
Time Complexity Issue
Brute force O(2N)
≈ 1030
for N = 100
not feasible
Hopcroft-Karp Algorithm
O(
√
NL) in worst case
O(logNL) in sparse graphs
Fast enough even for N ≈ 106
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 18 / 26
Driver Nodes
ND in real networks
there is no observable trend across different networks
regulatory networks have high ND ≈ 0.8
social networks display lowest ND
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 19 / 26
Hub controversy
Hub controversy
Are hubs ND or not?
Liu, Slotine, Barabási. Controllability of complex networks. 2011
ND tend to avoid hubs
amount of ND depends on degree distribution
sparse and heterogeneous networks are harder to control than
dense and homogeneous
Cowan et al. Nodal Dynamics, Not Degree Distributions, Determine the Structural Controllability of
Complex Networks. 2012
Signal to power dominating set is enough to control most
complex networks
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 20 / 26
Control Centrality
Control Centrality Measure5
Control Centrality
Control centrality of node i captures the controllable subspace’s
dimension or the controllable subsystem’s size when we control node
i only.
Reminder:
System dynamics: dX
dt = A × X(t) + B × u(t)
Kalman Controllability Matrix:
rankC = [B, A × B, A2 × B, · · · , AN−1 × B]
When we control node i only, B reduces to single non-zero value
vector b(i), and C becomes C(i)
5
Liu, Slotine, Barabási. 2012. Control Centrality and Hierarchical
Structure in Complex Networks
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 21 / 26
Control Centrality
Control Centrality Measure
rankC(i) can be used as a measure indicating the ability of the node
to control the system.
C(i) = N means that node i may control the whole system
C(i) < N indicates a fraction of network that node i may control
Hence, control centrality measure Cc may be defined as
Cc ≡ rankg(C(i))
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 22 / 26
Control Centrality
Control Centrality: Application6
A targeted attack on a malicious network aiming to damage their
controllability.
Challenge: To target an attack, we need to know the network’s
adjacency matrix, which is often not known in real systems.
Solution: Random upstream attack
Randomly choose a fraction of nodes P
For each of chosen nodes, remove one of the incoming
(upstream) neighbors
If there are no incoming neighbors, remove the chosen node
A random upstream attack is almost as good as a targeted attack (Cc)
6
Liu, Slotine, Barabási. 2012. Control Centrality and Hierarchical
Structure in Complex Networks
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 23 / 26
Case study
Synthetic Ablation7
Synthetic lethality
Simultaneous knockout of two otherwise nonessential genes (or
neurons) is lethal to the organism.
7
Towson, Barabási. 2020. Synthetic ablations in the C. elegans nervous
system
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 24 / 26
Case study
Synthetic Ablation
J. Spurný, E. Výtvarová ·Control ·May 12, 2023 25 / 26