Enumerating Markov Equivalence Classes of Acyclic Digraph Models
  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. The ratio of
number of classes to ADGs appears to approach an asymptote of about 0.267.
Classes were analyzed according to number of edges and class size. By edges,
the distribution of number of classes approaches a Gaussian shape. By class
size, classes of size 1 are most common, with the proportions for larger sizes
initially decreasing but then following a more irregular pattern. The maximum
number of classes generated by any undirected graph was found to increase
approximately factorially. The program also includes a new variation of orderly
algorithm for generating undirected graphs.
