鄂尔多斯人一随机图模型的概率如何确定

Question

我正在理解 erdos ranyi 随机图背后的逻辑 model.I 我正在使用 R studio 生成这个随机图。该模型有两个子部分，一个是 G(n,p)，其中，n = 节点总数，p = 任意两个节点共享一条边的概率。我们必须将概率作为输入才能通过。假设如果我进行随机掷硬币实验，那么如果有正面，我将连接两个节点，如果有反面，我将不连接概率为 0.5 的两个节点。当假设我将提供概率 p = 0.3 并且节点数为 5 那么节点将如何根据 0.3 概率连接时，我没有得到。我的r脚本如下。

library(igraph)
g10 <- erdos.renyi.game(5,0.3)

Answer 1

如果你有 5 个节点，那么你在无向图中有 5*4/2 = 10 条可能的边。如果每条边的存在概率为 0.3，则这些图的多个实例上的边数分布为二项分布，概率为 0.3，大小为 10。

让我们来试验一下。生成1000张图并统计节点数：

> g3_edges = table(replicate(1000,length(E(erdos.renyi.game(5,.3)))))
> g3_edges

  0   1   2   3   4   5   6   7   8 
 34 132 230 266 194 100  31  12   1

p=0.3 的 10 到 8 条边的理论分布由 dbinom 给出，我将乘以我的 1000 次模拟计数并取整数与我的模拟进行比较 table:

> p3_edges = as.integer(dbinom(0:8, size=10, p=0.3)*1000)
> p3_edges
[1]  28 121 233 266 200 102  36   9   1

看起来非常接近，并且可能在随机抽样变化范围内。此外，我们没有生成任何具有 9 条或 10 条边的图，并且理论分布已经下降到 8 条边时的 1，所以这也不足为奇。

> cbind(g3_edges, p3_edges)
  g3_edges p3_edges
0       34       28
1      132      121
2      230      233
3      266      266
4      194      200
5      100      102
6       31       36
7       12        9
8        1        1

如果需要，请重复 p=0.5。在这种情况下，我得到了最多 9 个边的图形：

> g5_edges = table(replicate(1000,length(E(erdos.renyi.game(5,.5)))))
> p5_edges = as.integer(dbinom(0:9, size=10, p=0.5)*1000)
> cbind(g5_edges, p5_edges)
  g5_edges p5_edges
0        2        0
1       14        9
2       53       43
3      102      117
4      216      205
5      266      246
6      199      205
7       91      117
8       39       43
9       18        9

那么你的问题在哪里？

鄂尔多斯人一随机图模型的概率如何确定

How to decide probability of Erdos renyi random graph model

r

graph-theory