搜索

x

留言板

姓名
邮箱
手机号码
标题
留言内容
验证码

引用本文:
Citation:

邢梓涵, 刘丝语, 刘慧, 陈凌霄
cstr: 32037.14.aps.74.20250416

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

XING Zihan, LIU Siyu, LIU Hui, CHEN Lingxiao
cstr: 32037.14.aps.74.20250416
Article Text (iFLYTEK Translation)
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.
      通信作者: 刘慧, hliu@hust.edu.cn
    • 基金项目: 国家自然科学基金(批准号: 62176099, U24A20272)和华中科技大学学科交叉研究项目(批准号: 5003170102)资助的课题.
      Corresponding author: LIU Hui, hliu@hust.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 62176099, U24A20272) and the Interdisciplinary Research Program of Huazhong University of Science and Technology, China (Grant No. 5003170102).
    [1]

    [2]

    [3]

    [4]

    [5]

    [6]

    [7]

    [8]

    [9]

    [10]

    [11]

    [12]

    [13]

    [14]

    [15]

    [16]

    [17]

    [18]

    [19]

    [20]

    [21]

    [22]

    [23]

    [24]

    [25]

    [26]

    [27]

    [28]

    [29]

    [30]

    [31]

    [32]

    [33]

    [34]

    [35]

    [36]

    [37]

  • N p 乘法次数减少

    100
    4 4.280556 × 108
    8 8.56112 × 108
    12 1.28417 × 109

    1000
    4 7.31605 × 1011
    8 1.46321 × 1012
    12 2.19481 × 1012

    10000
    4 3.73196 × 1015
    8 7.46392 × 1016
    12 1.11959 × 1017
    下载: 导出CSV

    受控节点组规模k 度中心性算法 介数中心性算法 K-Shell算法 NPE算法 AGM算法 HVGC算法 MFG算法
    1 0.0021 0.0032 0.0009 0.0010 0.0029 0.0030 0.0032
    2 0.0045 0.0045 0.0011 0.0010 0.0052 0.0054 0.0059
    3 0.0064 0.0064 0.0012 0.0010 0.0075 0.0081 0.0086
    4 0.0088 0.0081 0.0016 0.0110 0.0096 0.0100 0.0113
    5 0.0104 0.0093 0.0017 0.0118 0.0122 0.0133 0.0141
    6 0.0134 0.0107 0.0033 0.0136 0.0154 0.0160 0.0169
    7 0.0149 0.0120 0.0035 0.0163 0.0170 0.0180 0.0194
    8 0.0161 0.0126 0.0036 0.0191 0.0201 0.0212 0.0223
    9 0.0190 0.0149 0.0037 0.0202 0.0224 0.0235 0.0249
    10 0.0210 0.0171 0.0038 0.0221 0.0250 0.0269 0.0273
    11 0.0246 0.0181 0.0039 0.0243 0.0267 0.0289 0.0299
    12 0.0273 0.0188 0.0041 0.0249 0.0301 0.0310 0.0324
    下载: 导出CSV

    度中心
    性算法
    介数中心
    性算法
    K-Shell
    算法
    NPE
    算法
    AGM
    算法
    HVGC
    算法
    MFG
    算法
    4 616 838 616 616 616 616
    121 924 839 329 207 523 523
    198 329 837 595 523 207 207
    236 207 840 207 371 595 236
    329 595 238 924 236 924 371
    363 236 239 145 887 307 595
    371 382 868 307 417 417 417
    417 145 869 523 329 329 329
    523 307 237 339 339 701 887
    560 146 240 676 409 887 701
    612 814 836 409 382 382 382
    616 915 841 614 937 937 937
    下载: 导出CSV

    受控节点组规模k度中心性算法介数中心性算法K-Shell算法NPE算法AGM算法HVGCMFG算法
    10.01480.00560.00690.00560.01480.01480.0148
    20.02890.02090.01200.02090.02890.02890.0289
    30.03700.02860.01410.02860.03960.04000.0425
    40.05090.03410.01610.03410.05080.05080.0515
    50.05680.04450.01690.03990.05720.05830.0598
    60.06090.05110.01860.04810.06250.06310.0651
    70.06260.05490.02060.05400.06410.06530.0666
    80.06510.06380.02190.06610.06500.06590.0667
    90.06600.06650.02220.06650.06610.06620.0668
    100.06680.06670.02370.06660.06680.06680.0668
    110.06680.06680.02390.06670.06690.06690.0669
    120.06680.06680.02420.06680.06690.06690.0669
    下载: 导出CSV

    度中心
    性算法
    介数中心
    性算法
    K-Shell
    算法
    NPE
    算法
    AGM
    算法
    HVGC
    算法
    MFG
    算法
    7238 7200 379 7200 7238 7238 7238
    3531 7238 764 7238 6102 7200 3531
    4786 2855 952 2855 3531 6102 6102
    525 4357 1335 4357 4786 3531 4786
    3451 6102 2453 5455 4357 525 525
    2511 5455 3241 5128 3451 2855 1796
    3598 4339 3545 3451 1796 5275 3451
    2855 5128 3598 6102 5128 3451 5275
    5128 3451 4810 3545 4812 4812 4812
    6102 4786 4901 4901 5128 4901 2855
    4812 3531 5091 4339 525 4357 4357
    5579 3104 6109 3531 2855 5128 5128
    下载: 导出CSV

    受控节点组规模k度中心性算法介数中心性算法K-Shell算法NPE算法AGM算法HVGC算法MFG算法
    10.648840.648840.620290.648840.648840.648840.64884
    20.652180.652550.642210.652550.652880.652880.65355
    30.653220.653500.648450.653500.654020.654020.65420
    40.653710.654020.651170.653930.654510.654510.65469
    50.654200.654290.652370.654190.654780.654780.65497
    60.654370.654460.653070.654450.655170.654730.65529
    70.654480.654590.653890.654590.655280.654870.65539
    80.654580.654700.654010.654660.655340.654980.65550
    90.654660.654760.654140.654740.655420.655050.65563
    100.654690.654820.654260.654770.655500.655240.65572
    110.654830.654860.654290.654810.655620.655300.65588
    120.654870.654870.654330.654860.655770.655460.65601
    下载: 导出CSV

    度中心
    性算法
    介数中心
    性算法
    K-Shell
    算法
    NPE
    算法
    AGM
    算法
    HVGC
    算法
    MFG
    算法
    161 161 22 161 161 161 161
    122 87 29 122 122 87 87
    83 6 82 83 83 83 6
    108 83 115 108 108 63 83
    87 122 129 63 63 14 122
    63 108 130 87 250 6 378
    435 14 161 435 435 122 14
    14 378 170 250 184 108 108
    167 63 213 184 130 65 334
    184 65 250 167 167 534 435
    6 212 304 130 129 302 63
    65 534 372 65 87 167 167
    下载: 导出CSV

    受控节点组规模k度中心性算法介数中心性算法K-Shell算法NPE算法AGM算法HVGC算法MFG算法
    10.01370.01370.00610.00560.01370.01370.0137
    20.15070.15070.00610.02090.15070.15070.1507
    30.22620.22620.00610.02860.22620.22620.2262
    40.22630.22620.00610..03410.36740.53150.5789
    50.22630.57890.00610.03990.58990.69870.7033
    60.22630.70280.00610.04810.76750.75430.8032
    70.22630.70350.00610.05400.82360.92751.0000
    80.22630.72880.00610.06611.00001.00001.0000
    90.22631.00000.00610.06651.00001.00001.0000
    100.22631.00000.00610.06661.00001.00001.0000
    110.22631.00000.00610.06671.00001.00001.0000
    120.22631.00000.00621.00001.00001.00001.0000
    下载: 导出CSV
    Baidu
  • [1]

    [2]

    [3]

    [4]

    [5]

    [6]

    [7]

    [8]

    [9]

    [10]

    [11]

    [12]

    [13]

    [14]

    [15]

    [16]

    [17]

    [18]

    [19]

    [20]

    [21]

    [22]

    [23]

    [24]

    [25]

    [26]

    [27]

    [28]

    [29]

    [30]

    [31]

    [32]

    [33]

    [34]

    [35]

    [36]

    [37]

  • [1] 汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. 必威体育下载 , 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
    [2] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 必威体育下载 , 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [3] 刘慧, 王炳珺, 陆君安, 李增扬. 复杂网络牵制控制优化选点算法及节点组重要性排序. 必威体育下载 , 2021, 70(5): 056401. doi: 10.7498/aps.70.20200872
    [4] 谭索怡, 祁明泽, 吴俊, 吕欣. 复杂网络链路可预测性: 基于特征谱视角. 必威体育下载 , 2020, 69(8): 088901. doi: 10.7498/aps.69.20191817
    [5] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 必威体育下载 , 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [6] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 必威体育下载 , 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [7] 周建, 贾贞, 李科赞. 复杂网络谱粗粒化方法的改进算法. 必威体育下载 , 2017, 66(6): 060502. doi: 10.7498/aps.66.060502
    [8] 侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. 必威体育下载 , 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [9] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 必威体育下载 , 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [10] 刘金良. 具有随机节点结构的复杂网络同步研究. 必威体育下载 , 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [11] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 必威体育下载 , 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [12] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 必威体育下载 , 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [13] 郝崇清, 王江, 邓斌, 魏熙乐. 基于稀疏贝叶斯学习的复杂网络拓扑估计. 必威体育下载 , 2012, 61(14): 148901. doi: 10.7498/aps.61.148901
    [14] 吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. 必威体育下载 , 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
    [15] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 必威体育下载 , 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [16] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 必威体育下载 , 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [17] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 必威体育下载 , 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [18] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 必威体育下载 , 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [19] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 必威体育下载 , 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 必威体育下载 , 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  648
  • PDF下载量:  15
  • 被引次数: 0
出版历程
  • 收稿日期:  2025-03-31
  • 修回日期:  2025-05-28
  • 上网日期:  2025-06-18
  • 刊出日期:  2025-08-20

返回文章
返回
Baidu
map