# How to generate random graph?

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

-
Are you aware of the algorithm which generates mazes in the ages old Maze game, in a modern version, you can assign a maze density? If yes, a modification of that algorithm is sufficient for your task. – Cheeku Feb 27 '13 at 13:58

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.