利用节点传播熵识别超网络重要节点

doi:10.3778/j.issn.1002-8331.2212-0020

摘要/Abstract

摘要： 超网络中识别重要节点是一项基础且具有挑战性的重要课题，相关研究对进一步分析网络拓扑结构和功能特性具有广泛的应用价值。为了突破已有的重要节点识别方法评估的局限性，利用超图及信息熵理论，提出一种基于节点传播熵的超网络重要节点识别方法。该方法兼顾节点的局部和全局拓扑信息，利用节点聚集系数和邻居数目表征节点信息的局部传播影响，通过节点间最短路径和K壳中心性反映节点信息的全局传播影响，充分考虑节点自身及其邻域节点的影响，最终利用节点传播熵来表征节点在网络中的重要性。并通过单调性、鲁棒性以及SIR传播模型评价标准，在六个来自不同领域的真实网络上与其他方法进行比较，实验结果表明，该方法能够准确有效地识别网络中的重要节点。

关键词: 超图, 超网络, 重要节点, 节点传播熵

Abstract: It is a basic and challenging task to identify important nodes in hypernetworks, and the related research is of great value for further analysis of network topology and functional characteristics. In order to break through the limitations of the existing important node recognition methods, an important node recognition method based on node propagation entropy is proposed by using hypergraph and information entropy theory. This method takes into account both local and global topology information of nodes, uses the node clustering coefficient and the number of neighbors to represent the local propagation influence of node information, the global influence of the node information is reflected by the shortest path between nodes and K-shell centrality, and fully considers the influence of nodes and their neighbors, the importance of nodes in the network is represented by the size of node propagation entropy finally. Using monotonicity, robustness and SIR propagation model evaluation criteria, compared with other methods on six real networks from different fields, experimental results show that the proposed method can identify the important nodes in the hypernetwork accurately and effectively.

Key words: hypergraph, hypernetwork, important node, node propagation entropy

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

WU Yinghan, TIAN Kuo, LI Mingda, HU Feng. Important Node Recognition in Hypernetworks Based on Node Propagation Entropy[J]. Computer Engineering and Applications, 2023, 59(19): 66-74.

参考文献

