Uniform random generation of large acyclic digraphs
From MaRDI portal
Abstract: Directed acyclic graphs are the basic representation of the structure underlying Bayesian networks, which represent multivariate probability distributions. In many practical applications, such as the reverse engineering of gene regulatory networks, not only the estimation of model parameters but the reconstruction of the structure itself is of great interest. As well as for the assessment of different structure learning algorithms in simulation studies, a uniform sample from the space of directed acyclic graphs is required to evaluate the prevalence of certain structural features. Here we analyse how to sample acyclic digraphs uniformly at random through recursive enumeration, an approach previously thought too computationally involved. Based on complexity considerations, we discuss in particular how the enumeration directly provides an exact method, which avoids the convergence issues of the alternative Markov chain methods and is actually computationally much faster. The limiting behaviour of the distribution of acyclic digraphs then allows us to sample arbitrarily large graphs. Building on the ideas of recursive enumeration based sampling we also introduce a novel hybrid Markov chain with much faster convergence than current alternatives while still being easy to adapt to various restrictions. Finally we discuss how to include such restrictions in the combinatorial enumeration and the new hybrid Markov chain method for efficient uniform sampling of the corresponding graphs.
Recommendations
Cites work
- A characterization of Markov equivalence classes for acyclic digraphs
- Acyclic orientations of graphs
- Asymptotic behaviour of the number of labelled essential acyclic digraphs and labelled chain graphs
- Bayesian Graphical Models for Discrete Data
- Bayesian model averaging and model selection for markov equivalence classes of acyclic digraphs
- Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks
- Enumeration of labelled chain graphs and labelled essential directed acyclic graphs.
- Enumeration of labelled essential graphs.
- Estimating high-dimensional directed acyclic graphs with the PC-algorithm
- Finding a Minimum Circuit in a Graph
- Generating connected acyclic digraphs uniformly at random
- scientific article; zbMATH DE number 2186891 (Why is no real title available?)
- scientific article; zbMATH DE number 3585466 (Why is no real title available?)
- scientific article; zbMATH DE number 1134987 (Why is no real title available?)
- scientific article; zbMATH DE number 2014740 (Why is no real title available?)
- scientific article; zbMATH DE number 3348134 (Why is no real title available?)
- scientific article; zbMATH DE number 3409391 (Why is no real title available?)
- Improving the structure MCMC sampler for Bayesian networks by introducing a new edge reversal move
- Learning high-dimensional directed acyclic graphs with latent and selection variables
- On the Number of Maximal Vertices of a Random Acyclic Digraph
- Random Generation of Directed Acyclic Graphs
- The asymptotic number of acyclic digraphs. I
- The asymptotic number of acyclic digraphs. II
- The On-Line Encyclopedia of Integer Sequences
- The size distribution for Markov equivalence classes of acyclic digraph models.
Cited in
(7)- Generating connected acyclic digraphs uniformly at random
- Acyclic digraphs
- Random Generation of Directed Acyclic Graphs
- scientific article; zbMATH DE number 2044702 (Why is no real title available?)
- Efficient Sampling and Structure Learning of Bayesian Networks
- Random generation of essential directed acyclic graphs
- Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
This page was built for publication: Uniform random generation of large acyclic digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962736)
