TY - JOUR

T1 - Algebraic Bayesian Networks

T2 - Checking Backbone Connectivity

AU - Максимов, Анатолий Григорьевич

AU - Тулупьев, Александр Львович

PY - 2021/4

Y1 - 2021/4

N2 - The paper investigates one of the problems arising in machine learning of bases of knowledge fragments with uncertainty, presented in the form of algebraic Bayesian networks, the construction of an adjacency graph as a global network structure based on its primary structure. The aim of the research is to propose methods for solving the inverse problem. As the results, algorithms for checking a graph for belonging to a family of joint graphs and a family of minimal joint graphs are proposed, and estimates of their computational complexity are made. An improved version for the special case and an improvement for the general case on average are also proposed for the algorithm for checking membership in a family of joint graphs. The problem of recognition of joint graphs has not been previously researched; this issue is being addressed for the first time as currently drafted. The theoretical significance lies in the possibilities for applying the results in further research of graph-theoretic invariants in the global structures of algebraic Bayesian networks.

AB - The paper investigates one of the problems arising in machine learning of bases of knowledge fragments with uncertainty, presented in the form of algebraic Bayesian networks, the construction of an adjacency graph as a global network structure based on its primary structure. The aim of the research is to propose methods for solving the inverse problem. As the results, algorithms for checking a graph for belonging to a family of joint graphs and a family of minimal joint graphs are proposed, and estimates of their computational complexity are made. An improved version for the special case and an improvement for the general case on average are also proposed for the algorithm for checking membership in a family of joint graphs. The problem of recognition of joint graphs has not been previously researched; this issue is being addressed for the first time as currently drafted. The theoretical significance lies in the possibilities for applying the results in further research of graph-theoretic invariants in the global structures of algebraic Bayesian networks.

KW - algebraic Bayesian networks

KW - joint graph

KW - minimal joint graph

KW - algorithms

KW - complexity of algorithms

KW - ALGORITHM

U2 - 10.1134/S1063454121020059

DO - 10.1134/S1063454121020059

M3 - статья

VL - 54

SP - 187

EP - 195

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 2

ER -