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?
On
The number of expected vertices depend on the number of nodes and the edge probability as in E = p(n(n-1)/2).
The total number of possible edges in your graph is n(n-1) if any i is allowed to be linked to any j as both i->j and j->i. I am your friend, you are mine. If the graph is undirected (and an edge only means that we are friends) the total number of edges drop by half: n(n-1)/2 since i->j and j->i are the same.
The multiplication with p gives the expected number of edges, since every possible edge has become real or not depending on the probability. p=1 gives n(n-1)/2 edges since every possible edge actually happened. For graphs with p<1, the actual edge count might (obviously) differ from time to time if you were to actually generate a random graph using the p and n of your choice. Expected edge count will however be the most common observed edge count if you were to generate an infinite number of random graphs. NetLogo is a very pedagogical tool if you want to generate random graphs and get a feel for how network measurements arise from random graphs of different structures.
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).