Optimality of Fast Matching Algorithms for Random Networks with Applications to Structural Controllability

• Activity Number: 326
• Type: Contributed
• Date/Time: Tuesday, August 11, 2015 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Mohamad Kazem Shirani Faradonbeh* and Ambuj Tewari and George Michailidis
• Companies: University of Michigan and University of Michigan and University of Florida
• Keywords: Maximum Matching ; Karp-Sipser ; Structural Controllability ; Network Control ; Random Networks

Abstract

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 output 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 establish the convergence of matching algorithms for different random networks. 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.