Open AccessAlgebraic Bayesian networks: Checking backbone connectivity
Author(s) -
Anatolii G. Maksimov,
Alexander L. Tulupyev
Publication year - 2021
Publication title -
vestnik sankt-peterburgskogo universiteta. matematika. mehanika. astronomiâ/vestnik sankt-peterburgskogo universiteta. seriâ 1, matematika, mehanika, astronomiâ
Language(s) - English
Resource type - Journals
eISSN - 2587-5884
pISSN - 1025-3106
DOI - 10.21638/spbu01.2021.210
Subject(s) - bayesian network , computer science , algebraic number , theoretical computer science , algebraic graph theory , graph , algebraic structure , algebraic connectivity , artificial intelligence , algorithm , mathematics , line graph , mathematical analysis , pure mathematics
The paper investigates the construction of a joint graph as a global structure of network based on its primary structure, one of the problems arising in machine learning of bases of knowledge patterns with uncertainty, presented in the form of algebraic Bayesian networks. 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; issue is being addressed for the first time as currently drafted. The theoretical significance lies in the possibilities for applying the results in further researches of graph-theoretic invariants in the global structures of algebraic Bayesian networks.