An algorithm for mining key node groups in large-scale complex networks based on spectral graph theory

In this paper, we investigate the saliency identification of node groups in undirected complex networks by utilizing spectral graph theory of pinning control. According to the node significance criterion in network pinning control theory, where important controlled nodes are those maximizing the minimum eigenvalue of the grounded Laplacian matrix after their removal, we propose multi-metric fusion and enhanced greedy search algorithm (MFG), a novel key node group identification framework that integrates multi-metric linear fusion and an enhanced greedy search strategy. First, a linear weighted fusion model that synergistically integrates local centrality metrics with global graph properties is constructed to pre-screen potentially more important node groups, effectively reducing the inherent limitations of a single-metric evaluation paradigm. Second, a dual search strategy combining second-order neighborhood perturbation and global random walk mechanisms is developed to optimize the myopic nature of traditional greedy algorithms. Through iterative selection within pre-screened node groups, the nodes maximizing the minimum eigenvalue of the grounded Laplacian matrix are identified, achieving an optimal balance between local optimization and global search capabilities. Third, computational efficiency is enhanced by using a modified inverse power method for eigenvalue calculation, reducing the complexity of traditional spectral computations. Comprehensive simulations of generated networks and real-world networks demonstrate the framework’s superiority. The evaluation of the proposed algorithm includes three aspects: 1) comparison of the minimum eigenvalues between different algorithms; 2) SIR epidemic modeling for propagation capability assessment; 3) topological analysis of identified key nodes. The simulation results reveal the following two significant points: a) Our method outperforms state-of-the-art benchmarks (NPE, AGM, HVGC) in maximizing the ground Laplacian minimum eigenvalue in synthesized (NW small-world, ER) and real-world networks, especially at critical control sizes; b) The identified critical node groups exhibit unique topological features, typically combining high-level hubs with strategically located bridges to best balance local influence and global connectivity. Importantly, the SIR propagation model confirms that these topologically optimized populations accelerate the early outbreak of epidemics and maximize global saturation coverage, directly linking structural features with superior dynamic influence. These findings provide guidance for controlling information propagation in social networks.