Irreducible Markov Chains on spaces of graphs with fixed degree-color sequences
This provides a theoretical foundation for Markov chain Monte Carlo methods in colored network analysis, but the result is incremental as it generalizes known algebraic results from the 1990s.
The paper proves that the space of graphs with fixed degree and color sequences can be connected using simple color-preserving switches, enabling an irreducible Markov chain for testing block-partitioned network data. However, for simple graphs, the 1-norm of required moves increases with the number of colors.
We study a colored generalization of the famous simple-switch Markov chain for sampling the set of graphs with a fixed degree sequence. Here we consider the space of graphs with colored vertices, in which we fix the degree sequence and another statistic arising from the vertex coloring, and prove that the set can be connected with simple color-preserving switches or moves. These moves form a basis for defining an irreducible Markov chain necessary for testing statistical model fit to block-partitioned network data. Our methods further generalize well-known algebraic results from the 1990s: namely, that the corresponding moves can be used to construct a regular triangulation for a generalization of the second hypersimplex. On the other hand, in contrast to the monochromatic case, we show that for \emph{simple} graphs, the 1-norm of the moves necessary to connect the space increases with the number of colors.