# How to generate a connected random network topology for a specific number of nodes?

I'm trying to generate a random but realistic network topology so I can test the performance of some routing algorithms. I came across Waxman's model described in Routing of Multipoint Connections, which seems pretty simple:

1. Distribute $N$ nodes randomly across a plane (uniform in x and y).
2. For each pair of nodes, generate an edge between them with the probability $P = \beta \exp \frac{-d}{L\alpha}$, where $d$ is the euclidean distance between the nodes, $L$ is the maximum distance between two nodes, and $\alpha$ and $\beta$ are parameters in the range $(0, 1]$.

I've implemented my current understanding of Waxman's algorithm as a simple web-based demo, which visualizes a generated topology from chosen parameters $\alpha$, $\beta$, and $N$.

However, I want to be able to generate a connected network topology for a specific number of nodes. Since Waxman's algorithm generates edges probabilistically, I usually end up with disconnected nodes. How do I connect the rest of the nodes to the topology in a way consistent with Waxman's algorithm, i.e. simulates a real network topology?

There are plenty of ways to "finish" the topology by connecting the disconnected nodes, but I don't know which one is the most compatible with the already-generated edges. Waxman's paper doesn't seem to mention how disconnected nodes are treated.

• Waxman doesn't seem to discuss connectedness, as you say. What normally happens in random graph models is that, for suitable choice of the parameters ($\alpha$ and $\beta$), the graph is connected with very high probability (e.g., something like $1-e^{-N}$). The best thing to do would be to figure out that range, either analytically or experimentally, and stay inside it. – David Richerby Nov 3 '13 at 17:18

I played with your demo a little bit and I suppose given a distribution of points, $\beta$ and $\alpha$ can be chosen properly so that the generated graph is connected with a high probability. A brute-force approach can be choosing the parameters using a binary search.