随机走在有向图/网络中

Question

我有一个加权图(实际上)最多50,000个顶点.给定一个顶点,我想根据所有相邻边的相对权重随机选择一个相邻的顶点.

我应该如何将此图存储在内存中,以便进行选择？什么是最好的算法？它可以像每个顶点的键值存储一样简单,但这可能不适合最有效的算法.我还需要能够更新网络.

请注意,我一次只想采取一个"步骤".

---

更正式:给定的加权,定向,和潜在的完全图,让W(A,B)是边缘A-> B的重量,并让W¯¯ _一个是从所有的边缘的总和一个.给定一个输入顶点v,我想随机选择一个顶点,其中选择顶点x的可能性是W(v,x)/W _v

示例:

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

给定输入v,函数应以概率0.5和b或c以概率0.25 返回a.

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)