The minimum number of inputs needed to control a network is frequently used to quantify its controllability. Control of linear dynamics through a minimum set of inputs, however, often has prohibitively large energy requirements and there is an inherent trade-off between minimizing the number of inputs and control energy. To better understand this trade-off, we study the problem of identifying a minimum set of input nodes such that controllabililty is ensured while restricting the length of the longest control chain. The longest control chain is the maximum distance from input nodes to any network node, and recent work found that reducing its length significantly reduces control energy. We map the longest control chain-constraint minimum input problem to finding a joint maximum matching and minimum dominating set. We show that this graph combinatorial problem is NP-complete, and we introduce and validate a heuristic approximation. Applying this algorithm to a collection of real and model networks, we investigate how network structure affects the minimum number of inputs, revealing, for example, that for many real networks reducing the longest control chain requires only few or no additional inputs, only the rearrangement of the input nodes.
翻译:控制网络所需的最低投入数量经常被用来量化其可控性。通过一组最低投入对线性动态的控制,然而,通过一组最低投入对线性动态的控制往往具有令人望而却步的巨大能源需求,在尽量减少投入量和控制能源之间存在着内在的权衡。为了更好地理解这一权衡,我们研究如何确定一套最低投入节点,以便在限制最长控制链的长度的同时确保控制稳定性。最长的控制链是从输入节点到任何网络节点的最大距离,而最近发现缩短其长度会大大降低控制能量的工作。我们绘制了最长的控制链限制最小投入问题,以找到一个联合最大匹配和最小占位的套件。我们展示了这个图形组合问题是NP的,我们引入并验证了一种超常近似值。我们将这一算法应用到一个真实和模型网络的集合中,我们调查网络结构如何影响最低投入数量,例如,对于许多减少最长控制链的网络来说,只需要很少或没有额外的投入,只有输入节点的重新排列。