Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.00305 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914662502629376 |
|---|---|
| author | Mao, Cheng Wein, Alexander S. Zhang, Shenduo |
| author_facet | Mao, Cheng Wein, Alexander S. Zhang, Shenduo |
| contents | We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. In this model, a dense cycle of expected bandwidth $n τ$, representing the hidden one-dimensional geometry of vertices, is planted in an ambient random graph on $n$ vertices. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $τ$, and an edge-wise signal-to-noise ratio $λ$. In particular, the information-theoretic thresholds differ from the computational thresholds established in a recent work for low-degree polynomial algorithms, thereby justifying the existence of statistical-to-computational gaps for this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00305 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Information-Theoretic Thresholds for Planted Dense Cycles Mao, Cheng Wein, Alexander S. Zhang, Shenduo Statistics Theory Information Theory Social and Information Networks Machine Learning 94A15, 62B10, 68Q87, 05C80, 05C60 We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. In this model, a dense cycle of expected bandwidth $n τ$, representing the hidden one-dimensional geometry of vertices, is planted in an ambient random graph on $n$ vertices. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $τ$, and an edge-wise signal-to-noise ratio $λ$. In particular, the information-theoretic thresholds differ from the computational thresholds established in a recent work for low-degree polynomial algorithms, thereby justifying the existence of statistical-to-computational gaps for this problem. |
| title | Information-Theoretic Thresholds for Planted Dense Cycles |
| topic | Statistics Theory Information Theory Social and Information Networks Machine Learning 94A15, 62B10, 68Q87, 05C80, 05C60 |
| url | https://arxiv.org/abs/2402.00305 |