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

DOI10.2140/ASTAT.2021.12.115MaRDI QIDQ2076286zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(2)

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

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)