Recovering the Structure of Random Linear Graphs

0492167 - ÚI 2019 RIV US eng J - Článek v odborném periodiku
Rocha, Israel - Janssen, J. - Kalyaniwalla, N.
Recovering the Structure of Random Linear Graphs.
Linear Algebra and Its Applications. Roč. 557, 15 November (2018), s. 234-264. ISSN 0024-3795. E-ISSN 1873-1856
Institucionální podpora: RVO:67985807
Klíčová slova: Random graphs * Toeplitz Matrices * Random Matrices * Seriation problem * Stochastic block model * Rank correlation coefficient
Obor OECD: Applied mathematics
Impakt faktor: 0.977, rok: 2018

In a random linear graph, vertices are points on a line, and pairs of vertices are connected, independently, with a link probability that decreases with distance. We study the problem of reconstructing the linear embedding from the graph, by recovering the natural order in which the vertices are placed. We propose an approach based on the spectrum of the graph, using recent results on random matrices. We demonstrate our method on a particular type of random linear graph. We recover the order and give tight bounds on the number of misplaced vertices, and on the amount of drift from their natural positions.
Trvalý link: http://hdl.handle.net/11104/0285724