Optimality of Fast-Matching Algorithms for Random Networks With Applications to Structural Controllability
Optimality of Fast-Matching Algorithms for Random Networks With Applications to Structural Controllability
复制标题
随机网络快速匹配算法的最优性及其在结构可控性中的应用
DOI：
10.1109/tcns.2016.2553366
复制
发表时间：
2015
影响因子：
4.2
通讯作者：
G. Michailidis
中科院分区：
文献类型：
--
作者：
Mohamad Kazem Shirani Faradonbeh;Ambuj Tewari;G. Michailidis
网络控制是指一系列非常大且多样化的问题，包括线性时不变动力系统的可控性，其目标是选择适当的输入以将网络引导至所需状态。可控性有很多概念，其中之一是结构可控性，它与寻找底层网络拓扑的最大匹配密切相关。在这项工作中，我们研究了快速、可扩展的算法，用于寻找一大类随机网络的最大匹配。首先，我们说明度分布随机网络在结构可控性方面是真实网络的现实模型。随后，我们分析了 Karp 和 Sipser 提出的一种流行的、快速的、实用的启发式方法及其简化形式。对于这两种启发式方法，我们建立了渐近最优性，并提供了有关广泛类别的随机网络的最大匹配的渐近大小的结果。
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.