随着信息技术的快速发展，复杂网络已经从单纯的理论研究迈向了广泛的实际应用，成为揭示通信网络、社交网络、计算机网络、生物网络等复杂系统领域结构特征和行为属性的重要途径和策略。识别复杂网络中的关键节点就是确定一组在特定约束下，从网络中移除后会极大影响网络连通性的节点子集的优化问题。复杂网络的关键节点识别问题对于理解网络结构、分析网络功能和优化网络性能具有十分重要的作用。本文基于节点的综合特征，对关键节点识别问题展开深入研究，具体研究内容如下：

针对关键节点识别问题，提出一种基于层级划分和节点特征的关键节点识别方法框架BOLC。该方法首先计算出节点初始覆盖集并将其从原网络中移除，再从初始覆盖集中依据某种节点中心性指标向原网络迭代回添节点。为提高初始集的有效性和准确率，提出一种利用层级划分思想的初始覆盖集选择算法LIS。为避免回添过程陷入局部最优解，综合节点局部结构特征和全局属性，提出节点综合特征中心性指标SFC。通过在人工合成网络以及真实网络数据集上的实验结果表明，LIS算法可以更精准的选择初始覆盖集，BOLC方法和SFC中心性指标能够更准确的评估节点的重要性，且上述方法的性能显著优于其他方法。

针对关键节点解集局部极值问题以及更进一步优化可行解的质量，提出一种基于引力模型的关键节点迭代优化算法OBG，通过搜索并移除初始解中的低质量节点，回添补集中的高质量节点来优化解集。为避免算法过早收敛，导致解集陷入局部极值的问题，综合节点间多种特征属性信息，引入节点间引力模型GBN以探索更广的解空间。在人工合成网络和真实网络数据集上的实验结果表明，OBG算法迭代过程中的GBN扰动策略可以有效提升解集的质量。相较于其他启发式优化算法，OBG方法能更好的优化关键节点的初始解。

基于上述研究成果，使用BOLC和OBG方法，设计开发了一种复杂网络关键节点识别系统。系统支持自定义上传网络数据集，读取数据集格式并绘制网络可视化界面。首先，BOLC方法作用于识别网络数据集的初始解，之后输出计算结果并进行相应的可视化展示；其次，若初始解的质量无法满足应用问题目标的要求，可利用OBG算法对初始解进行优化。最后，为研究人员提供网络数据保存、可视化操作展示等功能。

With the rapid development of information technology, complex networks have moved from simple theoretical research to extensive practical applications, becoming an important way and strategy to reveal the structural characteristics and behavioral attributes of complex systems in fields such as communication networks, social networks, computer networks, and biological networks. Identifying critical nodes in complex networks is an optimization problem that determines a subset of nodes that, under specific constraints, will greatly affect network connectivity when removed from the network. The identification of critical nodes in complex networks plays a crucial role in understanding network structure, analyzing network functions, and optimizing network performance. This article conducts in-depth research on the identification of critical nodes based on the comprehensive characteristics of nodes. The specific research content is as follows:

Targeting critical node detection problem, propose a based on layer and centrality critical nodes select method (BOLC). This method first calculates the initial coverage set of nodes and removes them from the original network, and then iteratively add nodes back to the original network from the initial coverage set according to a node centrality index. To improve the effectiveness and accuracy of the initial set, proposed a layer iterate select of initial set method (LIS). To avoid getting stuck in local optima during the backpropagation process, a node synthetical feature centrality (SFC) is proposed by integrating the local structural characteristics and global attributes of the node. The experimental results on artificial synthetic networks and real network datasets show that LIS algorithm can more accurately select the initial coverage set, BOLC method and SFC centrality index can more accurately evaluate the importance of nodes, and the performance of the method is significantly better than other methods.

Targeting the local extremum problem of critical node solution set and further optimizing the quality of feasible solutions, propose a critical node iterative optimization algorithm based on gravity model (OBG), which optimizes the solution set by searching and removing low-quality nodes in the solution set and adding high-quality nodes in the complement set. To avoid premature convergence of algorithm iterations and the problem of falling into local extremum, comprehensive node multiple feature attribute information between nodes, the gravity model between nodes (GBN) is introduced to explore a wider solution space. The experimental results on both artificial and real network datasets show that the GBN perturbation strategy during OBG algorithm iteration can effectively improve the quality of the solution set. Compared to other heuristic optimization algorithms, the OBG method can better optimize the initial solution set of the problem.

