Optimizing Driver Nodes for Structural Controllability of Temporal Networks
In this article, we derive conditions for structural controllability of temporal networks that change topology and edge weights with time. The existing results for structural controllability of directed networks assume that all edge weights are chosen independently of each other. The undirected case is challenging due to the constraints on the edge weights. We show that even with this additional restriction, the structural controllability results for the directed case are applicable to the undirected case. We further address two important issues. The first is optimizing the number of driver nodes to ensure the structural controllability of the temporal network. The second is to characterize the maximum reachable subspace when there are constraints on the number of driver nodes. Using the max-flow min-cut theorem, we show that the dimension of the reachable subspace is a submodular function of a set of driver nodes. Hence, we propose greedy algorithms with approximation guarantees to solve the above NP-hard problems. The results of the two case studies illustrate that the proposed greedy algorithm efficiently computes the optimum driver node set for both directed and undirected temporal networks.
Optimizing network topology for average controllability
We address the problem of identifying a network topology of a networked system for maximizing a controllability measure, the average controllability under constraints on the number of links in the network. We consider networked systems consisting of subsystems with higher-order discrete-time linear time-invariant dynamics. We show that the average controllability is a monotone increasing supermodular function of a set of links in the networked system. Since maximizing such a function with cardinality constraints is an NP-hard problem, we analyze the performance guarantees obtained from the greedy algorithm for maximizing non-submodular set functions in terms of supermodular curvature. We show that the lower bound obtained for the greedy algorithm becomes trivial as the number of subsystems in the networked system increases. Hence, we propose two heuristic algorithms to solve the optimization problem and numerically demonstrate the efficiency of the proposed heuristics in terms of computational complexity and performance improvement in average controllability.