论文标题
图形线的线插件的重建
Reconstruction of Line-Embeddings of Graphons
论文作者
论文摘要
考虑一个随机的图形过程，其中$ n $顶点对应于点$ v_ {i} \ sim {unif} [0,1] $在间隔中随机嵌入，并且在$ v_ {i}，v_ {j} $之间插入边缘，并独立于graphon $ w（v _} $ w（i} $} $）。遵循Chuangpishit等。 （2015年），如果对于每种$ x $，$ w（x，y）$减少，我们称graphon $ w $对角线增加，$ y $从$ x $移动。如果$ v_ {σ（i）} <v_ {σ（j）} $，我们将这些顶点的排列称为s_ {n} $ in s_ {n} $作为所有$ i <j $的订购，然后问：我们如何准确地从观察图中估算$σ$？我们提出了一种随机算法，带有输出$ \hatσ$，对于大型图形，实现错误$ \ max_ {1 \ leq i \ leq n} | σ（i） - \hatσ（i）| = o^{*}（\ sqrt {n}）$具有高概率；我们还表明，这是大量算法和证明策略的最佳融合率。在某些流行的Graphon模型满足的其他假设下，我们以$ \ sqrt {n} $打破了此“障碍”，并获得了任何$ε> 0 $的$ o^{*}（n^ε）$的更高速率。这些改进的序列界限可以与先前的工作结合使用，以提供相关任务的更有效和准确的算法，包括：估计对角线增加图形，并测试Graphon是否对角线增加。
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.
