Target control of linear directed networks based on the path cover problem

Abstract

Abstract Securing complete control of complex systems comprised of tens of thousands of interconnected nodes holds immense significance across various fields, spanning from cell biology and brain science to human-engineered systems. However, depending on specific functional requirements, it can be more practical and efficient to focus on a pre-defined subset of nodes for control, a concept known as target control. While some methods have been proposed to find the smallest driver node set for target control, they either rely on heuristic approaches based on k-walk theory, lacking a guarantee of optimal solutions, or they are overly complex and challenging to implement in real-world networks. To address this challenge, we introduce a simple and elegant algorithm, inspired by the path cover problem, which efficiently identifies the nodes required to control a target node set within polynomial time. To practically apply the algorithm in real-world systems, we have selected several networks in which a specific set of nodes with functional significance can be designated as a target control set. The analysed systems include the complete connectome of the nematode worm C. elegans, the recently disclosed connectome of the Drosophila larval brain, as well as dozens of genome-wide metabolic networks spanning major plant lineages. The target control analysis shed light on distinctions between neural systems in nematode worms and larval brain insects, particularly concerning the number of nodes necessary to regulate specific functional systems. Furthermore, our analysis uncovers evolutionary trends within plant lineages, notably when examining the proportion of nodes required to control functional pathways.