An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem

DOI10.2140/ASTAT.2021.12.115zbMATH Open1479.05350arXiv1708.08242OpenAlexW2795495320MaRDI QIDQ2076286FDOQ2076286

Authors: Éva Czabarka, Z. Toroczkai, Shanise Walker, László A. Székely 

Publication date: 16 February 2022

Published in: Algebraic Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1708.08242

Recommendations

• Sampling \(k\)-partite graphs with a given degree sequence
• An efficient algorithm to test potential bipartiteness of graphical degree sequences
• Connected realizations of joint-degree matrices
• Efficient generation of graphical partitions
• Fast sequential creation of random realizations of degree sequences

zbMATH Keywords

computational complexitybipartite graphdegree sequenceperfect matchingHall's theoremMonte-Carlo algorithmjoint degree matrixexact matchingpartition adjacency matrix

Mathematics Subject Classification ID

Randomized algorithms (68W20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Transversal (matching) theory (05D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Matching theory
• Maximum likelihood estimation in the \(\beta\)-model
• The Factorization of Linear Graphs
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• The average distances in random graphs with given expected degrees
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• A remark on the existence of finite graphs
• Matching is as easy as matrix inversion
• A Short Proof of the Factor Theorem for Finite Graphs
• The complexity of restricted spanning tree problems
• Exact sampling of graphs with prescribed degree correlations
• Degree-based graph construction
• Relations between graphs and integer-pair sequences
• On realizations of a joint degree matrix
• Constructing and sampling graphs with a prescribed joint degree distribution
• On the computation of pfaffians
• An NP-complete matching problem
• A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
• Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices

Cited In (2)

• Graph realizations constrained by skeleton graphs
• Proportionally Fair Matching with Multiple Groups

This page was built for publication: An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2076286)