What are some useful invariants for distinguishing between random graph models?

Question

Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:

• The Erdős-Rényi model
• The Stochastic Block model
• The Watts-Strogatz model
• The Barabasi-Albert model

and many others. The general sort of question that I am trying to ask is: how do you do Bayesian statistics with random graphs? In other words: what can you infer about the underlying random graph model by looking at data? A natural strategy is to look at statistical properties of ordinary graph invariants, such as:

• The degree distribution
• The distribution of path lengths
• The clustering coefficient

These specific invariants are nice for statistics because they are relatively predictable for many graph models (e.g. it is known that degrees are asymptotically Poisson for Erdős-Rényi graphs and asymptotically power law for preferential attachment graphs) and they aren't too hard to compute from data.

What are some other "nice for statistics" graph invariants?

I'm curious about spectral invariants in particular, though this might be no easier than the well-known hard problem of estimating eigenvalues of random matrices.

For this question let's assume that the graphs are undirected, simple, and large but finite.

Answer 1

Any property for which there is an efficient property testing algorithm is a candidate, because such algorithms are extremely efficient.

Another approach is to note that many random graph models have an associated graphon, so (especially if you have a lot of samples of the graphs of interest) you could try to approximately compute the graphon. This is computationally intensive but has the advantage that it will probably expose a lot of important properties all at once. One relevant paper on this topic is Airoldi et al.

Answer 2

It really depends on your applications/goals, and the graphs you consider. Do you want to compare graph sequences or graphs of a fixed size?

First let's consider sequences.

The problem with property testing invariants is that they are trivial for any non-dense class of graphs (including the Watts-Strogatz and Barabasi-Albert models). In other words, $\mathcal{G}_i \rightarrow W_0$ for any graph sequences with $o(n^2)$ edges, where $W_0$ is the empty graphon.

The close equivalent of such properties for sparse-graphs is the distribution of neighborhoods, which gives the framework of local weak convergence. You can also look at the degree-degree correlations(Joint-Degree Distribution), or correlations for more vertices, but it becomes computationally expensive.

There are some invariants that work for any class of graph, such as the class of first-order definable properties, or connectivity, hamiltonicity, etc, but either they are a bit too simple (FO-properties) or they lack a proper way to be treated uniformly.

There are many other less known invariants, either in the social network community (Between-ness, Elite/Rich club or community analysis) or in the theoretical world (a good place to start is [1]). Here the keyword is "graph metrics".

If you are not interested in asymptotic analysis, you can pretty much use anything, including a mix of algorithms for sparse graphs and algorithms for dense graphs. With some applications in mind, you can also use the result/statistics of some algorithms as invariants (e.g. some routing algorithms). In that case rigorous mathematical may be out of the question, but it may be much more useful in practice [2][3].

[1] Bollobás, Riordan "Sparse graphs: metrics and random models."

[2] Sala, Cao, Wilson, Zablit, Zheng, "Measurement-calibrated graph models for social network experiments"

[3] Li, Alderson, Willinger, Doyle, "A first-principles approach to understanding the internet's router-level topology"