-
本文研究了无向复杂网络中基于谱图理论的节点组重要性挖掘问题。依据复杂网络牵制控制理论中节点重要性评价指标：删后Laplacian矩阵最小特征值较大者为重要受控节点。本文提出一种基于多重图特征线性融合与改进贪心搜索的重要节点组挖掘方法（Multi-metric Fusion and enhanced Greedy search algorithm，下文简称为MFG算法）。该方法首先通过融合度中心性、介数中心性、K-Shell值和电阻距离等多重指标，结合全局图特征（如图密度、平均路径长度等）构建线性加权融合模型，预筛选候选节点组以克服单一指标的局限性；其次，设计二阶邻域局部扰动与全局随机游走搜索策略，优化传统贪心算法的短视性，在预筛选节点组中迭代选择使得删后Laplacian矩阵最小特征值最大的节点，从而平衡局部最优与全局搜索能力；并利用改进的反幂法进行最小特征值的计算，降低了传统计算特征谱的复杂度，从而使得算法总体计算性能提升。最后，我们在经典网络模型和多个真实网络中进行仿真分析，利用不同算法挖掘重要节点组，计算删后拉普拉斯矩阵的最小特征值，利用SIR模型进行传播模拟，并从网络拓扑上分析不同算法筛选出的重要节点组特征。结果表明MFG算法相比其他几种算法挖掘重要节点组的效果更好，对于社交网络信息传播控制具有指导意义。
-
关键词:
- 复杂网络 /
- 节点组重要性 /
- 预筛选算法 /
- 删后拉普拉斯矩阵谱图理论
In this paper, we investigate node group significance identification in undirected complex networks by utilizing spectral graph theory of pinning control. Building upon 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 MFG (Multi-metric Fusion and enhanced Greedy search), a novel key node group identification framework that integrates multi-metric linear fusion and an enhanced greedy search strategy. The methodology initiates by constructing a linear weighted fusion model that synergistically integrates local centrality metrics with global graph properties to pre-screening node groups that are likely to be more important, effectively mitigating the inherent limitations of single-metric evaluation paradigms. Second, a dual search strategy combining second-order neighborhood perturbation and global random walk mechanisms is developed to optimize the myopic nature of conventional greedy algorithms. Through iterative selection within pre-screened node groups, this approach identifies nodes maximizing the minimum eigenvalue of the grounded Laplacian matrix, achieving an optimal balance between local optimization and global search capabilities. Third, computational efficiency is enhanced using a modified inverse power method for eigenvalue calculation, reducing the complexity of traditional spectral computations. Comprehensive simulations on generated networks and real-world networks demonstrate the framework’s superiority. The evaluation of the proposed algorithm incorporates three aspects: 1) comparison of the minimum eigenvalues under different algorithms; 2) SIR epidemic modeling for propagation capability assessment; 3) topological analysis of identified key nodes. Simulation results reveal two significant findings: a) Our method outperforms state-of-the-art benchmarks(NPE,AGM,HVGC) in maximizing the grounded Laplacian’s minimum eigenvalue across synthetic(NW small-world,ER) and real-world networks,particularly at critical control sizes; b) The identified critical node groups exhibit distinctive topological signatures-typically combining high-degree hubs with strategically located bridges-that optimally balance local influence and global connectivity. Critically, SIR propagation modeling confirms these topologically optimized groups accelerate early-stage outbreaks and maximize global saturation coverage,directly linking structural signatures to superior dynamic influence. These findings provide guidelines for information propagation control in social networks.-
Keywords:
- Complex network /
- Node group importance /
- Pre-screening algorithm /
- Spectral graph theory of the grounded Laplacian matrix
-
[1] Liu H, Xu X H, Lu J A, Chen G R, Zeng Z G 2021IEEE Trans. Syst. Man Cybern.: Syst. 51 786
[2] Liu H, Wang B J, Lu J A, Li Z Y 2021Acta Phys. Sin. 70 056401(in Chinese)[刘慧, 王炳珺, 陆君安, 李增扬2021物理学报70 056401]
[3] Zhou F, Su C, Xu S Q, Lü L Y 2022Chinese Phys. B 31 068901
[4] Dai J Y, Wang B, Sheng J F, Sun Z J, Khawaja F R, Ullah A 2019IEEE Access 7 131719
[5] Kong J T, Huang J, Gong J X, Li E Y 2018Acta Phys. Sin. 67 098901(in Chinese) [孔江涛，黄健，龚建兴，李尔玉2018物理学报67 098901]
[6] Wang T T, Lang Z W, Zhang R X 2023Acta Phys. Sin. 72 048901(in Chinese)[汪亭亭，梁宗文，张若曦2023物理学报72 048901]
[7] Yang S Q,Jiang Y,Tong T C,Yan Y W,Gan G S 2021Acta Phys. Sin. 70 216401(in Chinese)[杨松青，蒋沅，童天驰，严玉为，淦各升2021物理学报70 216401]
[8] Jiang T S,Ruan Y R,Li H,Bai L,Yuan Y F,Yu T Y 2025Acta Phys. Sin. 7420250329(in Chinese)[姜廷帅，阮逸润，李海，白亮，袁逸飞，于天元2025物理学报7420250329]
[9] Rezaei A A, Munoz J, Jalili M, Khayyam H 2023Expert Syst. Appl. 214 119086
[10] Zhang Y H, Lu Y L, Yang G Z, Hang Z J 2022Appl. Sci. 12 1944
[11] Wang B Y, Yang X C, Lu S R, Tang Y P, Hong S Q, Jiang H Y 2024Acta Phys. Sin. 73226401[王博雅, 杨小春, 卢升荣, 唐勇平, 洪树权, 蒋惠园2024物理学报73 226401]
[12] Lü L Y, Zhou T, Zhang Q M, Stanley H E 2016Nat. Commun. 7 10168
[13] Kou J H, Jia P, Liu J Y, Dai J Q, Luo H R 2023Neurocomputing 530 23
[14] Qiu Z H, Fan T L, Li M, Lü L Y 2021New J. Phys. 23 033036
[15] Chakrabarti S, Dom B, Raghavan P, Rajagopalan S, Gibson D, Kleinberg J 1998Computer Networks and ISDN Systems 30 65
[16] Fan C J, Zeng L, Sun Y Z, Liu Y Y 2020Nat. Mach. Intell. 2 317
[17] Zhao X Y, Huang B, Tang M, Zhang H F, Chen D B 2014Europhysics Letters 108 68005
[18] Bao Z K, Liu J G, Zhang H F 2017Phys. Lett. A 381 976
[19] Ji S G, Lü L Y, Yeung C H, Hu Y Q 2017New J. Phys. 19 073020
[20] Anderson R M, May R M 1991Infectious Diseases of Humans: Dynamics and Control (Oxford University Press)
[21] Pastor-Satorras R, Castellano C, Mieghem P V, Vespignani A 2015Rev. Mod. Phys. 87 925
[22] Feng M L, Zhang S F, Xia C Y, Zhao D W 2024Chaos 34 073128
[23] Avraam D, Hadjichrysanthou C 2024J. Theor. Biol. 599 112010
[24] Lu J A, Liu H, Chen J 2016Synchronization in Complex Dynamical Networks(Vol. 1) (Beijing: Higher Education Press) p49
[25] Pirani M, Sundaram S 2016IEEE Trans. Autom. Control 61 509
[26] Bapat R B 2010Graphs and Matrices(Springer London)
[27] Zhu H Y, Klein D J, Lukovits I 1996J. Chem. Inf. Model. 36 420
[28] Gutman I, Mohar B 1996J. Chem. Inf. Comput. Sci. 36982
[29] Guan Z, Chen J L 1990Numerical calculation method (Beijing: Tsinghua University Press) (in Chinese) [关治, 陈景良1990数值计算方法(北京:清华大学出版社)]
[30] Liu Y Q, Lu J A 2007Complex Systems and Complexity Science 413(in Chinese) [刘砚青, 陆君安2007复杂系统与复杂性科学413]
[31] Dean J, Ghemawat S 2008Commun. ACM 51 107
[32] Yin H, Benson A R, Leskovec J, Gleich D F 2017Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD’17) Halifax, NS, Canada, August 13-17, 2017 p555
[33] Wu Y H, Tian K, Li M D, Hu F 2023Comput. Appl. Eng. Educ. 1966(in Chinese) [吴英晗, 田阔, 李明达, 胡枫2023计算机工程与应用1966]
[34] Meng L, Xu G Q, Dong C 2025PHYSICA A 657 130237
[35] Zhu S Q, Zhan J, Li X 2023Sci Rep. 1316404
[36] Snap: Stanford network analysis project https://snap.stanford.edu/.
[37] Jiang W C, Wang Y H 2020IEEE Access 8 32432
计量
- 文章访问数: 262
- PDF下载量: 5
- 被引次数: 0
下载:
