Asymptotical Behaviour of Directed Graphs
Ángel Luis Garrido · 2009
Among the dierent graphs, Bayesian Networks are the most sucessful class of models to represent uncertain knowledge. But the representation of conditional independencies (CIs, in acronym) does not have uniqueness. The reason is that probabilistically equivalent models may have dierent representations. And this problem is overcome by the introduction of the concept of Essential Graph, as unique representant of each equiva- lence class. They represent CI models by graphs. Such mathematical and graphical tools containing both, directed or/and undirected edges; hence, producing respectively either Directed Graphs (DGs), in particular acyclic elements, or Directed Acyclic Graphs (DAGs), either Undirected Graphs (UGs), or Chain Graphs (CGs), in the mixed case. So, DAG models are generally represented as Essential Graphs (EGs). Knowing the ratio of EGs to DAGs is a valuable tool, because through this information we may decide in which space to search. If the ratio is low, we may prefer to search the space of DAG models, rather than the space of DAGs directly, as it was usual until now. The most common approach to learning DAG models is that of performing a search into the space of either DAGS or DAG models (EGs). It is preferable, from a mathematical point of view, to obtain the more exact solution possible, studying its asymptotic behaviour. But also it is feasible to propose a Monte Carlo Chain Method (MCMC) to approach the ratio, avoiding the straightforward enumeration of EGs. And a many more elegant construct, if very di¢ cult, through the Ihara Zeta function for counting graphs. Here we will shown some new results about the Graphs and its equiv- alence classes. And also the study of the enumerative asymptotic behav- iour, according its dierent possible situations.