Degree-based graph construction and sampling

 

HYUNJU KIM

UNIVERSITY OF NOTRE DAME

 

Degree-based graph construction is an ubiquitous problem in network modeling, ranging from social sciences through chemical compounds to biochemical reaction networks in the cell. While there are a number of heuristic methods to graph construction, here I present rigorous results [1] that allows exact and independent sampling [2] from the set of all labeled graphs realizing a given degree sequence. We show that, while the samples are constructed non-uniformly, their exact weight can be determined, which in turn can be used to produce averages of network observables, as if they were measured on uniformly sampled realizations. [1] H. Kim, Z. Toroczkai, P.L. Erdos, I. Miklos and L.A. Szekely. Degree-based graph construction. J. Phys. A: Math. Theor. 42, 392001 (2009). [2] C.I. Del Genio, H. Kim, Z. Toroczkai, K.E. Bassler. Efficient and exact sampling of simple graphs with given arbitrary degree sequence. http://arxiv.org/abs/1002.2975