## Randomised Networks

In order to see how the algorithm depends on the structure inherent in
the network, we constructed a number of parametrized classes of
networks. We explicitly constructed networks that display contextual
independence, as if there is not contextual independence this
algorithm degenerates to VE.
We have the following parameters for building random networks:

*n*- the number of variables
*s*- the number of splits (so there will be
*n+s*
confactors).
*p*- the probability that a predecessor variable that isn't in
the context of a confactor will be in the
table of the confactor.

The exact algorithm for constructing the examples is given in
Appendix *.
The variable *s* controls the number of confactors, and *p* controls
(probabilistically) the size of the tables. Figure
*^{10}
shows a scatter plot comparing the runtimes of CVE and VE for *n=30*
and *p=0.2* and for three different values of *s*, *5*, *10*, and
*15*.

Scatterplot of runtimes (in seconds) of CVE (x-axis) and VE
(y-axis) for randomised networks

While this may look reasonable, it should be noticed that the number
of splits and the number of different variables in the splits is
strongly correlated in these examples (see Appendix *
for details). However, one of the properties of
CVE is that if a variable does not appear in the body of any
confactor, it is never added to the context of a constructed
confactor. That is, a variable that only appears in tables,
always stays in tables. Thus it may be conjectured that having fewer
variables appearing in contexts may be good for efficiency.

We carried out another experiment to test this hypothesis. In this
experiment, the
networks were generated as before, however, when we went to split a
context we attempted to first split it using a variable that appears in a
different context before using a variable that didn't appear in a
context. The full details of the algorithms to generate examples and
some example data are given in Appendix *. Figure
* shows a scatter plot of comparing the run times for
CVE and VE for each of the generated examples. With this class of networks CVE is significantly
faster than VE.

Scatterplot of runtimes (in seconds) of CVE (x-axis) and VE
(y-axis) for random networks biased towards fewer different variables
in the contexts.

David Poole
and Nevin Lianwen
Zhang,Exploiting Contextual
Independence In Probabilistic Inference, Journal of
Artificial Intelligence Research, 18, 2003, 263-313.