An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles

Abstract

Markov Chain Monte Carlo (MCMC) algorithms are commonly used to sample from graph ensembles. Two graphs are neighbors in the state space if one can be obtained from the other with only a few modifications, e.g., edge rewirings. For many common ensembles, e.g., those preserving the degree sequences of bipartite graphs, rewiring operations involving two edges are sufficient to create a fully-connected state space, and they can be performed efficiently. We show that, for ensembles of bipartite graphs with fixed degree sequences and number of butterflies (k2,2 bi-cliques), there is no universal constant c such that a rewiring of at most c edges at every step is sufficient for any such ensemble to be fully connected. Our proof relies on an explicit construction of a family of pairs of graphs with the same degree sequences and number of butterflies, with each pair indexed by a natural c, and such that any sequence of rewiring operations transforming one graph into the other must include at least one rewiring operation involving at least c edges. Whether rewiring these many edges is sufficient to guarantee the full connectivity of the state space of any such ensemble remains an open question. Our result implies the impossibility of developing efficient, graph-agnostic, MCMC algorithms for these ensembles, as the necessity to rewire an impractically large number of edges may hinder taking a step on the state space.

arXiv commentAccepted for publication in Physical Review E

References in corpus (16)

• The structure and function of complex networks
• Random graphs with clustering
• The Statistical Physics of Real-World Networks
• The Babe Ruth Algorithm: a fast, unbiased procedure to randomize presence-absence data matrices with fixed row and column totals
• Analytical maximum-likelihood method to detect patterns in real networks
• Quantifying randomness in real networks
• Randomizing bipartite networks: the case of the World Trade Web
• Systematic Topology Analysis and Generation Using Degree Correlations
• Unbiased sampling of network ensembles
• Constructing and sampling directed graphs with given degree sequences
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• Exact sampling and counting for fixed-margin matrices
• Exact sampling of graphs with prescribed degree correlations
• On Realizations of a Joint Degree Matrix
• A Fast MCMC for the Uniform Sampling of Binary Matrices with Fixed Margins
• Alice and the Caterpillar: A more descriptive null model for assessing data mining results