Выбор элемента из коллекции с вероятностью, пропорциональной значению элемента

Question

У меня есть список вершин, из которых я должен выбрать случайную вершину с вероятностью, пропорциональной deg (v), где deg (v) - степень вершины. Псевдо-код для этой операции выглядит так:

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

где и случайным образом выбирается вершина, L список вершин и V является вершиной в L. Проблема заключается в том, что я не понимаю, как сделай это. Может кто-нибудь объяснить мне, как получить эту случайную вершину. Я был бы очень признателен, если бы кто-нибудь мог мне это объяснить. Псевдокод будет еще более оценен;).

Answer 1

решения Простейшего является заполнение списка размеров Sum(d(v)) для каждого v - вы будете держать ссылку на v в точноd(v) записи из списка.

Теперь выберите равномерно распределенную переменную x в диапазоне [0,Sum(d(v))) и вернуть 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|)