Based on the above research results, a critical node detection system for complex networks is designed and developed using BOLC and OBG methods. The system supports user-defined uploading of network datasets, reading the dataset formats and drawing the network visualization interfaces. Firstly, the BOLC method is used to identify the initial solution of the network dataset, and then the calculation results are outputted and displayed visually; Secondly, if the quality of the initial solution cannot meet the requirements of the application problem goal, the OBG algorithm can be used to optimize the initial solution. Finally, it provides researchers with functions such as network data storage, visual operation display, etc.

[1]Lalou M, Tahraoui M A, Kheddouci H. The critical node detection problem in networks :A survey[J]. Computer Science Review, 2018, 28(MAY): 92-117.

[2]Borgatti S P, Mehra A, Brass D J, et al. Network analysis in the social sciences[J]. Science, 2009, 323(5916): 892-895.

[3]Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(02), 026113. 1-15.

[4]Megzari, A., Pravija Raj, P.V., Osamy, W. et al. Applications, challenges, and solutions to single- and multi-objective critical node detection problems: a survey[J]. J Supercomput, 2023, 79(17): 19770–19808.

[5]任晓龙, 吕琳媛. 网络重要节点排序方法综述[J].科学通报, 2014, 59(13):1175-1197.

[6]D’Souza, R.M., di Bernardo, M. & Liu, YY. Controlling complex networks with complex nodes[J]. Nat Rev Phys, 2023, 5(4), 250–262.

[7]S. Pant, M. Sharma, D. K. Sharma, et al. Enforcing intelligent Learning-Based security in internet of everything[J], IEEE Internet of Things Journal, 2023, 10(4), 3071-3078.

[8]Tingting C, Yan L, Xiongfei J, et al. Spatiotemporal patterns of risk propagation in complex financial networks[J]. Applied Sciences, 2023, 13(2): 1129.

[9]Yang L, Ma Z Y, Li Z W. Rumor containment by blocking nodes in social networks[J]. IEEE Transactions on Systems, Man, and Cybernetics:Systems,2023,53(7): 3990-4002.

[10]Huang X L, Chen J, Cai M, et al. Traffic node importance evaluation based on clustering in represented transportation networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(9): 16622-16631.

[11]Tian G, Yang X, Li Y,et al. Hybrid weighted communication network node importance evaluation method[J]. Frontiers in Physics. 2023, 11: 1133250.

[12]Aringhieri R, Grosso A, Hosteins P, et al. A general evolutionary framework for different classes of critical node problems[J]. Engineering Applications of Artificial Intelligence, 2016, 55: 128-145.

[13]Arulselvan A, Commander W C, Elefteriadou L, et al. Detecting critical nodes in sparse graphs[J]. Computers & Operations Research, 2009, 36(7): 2193-2200.

[14]Freeman L C. Centrality in social networks conceptual clarification[J]. Social Network, 1979, 1(3): 215-239.

[15]Sabidussi G. The centrality index of a graph[J]. Psychombtrika,1966,31(4):581-603.

[16]Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.

[17]李鹏, 王世林, 陈光武等. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 计算机应用, 2023, 43(04): 1109-1114.

[18]Zhao Na, Wang Hao, Wen Jun-jie, et al. Identifying critical nodes in complex networks based on neighborhood information[J]. New Journal of Physics,2023, 25(8).

[19]吴亚丽, 任远光, 董昂等. 基于邻域K-shell分布的关键节点识别方法[J]. 计算机工程与应用, 2024, 60(02): 87-95.

[20]汪亭亭,梁宗文,张若曦.基于信息熵与迭代因子的复杂网络节点重要性评价方法[J]. 物理学报, 2023, 72(04): 337-347.

[21]Képes T. The critical node detection problem in hypergraphs using weighted node degree centrality[J]. PeerJ Computer science, 2023, 9: e1351.

[22]Dal C A,Petronetto, F. Graph regularization centrality[J]. Physica A: Statistical Mechanics and its Applications, 2023, 628: 129188.

[23]Min L, Shuming Z, Dajin W, et al. Identifying influential nodes based on resistance distance[J]. Journal of Computational Science, 2023, 67：101972.

[24]朱敬成, 刘辉, 王伦文等. 基于网络拓扑重合度的关键节点识别方法[J]. 计算机应用研究, 2021, 38(12): 3581-3585.

[25]Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893

