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 \( {\text{n}}!2^{{\frac{{n\left( {n - 1} \right)}}{2}}} \) to the \( 2^{{\frac{{n\left( {n - 1} \right)}}{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 \( \text{O}\left( {mu^{2} nr} \right) \), where u that is number of parent, In the worst case, u = n, complexity of the algorithm is \( \text{O}\left( {mn^{3} r} \right) \). The empirical results present in term of time complexity grouping parallel algorithm has significance compared with the traditional algorithm.