Reconstruction of Line-Embeddings of Graphons
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916298982686720 |
|---|---|
| author | Janssen, Jeannette Smith, Aaron |
| author_facet | Janssen, Jeannette Smith, Aaron |
| contents | Consider a random graph process with $n$ vertices corresponding to points $v_{i} \sim {Unif}[0,1]$ embedded randomly in the interval, and where edges are inserted between $v_{i}, v_{j}$ independently with probability given by the graphon $w(v_{i},v_{j}) \in [0,1]$. Following Chuangpishit et al. (2015), we call a graphon $w$ diagonally increasing if, for each $x$, $w(x,y)$ decreases as $y$ moves away from $x$. We call a permutation $σ\in S_{n}$ an ordering of these vertices if $v_{σ(i)} < v_{σ(j)}$ for all $i < j$, and ask: how can we accurately estimate $σ$ from an observed graph? We present a randomized algorithm with output $\hatσ$ that, for a large class of graphons, achieves error $\max_{1 \leq i \leq n} | σ(i) - \hatσ(i)| = O^{*}(\sqrt{n})$ with high probability; we also show that this is the best-possible convergence rate for a large class of algorithms and proof strategies. Under an additional assumption that is satisfied by some popular graphon models, we break this "barrier" at $\sqrt{n}$ and obtain the vastly better rate $O^{*}(n^ε)$ for any $ε> 0$. These improved seriation bounds can be combined with previous work to give more efficient and accurate algorithms for related tasks, including: estimating diagonally increasing graphons, and testing whether a graphon is diagonally increasing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_06444 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Reconstruction of Line-Embeddings of Graphons Janssen, Jeannette Smith, Aaron Probability Data Structures and Algorithms 60-08 (primary) 60B20, 05C80 (secondary) G.3; G.2.2 Consider a random graph process with $n$ vertices corresponding to points $v_{i} \sim {Unif}[0,1]$ embedded randomly in the interval, and where edges are inserted between $v_{i}, v_{j}$ independently with probability given by the graphon $w(v_{i},v_{j}) \in [0,1]$. Following Chuangpishit et al. (2015), we call a graphon $w$ diagonally increasing if, for each $x$, $w(x,y)$ decreases as $y$ moves away from $x$. We call a permutation $σ\in S_{n}$ an ordering of these vertices if $v_{σ(i)} < v_{σ(j)}$ for all $i < j$, and ask: how can we accurately estimate $σ$ from an observed graph? We present a randomized algorithm with output $\hatσ$ that, for a large class of graphons, achieves error $\max_{1 \leq i \leq n} | σ(i) - \hatσ(i)| = O^{*}(\sqrt{n})$ with high probability; we also show that this is the best-possible convergence rate for a large class of algorithms and proof strategies. Under an additional assumption that is satisfied by some popular graphon models, we break this "barrier" at $\sqrt{n}$ and obtain the vastly better rate $O^{*}(n^ε)$ for any $ε> 0$. These improved seriation bounds can be combined with previous work to give more efficient and accurate algorithms for related tasks, including: estimating diagonally increasing graphons, and testing whether a graphon is diagonally increasing. |
| title | Reconstruction of Line-Embeddings of Graphons |
| topic | Probability Data Structures and Algorithms 60-08 (primary) 60B20, 05C80 (secondary) G.3; G.2.2 |
| url | https://arxiv.org/abs/2007.06444 |