Connectivity

The “connectivity” of a net refers to a net’s link structure.  High connectivity means that there are a lot of links.

You can use the link structure of a net to determine independence between nodes, by using the d-separation algorithm.

A Multiply-Connected net is a net which has more than one undirected path between some pairs of nodes.  In other words, it has loops.

A Singly-Connected net is a net that has at most one path between any two nodes.  In other words, it has no loops.  If the link directions are ignored, it is always possible to consider it as a tree.  If the link directions are not ignored, then some people call it a “polytree” (because it can be considered to be several directed trees, with arrows from root to leaves, fused together at leaf nodes).

The time it takes for Netica to do belief updating is very dependent on the connectivity of the net.  Adding a link always results in longer updating times, but where that link is added can make a big difference.  If a node has many parents, then its conditional probability table will be very large, which results in slower overall updating times.  The number of loops a net has is also very significant.  If a net has no loops, then Netica can do updating extremely fast, and each added loop will increase the updating time.

Netica implements a number of graph algorithms to make various connectivity results available to you, such as finding all parents, children, ancestors, descendents, connected, d-separated, Markov boundary, interconnecting links, cycles, etc.  More Info