Graphs with probabilistic properties
The most common random graph model is the Erdős–Rényi model. Random connections among a given set of nodes.
Random graphs are locally tree-like
http://tuvalu.santafe.edu/~aaronc/courses/5352/fall2013/csci5352_2013_L11.pdf
Random graph with given degree distribution
See this chapter
.... See Newman's book on Networks
Random Graphs, Geometry and Asymptotic Structure
https://www.youtube.com/watch?v=pylTEAyUQiM
THE PHASE TRANSITION IN INHOMOGENEOUS RANDOM GRAPHS
Random Graphs and Complex Networks. Vol. II
aka stochastic block model
Erdos-Renyi mixture model ( stochastic block models , see Nowicky and Snijders (2001) ). Nodes are of, say, L different types. Edges are constructed independently, such that the probability for an edge depends only on the type of the nodes at the endpoints of the edge. This model does not produce a power-law degree distribution. Robin et al. (2008) use it to model a metabolic network of E.coli ; nodes are chemical reactions, and two reactions are connected if a compount produced by the first one is a part of the second one (or vice versa). Their network has 605 nodes and 1782 edges. The best-fitting model is a model with L = 21 classes, and many of these classes gather reactions involving a same compound
See this video