1

I have a random graph G(n, p) with n = 5000 vertices and an edge probability of p = 0.004. I wonder what would be the expected number of edges in the graph but I have not much knowledge in probability-theory.

Can anyone help me?

Thank you so much!

EDIT: If pE is the number of possible edges in the Graph, wouldn't I have to calculate 0.004 * pE to get the expected number of edges in the graph?

4

2 回答 2

2

首先,问问自己图中可能的最大边数。这是当每个顶点都连接到每个其他顶点时(nC2 = n * (n-1)/2),假设这是一个没有自环的无向图)。

如果每个可能的边的可能性为 0.004,并且可能的边数为 n(n-1)/2,那么预期的边数将为 0.004*(n(n-1)/2)。

于 2014-11-22T21:07:18.810 回答
0

预期顶点的数量取决于节点的数量和边缘概率,如 E = p(n(n-1)/2)。

如果允许任何 i 作为 i->j 和 j->i 链接到任何 j,则图中可能的边的总数为 n(n-1)。我是你的朋友,你是我的。如果图是无向的(一条边只意味着我们是朋友),边的总数会减少一半:n(n-1)/2,因为 i->j 和 j->i 是相同的。

与 p 的乘法给出了预期的边数,因为每个可能的边都变为真实的或不真实的取决于概率。p=1 给出 n(n-1)/2 个边,因为每个可能的边都实际发生了。对于 p<1 的图,如果您要使用您选择的 p 和 n 实际生成随机图,则实际边数可能(显然)不时不同。但是,如果您要生成无限数量的随机图,则预期边数将是最常见的观察到的边数。如果您想生成随机图并了解网络测量是如何从不同结构的随机图产生的,NetLogo 是一个非常有教学意义的工具。

于 2016-04-05T16:50:39.327 回答