Controllability, Matching Ratio and Graph Convergence

There is an important parameter in control theory which is closely related to the directed matching ratio of the network, as shown in the paper of Liu et al. (Nature 473:167–173, 2011). We give proofs of two main statements of Liu et al. (2011) on the directed matching ratio, which were based on numerical results and heuristics from statistical physics. First, we show that the directed matching ratio of directed random networks given by a fix sequence of degrees is concentrated around its mean. We also examine the convergence of the (directed) matching ratio of a random (directed) graph sequence that converges in the local weak sense, and generalize the result of Elek and Lippner (Proc Am Math Soc 138(8):2939–2947, 2010). We prove that the mean of the directed matching ratio converges to the properly defined matching ratio parameter of the limiting graph. We further show the almost sure convergence of the matching ratios for the most widely used families of scale-free networks, which was the main motivation of Liu et al. (2011).