Efficient driver-node selection for pinning control via second-order perturbations

Driver-node selection is a fundamental problem in the pinning control of complex networks, where the aim is to identify a small set of nodes whose external control can most effectively steer the collective dynamics of the network. Driver nodes are typically selected sequentially, and greedy optimization serves as the standard benchmark for such sequential methods since it produces near-optimal node sets. However, this level of accuracy comes at a computational cost that becomes prohibitive for large networks. In this work, we propose a second-order perturbation framework that overcomes this limitation by estimating the shift in the smallest eigenvalue of the network Laplacian, the quantity that governs the stability of the pinned network, using second-order perturbation theory. Consequently, the proposed method reduces the computational complexity of driver-node selection from O(N5) in conventional greedy schemes to O(N4), enabling efficient and scalable selection in large-scale networks. Extensive simulations across diverse network topologies, including small-world, scale-free, and random networks, demonstrate that the proposed method consistently outperforms standard centrality-based heuristics. It achieves performance comparable to optimal greedy benchmarks, while offering substantially higher computational efficiency. The proposed framework thus provides a practical and scalable solution for the control of large complex networks, and more broadly, demonstrates the utility of higher-order perturbation analysis for node-ranking problems in network controllability.