What can be considered a "good" fitness value for an arbitrary data set?

To better answer this question, it is important to understand the fitness function and what a fitness value means.

What fitness means

We have m1 ... mn distance metrics. We can compute a distance metric between the real network and a synthetic network generated by evolution (let's say m1_s) and between the real network and a random network of the same size (let's say m1_r). For each metric, we can compute a ratio of improvement (f1 = m1_s / m1_r). In other words, how much closer the synthetic network is to the real one, in relation to a random network of the same size. It could actually be worse than a random network, in which case f1 > 1.

So the fitness value is just max(f1, ..., fn). It's the improvement ratio for the worst performing metric, and it's value is in [0, +inf[.

This maximum strategy in fact forces evolution to never sacrifice improvements in one metric at the expanse of the others, leading to some balance.

An edge case

Now, consider the case where the target network is in fact random. Then you cannot hope for a fitness that is not close to 1. The best approximation you can make is, in fact, no improvement over a random network. So the fitness value by itself does not measure the quality of an approximation.

Empirical assessment

What you can do is look at the absolute values of the metrics that go with a certain fitness value and judge for yourself. These values are output to auxiliary files in the target directory. In our paper, you can see an example of such an assessment in fig. 3.

Now, more broadly, the idea is that the evolutionary effort is a validation in itself. So you can look at the full interpretation of the results as: the best generator that could be found for a certain amount of evolutionary effort. In the paper, we give several examples of what to expect for a reasonable evolutionary effort (30 runs up to 10K stable generations). Then you can draw empirical conclusions by comparison. If you do 30 runs up to 10K stable generators and always find the generator of the random network, then you have some empirical evidence that the target network is probably a random network.