Random walks with resetting on hypergraph
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918012546711552 |
|---|---|
| author | Ma, Fei Hu, Xincheng Shi, Haobin Pan, Wei Wang, Ping |
| author_facet | Ma, Fei Hu, Xincheng Shi, Haobin Pan, Wei Wang, Ping |
| contents | Hypergraph has been selected as a powerful candidate for characterizing higher-order networks and has received
increasing attention in recent years. In this article, we study random walks with resetting on hypergraph by utilizing
spectral theory. Specifically, we derive exact expressions for some fundamental yet key parameters, including occupation
probability, stationary distribution, and mean first passage time, all of which are expressed in terms of the eigenvalues
and eigenvectors of the transition matrix. Furthermore, we provide a general condition for determining the optimal
reset probability and a sufficient condition for its existence. In addition, we build up a close relationship between
random walks with resetting on hypergraph and simple random walks. Concretely, the eigenvalues and eigenvectors
of the former can be precisely represented by those of the latter. More importantly, when considering random walks,
we abandon the traditional approach of converting hypergraph into a graph and propose a research framework that
preserves the intrinsic structure of hypergraph itself, which is based on assigning proper weights to neighboring nodes.
Through extensive experiments, we show that the new framework produces distinct and more reliable results than
the traditional approach in node ranking. Finally, we explore the impact of the resetting mechanism on cover time,
providing a potential solution for optimizing search efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04215 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Random walks with resetting on hypergraph Ma, Fei Hu, Xincheng Shi, Haobin Pan, Wei Wang, Ping Social and Information Networks Data Analysis, Statistics and Probability Hypergraph has been selected as a powerful candidate for characterizing higher-order networks and has received increasing attention in recent years. In this article, we study random walks with resetting on hypergraph by utilizing spectral theory. Specifically, we derive exact expressions for some fundamental yet key parameters, including occupation probability, stationary distribution, and mean first passage time, all of which are expressed in terms of the eigenvalues and eigenvectors of the transition matrix. Furthermore, we provide a general condition for determining the optimal reset probability and a sufficient condition for its existence. In addition, we build up a close relationship between random walks with resetting on hypergraph and simple random walks. Concretely, the eigenvalues and eigenvectors of the former can be precisely represented by those of the latter. More importantly, when considering random walks, we abandon the traditional approach of converting hypergraph into a graph and propose a research framework that preserves the intrinsic structure of hypergraph itself, which is based on assigning proper weights to neighboring nodes. Through extensive experiments, we show that the new framework produces distinct and more reliable results than the traditional approach in node ranking. Finally, we explore the impact of the resetting mechanism on cover time, providing a potential solution for optimizing search efficiency. |
| title | Random walks with resetting on hypergraph |
| topic | Social and Information Networks Data Analysis, Statistics and Probability |
| url | https://arxiv.org/abs/2505.04215 |