Open Access

ARTICLE

A Constrained Local Neighborhood Approach for Efficient Markov Blanket Discovery in Undirected Independent Graphs

Kun Liu^1,2, Peiran Li³, Yu Zhang^1,*, Jia Ren¹, Ming Li⁴, Xianyu Wang², Cong Li²

1 School of Information and Communication Engineering, Hainan University, Haikou, 570228, China
2 National Key Laboratory of Science and Technology on Space Microwave, China Academy of Space Technology Xi’an, Xi’an, 710100, China
3 Strategic Emerging Industries Department, CRSC Communication & Information Group Co., Ltd., Beijing, 100070, China
4 Military Representative Bureau of the Army Equipment Department in Xi’an, Xi’an, 710032, China

* Corresponding Author: Yu Zhang. Email:

(This article belongs to the Special Issue: Exploring the Metaverse: Advancements in Future Networks Communication and Computing Technologies for Enhanced Quality of Experience)

Computers, Materials & Continua 2024, 80(2), 2535-2555. https://doi.org/10.32604/cmc.2024.052166

Received 25 March 2024; Accepted 28 June 2024; Issue published 15 August 2024

Abstract

When learning the structure of a Bayesian network, the search space expands significantly as the network size and the number of nodes increase, leading to a noticeable decrease in algorithm efficiency. Traditional constraint-based methods typically rely on the results of conditional independence tests. However, excessive reliance on these test results can lead to a series of problems, including increased computational complexity and inaccurate results, especially when dealing with large-scale networks where performance bottlenecks are particularly evident. To overcome these challenges, we propose a Markov blanket discovery algorithm based on constrained local neighborhoods for constructing undirected independence graphs. This method uses the Markov blanket discovery algorithm to refine the constraints in the initial search space, sets an appropriate constraint radius, thereby reducing the initial computational cost of the algorithm and effectively narrowing the initial solution range. Specifically, the method first determines the local neighborhood space to limit the search range, thereby reducing the number of possible graph structures that need to be considered. This process not only improves the accuracy of the search space constraints but also significantly reduces the number of conditional independence tests. By performing conditional independence tests within the local neighborhood of each node, the method avoids comprehensive tests across the entire network, greatly reducing computational complexity. At the same time, the setting of the constraint radius further improves computational efficiency while ensuring accuracy. Compared to other algorithms, this method can quickly and efficiently construct undirected independence graphs while maintaining high accuracy. Experimental simulation results show that, this method has significant advantages in obtaining the structure of undirected independence graphs, not only maintaining an accuracy of over 96% but also reducing the number of conditional independence tests by at least 50%. This significant performance improvement is due to the effective constraint on the search space and the fine control of computational costs.

---

Keywords

---