Enumerating Markov Equivalence Classes of Acyclic Digraph Models

Understand

Graphical Markov models determined by acyclic digraphs (ADGs), also called directed acyclic graphs (DAGs), are widely studied in statistics, computer science (as Bayesian networks), operations research (as influence diagrams), and many related fields.

• Because different ADGs may determine the same Markov equivalence class, it long has been of interest to determine the efficiency gained in model specification and search by working directly with Markov equivalence classes of ADGs rather than with ADGs themselves.
• A computer program was written to enumerate the equivalence classes of ADG models as specified by Pearl & Verma's equivalence criterion.
• The program counted equivalence classes for models up to and including 10 vertices.