Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, January 30, 2018 - 3:00pm

David Burstein



University of Pennsylvania


Constructing graphs that resemble their empirically observed counterparts is integral for simulating dynamical processes that occur on networks. Since many real-world networks exhibit degree heterogeneity, we consider some challenges in randomly constructing graphs with a given bi-degree sequence in an unbiased way. In particular, we propose a novel method for the asymptotic enumeration of directed graphs that realize a bi-degree sequence, d, with maximum degree d_max = O(S^{1/2 - tau}) for an arbitrarily small positive number tau, where S is the number of edges; the previous best results allow for d_max = o(S^{1/3} ). Our approach is based on two key steps, graph partitioning and degree preserving switches. The former allows us to relate enumeration results to sequences that are easy to handle, while the latter facilitates expansions based on numbers of shared neighbors of pairs of nodes. We will then discuss the implications of our work in context to other methods, such as Markov Chain Monte Carlo, for generating graphs with a prescribed degree sequence. Joint work with Jonathan Rubin.