Finding community structure in Bayesian networks by heuristic K-standard deviation method

When constructing a Bayesian network for high-dimensional data, due to the complex relationships among distinct nodes, the difficulty in detecting the community structure will directly restrict the feasibility of the divide-and-conquer learning algorithm. This study attempts to solve this problem from the shortest path perspective and proposes the heuristic K-standard deviation algorithm. Firstly, we design a novel heuristic function and drive the A* algorithm to find the shortest paths between nodes in the Bayesian network. In addition, the new heuristic function is theoretically proved to be admissible and consistent. Experiments on different synthetic datasets and benchmark Bayesian networks verify that the proposed heuristic K-standard deviation algorithm generally gets better clustering performance than other representative algorithms and improves the efficiency and accuracy of the conventional Bayesian network structure learning algorithms, especially for high-dimensional data.