摘要 了解哪些類型的現象會導致隨機網路連接中的不連續相變是一個突出的挑戰

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

了解哪些類型的現象會導致隨機網路連接中的不連續相變是一個突出的挑戰。在這裡，我們展示了圖演化的簡單隨機模型會導致不連續的滲透轉變，並且我們得出了潛在的機制：超車成長。從 n 個孤立節點的集合開始，一次檢查一個從完整圖中均勻隨機選擇的潛在邊，同時強制執行最大允許組件大小的上限 k。如果邊的接受分數永遠不會小於隨 k 減少的函數，即 g(k) = 1/2 + (2k)(-beta)，則可以簡單地拒絕相加超過 k 的邊。我們證明，如果 beta < 1，則總是有可能拒絕採樣邊緣，並且最大分量的增長由導致不連續過渡的超車機制主導。如果 beta > 1，一旦 k >= n(1/beta)，有時 !必須接受採樣邊緣，導致由隨機波動和「弱」不連續過渡主導的直接增長。我們還表明，組件尺寸的分佈和組件尺寸的演變與先前觀察到的不同，並且對於所研究的 beta 範圍沒有顯示有限尺寸效應。