基于重要性度量矩阵的超网络关键节点识别算法

doi:10.12005/orms.2025.0085

摘要/Abstract

摘要： 识别超网络中的关键节点,对优化网络结构和信息的有效传播起着至关重要的作用。在超网络中,关键节点的重要程度并非单纯由节点自身所具备的影响力与运行效率决定,还依赖于其相邻节点所作出的贡献程度。因此,要全面且精准地剖析关键节点的重要性,不仅需考量节点自身的重要属性,还需探究其相邻节点对该节点重要性所产生的影响。通过定义超网络中节点的超度、效率,以及构建节点重要性度量矩阵,本文提出了一种新的超网络关键节点识别方法。该方法并非仅着眼于节点自身所固有的性质,还充分融合了相邻节点在重要度方面所做出的贡献。该方法通过运用节点的超度值以及效率这两个量化指标,精准地表征了节点对相邻节点重要度的贡献情况。与此同时,此方法巧妙地将节点的局部重要性与全局重要性有机结合,能够切实提高对节点重要性进行度量时的精度,高度契合节点重要性度量在实际应用场景中的需求。此外,该方法还应用于蛋白复合物超网络中加以验证,实验结果表明,本文所提方法能够高效且精准地识别出复杂超网络中的关键节点。这一成果为后续针对超网络中关键节点的深入探究,以及超网络拓扑结构的系统性研究,提供了一定的借鉴与参考。

关键词: 超网络, 关键节点, 超度, 节点效率, 重要性度量矩阵

Abstract: Critical nodes are a small number of nodes that exist in a complex network, and have a significant impact on the property, function and behavior of the complex network. The identification of critical nodes in a complex network is crucial for optimizing network structure and enabling efficient information propagation. With the development of network in the real society, the number of edges between nodes increases dramatically. Due to the diversity of edge types and the complexity of their structures, complex networks are no longer able to describe real-world network features comprehensively and effectively. A hyperedge in a hypergraph can contain multiple nodes, which makes the hypernetwork better able to describe complex multi-dimensional and multi-criteria systems. Identifying critical nodes in hypernetworks based on hypergraph structures has become an important direction in the research of hypernetworks, and has high application value in real world for information dissemination, infectious disease spread, product promotion and so on. Traditional methods only consider the influence of nodes on their neighbors, but there is little discussion on the role of nodes in the entire network information transmission and the contribution relationship between adjacent nodes of nodes.
A hypernetwork is composed of nodes and hyperedges, and the importance of nodes depends not only on their influence on the local network, but also on their position and the importance of their neighboring nodes. Therefore, considering comprehensively the importance of a node in itself and its neighboring nodes, we propose a method for identifying critical nodes in a hypernetwork based on the importance matrix, by defining the hyperdegree, efficiency, and node importance matrix of nodes in the hypernetwork. The importance contribution matrix reflects the proportion of importance contribution values of nodes in a hypernetwork to their neighboring nodes. The importance contribution value of a node to its neighboring nodes is related to its node efficiency and hyperdegree. The larger these two indicators, the higher its importance contribution value to neighboring nodes. Both the hyperdegree and the importance contribution values of a node are instrumental in reflecting the local significance of nodes within the hypernetwork. Conversely, node efficiency embodies the global significance of nodes. This approach focuses on node efficiency and the contributions made by neighboring nodes. It not only effectively reveals the differences in the importance levels among nodes, but also significantly improves the accuracy of identifying “bridge” nodes within hypernetworks.
The advantage of this method is that it not only considers the properties of the nodes themselves, but also fuses the importance contributions of neighboring nodes, and uses the hyperdegree and efficiency of the nodes to characterize their importance contributions to neighboring nodes, and this method combines the local importance and global importance of the nodes, so it can improve the accuracy of the node importance measure, consistent with the practical need of the node importance measure. Furthermore, this method has been applied to protein complex hypernetworks for verification. The experimental results show that this approach can effectively identify critical nodes in hypernetworks. Additionally, it provides a significant level of reference value for future research on critical nodes in hypernetworks.

Key words: hypernetwork, critical nodes, hyperdegree, node efficiency, importance measurement matrix

中图分类号:

TP301.5

李发旭, 卫良, 徐慧, 胡枫, 巩云超. 基于重要性度量矩阵的超网络关键节点识别算法[J]. 运筹与管理, 2025, 34(3): 119-125.

LI Faxu, WEI Liang, XU Hui, HU Feng, GONG Yunchao. Critical Node Identification in Complex Hypernetwork Based on Importance Measurement Matrix[J]. Operations Research and Management Science, 2025, 34(3): 119-125.

参考文献

