我有一个带有（实际上）多达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。
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.
More Formally: Given a weighted, directed, and potentially complete graph, let W(a,b) be the weight of edge a->b and let Wa 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) / Wv
Example:
Say W(v,a) = 2, W(v,b) = 1, W(v,c) = 1.
Given input v, the function should return a with probability 0.5 and b or c with probability 0.25.
最满意答案
如果您担心生成随机游走的性能，则可以使用别名方法构建适合您选择随机出局边缘的要求的数据结构。 开销只是你必须为每个有向边指定一个概率权重和一个所谓的别名边。
因此，对于每个音符，您都有一个向外边缘矢量以及重量和别名边缘。 然后你可以选择在不变的时间内的随机边缘（只有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= ...) ...如果你想选择一个输出边（即下一个节点），你只需要从区间[0,1）产生一个随机数r uniform。
然后你得到no=floor(N[v] * r)和pv=frac(N[v] * r) ，其中N[v]是输出边的数量。 即，您以完全相同的概率选取每条边（即节点v示例中的1/3）。
然后，您将该边缘的分配概率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的例子
以概率1/3*3/4选择边b （即每当no=1且pv<3/4 ） 选择边缘c的概率为1/3*3/4 （即每当no=2且pv<3/4 ） 选择概率为1/3 + 1/3*1/4 + 1/3*1/4边a （即每当no=0或pv>=3/4 ）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.
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= ...) ...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).
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).
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.
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.8Therefore we choose the second outgoing edge (note the index starts with zero) which is
->b (p=3/4, alias= ->a)and switch to the alias edge ->a since p=3/4 < pv.
For the example of node v we therefore
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)更多推荐
发布评论