Study on the reliability of hypergraphs based on non-backtracking matrix centrality

Hao PENG; Cheng QIAN; Dandan ZHAO; Ming ZHONG; Jianmin HAN; Ziyi XIE; Wei WANG

doi:10.11959/j.issn.2096-109x.2024011

您当前的位置：

首页 >

文章列表页 >

Study on the reliability of hypergraphs based on non-backtracking matrix centrality

Papers | 更新时间：2024-06-03

- Study on the reliability of hypergraphs based on non-backtracking matrix centrality
- Chinese Journal of Network and Information Security Vol. 10, Issue 1, Pages: 22-32(2024)
- 作者机构：
  
  1. 浙江师范大学计算机与科学技术学院，浙江金华 321004
  2. 浙江师范大学浙江省智能教育技术与应用重点实验室，浙江金华 321004
  3. 重庆医科大学公共卫生学院，重庆 400016
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2024011
  CLC： TP301.6
- Online First：2024-02，
  
  Published：25 February 2024
- 稿件说明：
移动端阅览
Hao PENG, Cheng QIAN, Dandan ZHAO, et al. Study on the reliability of hypergraphs based on non-backtracking matrix centrality[J]. Chinese Journal of Network and Information Security, 2024, 10(1): 22-32.
DOI：

Hao PENG, Cheng QIAN, Dandan ZHAO, et al. Study on the reliability of hypergraphs based on non-backtracking matrix centrality[J]. Chinese Journal of Network and Information Security, 2024, 10(1): 22-32. DOI： 10.11959/j.issn.2096-109x.2024011.

摘要

近年来，超图作为网络科学的一个研究热点，引起了广泛的关注。超图区别于传统图的结构特点在于它的超边可以同时连接多个节点，从而形成更为复杂和高阶的关系。在这样的网络结构中，有效地识别重要的节点和超边成为一个关键的挑战。特征向量中心性是一个常见的度量标准，但当网络中存在着极大度值的枢纽节点时，使用特征向量中心性度量方法会使结果表现出局域性，限制了该方法的应用场景。因此，将超图转化成对应的线图，在此基础上使用非回溯矩阵中心性这一方法，该方法在评估超边重要性时表现出更好的均匀性和区分度。此外，还探讨了特征向量中心性和非回溯矩阵中心性在超图中节点重要性评估上的应用。通过比较这两种方法，研究发现非回溯矩阵中心性在区分节点重要程度方面具有更明显的优势。研究不仅包括理论分析和模型构建，还包括对真实世界数据的实证。为了验证所提方法和结论，选取了6个真实世界超图作为实验对象。通过在这些超图上的应用，证明了非回溯矩阵中心性在识别重要节点和超边方面的有效性。研究为超图中关键元素的识别提供了一种新的视角和方法，对于理解和分析实际复杂网络系统，具有重要的理论和实践意义。

Abstract

In recent years

there has been widespread attention on hypergraphs as a research hotspot in network science.The unique structure of hypergraphs

which differs from traditional graphs

is characterized by hyperedges that can connect multiple nodes simultaneously

resulting in more complex and higher-order relationships.Effectively identifying important nodes and hyperedges in such network structures poses a key challenge.Eigenvector centrality

a common metric

has limitations in its application due to its locality when dealing with hub nodes with extremely high degree values in the network.To address this issue

the hypergraphs were transformed into their corresponding line graphs

and non-backtracking matrix centrality was employed as a method to measure the importance of hyperedges.This approach demonstrated better uniformity and differentiation in assessing the importance of hyperedges.Furthermore

the application of both eigenvector centrality and non-backtracking matrix centrality in assessing the importance of nodes in hypergraphs was explored.Comparative analysis revealed that non-backtracking matrix centrality effectively distinguished the importance of nodes.This research encompassed theoretical analysis

model construction

and empirical studies on real-world data.To validate the proposed method and conclusion

six real-world hypergraphs were selected as experimental subjects.The application of these methods to these hypergraphs confirmed the effectiveness of non-backtracking matrix centrality in identifying important nodes and hyperedges.The findings of this research offer a fresh perspective and approach for identifying key elements in hypergraphs

holding significant theoretical and practical implications for understanding and analyzing complex network systems.

关键词

Keywords

references

COHEN R , HAVLIN S . Complex networks:structure,robustness and function [M ] . Cambridge : Cambridge University Press , 2010 .

TU H , XIA Y , IU H H C , et al . Optimal robustness in power grids from a network science perspective [J ] . IEEE Transactions on Circuits and Systems II:Express Briefs , 2018 , 66 ( 1 ): 126 - 130 .

LI D , LIU J . Modeling influence diffusion over signed social networks [J ] . IEEE Transactions on Knowledge and Data Engineering , 2019 , 33 ( 2 ): 613 - 625 .

DING R , UJANG N , HAMID H B , et al . Application of complex networks theory in urban traffic network researches [J ] . Networks and Spatial Economics , 2019 , 19 : 1281 - 1317 .

