Случайные прогулки в ориентированных графах / сетях

Question

У меня есть взвешенный график с (на практике) до 50 000 вершин. Для данной вершины я хочу случайным образом выбрать соседнюю вершину на основе относительных весов всех соседних ребер.

Как мне сохранить этот график в памяти, чтобы сделать выбор эффективным? Какой алгоритм лучше? Это может быть просто хранилище значений ключей для каждой вершины, но это может не соответствовать самому эффективному алгоритму. Мне также нужно будет иметь возможность обновить сеть.

Обратите внимание, что я хотел бы сделать только один "шаг" за раз.

---

Более формально : Для взвешенного, направленного и потенциально полного графа пусть W (a, b) будет весом ребра a-> b и пусть W _a будет суммой всех ребер из a . Учитывая входную вершину v , я хочу выбрать вершину случайным образом, где вероятность выбора вершины x равна W (v, x) / W _v

Пример

Скажите W (v, a) = 2, W (v, b) = 1, W (v, c) = 1.

При заданном входе v функция должна вернуть a с вероятностью 0,5 и b или c с вероятностью 0,25.

Answer 1

Если вы беспокоитесь о производительности генерации случайного блуждания, вы можете использовать метод псевдонима для построения структуры данных, которая соответствует вашим требованиям по выбору случайного исходящего фронта достаточно хорошо. Затраты только на то, что вы должны назначить каждому направленному фронту вес вероятности и так называемый псевдоним.

Таким образом, для каждой ноты у вас есть вектор исходящих ребер, а также вес и ребро псевдонима. Затем вы можете выбрать случайные ребра в постоянное время (только генерация структуры edata является линейным временем по отношению к числу общих ребер или количеству ребер узла). В этом примере ребро обозначено ->[NODE], а узел v соответствует приведенному выше примеру:

Node v
    ->a (p=1,   alias= ...)
    ->b (p=3/4, alias= ->a)
    ->c (p=3/4, alias= ->a)

Node a
    ->c (p=1/2, alias= ->b)
    ->b (p=1,   alias= ...)

...

Если вы хотите выбрать исходящий фронт (то есть следующий узел), вам просто нужно сгенерировать одно случайное число r, унифицированное из интервала [0,1).

Затем вы получите no=floor(N[v] * r) и pv=frac(N[v] * r), где N[v] - это количество исходящих ребер. То есть вы выбираете каждое ребро с точно такой же вероятностью (а именно 1/3 в примере узла v).

Затем вы сравниваете присвоенную вероятность p этого ребра с сгенерированным значением pv. Если pv меньше, вы сохраняете край, выбранный ранее, в противном случае вы выбираете его край псевдонима.

Если, например, у нас есть r=0.6 из нашего генератора случайных чисел, у нас есть

no = floor(0.6*3) = 1 
pv = frac(0.6*3) = 0.8

Поэтому мы выбираем второй исходящий фронт (обратите внимание, что индекс начинается с нуля), который равен

->b (p=3/4, alias= ->a)

и переключиться на псевдоним ->a, начиная с p=3/4 < pv.

Для примера узла v мы, следовательно,

• выберите ребро b с вероятностью 1/3*3/4 (т.е. всякий раз, когда no=1 и pv<3/4)
• выберите ребро c с вероятностью 1/3*3/4 (т.е. всякий раз, когда no=2 и pv<3/4)
• выберите ребро a с вероятностью 1/3 + 1/3*1/4 + 1/3*1/4 (т.е. всякий раз, когда no=0 или pv>=3/4)

Answer 2

Теоретически, наиболее эффективным способом является сохранение для каждого узла морального эквивалента сбалансированного бинарного дерева (красно-черное, или BTree, или все списки пропусков) всех связанных узлов и их весов, и общий вес с каждой стороны. Затем вы можете выбрать случайное число от 0 до 1, умножить его на общий вес подключенных узлов, а затем выполнить двоичный поиск, чтобы найти его.

Однако обход такого бинарного дерева включает в себя множество вариантов, которые имеют тенденцию создавать конвейерные остановки. Которые очень дороги. Так что на практике, если вы программируете на эффективном языке (например, C ++), если у вас есть менее пары сотен связанных ребер на узел, линейный список ребер (с предварительно вычисленной суммой), по которому вы переходите цикл может оказаться быстрее.