4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Commented Nov 3, 2013 at 17:18

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

You could compute connected components, find the largest connected component, and keep all the nodes in the largest component (discarding the rest of the nodes). That would give you a connected graph and might yield a reasonable distribution on the resulting graph.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This would work, but I'd have to generate a topology for a lot more edges than I actually need in order to get enough connected nodes with a high probability, which is undesirable. $\endgroup$
    – blendmaster
    Commented Nov 3, 2013 at 5:47
  • $\begingroup$ @blendmaster, doesn't that depend upon the parameters you choose? I'd expect there to be a range of parameter values where the largest component has at least a constant fraction of the nodes (which is enough that this procedure would be efficient). $\endgroup$
    – D.W. ♦
    Commented Nov 3, 2013 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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