Optimizing Driver Nodes for Structural Controllability of Temporal Networks

Published in "IEEE Transactions on Control of Network Systems "
Manikya Valli Srighakollapu , Rachel Kalpana Kalaimani , Ramkrishna Pasumarthy

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.