Structural controllability and optimal control of complex networks

• Main Author: Li, Xiang
• Other Authors: Xiao Gaoxi
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2024
• Subjects: Computer and Information Science; Engineering
• Online Access: https://hdl.handle.net/10356/177579
• Institution: Nanyang Technological University

The last two decades have witnessed the rapid growth of studies on complex networks, with vast applications in many areas ranging from physical and engineering domains to neural and economic sciences. For many applications, it is highly desirable to control complex networks. Specifically, according to control theory, a dynamic network system is controllable if it can be driven from any initial state to any desired final state with appropriate external inputs. There are two fundamental issues related to the control of complex networks, including (i) the structural controllability problem, which aims at finding the minimum number of driver nodes connected to external controllers for ensuring that the network, theoretically speaking, can be driven to any state given sufficient time and energy inputs; and (ii) the minimum-cost control problem, which aims at minimizing the cost for driving the system to any predefined state with a given number of controllers. In this thesis, our research mainly contains four different parts. We first study the sufficient control of complex networks. This is to control a sufficiently large portion of the network, where only the quantity of controllable nodes matters. We prove that the minimum input sufficient controllability problem, which involves determining the minimum number of control inputs needed for ensuring structural controllability, can be converted into a minimum-cost flow problem. An algorithm with polynomial complexity is devised to solve this problem. Further, we study the problem of the minimum-cost sufficient control, the goal of which is to drive a sufficiently large subset of the network nodes to any predefined state with the minimum energy cost using a given number of controllers. We propose an “extended L0 norm-constraint-based Projected Gradient Method” (eLPGM) algorithm, which may achieve suboptimal solutions for problems of small or medium sizes. To tackle the large-scale problems, we propose to convert the control problem into a graph problem and devise an efficient low-complexity “Evenly Divided Control Paths” (EDCP) algorithm to tackle the graph problem. Then, we consider the structural controllability of multiplex networks. By proposing a graph-theoretic framework, we address the problem of identifying the minimum set of driver nodes to ensure the structural controllability of multiplex networks, where the driver nodes can only be located in the first layer. We rigorously prove that the problem is essentially a minimum-cost flow problem and devise an algorithm termed “Minimum- cost Flow based Driver-node Identification” (MFDI) algorithm which can achieve the optimal solution with polynomial time complexity. Our research further extends into applying machine learning methods to solve the minimum-cost control problem of complex networks, which entails positioning a specified number of driver nodes to direct the network towards a desired state with minimal overall energy input. To address this challenge, we propose an innovative end-to-end Actor-Cretic method. This model combines the Actor-Cretic mechanism and a projected gradient operator. The Actor-Cretic mechanism balances exploration and exploitation by continuously refining the policy through direct interaction with the environment, while simultaneously leveraging value-based assessments to stabilize the learning process. The projected gradient operator further decreases the control cost until the convergence. The last significant issue we deal with is the minimum-cost control problem on temporal networks, which involves designing a control input signal and an invariant input matrix that minimizes the control cost. By employing variable substitution, we narrow the decision variable down to the input matrix alone. The resulting simplification allows us to relax the Boolean constraints on the input matrix into the convex hull. We propose the “L1 norm based Projected Gradient Method” (L1PGM), which offers a solution residing in a relaxed feasible set, and thus representing a strict lower bound on the control cost. However, as this solution may not be feasible in the original space, we further project it back onto the original feasible region using the “L1-norm based Projected Gradient Method Extension” (L1PGME). This ultimately provides a feasible solution to the minimum-cost control problem in temporal networks, thereby extending the applicability of control strategies to networks with dynamically changing interactions.