Systematic testing of randomize() validity

[TheoBerglin]

We need to establish a method for systematicly testing randomize() function validity.

Method proposal

The randomize() function implemented in Braph and BCT are considered to be "ground truth" and used for comparision. Consider a matrix A which is randomized using the current randomize function to matrix rAGT. The same (should it be the same matrix or matrix with the same density?)_ matrix A is randomized using a new method to the matrix rA. We then compare some graph theoretical measures of the two matrices, rA and rA_GT, and if these follow the same distribution we consider the randomize function to be working properly. The tests should be carried out for different matrix densities and especially in the limit of low density matrices.

I think the best way is to separate the functionality to multiple test files. One which runs the randomization and saves the result and one file which analyzes the original and randomized matrices.

Questions that needs to be answered (Add questions if needed)

1. Should we perform the comparision test multiple times for the same matrix?
2. Should we have a set of fixed matrices of different densitities which we perform the tests on or should we create random matrices with a given density for each test?
3. How do we make the comparision between measure distribution? Preferably some statistical test.
4. Which measures are we going to use for the tests?
5. How and what information do we save from a run so that we minimize the times we have to run the randomize() function?

Question 2 I think it would be best to have a fixed set of matrices for which we run the different randomize functions on. This way we don't have to save a bunh of randomly generated matrices as we run the tests. We can also test the methods on the same set of matrices.

Question 5 I think we should save the randomized matrices only. Each randomize function should have a tag so that we can distinguish the different functions. Then the save structure will be: randomize->data->Randomize_tag_1->run1.txt __|__run2.txt __| __--Randomize_tag_2->run1.txt

The name of the files should be depending on the run time of the algorithm, which matrix we randomized and the time we ran the algorithm in YY-MM-DD-HH-mm-ss. The date part is used so that we can run the test files on multiple computers at the same time and upload them to Git without a name conflict. File name suggestion: om_{original_matrix}rt{run_time}date{date}.txt

[giovannivolpe]

I agree. It seems correct.

should it be the same matrix or matrix with the same density?

A should be the same matrix

I think the best way is to separate the functionality to multiple test files. One which runs the randomization and saves the result and one file which analyzes the original and randomized matrices.

It's probably best if you don't save the matrices, but analyse them on the fly, to avoid having to use too much memory.

1. Should we perform the comparision test multiple times for the same matrix?

Yes, you should generate multiple random matrices for a given matrix.

2. Should we have a set of fixed matrices of different densitities which we perform the tests on or should we create random matrices with a given density for each test?

It's be best to be able to run the test both on a set of pre-sevaed matrices (good for pre-saved distributions, see point 5) and on matrices created on the fly.

3. How do we make the comparision between measure distribution? Preferably some statistical test.

For example, you can use the Kolmogorov-Smirnov test to compare the probability distributions: https://en.wikipedia.org/wiki/Kolmogorov–Smirnov_test

4. Which measures are we going to use for the tests?

Global measures.

5. How and what information do we save from a run so that we minimize the times we have to run the randomize() function?

In the test function, we just run it multiple times. If you want, we can save the probability distribution of the global measures for the "ground truth" randomization.

[TheoBerglin]

Great!

Is it of importance to run the randomization on exactly the same initial graph A when comparing two methods or is similar density enough?

A pseudo-code for the analysis could be the following gm_new = test_randomization(A, type, randomize_function_new, n_randomizations) gm_old = test_randomization(A, type, randomize_function_old, n_randomizations) valid = compare_two_methods(gm_new, gm_old) %statistical comparision save_validation(valid) save_global_measures(gm_new, gm_old) % Save so we can plot them etc after

function gm_list = test_randomization(A, type, randomize_function, n_randomizations) for i = 1:n_randomizations rA = randomize_function(A) gm = calculate_global_measures(A, type) add_measure_to_list_of_measures(gm) return list_of_all_global_measures

[giovannivolpe]

I think it's be better to compare for the same initial graph (otherwise we'd need to average over many initial graphs, which will increase exponentially the computational time).