Minimum-cost control of directed complex networks

• Main Author: Ding, Jie
• Other Authors: Wen Changyun
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: http://hdl.handle.net/10356/74223
• Institution: Nanyang Technological University

Complex networks emerge in diverse areas, ranging from social to biological, economic and technological systems. Among these applications, controlling the complex networks is one of the most important problem, which can guarantee reliable and efficient operations of the network. 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. Existing works mainly focus on the problem of finding the minimum number of nodes connected with external input signals under different conditions such that the resulting network system is controllable. However, as we know when the Gramian matrix tend to be singular, the control cost of the network will be prohibitively large, resulting in the network is theoretically controllable but practically uncontrollable. Therefore, controlling the network with minimum cost has been an important problem to be solved. In this dissertation, we first consider the problem of locating a key node set of a network, which is a subset of nodes connected with a given number of external control sources to achieve minimum control cost in controlling the network. To solve this problem, projected gradient method (PGM) and projected trust-region method (PTM) are proposed with established convergence property. We show that PGM is more computationally efficient than PTM. Projected gradient method extension (PGME) is also proposed to identify the key node set with the definition of importance index. Simulation results demonstrate satisfactory performance of the proposed algorithms. It is found that the importance index of a node is strongly correlated to occurrence rate of that node to be selected as a key node in Monte-Carlo realizations. We also point out that key nodes tends to divide elementary topologies equally when the control cost reaches its minimum and low-degree nodes are more likely to be selected as key nodes. Additionally, we further improve the results of key node selection based on degree distribution and proposed an algorithm which outperforms PGME. We first reformulate the minimum-control-cost model in Boolean constraints. By relaxing these constraints into their convex hull, we introduce inexact alternating direction method of multipliers (IADMM). With the help of degree distribution, an extension algorithm, named degree-based IADMM (D-IADMM), is proposed such that key nodes can be pinpointed. We further improve the performance of D-IADMM by employing a simple greedy algorithm named local optimization. The proposed algorithms are validated by numerical examples ranging from Erdos-Renyi networks, scale-free networks to some real-life networks. Moreover, we investigate the implicit linear quadratic regulation problem where a feasibility is provided to minimize the control cost with regards to input and state. Specifically, a quadratic term is added to the objective function such that the deviation of transient state is penalized. To obtain the optimal input strategy, orthonormal-constraint-based projected gradient method (OPGM) is proposed. The convergence of OPGM is established theoretically. The effectiveness and validity of OPGM is examined through extensive simulations. The variations of inputs and system states are observed under different cost functions. The last significant issue we deal with is to design the network topology with given external control sources such that the control cost is minimum. A matrix function optimization model is proposed to study how the network topology evolves when the objective is to achieve an optimal control of the networks. By obtaining the direction of network topology evolution, a normalized and projected gradient-decent method (NPGM) based on the obtained gradient of the network topology evolution is developed to solve the proposed optimization problem. It is proven that NPGM linearly converges to a local minimum point. We also derive an optimality condition to determine whether a converged solution is global minimum or not, and such a condition is verified through numerous experimental tests on directed networks. We find that a network adaptively changes its topology in such a way that many sub-networks are gradually evolved towards a pre-established control target. Such a finding enables us to model and explain how real-world complex networks adaptively self-organize themselves to many similar subnetworks during a relatively long evolution process. We further extend the model to another case, i.e. to investigate how connection strengths between nodes vary in accordance with control cost for complex networks with fixed topological structure. We obtain the optimal connection strength matrix with the proposed NPGM. It is discovered that several control-flow subnetworks are self-formed. Moreover, the control cost with optimal weight matrix is smallest when pre-located controller sources distribute evenly. These observations provide a comprehensive understanding of the impact of connection link weight on control cost for complex networks.