Fixed degree sequence graphs: “The configuration model”

Often, the ER graph does not serve well as a “null model”; it’s degree distribution is insufficiently interesting. If we want to “resample” our graph from a “null model”, then we could compute our degree sequence and sample uniformly from all graphs with this degree sequence.

1. How to do this. Show algorithm on board.
   
2. Are there some degree sequences for which there is no graph? More generally, how many graphs are there for any given degree sequence? I don’t know the answer to this second question. If someone could find the answer, that would be super interesting! Start with a google search. What if there were only 3 graphs with a given degree sequence?
   
3. Do you expect these graphs to be connected? Giant component? Should we expect to see triangles? (Exercise: compute the expected global clustering coefficient.)
4. The previous construction can produce self loops and multi-graphs.
   
5. “Deriving rigorous proofs for random graphs with exact degree sequences is rather com- plicated and usually requires additional ‘smoothing’ conditions because of the dependency among the edges” -Chung and Lu. So, “relax” to expected degrees. Click through to paper.

See “The structure and function of complex networks” by MEJ Newman, 2003 SIAM Review for more details.