随机图模型

Question

当我们说在随机图中，我们添加一个具有一定固定概率的边缘，我们实际上是什么意思？

例如，如果概率为0.5，这是否意味着我们可以在图中添加两个边缘，因为0.5+0.5 = 1。

Answer 1

假设您希望计算随机图$ g（n，p）$，它是带有$ n $顶点的图形，其中添加每个边缘的概率$ p。$。

假设您有一枚硬币，该硬币具有概率$ p $的尾部，概率为$ 1-p。$。

然后，您要做的是$ {1，...，n } $作为图形的顶点集，每对$（i，j） in { {1， ldots，n } 选择2} $您翻转硬币。如果尾巴来了，则将边缘$（i，j）$添加到图形，否则您不会。

Answer 2

在随机$ g（n，p）$型号中，$ binom {n} {2} $ edges都添加到图形中，概率$ p $ 独立. 。这意味着，如果您考虑任何两个边，则两者都在图中，概率$ p^2 $，而不是$ 2p $。

Answer 3

除了说正确的话，您还可以构建一个随机图$ g（n，p）$，价格为$ 0 leq p leq 1 $，如下：

假设您有一组顶点$ v $和空的边缘$ e $。对于$ v $中的每个$ v $：对于$ v $中的每个$ u $（其中$ u> v $相对于$ v $的节点中的某些总订单）：生成一个统一的随机数$ r $ $ r in [0,1] $。如果（$ r leq p $），则包括边缘$（v，u）$和$（u，v）$ to $ e $。

这会生成一个随机图$ g =（v，e）$表示$ g（n，p）$ white $ | v | = n $。但是，这是一个有向图。如果您想将其制作为有向图，因为该图形不遵循定义，请仅添加图$（v，u）$。