Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes

Abstract

The problem of controllability of the dynamical state of a network is central in network theory and has wide applications ranging from network medicine to financial markets. The driver nodes of the network are the nodes that can bring the network to the desired dynamical state if an external signal is applied to them. Using the framework of structural controllability, here we show that the density of nodes with in-degree and out-degree equal to $0$, $1$ and $2$ determines the number of driver nodes of random networks. Moreover we show that networks with minimum in-degree and out-degree greater than 2, are always fully controllable by an infinitesimal fraction of driver nodes, regardless on the other properties of the degree distribution. Finally, based on these results, we propose an algorithm to improve the controllability of networks.

arXiv comment(9 pages, 4 figures)

References in corpus (18)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Critical phenomena in complex networks
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• The Bethe lattice spin glass revisited
• Pinning-controllability of complex networks
• Controlling edge dynamics in complex networks
• Controlling complex networks: How much energy is needed?
• Cut-offs and finite size effects in scale-free networks
• Emergence of bimodality in controlling complex networks
• Effect of correlations on network controllability
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• The number of matchings in random graphs
• Glass models on Bethe lattices
• Scale-free networks with an exponent less than two
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• The stochastic matching problem
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm

Cited by in corpus (38)

• Control Principles of Complex Networks
• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• Spectrum of Controlling and Observing Complex Networks
• Interdisciplinary and physics challenges of Network Theory
• Control of coupled oscillator networks with application to microgrid technologies
• Control of Multilayer Networks
• Predicting Network Controllability Robustness: A Convolutional Neural Network Approach
• Toward Stronger Robustness of Network Controllability: A Snapback Network Model
• A Learning Convolutional Neural Network Approach for Network Robustness Prediction
• Rare events and discontinuous percolation transitions
• Value of peripheral nodes in controlling multilayer networks
• The theory of percolation on hypergraphs
• Knowledge-Based Prediction of Network Controllability Robustness
• Fluctuations in percolation of sparse complex networks
• Controllability and maximum matchings of complex networks
• Towards Optimal Robustness of Network Controllability: An Empirical Necessary Condition
• Irrelevance of linear controllability to nonlinear dynamical networks
• A Framework of Hierarchical Attacks to Network Controllability
• Stochastic cycle selection in active flow networks
• Multiplex congruence network of natural numbers
• An efficient algorithm for finding all possible input nodes for controlling complex networks
• Input graph: the hidden geometry in controlling complex networks
• Noise Response Data Reveal Novel Controllability Gramian for Nonlinear Network Dynamics
• SPP-CNN: An Efficient Framework for Network Robustness Prediction
• Impulse-induced localized control of chaos in starlike networks
• Controllability of Social Networks and the Strategic Use of Random Information
• Diversity of structural controllability of complex networks with given degree sequence
• One-loop diagrams in the Random Euclidean Matching Problem
• Higher-order models capture changes in controllability of temporal networks
• General theory for extended-range percolation on simple and multiplex networks
• Statistical mechanics of bipartite $z$-matchings
• Altering control modes of complex networks based on edge removal
• Altering nodes types in controlling complex networks
• Characterization of Driver Nodes of Anti-Stable Networks
• Controllability of networked MIMO systems
• Phase transition in the bipartite z-matching
• Control and controllability of nonlinear dynamical networks: a geometrical approach
• Fundamental building blocks of controlling complex networks: A universal controllability framework