I am new to Graph theory. Please correct me if I am wrong.
How do I define the probability of linking nodes to create a random bidirectional network (Erdos Renyi network) with network density of $25$%?
For instance in a bidirectional graph, I have 10 nodes, which implies that there can be max of $90$ connections (remember it is a bidirectional graph). Now I need to generate a random graph with these $10$ nodes with a density of $25$%, i.e the number of connections should be $23$.
So can anybody help me out with this? Any information on this will be highly beneficial.
Thanks
Best Answer
You seem to be describing the directed Erdős-Rényi $\vec{G}(n,m)$ model.
In this model, we start with a graph $G$ with $n=10$ vertices and no arcs. We generate two vertices at random $i$ and $j$. If $i \neq j$, we add the arc $ij$ to $G$ (provided it is not already there). We keep going until we have the desired number of arcs (usually denoted $m$).
This process will sample uniformly at random from all graphs on $n$ vertices with $m$ arcs.
If you're keen on using the $\vec{G}(n,p)$ model, you can choose $p$ such that the expected number of edges $n(n-1)p$ is $m$. We simply take $p=\frac{m}{n(n-1)}$. The number of edges will be distributed binomially $\sim \mathrm{Bi}(n(n-1),p)$ about this mean with variance $m(1-p)$.
If you need to obtain exactly $25$ edges, it's probably going to be best to use the $G(n,m)$ model.