本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2021
摘要
Embedding graphs in a geographical or latent space, i.e., inferring locations for vertices in Euclidean space or on a smooth submanifold, is a common task in 網絡 analysis, 統計 inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to symmetry, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r=nα for α>0, with high probability reconstructs the vertex positions with a maximum error of O(nβ) where β=1/2−(4/3)α, until α≥3/8 where β=0 and the error becomes O(logn‾‾‾‾‾√). This improves ove
※ 此為已發表論文，全文需透過期刊付費取得