[1] NEWMAN M E J.The structure and function of complex networks[J].SIAM Review，2003，45（2）：167-256.
[2] DOROGOVTSEV S N，MENDES J F F.Evolution of networks[J].Advances in Physics，2002，51（4）：1079-1187.
[3] STROGATZ S H.Exploring complex networks[J].Nature，2001，410：268-276.
[4] NEUBAUER N，OBERMAYER K.Hyperincident connected components of tagging networks[C]//Proceedings of the 20th ACM Conference on Hypertext and Hypermedia.New York：ACM Press，2009：229-238.
[5] ESTRADA E，RODRíGUEZ-VELáZQUEZ J A.Subgraph centrality and clustering in complex hypernetworks[J].Physica A，2006，364：581-594.
[6] 王志平，王众托.超网络理论及其应用[M].北京：科学出版社，2008：206-222.
WANG Z P，WANG Z T.Hypernetwork theory and its application[M].Beijing：Science Press，2008：206-222.
[7] 郭进利，祝昕昀.超网络中标度律的涌现[J].物理学报，2014，63（9）：47-53.
GUO J L，ZHU X Y.Emergence of scaling in hypernetworks[J].Acta Physica Sinica，2014，63（9）：47-53.
[8] 郭进利.非均齐超网络中标度律的涌现——富者愈富导致幂律分布吗?[J].物理学报，2014，63（20）：402-407.
GUO J L.Emergence of scaling in non-uniform hypernetworks—does “the rich get richer” lead to a power-law distribution?[J].Acta Physica Sinica，2014，63（20）：402-407.
[9] 任晓龙，吕琳媛.网络重要节点排序方法综述[J].科学通报，2014，59（13）：1175-1197.
REN X L，LYU L Y.Review of ranking nodes in complex networks[J].Chinese Science Bulletin，2014，59（13）：1175-1197.
[10] 周丽娜，李发旭，巩云超，等.基于K-shell的超网络关键节点识别方法[J].复杂系统与复杂性科学，2021，18（3）：15-22.
ZHOU L N，LI F X，GONG Y C，et al.Identification methods of vital nodes based on K-shell in hypernetworks[J].Complex Systems and Complexity Science，2021，18（3）：15-22.
[11] SON F，HEATH E，JEFFERSON B，et al.Hypergraph models of biological networks to identify genes critical to pathogenic viral response[J].BMC Bioinformatics，2021，22（1）：287.
[12] KOVALENKO K，ROMANCE M，VASILYEVA E，et al.Vector centrality in networks with higher-order interactions[J].arXiv：2108.13846，2021.
[13] AKTAS M E，NGUYEN T，JAWAID S，et al.Identifying critical higher-order interactions in complex networks[J].arXiv：2105.02763，2021.
[14] XIE M，ZHAN X X，LIU C，et al.An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphs[J].Information Processing & Management，2022，60（2）：103161.
[15] LAI Q，ZHANG H H.Analysis of identification methods of key nodes in transportation network[J].Chinese Physics B，2022，31（6）：68905.
[16] SHANNON C E，WEAVER W.The mathematical theory of communication[M].Urbana，IL：University of IIIinois Press，1949.
[17] MOWSHOWITZ A.Entropy and the complexity of graphs：I.an index of the relative complexity of a graph[J].Bulllletin of Mathematical Biology，1968，30（1）：175-204.
[18] CHEN D B，LV L Y，SHANG M S，et al.Identifying influential nodes in complex networks[J].Physica A，2012，391（4）：1777-1787.
[19] 张齐.基于熵的复杂网络结构特性研究[D].重庆：西南大学，2017.
ZHANG Q.Structure analysis of complex networks based on entropy[D].Chongqing：Southwest University，2017.
[20] 黄亚丽，霍宥良，王青，等.基于K-阶结构熵的网络异构性研究[J].物理学报，2019，68（1）：325-336.
HUANG L Y，HUO Y L，WANG Q，et al.Network heterogeneity based on K-order structure entropy[J].Acta Physica Sinica，2019，68（1）：325-336.
[21] WANG M，LI W C，GUO Y N，et al.Identifying influential spreaders in complex networks based on K-shell method[J].Physica A：Statistical Mechanics and Its Applications，2018，499：310-324.
[22] ZHAO J，LEI X.Predicting essential proteins based on second-order neighborhood information and information entropy[J].IEEE Access，2019，7：136012-136022.
[23] 赖强，张宏昊，王徐盱.基于复杂网络理论的城市公交网络鲁棒性分析与优化[J].计算机工程与应用，2022，58（10）：249-254.
LAI Q，ZHANG H H，WANG X X.Robustness analysis and optimization of urban public transport network based on complex network theory[J].Computer Engineering and Applications，2022，58（10）：249-254.
[24] 田文，方琴，周雪芳，等.航路网络关键节点识别方法研究[J].西南交通大学学报，2022（1）：1-10.
TIAN W，FANG Q，ZHOU X F，et al.Research on identification method of key nodes in en-route network[J].Journal of Southwest Jiaotong University，2022（1）：1-10.
[25] 王福红，郭进利.超网络的上下熵研究[J].数学的实践与认识，2020，50（22）：122-133.
WANG F H，GUO J L.Study on upper and lower entropy of hypernetwork[J].Mathematics in Practice and Theory，2020，50（22）：122-133.
[26] 周丽娜，常笑，胡枫.利用邻接结构熵确定超网络关键节点[J].计算机工程与应用，2022，58（8）：76-82.
ZHOU L N，CHANG X，HU F.Using adjacent structure entropy to determine vital nodes of hypernetwork[J].Computer Engineering and Applications，2022，58（8）：76-82.
[27] BERGE C.Graphs and hypergraphs[M].New York：Elsevier，1973.
[28] 胡枫，刘猛，赵静，等.蛋白复合物超网络特性分析及应用[J].复杂系统与复杂性科学，2018，15（4）：31-38.
HU F，LIU M，ZHAO J，et al.Analysis and application of the topological properties of protein complex hypernetworks[J].Complex Systems and Complexity Science，2018，15（4）：31-38.
[29] CHEN W H，MINGUEZ P，LERECHER M J，et al.OGEE：an online gene essentially database[J].Nucleic Acids Research，2012，40：901-906.