Reconstruction of line-embeddings of graphons
Jeannette Janssen, Aaron Douglas Smith · Electronic Journal of Statistics · 2022
Consider a random graph process with n vertices corresponding to points vi∼i.i.d.Unif[0,1] embedded randomly in the interval, and where edges are inserted between vi,vj independently with probability given by the graphon w(vi,vj)∈[0,1]. Following [11], 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 σ∈Sn an ordering of these vertices if vσ(i) 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 [20, 21] and testing whether a graphon is diagonally increasing [11].