Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 2021, Volume 8, Issue 2, Pages 305–316
DOI: https://doi.org/10.21638/spbu01.2021.210
(Mi vspua117)
 

MATHEMATICS

Algebraic bayesian networks: checking backbone connectivity.

A. G. Maksimova, A. L. Tulupyevba

a St. Petersburg Federal Research Center of the Russian Academy of Sciences, 39, 14-ia liniia V.O., St. Petersburg, 199178, Russian Federation
b St. Petersburg State University, 7-9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation
Abstract: 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.
Keywords: algebraic Bayesian networks, joint graph, minimal joint graph, algorithms, complexity of algorithms.
Funding agency Grant number
Russian Academy of Sciences - Federal Agency for Scientific Organizations 0073-2019-0003
The work was performed on state assignment of St. Petersburg Federal Research Center of the Russian Academy of Sciences (project no. 0073-2019-0003).
Received: 20.07.2020
Revised: 03.09.2020
Accepted: 17.12.2020
English version:
Vestnik St. Petersburg University, Mathematics, 2021, Volume 8, Issue 3, Pages 187–195
DOI: https://doi.org/10.1134/S1063454121020059
Document Type: Article
UDC: 519.178+004.8
MSC: 05C85, 68T37
Language: Russian
Citation: A. G. Maksimov, A. L. Tulupyev, “Algebraic bayesian networks: checking backbone connectivity.”, Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 8:2 (2021), 305–316; Vestn. St. Petersbg. Univ., Math., 8:3 (2021), 187–195
Citation in format AMSBIB
\Bibitem{MakTul21}
\by A.~G.~Maksimov, A.~L.~Tulupyev
\paper Algebraic bayesian networks: checking backbone connectivity.
\jour Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy
\yr 2021
\vol 8
\issue 2
\pages 305--316
\mathnet{http://mi.mathnet.ru/vspua117}
\crossref{https://doi.org/10.21638/spbu01.2021.210}
\transl
\jour Vestn. St. Petersbg. Univ., Math.
\yr 2021
\vol 8
\issue 3
\pages 187--195
\crossref{https://doi.org/10.1134/S1063454121020059}
Linking options:
  • https://www.mathnet.ru/eng/vspua117
  • https://www.mathnet.ru/eng/vspua/v8/i2/p305
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy
    Statistics & downloads:
    Abstract page:41
    Full-text PDF :6
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024