Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8897662 | Linear Algebra and its Applications | 2018 | 33 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Israel Rocha, Jeannette Janssen, Nauzer Kalyaniwalla,