[26]谢丽霞, 孙红红, 杨宏宇, 等. 基于K-shell的复杂网络关键节点识别方法[J]. 清华大学学报(自然科学版), 2022, 62(05): 849-861.

[27]熊才权, 古小惠, 吴歆韵. 基于K-shell位置和两阶邻居的复杂网络节点重要性评估方法[J]. 计算机应用研究, 2023, 40(03): 738-742.

[28]Mukhtar M F, Abas Z A, Baharuddin A S, et al. Integrating local and global information to identify influential nodes in complex networks[J]. Scientific Reports, 2023, 13(1).

[29]李蜜佳, 卫红权, 李英乐, 等. 基于改进K-Shell的社会网络关键节点挖掘算法[J]. 计算机应用与软件, 2023, 40(07): 305-310.

[30]Brin S, Page L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1): 107-117.

[31]Zheng J M, Liu J. A new scheme for identifying important nodes in complex networks based on generalized degree[J]. Journal of Computational Science, 2023,67.

[32]Zhang R X, Liang Z W, Wang T T. Node importance measurement method based on multi-attribute fusion[J]. Modern Physics Letters B, 2023, 37(23).

[33]Di Summa M, Grosso A, Locatelli M. Branch and cut algorithms for detecting critical nodes in undirected graphs[J]. Comput Optim Appl, 2012, 53(3): 649-680.

[34]Veremyev A, Boginski V, Pasiliao L E. Exact identification of critical nodes in sparse networks via new compact formulations[J]. Optimization Letters, 2014, 8(4): 1245-1259.

[35]程适, 王雪萍, 刘悦, 等. 面向非线性方程组的学习型头脑风暴优化算法[J]. 计算机工程, 2023, 49(07): 47-54.

[36]Veremyev A, Prokopyev A O, Pasiliao L E. An integer programming framework for critical elements detection in graphs[J]. J Comb Optim, 2014, 28(1): 233-273.

[37]Shen Y L, Nguyen P N, Xuan Y, et al. On the discovery of critical links and nodes for assessing network vulnerability[J]. IEEE/ACM Transactions on Networking (TON), 2013, 21(3): 963-973.

[38]Javad R, Fatemeh Z, Ali S M, et al. EIA-CNDP: An exact iterative algorithm for critical node detection problem[J]. Computers and Operations Research, 2021,127.

[39]Veremyev A, Prokopyev A O, Pasiliao L E. Critical nodes for distance‐based connectivity and related problems in graphs[J]. Networks, 2015, 66(3): 170-195.

[40]Uche G A, Ashwin A, Kerem A, et al. Efficient methods for the distance-based critical node detection problem in complex networks[J]. Computers Operations Research, 2021, 131: 105254.

[41]Salemi H, Buchanan A. Solving the distance-based critical node problem[J]. INFORMS Journal on Computing, 2022, 34(3): 1309-1326.

[42]Yang K W, Li J C, Liu M D, et al. Complex systems and network science: a survey[J]. Journal of Systems Engineering and Electronics, 2023, 34(3): 543-573.

[43]Addis B, Aringhieri R, Grosso A, et al. Hybrid constructive heuristics for the critical node problem[J]. Annals of Operations Research, 2016, 238(1-2): 637-649.

[44]许钦钧, 徐龙琴, 刘双印, 等. 基于飞蛾扑火算法的关键节点挖掘方法[J]. 计算机应用研究, 2023, 40(09): 2713-2719+2728.

[45]熊才权, 古小惠, 吴歆韵. 基于邻居层级分布引力模型的节点重要性评估方法[J]. 数学物理学报, 2023, 43(06): 1869-1879.

[46]邓志文, 李新春, 孔杰等. 基于层间互信息的时序网络节点重要性识别方法[J]. 运筹与管理, 2023, 32(08): 108-113.

[47]吴英晗, 田阔, 李明达等. 利用节点传播熵识别超网络重要节点[J]. 计算机工程与应用, 2023, 59(19): 66-74.

[48]原慧琳, 冯宠. 基于k-shell熵的影响力节点的排序与识别[J]. 计算机科学, 2022, 49(S2): 226-230.

[49]刘子彤, 王威, 丁国如等. 一种面向有权重通信网络的关键节点识别方法[J]. 数据采集与处理, 2023, 38(01): 51-62.

[50]郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(09): 1872-1880.

