Počet záznamů: 1
Recovering the Structure of Random Linear Graphs
- 1.
SYSNO ASEP 0492167 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Recovering the Structure of Random Linear Graphs Tvůrce(i) Rocha, Israel (UIVT-O) RID, SAI, ORCID
Janssen, J. (CA)
Kalyaniwalla, N. (CA)Zdroj.dok. Linear Algebra and Its Applications. - : Elsevier - ISSN 0024-3795
Roč. 557, 15 November (2018), s. 234-264Poč.str. 31 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova Random graphs ; Toeplitz Matrices ; Random Matrices ; Seriation problem ; Stochastic block model ; Rank correlation coefficient Vědní obor RIV BA - Obecná matematika Obor OECD Applied mathematics Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000444926700011 EID SCOPUS 85050823990 DOI 10.1016/j.laa.2018.07.029 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2019
Počet záznamů: 1