Optimal recovery of correlated Erdős-Rényi graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929718275604480 |
|---|---|
| author | Du, Hang |
| author_facet | Du, Hang |
| contents | For two unlabeled graphs $G_1,G_2$ independently sub-sampled from an Erdős-Rényi graph $\mathbf G(n,p)$ by keeping each edge with probability $s$, we aim to recover \emph{as many as possible} of the corresponding vertex pairs. We establish a connection between the recoverability of vertex pairs and the balanced load allocation in the true intersection graph of $ G_1 $ and $ G_2 $. Using this connection, we analyze the partial recovery regime where $ p = n^{-α+ o(1)} $ for some $ α\in (0, 1] $ and $ nps^2 = λ= O(1) $. We derive upper and lower bounds for the recoverable fraction in terms of $ α$ and the limiting load distribution $ μ_λ$ (as introduced in \cite{AS16}). These bounds coincide asymptotically whenever $ α^{-1} $ is not an atom of $ μ_λ$. Therefore, for each fixed $ λ$, our result characterizes the asymptotic optimal recovery fraction for all but countably many $ α\in (0, 1] $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_12077 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal recovery of correlated Erdős-Rényi graphs Du, Hang Probability 60C05 For two unlabeled graphs $G_1,G_2$ independently sub-sampled from an Erdős-Rényi graph $\mathbf G(n,p)$ by keeping each edge with probability $s$, we aim to recover \emph{as many as possible} of the corresponding vertex pairs. We establish a connection between the recoverability of vertex pairs and the balanced load allocation in the true intersection graph of $ G_1 $ and $ G_2 $. Using this connection, we analyze the partial recovery regime where $ p = n^{-α+ o(1)} $ for some $ α\in (0, 1] $ and $ nps^2 = λ= O(1) $. We derive upper and lower bounds for the recoverable fraction in terms of $ α$ and the limiting load distribution $ μ_λ$ (as introduced in \cite{AS16}). These bounds coincide asymptotically whenever $ α^{-1} $ is not an atom of $ μ_λ$. Therefore, for each fixed $ λ$, our result characterizes the asymptotic optimal recovery fraction for all but countably many $ α\in (0, 1] $. |
| title | Optimal recovery of correlated Erdős-Rényi graphs |
| topic | Probability 60C05 |
| url | https://arxiv.org/abs/2502.12077 |