本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
了解互聯網的圖結構是建立準確的網路模型和為互聯網應用設計高效演算法的關鍵一步。然而，要獲得這種圖結構可能是一項非常困難的任務，因為無法明確查詢邊。例如，對網際網路協定 (IP) 位址網路的實證研究通常依賴追蹤路由等間接方法來建構近似單源、全目的地、最短路徑樹。這些樹僅對網路邊緣的一小部分進行採樣，Lakhina 等人的一篇論文。 [2003] 根據經驗發現，所得樣本本質上是有偏差的。此外，在模擬中，他們觀察到即使底層度分佈是泊松分佈，追蹤路由取樣下的度分佈也呈現冪律分佈。在本文中，我們從數學角度研究了追蹤路由採樣的偏差，並且對於一類非常一般的底層度分佈，明確地計算了將觀察到的分佈。作為我們機器的範例應用，我們證明追蹤路由取樣可以在 delta 正規和泊松分佈隨機圖中找到冪律度分佈。因此，我們的工作將 Lakhina 等人的觀察結果納入其中。在嚴格的基礎上，並將它們擴展到幾乎任意的程度分佈。