随机行走有向图/网络
我有一个带有（实际上）多达50,000个顶点的加权图。 给定一个顶点，我想根据所有相邻边的相对权重随机选择一个相邻顶点。
我应该如何将此图存储在内存中，以便使选择更有效率？ 什么是最好的算法？ 它可以像每个顶点的关键值存储一样简单，但这可能不适用于最有效的算法。 我还需要能够更新网络。
请注意，我一次只需要一个“步骤”。
更正式地 ：给定一个加权的，有向的和可能完整的图，令W（a，b）为边a-> b的权重，令Wa为a的所有边的和。 给定一个输入顶点v，我想随机选择一个顶点，其中选择顶点x的可能性为W（v，x）/ Wv
示例 ：
假设W（v，a）= 2，W（v，b）= 1，W（v，c）= 1。
给定输入v，函数应该返回a的概率为0.5，b或c的概率为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 ） 在理论上，要做的绝对最有效的事情是为每个节点存储连接节点及其权重的平衡二叉树（红黑色或BTree或跳过列表全部拟合）的道德等价物，重量向每边。 然后，您可以从0到1中选取一个随机数，乘以所连接节点的总重量，然后执行二进制搜索以找到它。
然而，像这样遍历一个二叉树涉及到很多选择，这有助于创建管道延迟。 这是非常昂贵的。 因此，在实践中，如果您使用高效语言（例如C ++）进行编程，如果每个节点的连接边数少于几百个，则可以使用步进的线性边缘列表（包含预先计算的总和）循环可能会证明更快。
链接地址: http://www.djcxy.com/p/70683.html