Search code examples
graphprobability-theory

Finding probability of edges in a graph

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?

Solution

  • First, ask yourself the maximum number of possible edges in the graph. This is when every vertex is connected to every single other vertex (nC2 = n * (n-1)/2), assuming this is an undirected graph without self-loops).

    If each possible edge has a likelihood of 0.004, and the # of possible edges is n(n-1)/2, then the expected number of edges will be 0.004*(n(n-1)/2).