本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
將圖嵌入到地理或潛在空間中，即推斷歐幾里德空間中或平滑子流形上的頂點位置，是網絡分析、統計推斷和圖形視覺化中的常見任務。我們考慮隨機幾何圖的經典模型，其中n個點均勻分散在面積為n的正方形中，並且當且僅當它們的歐幾里德距離小於r時，兩個點之間才有邊。然後，重構問題包括在僅給出結果圖的鄰接矩陣的情況下推斷頂點位置直至對稱性。我們給了一個演算法，如果 r=nα 且 α>0，則以高機率重建頂點位置，最大誤差為 O(nβ)，其中 β=1/2−(4/3)α，直到 α≥3/8，其中 β=0，誤差變成 O(logn‾‾‾‾‾√)。這比早期的結果有所改進，早期的結果無法以小於 r 的誤差進行重建。我們的方法使用圖距離和基於共同鄰居數量的短程估計的混合來估計歐幾里德距離。我們草擬了證明，證明我們的結果也適用於球體表面，並且（指數略有不同）任何固定維度。