Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:
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.