BN State Space

Since a Bayesian network is a directed acyclical graph, it can be represented as a series of ordered nodes connected by directed arcs. The nodes are ordered in a hierarchy where a node cannot be the parent of another node higher in the hierarchy. In other words, the nodes are topologically ordered.

n*(n-1)/2

sum{i=n-1}{n*(n-1)/2}{(matrix{2}{1}{n*(n-1)/2 i})}

BNStateSpace.py
import math
 
def C(n, r):
    '''C(n, r)->Integer representing the combination of n things taken r at a
    time.
    n:  Number of things in "bag"
    r:  Number of things taken from the "bag"'''
    return math.factorial(n)/(math.factorial(n - r)*math.factorial(r));
 
def bnStateSpace(n):
    '''bnStateSpace(n)->Integer representing a rough approximation of the number
    of possible BN configurations
    n: The number of nodes in the Bayesian network'''
    sumSS = 0;
 
    # A BN with n nodes can have n-1 to n*(n - 1)/2 arcs
    # Thus, a BN with 5 nodes can have 4 to 10 arcs
    for i in range(n - 1,  n*(n - 1)/2 + 1):
        # Combinations of max arcs taken i at a time
        # representing the number of legal BN configurations with i arcs
        sumSS += C(n*(n - 1)/2, i);
 
    return sumSS
 
# Print out BN state space for BNs with 1 to 10 nodes
for i in range(1, 11):
    print '%i: %12.0f' % (i, bnStateSpace(i));
 
# Calculate BN state space from user input
print 'BN state space:  %12.0f' % (bnStateSpace(input("Number of nodes in BN:  ")));
 
# Pause before ending execution
raw_input();

goplayer/bnstatespace.txt · Last modified: 2011/02/17 22:15 by aiartificer