Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.