Grouping Parallel Bayesian Network Structure Learning Algorithm Based on Variable Ordering

Given an ordering constraint of n random variables and the maximum in- degree u for any variable, the search space of Bayesian network structure reduces from n!2(n(n-1)/2) to the 2(n(n-1)/2). Even so, with the increase of the number of variables, the requirement of time cannot be tolerated. In this paper, we present a parallel Bayesian network structure learning algorithm based on variable ordering. The algorithm includes three components: 1. variable grouping: it completes variable partition; 2. group learning: it completes independently construct of sub-Bayesian network; 3. Between the groups learning: it asynchronously combines sub-Bayesian network in order to get the full Bayesian networks. We theoretically analyzed that time complexity of our algorithm is O(mu(2)nr), where u that is number of parent, In the worst case, u = n, complexity of the algorithm is O(mn(3)r). The empirical results present in term of time complexity grouping parallel algorithm has significance compared with the traditional algorithm.