Graph Reconstruction from Noisy Random Subgraphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909713138974720 |
|---|---|
| author | McGregor, Andrew Sengupta, Rik |
| author_facet | McGregor, Andrew Sengupta, Rik |
| contents | We consider the problem of reconstructing an undirected graph $G$ on $n$ vertices given multiple random noisy subgraphs or "traces". Specifically, a trace is generated by sampling each vertex with probability $p_v$, then taking the resulting induced subgraph on the sampled vertices, and then adding noise in the form of either (a) deleting each edge in the subgraph with probability $1-p_e$, or (b) deleting each edge with probability $f_e$ and transforming a non-edge into an edge with probability $f_e$. We show that, under mild assumptions on $p_v$, $p_e$ and $f_e$, if $G$ is selected uniformly at random, then $O(p_e^{-1} p_v^{-2} \log n)$ or $O((f_e-1/2)^{-2} p_v^{-2} \log n)$ traces suffice to reconstruct $G$ with high probability. In contrast, if $G$ is arbitrary, then $\exp(Ω(n))$ traces are necessary even when $p_v=1, p_e=1/2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04261 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph Reconstruction from Noisy Random Subgraphs McGregor, Andrew Sengupta, Rik Information Theory Data Structures and Algorithms We consider the problem of reconstructing an undirected graph $G$ on $n$ vertices given multiple random noisy subgraphs or "traces". Specifically, a trace is generated by sampling each vertex with probability $p_v$, then taking the resulting induced subgraph on the sampled vertices, and then adding noise in the form of either (a) deleting each edge in the subgraph with probability $1-p_e$, or (b) deleting each edge with probability $f_e$ and transforming a non-edge into an edge with probability $f_e$. We show that, under mild assumptions on $p_v$, $p_e$ and $f_e$, if $G$ is selected uniformly at random, then $O(p_e^{-1} p_v^{-2} \log n)$ or $O((f_e-1/2)^{-2} p_v^{-2} \log n)$ traces suffice to reconstruct $G$ with high probability. In contrast, if $G$ is arbitrary, then $\exp(Ω(n))$ traces are necessary even when $p_v=1, p_e=1/2$. |
| title | Graph Reconstruction from Noisy Random Subgraphs |
| topic | Information Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.04261 |