中国物理B ›› 2025, Vol. 34 ›› Issue (4): 48902-048902.doi: 10.1088/1674-1056/adb269

所属专题： Featured Column — COMPUTATIONAL PROGRAMS FOR PHYSICS

• • 上一篇    下一篇

Identifying important nodes of hypergraph: An improved PageRank algorithm

Yu-Hao Piao(朴宇豪)1, Jun-Yi Wang(王俊义)2, and Ke-Zan Li(李科赞)1,3,†   

  1. 1 School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China;
    2 School of Information and Communication, Guilin University of Electronic Technology, Guilin 541004, China;
    3 Guangxi Wireless Broadband Communication and Signal Processing Key Laboratory, Guilin University of Electronic Technology, Guilin 541004, China
  • 收稿日期:2024-12-06 修回日期:2025-01-12 接受日期:2025-02-05 出版日期:2025-04-15 发布日期:2025-04-15
  • 通讯作者: Ke-Zan Li E-mail:lkzzr@guet.edu.cn
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant No. 62166010) and the Guangxi Natural Science Foundation (Grant No. 2023GXNSFAA026087).

Identifying important nodes of hypergraph: An improved PageRank algorithm

Yu-Hao Piao(朴宇豪)1, Jun-Yi Wang(王俊义)2, and Ke-Zan Li(李科赞)1,3,†   

  1. 1 School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China;
    2 School of Information and Communication, Guilin University of Electronic Technology, Guilin 541004, China;
    3 Guangxi Wireless Broadband Communication and Signal Processing Key Laboratory, Guilin University of Electronic Technology, Guilin 541004, China
  • Received:2024-12-06 Revised:2025-01-12 Accepted:2025-02-05 Online:2025-04-15 Published:2025-04-15
  • Contact: Ke-Zan Li E-mail:lkzzr@guet.edu.cn
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant No. 62166010) and the Guangxi Natural Science Foundation (Grant No. 2023GXNSFAA026087).

RichHTML

2

PDF (PC)

440

赞

摘要： Hypergraphs can accurately capture complex higher-order relationships, but it is challenging to identify their important nodes. In this paper, an improved PageRank (ImPageRank) algorithm is designed to identify important nodes in a directed hypergraph. The algorithm introduces the Jaccard similarity of directed hypergraphs. By comparing the numbers of common neighbors between nodes with the total number of their neighbors, the Jaccard similarity measure takes into account the similarity between nodes that are not directly connected, and can reflect the potential correlation between nodes. An improved susceptible-infected (SI) model in directed hypergraph is proposed, which considers nonlinear propagation mode and more realistic propagation mechanism. In addition, some important node evaluation methods are transferred from undirected hypergraphs and applied to directed hypergraphs. Finally, the ImPageRank algorithm is used to evaluate the performance of the SI model, network robustness and monotonicity. Simulations of real networks demonstrate the excellent performance of the proposed algorithm and provide a powerful framework for identifying important nodes in directed hypergraphs.

关键词: hypergraph, important node, PageRank, susceptible-infected (SI) model, centrality index

Abstract: Hypergraphs can accurately capture complex higher-order relationships, but it is challenging to identify their important nodes. In this paper, an improved PageRank (ImPageRank) algorithm is designed to identify important nodes in a directed hypergraph. The algorithm introduces the Jaccard similarity of directed hypergraphs. By comparing the numbers of common neighbors between nodes with the total number of their neighbors, the Jaccard similarity measure takes into account the similarity between nodes that are not directly connected, and can reflect the potential correlation between nodes. An improved susceptible-infected (SI) model in directed hypergraph is proposed, which considers nonlinear propagation mode and more realistic propagation mechanism. In addition, some important node evaluation methods are transferred from undirected hypergraphs and applied to directed hypergraphs. Finally, the ImPageRank algorithm is used to evaluate the performance of the SI model, network robustness and monotonicity. Simulations of real networks demonstrate the excellent performance of the proposed algorithm and provide a powerful framework for identifying important nodes in directed hypergraphs.

Key words: hypergraph, important node, PageRank, susceptible-infected (SI) model, centrality index

中图分类号:  (Complex systems)

  • 89.75.-k