An algebraic Monte-Carlo algorithm for the Partition Adjacency Matrix realization problem

Abstract

The graphical realization of a given degree sequence and given partition adjacency matrix simultaneously is a relevant problem in data driven modeling of networks. Here we formulate common generalizations of this problem and the Exact Matching Problem, and solve them with an algebraic Monte-Carlo algorithm that runs in polynomial time if the number of partition classes is bounded.

References in corpus (4)

• Quantifying randomness in real networks
• Exact sampling of graphs with prescribed degree correlations
• Graphic Realizations of Joint-Degree Matrices
• Statistical Models for Degree Distributions of Networks