Insight into controllability of complex networks through augmenting trail

Abstract Controlling complex networks remains a central challenge in modern network science and engineering, with broad implications across disciplines such as electronic circuits, gene regulation, metabolic systems, and ecological networks. Structural controllability theory provides a mathematical foundation for identifying a minimal set of driver nodes through which external inputs can steer the entire system. Traditional approaches based on maximum matching, such as Path Finding and Signal Sharing, often yield redundant or non-optimal driver-node selections, particularly in networks lacking a root strongly connected component. In this study, a refined framework is developed by introducing new concepts in matching theory and formulating an Augmenting Trail method for determining maximum matchings in directed networks. The unmatched nodes resulting from this process represent the optimal set of driver nodes required for full structural controllability. Comprehensive experiments on 90 empirical networks and multiple synthetic models demonstrate that the Augmenting Trail method consistently identifies a smaller and structurally more diverse set of driver nodes compared with existing algorithms. Analyses of node-level indices—including degree, coreness, and clustering coefficient—reveal that Augmenting Trail tends to select nodes of moderate connectivity located at the periphery of strongly connected components, thereby ensuring efficient and distributed control. Jaccard similarity assessments confirm that the Augmenting Trail method introduces new, non-redundant driver nodes while maintaining partial overlap with established methods. Furthermore, a strong negative correlation ($ \rho = -0.62 $, $ p\,\lt\,0.001 $) between degree heterogeneity and the fraction of driver nodes underscores that networks with higher topological variability require fewer control inputs, a relationship consistently observed across Erdős–Rényi, small-world, and clustered network types. Overall, the Augmenting Trail framework achieves a superior balance between control efficiency and structural diversity, bridging theoretical rigor with computational scalability. It provides a generalized foundation for analyzing controllability in large-scale, heterogeneous, and dynamically evolving networked systems.