  Network control refers to a very large and diverse set of problems including
controllability of linear time-invariant dynamical systems, where the objective
is to select an appropriate input to steer the network to a desired state.
There are many notions of controllability, one of them being structural
controllability, which is intimately connected to finding maximum matchings on
the underlying network topology. In this work, we study fast, scalable
algorithms for finding maximum matchings for a large class of random networks.
First, we illustrate that degree distribution random networks are realistic
models for real networks in terms of structural controllability. Subsequently,
we analyze a popular, fast and practical heuristic due to Karp and Sipser as
well as a simplification of it. For both heuristics, we establish asymptotic
optimality and provide results concerning the asymptotic size of maximum
matchings for an extensive class of random networks.
