本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
「選擇的力量」已被證明可以從根本上改變許多隨機演算法的行為。在這裡，我們探討選擇對隨機樹生長模型的影響。在我們的模型中，每個新節點都有 k 個隨機選擇的聯絡人，其中 k > 1 是常數。然後，它會附著到這些接觸中在某種意義上最需要的任何一個，例如與根的距離或其度數。即使新節點只有兩個選擇，即 k = 2 時，生成的樹也可能與隨機圖或樹非常不同。例如，如果新節點連接到最接近樹根的接觸點，則深度分佈從泊松解變為行波解。如果新節點以最小度數連接到接觸，則度數分佈比隨機圖中更接近均勻，因此樹中很可能不存在度數大於 O(log logN) 的節點。最後，如果新節點附著到具有最大度數的接觸，我們發現度數分佈是冪律，指數為-1，直到度數大致等於k，超過該值時有指數截止；因此，在這種情況下，我們需要 k >> 1 才能看到大範圍度數的冪律。