從概率與元素值成正比的集合中選擇元素

Question

我有一個頂點列表，我必須從中選擇一個概率與deg（v）成比例的隨機頂點，其中deg（v）是頂點度。此操作的僞代碼看起來像：

Select u ∈ L with probability deg(u)/Sigma ∀v∈L deg(v) 

其中U是隨機選擇的頂點，L是頂點和v的列表是L.頂點的問題是，我不知道如何做到這一點。有人可以向我解釋，如何得到這個隨機頂點。如果有人能向我解釋這一點，我將不勝感激。僞代碼將更加欣賞;）。

Answer 1

簡單的辦法是填充大小Sum(d(v))的列表，每個v - 你會堅持v參考您的列表中的恰好d(v)條目。

現在，在範圍[0,Sum(d(v)))選擇均勻分佈的變量x，並返回list[x]

此方法要求O(n^2)空間（由於用於簡單圖Sigma(d(v)) is O(n^2)），和初始化時間也O(n^2)，但它是僅進行一次。假設你要選擇一個頂點很多次，每次你選擇它，除了第一個，將是O(1) [假設O(1)隨機化函數和隨機訪問列表]。

Answer 2

另一種解決方案;仍然簡單，並且不需要任何預處理或額外的存儲器（如果您有圖表中的邊緣列表）：

選擇一個隨機邊，然後隨機選擇其中一個連接的節點;那是你的隨機頂點。概率與頂點度成正比 - 對於每個節點，概率是

P(v) = sum(P(e: e uses v))/2 = |{e: e uses v}|/(2*|E|) = deg(v)/(2*|E|)