Title: Controllability and maximum matchings of complex networks,
Abstract: Previously, the controllability problem of a linear time-invariant dynamical
system was mapped to the maximum matching (MM) problem on the bipartite
representation of the underlying directed graph, and the sizes of MMs on random
bipartite graphs were calculated analytically with the cavity method at zero
temperature limit. Here we present an alternative theory to estimate MM sizes
based on the core percolation theory and the perfect matching of cores. Our
theory is much more simplified and easily interpreted, and can estimate MM
sizes on random graphs with or without symmetry between out- and in-degree
distributions. Our result helps to illuminate the fundamental connection
between the controllability problem and the underlying structure of complex
systems.