Efficiently matching random inhomogeneous graphs via degree profiles
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915448288706560 |
|---|---|
| author | Ding, Jian Fei, Yumou Wang, Yuanzheng |
| author_facet | Ding, Jian Fei, Yumou Wang, Yuanzheng |
| contents | In this paper, we study the problem of recovering the latent vertex correspondence between two correlated random graphs with vastly inhomogeneous and unknown edge probabilities between different pairs of vertices. Inspired by and extending the matching algorithm via degree profiles by Ding, Ma, Wu and Xu (2021), we obtain an efficient matching algorithm as long as the minimal average degree is at least $Ω(\log^{2} n)$ and the minimal correlation is at least $1 - O(\log^{-2} n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_10441 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficiently matching random inhomogeneous graphs via degree profiles Ding, Jian Fei, Yumou Wang, Yuanzheng Data Structures and Algorithms Probability Statistics Theory Machine Learning In this paper, we study the problem of recovering the latent vertex correspondence between two correlated random graphs with vastly inhomogeneous and unknown edge probabilities between different pairs of vertices. Inspired by and extending the matching algorithm via degree profiles by Ding, Ma, Wu and Xu (2021), we obtain an efficient matching algorithm as long as the minimal average degree is at least $Ω(\log^{2} n)$ and the minimal correlation is at least $1 - O(\log^{-2} n)$. |
| title | Efficiently matching random inhomogeneous graphs via degree profiles |
| topic | Data Structures and Algorithms Probability Statistics Theory Machine Learning |
| url | https://arxiv.org/abs/2310.10441 |