Barabasi Lab Center for Complex Network Research

Contents I. Introduction 2 II. Previous Work and Relation of Controllability to Other Problems 2 A. Controllability of Undirected Network 2 B. Network Synchronizability 4 C. Congestion Control 4 III. Structural Control Theory 5 A. Why Linear Dynamics? 6 B. Simple Examples 8 C. Structural Controllability Theorem 10 D. Minimum Inputs Theorem 13 IV. Maximum Matching 16

A. Statistical physics description 16 B. Internal energy 17 1. r−regular random digraph 21 2. Poisson-distributed digraph 23 3. Exponentially distributed digraph 24 4. Power-law distributed digraphs 25 5. Static model 27 6. Chung-Lu model 29 C. Entropy 32 V. Control Robustness 37 VI. Network Datasets 38 2 References 42 I. INTRODUCTION This Supplementary Information is organized as follows. In Sec. II, we clarify the fundamental differences between our work and previous research on network controllability. In Sec. III, we give a short introduction to the structural control theory, which can be simply applied to directed networks. The reasons why we focus on linear dynamics are given in Sec. IIIA. Some simple examples in Sec. IIIB demonstrate the difference between controllability, structural controllability and strong structural controllability. The sufficient and necessary conditions for a linear system to be structurally controllable are given by Lin’s structural controllability theorem (SCT), which is discussed in Sec. IIIC. Based on SCT, we derived the minimum input theorem in Sec. IIID, which gives the minimum number of inputs that we need to fully control a directed network. This theorem also enables us to find the driver nodes to which the external inputs should be injected, based on a deep relation between structural controllability and maximum matching. In Sec. IV, we analytically derived the average size and number of the maximum matchings for a random directed network ensemble with a prescribed degree distribution, using the cavity method developed in statistical physics. In Sec. V, we show the results on control robustness against node failure, compared to the results on link failure shown in the main text. The real-world networks analyzed in this work are listed and briefly described in Sec. VI. II. PREVIOUS WORK AND RELATION OF CONTROLLABILITY TO OTHER PROBLEMS A. Controllability of Undirected Network Network controllability is a vast area of research with a long history[1–5]. Here, we clarify the relationship and differences between our work and earlier research in this direction. In particular, we want to emphasize that: 1. The classical concept and condition of controllability was usually applied to undirected net- works. While the control of undirected networks is a problem with its own intellectual challenges, it has so far found little applications to complex systems. The reason is that to best of our knowledge, most, if not all, real-world complex networks where control is SUPPLEMENTARY INFORMATION 2 | WWW.NATURE.COM/NATURE RESEARCH 2...

Website: www.barabasilab.com | Filesize: -
No of Page(s): 44
Download c - Barabasi Lab -- Center for Complex Network Research.pdf