Maximizing the smallest eigenvalue of grounded Laplacian matrix

For a connected graph $$\mathcal {G}=(V,E)$$ G = ( V , E ) with n nodes, m edges, and Laplacian matrix $${\varvec{ L }}$$ L , a grounded Laplacian matrix $${\varvec{ L }}(S)$$ L ( S ) of $$\mathcal {G}$$ G is a $$(n-k) \times (n-k)$$ ( n - k ) × ( n - k ) principal submatrix of $${\varvec{ L }}$$ L , obtained from $${\varvec{ L }}$$ L by deleting k rows and columns corresponding to k selected nodes forming a set $$S\subseteq V$$ S ⊆ V . The smallest eigenvalue $$\lambda (S)$$ λ ( S ) of $${\varvec{ L }}(S)$$ L ( S ) plays a pivotal role in various dynamics defined on $$\mathcal {G}$$ G . For example, $$\lambda (S)$$ λ ( S ) characterizes the convergence rate of leader-follower consensus, as well as the effectiveness of a pinning scheme for the pinning control problem, with larger $$\lambda (S)$$ λ ( S ) corresponding to smaller convergence time or better effectiveness of a pinning scheme. In this paper, we focus on the problem of optimally selecting a subset S of fixed $$k \ll n$$ k ≪ n nodes, in order to maximize the smallest eigenvalue $$\lambda (S)$$ λ ( S ) of the grounded Laplacian matrix $${\varvec{ L }}(S)$$ L ( S ) . We show that this optimization problem is NP-hard and that the objective function is non-submodular but monotone. Due to the difficulty of obtaining the optimal solution, we first propose a naïve heuristic algorithm selecting one optimal node at each time for k iterations. Then we propose a fast heuristic scalable algorithm to solve this problem, using the derivative matrix, matrix perturbations, and Laplacian solvers as tools. Our naïve heuristic algorithm takes $$\tilde{O}(knm)$$ O ~ ( k n m ) time, while the fast greedy heuristic has a nearly linear time complexity of $$\tilde{O}(km)$$ O ~ ( k m ) , where $$\tilde{O}(\cdot )$$ O ~ ( · ) notation suppresses the $$\textrm{poly} (\log n)$$ poly ( log n ) factors. We also conduct numerous experiments on different networks sized up to one million nodes, demonstrating the superiority of our algorithm in terms of efficiency and effectiveness compared to baseline methods.