ALBERT R , BARABÁSI A L . Statistical mechanics of complex networks [J ] . Reviews of Modern Physics , 2002 , 74 ( 1 ): 47 .

BOCCALETTI S , LATORA V , MORENO Y , et al . Complex networks:structure and dynamics [J ] . Physics Reports , 2006 , 424 ( 4-5 ): 175 - 308 .

JACKSON M O . Social and economic networks [M ] . Princeton : Princeton University Press , 2008 .

朱会虎 , 邱菡 , 朱俊虎 , 等 . 基于传播动力学的域间路由系统关键节点识别方法 [J ] . 网络与信息安全学报 , 2019 , 5 ( 5 ): 9 - 20 .

ZHU H H , QIU H , ZHU J H , et al . Spreading dynamics based key nodes identification in inter-domain routing system [J ] . Chinese Journal of Network and Information Security , 2019 , 5 ( 5 ): 9 - 20 .

BRÓDKA P , SKIBICKI K , KAZIENKO P , et al . A degree centrality in multi-layered social network [C ] // Proceedings of 2011 International Conference on Computational Aspects of Social Networks (CASoN) . 2011 : 237 - 242 .

WEI D , LI Y , ZHANG Y , et al . Degree centrality based on the weighted network [C ] // Proceedings of 2012 24th Chinese Control and Decision Conference (CCDC) . 2012 : 3976 - 3979 .

BARTHELEMY M . Betweenness centrality in large complex networks [J ] . The European Physical Journal B , 2004 , 38 ( 2 ): 163 - 168 .

NEWMAN M E J . A measure of betweenness centrality based on random walks [J ] . Social networks , 2005 , 27 ( 1 ): 39 - 54 .

RUHNAU B . Eigenvector-centrality—a node-centrality [J ] . Social Networks , 2000 , 22 ( 4 ): 357 - 365 .

BONACICH P . Some unique properties of eigenvector centrality [J ] . Social Networks , 2007 , 29 ( 4 ): 555 - 564 .

SCHNEIDER C M , YAZDANI N , ARAÚJO N A M , , et al . Towards designing robust coupled networks [J ] . Scientific Reports , 2013 , 3 ( 1 ): 1969 .

MARTIN T , ZHANG X , NEWMAN M E J . Localization and centrality in networks [J ] . Physical Review E , 2014 , 90 ( 5 ): 052808 .

BRETTO A . Hypergraph theory [M ] . Berlin : Springer , 2013 .

BATTISTON F , CENCETTI G , IACOPINI I , et al . Networks beyond pairwise interactions:structure and dynamics [J ] . Physics Reports , 2020 , 74 : 81 - 92 .

YADATI N , NIMISHAKAVI M , YADAV P , et al . Hypergcn:a new method for training graph convolutional networks on hypergraphs [J ] . Advances in Neural Information Processing Systems , 2019 ,( 32 ).

KOVALENKO K , ROMANCE M , VASILYEVA E , et al . Vector centrality in hypergraphs [J ] . Chaos,Solitons ＆ Fractals , 2022 ,162:112397.

PENG H , QIAN C , ZHAO D , et al . Targeting attack hypergraph networks [J ] . Chaos:An Interdisciplinary Journal of Nonlinear Science , 2022 , 32 ( 7 ).

PENG H , QIAN C , ZHAO D , et al . Disintegrate hypergraph networks by attacking hyperedge [J ] . Journal of King Saud University-Computer and Information Sciences , 2022 , 34 ( 7 ): 4679 - 4685 .

TUDISCO F , HIGHAM D J . Node and edge nonlinear eigenvector centrality for hypergraphs [J ] . Communications Physics , 2021 , 4 ( 1 ): 201 .

MISHRA A , JALAN S . alan S.Eigenvector localization in hypergraphs:pairwise versus higher-order links [J ] . Physical Review E , 2023 , 107 ( 3 ): 34311 .

周丽娜 , 常笑 , 胡枫 . 利用邻接结构熵确定超网络关键节点 [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 .

BERMOND J C , HEYDEMANN M C , SOTTEAU D . Line graphs of hypergraphs I [J ] . Discrete Mathematics , 1977 , 18 ( 3 ): 235 - 241 .

LANG S . Introduction to linear algebra [M ] . Springer Science ＆Business Media , 2012 .

KRZAKALA F , MOORE C , MOSSEL E , et al . Spectral redemption in clustering sparse networks [J ] . Proceedings of the National Academy of Sciences , 2013 , 110 ( 52 ): 20935 - 20940 .

ZHANG M , CUI Z , JIANG S , et al . Beyond link prediction:predicting hyperlinks in adjacency space [C ] // Proceedings of the AAAI Conference on Artificial Intelligence . 2018 .

Views

203

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Hypernetwork link prediction method based on the SCL-CMM model

Related Author

REN Yuyuan

MA Hong

LIU Shuxin

WANG Kai

Related Institution

Information Engineering University

⁰