利用邻接结构熵确定超网络关键节点

doi:10.3778/j.issn.1002-8331.2104-0043

摘要/Abstract

摘要： 识别网络中的关键节点对研究网络的拓扑结构及功能特性具有重要的实际应用价值。基于超图的超网络拓扑结构为超图，由于超图中的超边可以包含任意数量的节点，使得超网络能够清晰明了地表达出多元、多维、多准则的复杂关系。为了更好地挖掘超网络中的关键节点，基于超图理论及性质，提出超图中的邻接结构熵识别超网络中的关键节点，该方法通过研究节点及其直接与间接节点间的关系，利用节点信息熵刻画不同节点在超网络中的重要性。其优势在于不仅考虑了超网络中节点自身的性质，也融合了邻居节点的影响力，且由于该算法只利用节点的局部属性，故其复杂度较低。并通过对科研合作超网络进行的实证分析，结果表明邻接结构熵能够准确有效地识别超网络中的关键节点，为今后研究超网络中的关键节点以及研究超网络的拓扑结构提供一定的借鉴和参考。

关键词: 超图, 超网络, 关键节点, 网络结构熵, 邻接结构熵

Abstract: It is of great practical value to identify the vital nodes in the network for studying the topology and functional characteristics of the network. The topology of hypernetwork based on hypergraph is hypergraph. Because the hyperedges in hypergraph can contain any number of nodes, the hypernetwork can clearly express the complex relationship of multi-dimension, multi-criteria. In order to better mine the vital nodes in the hypernetwork, based on the theory and properties of hypergraph, this paper proposes the adjacency structure entropy of hypergraph to identify the vital nodes in the hypernetwork. By studying the relationship between the nodes and their direct and indirect nodes, this method uses the node information entropy to describe the importance of different nodes in the hypernetwork. The advantage of this algorithm is that it not only considers the properties of the nodes in the hypernetwork, but also integrates the influence of neighbor nodes. Moreover, because this algorithm only uses the local attributes of nodes, its complexity is low. And through the empirical analysis of the research cooperation hypernetwork, the results show that the adjacency structure entropy can accurately and effectively identify the vital nodes in the hypernetwork, which provides a certain reference for the future research on the vital nodes in the hypernetwork and the topological structure of the hypernetwork.

Key words: hypergraph, hypernetwork, vital node, network structure entropy, adjacency structure entropy

周丽娜, 常笑, 胡枫. 利用邻接结构熵确定超网络关键节点[J]. 计算机工程与应用, 2022, 58(8): 76-82.

ZHOU Lina, CHANG Xiao, HU Feng. Using Adjacent Structure Entropy to Determine Vital Nodes of Hypernetwork[J]. Computer Engineering and Applications, 2022, 58(8): 76-82.

参考文献

