Number of the records: 1
Recovering the Structure of Random Linear Graphs
- 1.
SYSNO ASEP 0492167 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Recovering the Structure of Random Linear Graphs Author(s) Rocha, Israel (UIVT-O) RID, SAI, ORCID
Janssen, J. (CA)
Kalyaniwalla, N. (CA)Source Title Linear Algebra and Its Applications. - : Elsevier - ISSN 0024-3795
Roč. 557, 15 November (2018), s. 234-264Number of pages 31 s. Language eng - English Country US - United States Keywords Random graphs ; Toeplitz Matrices ; Random Matrices ; Seriation problem ; Stochastic block model ; Rank correlation coefficient Subject RIV BA - General Mathematics OECD category Applied mathematics Institutional support UIVT-O - RVO:67985807 UT WOS 000444926700011 EID SCOPUS 85050823990 DOI 10.1016/j.laa.2018.07.029 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2019
Number of the records: 1