[1] 彭华涛,邱子恒. 超网络视角的精准创业扶贫资源拼凑机理研究[J].复杂系统与复杂性科学,2020,17(4): 48-57.
[2] 王雨,郭进利.超网络视角下的科研合作网络节点重要性评估[J].图书馆杂志,2018,37(10): 89-100.
[3] YAO C Y, HE G M. Key nodes analysis of microblogging public opinion spread about public emergencies[C]//GHOLAMI M, RAM J, TAVASOLI A. Proceedings of the 2015 International Conference on Modeling, Simulation and Applied Mathematics. Thailand: Atlantis Press, 2015: 264-268.
[4] 周漩,张凤鸣,李克武,等.利用重要度评价矩阵确定复杂网络关键节点[J].物理学报,2012,61(5): 1-7.
[5] YOSHIMARU T, NAKAMURA Y, KATAGIRI T. Functional genomics for breast cancer drug target discovery[J]. Journal of Human Genetics, 2021, 66(9): 927-935.
[6] 胡枫,刘猛,赵静,等.蛋白复合物超网络特性分析及应用[J].复杂系统与复杂性科学,2018,15(4): 31-38.
[7] 胡枫,赵海兴,何佳倍,等.基于超图结构的科研合作网络演化模型[J].物理学报,2013,62(19): 547-554.
[8] ZHAO L M, ZHANG H H, WU W Q. Knowledge service decision making in business incubators based on the supernetwork model[J]. Physica A: Statistical Mechanics and its Applications, 2017, 479: 249-264.
[9] ZHANG Z K, LIU C. A hypergraph model of social tagging networks[J]. Journal of Statistical Mechanics, 2010(10): 10005.
[10] 卢文,赵海兴,孟磊,等.具有双峰特性的双层超网络模型[J].物理学报,2021,70(1): 384-392.
[11] 万晨洁,何建佳,蒋雪琳.社区便利O2O的供应链超网络均衡模型研究[J].计算机工程与应用,2017,53(5): 241-248.
[12] 索琪,郭进利.超网络中的舆情传播模型及仿真研究[J].计算机应用研究,2017,34(9): 2629-2632.
[13] JIN H Y, ZHANG C X, MA M Z, et al. Inferring essential proteins from centrality in interconnected multilayer networks[J]. Physica A: Statistical Mechanics and its Applications, 2020, 557: 124853.
[14] XIAO Q. Scientific research collaboration hypernetwork modeling and node importance measuring[C]//2014 International Conference on Management of e-Commerce and e-Government, October 31-November 2, 2014, Shanghai, China. IEEE, 2014: 108-113.
[15] CHENG Z S, CAO J D. Cascade of failures in interdependent networks coupled by different type networks[J]. Physica A: Statistical Mechanics and its Applications, 2015, 430: 193-200.
[16] WANG J P, GUO Q, YANG G Y, et al. Improved knowledge diffusion model based on the collaboration hypernetwork[J]. Physica A: Statistical Mechanics and its Applications, 2015, 428: 250-256.
[17] DONG G G, TIAN L X, DU R J, et al. Analysis of percolation behaviors of clustered networks with partial support-dependence relations[J]. Physica A: Statistical Mechanics and its Applications, 2014, 394: 370-378.
[18] SUO Q, GUO J L, SHEN A Z. Information spreading dynamics in hypernetworks[J]. Physica A: Statistical Mechanics and its Applications, 2018, 495: 475487.
[19] WEI S T, ZHANG Z, CHEN X T. How does business incubator motivate start-ups based on super-network: A dynamic capability perspective[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40(6): 11131-11144.
[20] ESTRADA E, RODRIGUEZ-VELAZQUEZ J A. Subgraph centrality and clustering in complex hyper-networks[J]. Physica A: Statistical Mechanics and its Applications, 2006, 364: 581-594.
[21] 单而芳,蔡蕾,曾晗,等.超网络中心性度量的υ-Position值方法[J].运筹与管理,2020,29(5): 135-142.
[22] 周丽娜,李发旭,巩云超,等.基于K-shell的超网络关键节点识别方法[J].复杂系统与复杂性科学,2021,18(3): 15-22.
[23] WU P, ZHAO D. Research on the identification of key nodes in the process of WeChat epidemic information dissemination: A Supernetwork Perspective[J]. Mathematical Problems in Engineering, 2020(1): 6751686.
[24] 张连峰,周红磊,王丹,等.基于超网络理论的微博舆情关键节点挖掘[J].情报学报,2019,38(12): 1286-1296.
[25] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6: 888893.
[26] 周丽娜,常笑,胡枫.利用邻接结构熵确定超网络关键节点[J].计算机工程与应用,2022,58(8): 7682.
[27] JEONG H, MASON S P, BARABÁSI A L, et al. Lethality and centrality in protein networks[J]. Nature: International Weekly Journal of Science, 2001, 411: 4142.