[1] NEWMAN M E J.The structure and function of complex networks[J].SIAM Review，2003，45（2）：167-256.
[2] KEELING M J，ROHANI P，POURBOHLOUL B.Modeling infectious diseases in humans and animals[J].Clinical Infectious Diseases，2008，47（6）：864-865.
[3] LESKOVEC J，ADAMIC L A，HUBERMAN B A.The dynamics of viral marketing[J].Transactions on the Web，2005，1（1）：1-40.
[4] CSERMELY P，KORCSMROS T，KISS H J，et al.Structure and dynamics of molecular networks：a novel paradigm of drug discovery：a comprehensive review[J].Pharmacol Ther，2013，138：333-408.
[5] DOROGOVTSEV S N，MENDES J F F.Evolution of networks[J].Advances in Physics，2002，51（4）：1079-1187.
[6] STROGATZ S H.Exploring complex networks[J].Nature，2001，410：268-276.
[7] 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.
[8] ESTRADA E，RODRíGUEZ-VELáZQUEZ J A.Subgraph centrality and clustering in complex hyper-networks[J].Physica A，2006，364：581-594.
[9] 王志平，王众托.超网络理论及其应用[M].北京：科学出版社，2008：206-222.
WANG Zhiping，WANG Zhongtuo.Hypernetwork theory and its application[M].Beijing：Science Press，2008：206-222.
[10] WANG J W，RONG L L，DENG Q H，et al.Evolving hypernetwork model[J].The European Physocial Journal B，2010，77（4）：493-498.
[11] 胡枫，赵海兴，马秀娟.一种超网络演化模型构建及特性分析[J].中国科学：物理学力学天文学，2013，43（1）：16-22.
HU Feng，ZHAO Haixing，MA Xiujuan.An evolving hypernetwork model and its properties[J].SCIENCE CHINA Physics，Mechanics & Astronomy，2013，43（1）：16-22.
[12] SUO Q，GUO J L，SHEN A Z.Information spreading dynamics in hypernetworks[J].Physica A，2018，495：475-487.
[13] SUO Q，GUO J L，SUN S W，et al.Exploring the evolutionary mechanism of complex supply chain systems using evolving hypergraphs[J].Physica A，2018，489：141-148.
[14] 郭进利.非均齐超网络中标度率的涌现—富者愈富导致幂律分布吗?[J].物理学报，2014，63（20）：402-407.
GUO Jinli.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.
[15] 卢文，赵海兴，孟磊，等.具有双峰特性的双层超网络模型[J].物理学报，2021，70（1）：384-392.
LU Wen，ZHAO Haixing，MENG Lei，et al.Double-layer hypernetwork model with bimodal peak characteristics[J].Acta?Physica Sinica，2021，70（1）：384-392.
[16] 刘胜久，李天瑞，刘佳，等.超网络能量研究与应用[J].计算机科学与探索，2021，15（4）：682-689.
LIU Shengjiu，LI Tianrui，LIU Jia，et al.Research and application of hypernetwork energy[J].Journal of Frontiers of Computer Science & Technology，2020，15（4）：682-689.
[17] 马涛，郭进利.基于加权超图的产学研合作申请专利超网络模型——以上海电子信息产业为例[J].技术经济，2019，38（6）：109-118.
MA Tao，GUO Jinli.Industry-university-research cooperative hypernetwork model for applying patent based on weighted hypergraph：case of electronic information industry from Shanghai[J].Technology Economics，2019，38（6）：109-118.
[18] 陆睿敏，郭进利.上海市公交超网络拓扑特征与鲁棒性分析[J].数学的实践与认识，2018，48（20）：129-137.
LU Ruimin，GUO Jinli.Topological characteristics and robustness analysis of Shanghai bus hypernetwork mathematics in practice and theory[J].Mathematics in Practice and Theory，2018，48（20）：129-137.
[19] 胡枫，刘猛，赵静，等.蛋白复合物超网络特性分析及应用[J].复杂系统与复杂性科学，2018，15（4）：31-38.
HU Feng，LIU Meng，ZHAO Jing，et al.Analysis and application of the topological properties of protein complex hypernetworks[J].Complex Systems and Complexity Science，2018，15（4）：31-38.
[20] 王雨，郭进利.超网络视角下的科研合作网络节点重要性评估[J].图书馆杂志，2018，37（10）：91-102.
WANG Yu，GUO Jinli.The evaluation of node importance within the scientific collaboration network from hypernetwork perspective[J].Library Journal，2018，37（10）：91-102.
[21] 单而芳，蔡蕾，曾晗，等.超网络中心性度量的υ-Position值方法[J].运筹与管理，2020，29（5）：135-142.
SHAN Erfang，CAI Lei，ZENG Han，et al.The υ-position value measure on centrality of hypernetworks[J].Operations Research and Management Science，2020，29（5）：135-142.
[22] 孙琳，郭进利.基于超网络视角对上海轨道交通网络的研究[J].物流科技，2015，38（4）：15-19.
SUN Lin，GUO Jinli.Study of Shanghai rail transit network based on the hypernetwork[J].Logistics Management，2015，38（4）：15-19.
[23] SHANNON C E，WEAVER W W.The mathematical theory of communication[J].Physics Today，1950，3（9）：31-32.
[24] FEI L，DENG Y.A new method to identify influential nodes based on relative entropy[J].Chaos，Solitons and Fractals，2017，104：257-267.
[25] 黄丽亚，霍宥良，王青，等.基于K-阶结构熵的网络异构性研究[J].物理学报，2019，68（1）：347-359.
HUANG Liya，HUO Youliang，WANG Qing，et al.Network heterogeneity based on K-order structure entropy[J].Acta Physica Sinica，2019，68（1）：347-359.
[26] 胡钢，徐翔，高浩，等.基于邻接信息熵的网络节点重要性识别算法[J].系统工程理论与实践，2020（3）：714-725.
HU Gang，XU Xiang，GAO Hao，et al.Node importance recognition algorithm based on adjacency information entropy in networks[J].Systems Engineering-Theory & Practice，2020（3）：714-725.
[27] 李懂，席景科，孙成成.融合度与K核迭代次数的节点重要性排序算法[J].计算机工程与设计，2019，40（6）：1518-1522.
LI Dong，XI Jingke，SUN Chengcheng.Node importance ranking algorithm with fusing degree and K-shell iteration number[J].Computer Engineering and Design，2019，40（6）：1518-1522.
[28] 王倩，胡松旺，郭嘉伟，等.有向复杂网络结构熵的软件动态执行关键节点挖掘算法[J].小型微型计算机系统，2019，40（4）：884-889.
WANG Qian，HU Songwang，GUO Jiawei，et al.Structure entropy of directed complex network based key node mining algorithm in software dynamic execution[J].Mini-micro Systems，2019，40（4）：884-889.
[29] BERGE C.Graphs and hypergraphs[M].New York：Elsevier，1973.
[30] 谭跃进，吴俊.网络结构熵及其在非标度网络中的应用[J].系统工程理论与实践，2004（6）：24-26.
TAN Yuejin，WU Jun.Network structure entropy and its application to scale-free networks[J].Systems Engineering—Theory & Practice，2004（6）：24-26.