6
$\begingroup$

There are many practical measures of randomness for binary or number sequences. Some randomness tests yield a single number (like Kolmogorov complexity), others come as batteries of tests (like the diehard tests). These randomness tests may supposedly not be applied to graphs (given as binary adjacency matrices), at least not in a straight forward way. This is because each permutated adjacency matrix (yielding a different binary sequence) must have the same degree of randomness.

I am looking for a concise overview over "direct" measures of randomness of graphs.

$\endgroup$
8
  • 1
    $\begingroup$ Since you mention it, you could represent a graph with its adjacency matrix and then compute the Kolmogorov complexity of the adjacency matrix. $\endgroup$ – John_Krampf Mar 25 at 12:55
  • $\begingroup$ @John_Krampf: By arbitrary permutations one can make the strictly ordered adjacency matrix of - say - a circle or grid graph into a seemingly random matrix resp. binary sequence. How would Kolmogorov check this - and not the randomness of the permutation? $\endgroup$ – Hans-Peter Stricker Mar 25 at 13:02
  • 1
    $\begingroup$ There are two ways to go around that : brute force, and canon. Brute force would be : generate every permutation of the adjacency matrix, find the smallest in (typically) lexicographic order, and give that one to the Kolmogorov complexity. Canon would be : choose one canonical way to order the vertices in the graph, and always use it. This might give a little better results in Kolmogorov complexity because sometimes that canonical representation might be more natural (and simple) than the lexicographically smallest one ; but you have to be sure about your represenation being unique. $\endgroup$ – Hugo Manet Mar 25 at 16:52
  • $\begingroup$ The brute force can be even more brutal : you generate every permutation, sort them by lexicographic order, and then concatenate them. This way you're a little more sure that the program generating the sequence has some understanding of the symmetry through permutation of the vertices. $\endgroup$ – Hugo Manet Mar 25 at 17:02
  • 1
    $\begingroup$ Every permutation of the adjacency matrix is one permutation away (which is quite small for Kolmogorov complexity) from another, so it wouldn't matter. But yeah, it works. None of this is practical anyway. If you want a practical measure, it's probably because you have an application in mind where you need randomness ; and thus you should design the test with that application in mind... $\endgroup$ – Hugo Manet Mar 27 at 11:40
1
+150
$\begingroup$

As you probably know, the question you ask is crucial in many random graph generation methods.

Indeed, many of them start with a given (biased) graph in a class of interest and perform random small rearrangements of edges that mix the graph and are known to ultimately lead to a uniformly distributed random graph the given class.

A typical example is edge swap (replace $u-v$ and $u'-v'$ by $u-v'$ and $u'-v$) under constraints (not creating loops nor multi-edges) in order to generate random simple graphs. See the following paper for more: Generating constrained random graphs using multiple edge switches by Lionel Tabourier, Camille Roth, Jean-Philippe Cointet.

Unfortunately, in most cases, the number of local rearrangements needed to reach uniform distribution is huge, and, even worse, unknown. Therefore, one then resorts to make many rearrangements and hope this is enough. This is where your question is crucial: how do we know we made enough rearrangements?

Well, people usually make as many as they can, and plot basic statistics of the obtained graphs, as a function of the number of rearrangements (there are several examples in the paper above). If the statistics converges to a steady value, then one assumes that the graph is random regarding this statistics. One may also use an estimate of the expected value of the statistics (when available), and check that the mixing reached a value close to this expected value... but this remains very empirical.

I fear this does not answer your question, but this shows that there is certainly no (known) way to have a formally grounded but practical randomness test for graphs, in general.

Maybe this is possible in some restricted classes?

I suggest you ask on MathOverflow.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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