[brite-users] Setting "good" parameters...

Arnaud Legrand Arnaud.Legrand@ens-lyon.fr
Wed Jan 29 16:04:01 2003


Hi,

  I am trying to use BRITE and I have difficulties to find good parameters.
In the user manual you briefly compare some models but you do not provide the
set of parameters you have used for BRITE. You also compare your
implementation with a flat random graph generated with gt-itm but you do not
precise which model was used (Waxman, Pure random, Doar-Leslie, Exponential,
Locality...).

Do you have an idea of where I could find such information ?

In the manual, you do not present any result for the top-down model. Are
some results available somewhere ?

By the way. I have tried to use the Waxman model and it seems to me that
your implementation is incorrect. Let me explain why.

In the Waxman model (as you explain in the documentation and as presented in
most papers I have read), two nodes u and v are connected with a probability
P(u,v)=\alpha e^{-d(u,v)/\beta L}, where \alpha and \beta are in [0,1]. Thus, the
basic method for generating such a graph consist in considering all couples
(u,v) of nodes, to generate a random number x between 0 and 1 and to connect u
and v iff x is smaller or equal than P(u,v). That is why the alpha parameter
controls the "density" of the graph, i.e. the number of edges.

I have been then surprised that changing this parameters had almost no
impact on the look of my graphs. Thus, I have check out your code (C++ and
Java). And in both sources, you proceed roughly in the following way (I do
not take in account the m parameter which does not really change the
problem).

You pick up randomly a node v1.
While v1 is not connected to somebody else :
  You pick up randomly a node v2 which is not already connected to v1.
  You determine whether v1 should be connected to v2 and connect it if it is
  the case.

You repeat this operation until all nodes are connected.

You obviously use this method to ensure that the resulting graph will be
connected. But what if alpha is very high ? Then you're are going to connect
v1 with the the first other node at each step and the resulting graph will
almost look like a tree (with some more edges but not as much as it should).
If the alpha is very small, you are going to have the same kind of graph
because your condition for stopping the creation of new edges is the
connectivity of the graph.

I think you should use the plain method of checking all pairs of node for
deciding whether a new edge should be created or not. Of course, when alpha
is too low, there are some risks for the graph to be non connected. You
should then try to generate a graph following this scheme until you find a
connected graph.

Hope this helps.

Best regards,

	Arnaud Legrand

--
Arnaud Legrand                          tel + 33 4 72 72 85 47
Projet ReMaP, Laboratoire LIP           fax + 33 4 72 72 80 80
UMR CNRS-INRIA-ENS NDEG5668             Arnaud.Legrand@ens-lyon.fr
École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France