Recovering the Structure of Random Linear Graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F18%3A00492167" target="_blank" >RIV/67985807:_____/18:00492167 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.laa.2018.07.029" target="_blank" >http://dx.doi.org/10.1016/j.laa.2018.07.029</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.laa.2018.07.029" target="_blank" >10.1016/j.laa.2018.07.029</a>

Result language
angličtina
Original language name
Recovering the Structure of Random Linear Graphs
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10102 - Applied mathematics

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)