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.
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.