随机游走在向图/网络 [英] Random walks in directed graphs/networks

问题描述

我有一个加权图，（实际上）高达50,000顶点。给定一个顶点，我想随机选择基于所有相邻边的相对权重的邻点。

I have a weighted graph with (in practice) up to 50,000 vertices. Given a vertex, I want to randomly choose an adjacent vertex based on the relative weights of all adjacent edges.

我应该如何存储这些图形在内存中，这样做的选择是有效的？什么是最好的算法？它可以是简单的密钥值存储每个顶点，但是，很可能不适于到最有效的算法。我还需要能够更新网络。

How should I store this graph in memory so that making the selection is efficient? What is the best algorithm? It could be as simple as a key value store for each vertex, but that might not lend itself to the most efficient algorithm. I'll also need to be able update the network.

请注意，我想借此只有一个一步到位的时间。

Note that I'd like to take only one "step" at a time.

更正式：给定一个加权，定向，并可能完全图，让我们的 W（A，B）的是边A-> B，让体重是W <子>一 的全部边缘的距离的在。给定一个输入顶点的 v 的，我想选择一个顶点随机，其中选择顶点的 X 的是 W（V，X） / <的可能性EM>是W <子> v 的

More Formally: Given a weighted, directed, and potentially complete graph, let W(a,b) be the weight of edge a->b and let W_a be the sum of all edges from a. Given an input vertex v, I want to choose a vertex randomly where the likelihood of choosing vertex x is W(v,x) / W_v

示例

说的 W（V，A） = 2， W（V，B）的= 1， W（V，C）的= 1。

Say W(v,a) = 2, W(v,b) = 1, W(v,c) = 1.

由于输入的 v 的，该函数返回的在的概率为0和 B 或 C 的概率为0.25

Given input v, the function should return a with probability 0.5 and b or c with probability 0.25.

推荐答案

如果您担心产生的随机游走，你可以使用的别名方法建立哪些适合你的选择随机出边相当不错的需求的数据结构。开销就是，你必须为每个有向边的概率重量和所谓的别名优势。

If you are concerned about the performance of generating the random walk you may use the alias method to build a datastructure which fits your requirements of choosing a random outgoing edge quite well. The overhead is just that you have to assign each directed edge a probability weight and a so-called alias-edge.

因此​​，对于每个注意你有出边的矢量连同重量和别名边缘。然后，你可以选择在固定时间随机边缘（第的EDATA结构是相对于总的边缘或节点的边数数线性时间只有代）。在这个例子中的边缘记为 - ＆GT; [NODE] 和节点 v 对应上面给出的例子：

So for each note you have a vector of outgoing edges together with the weight and the alias edge. Then you may choose random edges in constant time (only the generation of th edata structure is linear time with respect to number of total edges or number of node edges). In the example the edge is denoted by ->[NODE] and node v corresponds to the example given above:

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= ...)

...

如果你想选择一个出边（即下一个节点），你只需要产生一个随机数区间[0,1 研究制服）。

If you want to choose an outgoing edge (i.e. the next node) you just have to generate a single random number r uniform from interval [0,1).

您再拿到无=地板（N [V] * R）和 PV =压裂（N [V] * R），其中 N [V] 是出边的数量。即你选择的每个边具有完全相同的概率（在节点的例子，即1/3 v ）。

You then get no=floor(N[v] * r) and pv=frac(N[v] * r) where N[v] is the number of outgoing edges. I.e. you pick each edge with the exact same probability (namely 1/3 in the example of node v).

那你这条边的分配概率 P 与生成的值光伏进行比较。如果光伏少你保持之前选择的边缘，否则你选择它的别名优势。

Then you compare the assigned probability p of this edge with the generated value pv. If pv is less you keep the edge selected before, otherwise you choose its alias edge.

例如，如果我们有 R = 0.6 从我们的随机数生成器，我们有

If for example we have r=0.6 from our random number generator we have

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

因此​​，我们选择第二个出边（注意索引从0开始），这是

Therefore we choose the second outgoing edge (note the index starts with zero) which is

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

和切换到别名边缘 - ＆gt;在，因为点= 3/4℃;光伏。

and switch to the alias edge ->a since p=3/4 < pv.

有关节点的例子 v 因此我们

For the example of node v we therefore

• 选择边缘 B 的概率三分之一*四分之三（即每当无= 1 和 PV＆LT; 3/4 ）
• 选择边缘 C 的概率三分之一*四分之三（即每当无= 2 和 PV＆LT; 3/4 ）
• 选择边缘 A 的概率 1/3 + 1/3 * 1/4 + 1/3 *四分之一（即每当无= 0 或 PV＆GT; =四分之三）

• choose edge b with probability 1/3*3/4 (i.e. whenever no=1 and pv<3/4)
• choose edge c with probability 1/3*3/4 (i.e. whenever no=2 and pv<3/4)
• choose edge a with probability 1/3 + 1/3*1/4 + 1/3*1/4 (i.e. whenever no=0 or pv>=3/4)

这篇关于随机游走在向图/网络的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！