搜索

x
中国物理学会期刊

基于谱图理论的大规模复杂网络重要节点组挖掘算法

CSTR: 32037.14.aps.74.20250416

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

CSTR: 32037.14.aps.74.20250416
PDF
HTML
导出引用
  • 本文研究了无向复杂网络中基于谱图理论的节点组重要性挖掘问题. 依据复杂网络牵制控制理论中节点重要性评价指标, 删后Laplacian矩阵最小特征值较大者为重要受控节点. 本文提出一种基于多重图特征线性融合与改进贪心搜索的重要节点组挖掘方法(multi-metric fusion and enhanced greedy search algorithm, MFG算法). 该方法首先通过融合度中心性、介数中心性、K-Shell值和电阻距离等多重指标, 结合全局图特征(如图密度、平均路径长度等)构建线性加权融合模型, 预筛选候选节点组以克服单一指标的局限性; 其次, 设计二阶邻域局部扰动与全局随机游走搜索策略, 优化传统贪心算法的短视性, 在预筛选节点组中迭代选择使得删后Laplacian矩阵最小特征值最大的节点, 从而平衡局部最优与全局搜索能力; 并利用改进的反幂法进行最小特征值的计算, 降低了传统计算特征谱的复杂度, 从而使得算法总体计算性能提升. 最后, 在经典网络模型和多个真实网络中进行仿真分析, 利用不同算法挖掘重要节点组, 计算删后拉普拉斯矩阵的最小特征值, 利用SIR模型进行传播模拟, 并从网络拓扑上分析不同算法筛选出的重要节点组特征. 结果表明MFG算法相比其他几种算法挖掘重要节点组的效果更好, 对于社交网络信息传播控制具有指导意义.

     

    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.

     

    目录

    /

    返回文章
    返回