[51]Lu P L, Zhang Z R. Critical nodes identification in complex networks via similarity coefficient[J]. Modern Physics Letters B, 2022, 36(09): 2150620.

[52]Zhang L, Zhang H J, Yang H P, et al. An interactive co-evolutionary framework for multi-objective critical node detection on large-scale complex networks[J]. IEEE Transactions on Network Science and Engineering,2023,10(3):1722-1735.

[53]Liu C J, Ge S K, Zhang Y K. Identifying the cardinality-constrained critical nodes with a hybrid evolutionary algorithm[J]. Information Sciences, 2023, 642.

[54]Zhang Y H, Lu Y L, Yang G Z, et al. Multi-attribute decision making method for node importance metric in complex network[J]. Applied Sciences, 2022, 12(4): 1944.

[55]Zhou Y M, Li J Q , Hao J K, et al. Detecting critical nodes in sparse graphs via "Reduce-Solve-Combine" memetic search[J]. INFORMS Journal on Computing, 2023, 36(1): 39-60.

[56]Sun S X, Ren T, Xu Y J. Edge-weights-based method to identify influential spreaders in complex networks[J]. Transactions of the Institute of Measurement and Control, 2024, 46(5): 815-823.

[57]Zhang Y H, Lu Y L, Yang G Z, et al. Research on the identification of internet critical nodes based on multilayer network modeling[J]. Security and Communication Networks, 2022, 2036370.

[58]Ugurlu O. Comparative analysis of centrality measures for identifying critical nodes in complex networks[J]. Journal of Computational Science, 2022, 62: 101738.

[59]Yin R R, Li L H, Wang Y M, et al. Identifying critical nodes in complex networks based on distance Laplacian energy[J]. Chaos, Solitons & Fractals, 2024, 180: 11448.

[60]Massimo B, Alessandro C, Marco C, et al. Seeking critical nodes in digraphs[J]. Journal of Computational Science, 2023, 69: 102012.

[61]Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.

[62]Collins S R, Kemmeren P, Zhao X C, et al. Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae[J]. Molecular & Cellular Proteomics: MCP, 2007, 6(3): 439-450.

[63]Spring N, Mahajan R, Wetherall D, et al. Measuring ISP topologies with rocketfuel[J]. IEEE/ACM Transactions on Networking: A Joint Publication of the IEEE Communications Society, the IEEE Computer Society, and the ACM with Its Special Interest Group on Data Communication, 2004, 12(1): 2-16.

[64]J. McAuley, J. Leskovec. Learning to discover social circles in ego networks[C] //Neural Information Processing Systems. Curran Associates Inc,2012, pp:539-547.

[65]J. Leskovec, J. Kleinberg, C. Faloutsos. Graph evolution: densification and shrinking diameters[C] // ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1), 2007.

[66]Singh R, Xu J, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J].Proceedings of the National Academy of Sciences of the United States of America,2008,105(35):12763-12768.

[67]A. Beveridge, J. Shan, Network of thrones[J]. Math Horizons23(4), 18-22 (2016)

[68]Dolan D E, Moré J J. Benchmarking optimization software with performance profiles[J]. Math. Program, 2001, 91(2): 201-213.

[69]Ventresca M. Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem[J]. Computers & Operations Research, 2012, 39(11): 2763-2775.

[70]Lu C, Zheng J, Yin L J, et al.An improved iterated greedy algorithm for the distributed hybrid flowshop scheduling problem[J]. Engineering Optimization, 2023.

[71]陈峰, 丁泉, 吴乐等. 混合驱动的粒子群算法[J/OL]. 计算机工程与应用,2023: 1-13.

[72]Su H, Zhao D, Heidari A A, et al. RIME: A physics-based optimization[J]. Neurocomputing, 2023, 532: 183-214.

[73]熊才权, 古小惠, 吴歆韵. 基于邻居层级分布引力模型的节点重要性评估方法[J]. 数学物理学报, 2023, 43(06): 1869-1879.

[74]Ma L, Ma C, Zhang H, et al. Identifying influential spreaders in complex networks based on gravity formula[J]. Physica A: Statistical Mechanics and its Applications, 2016, 451: 205-212.

[75]Leskovec J, Lang J K, Dasgupta A, et al. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters[J]. Internet Mathematics, 2009, 6(1): 29-123.

[76]阮逸润, 老松杨, 汤俊等. 基于引力方法的复杂网络节点重要度评估方法[J]. 物理学报, 2022, 71(17): 298-309.