Adjacency Tree Families and Complementarity Criteria

  • Anatoliy G. Maksimov Saint Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14 Line, 199178, Saint Petersburg, Russia
  • Arsenii D. Zavalishin Saint Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14 Line, 199178, Saint Petersburg, Russia
  • Maxim V. Abramov Saint Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14 Line, 199178, Saint Petersburg, Russia
  • Alexander L. Tulupyev Saint Petersburg State University, Universitetskaya nab., 7-9, 199034, Saint Petersburg, Russia
DOI: https://doi.org/10.32603/2071-2340-2020-1-28-37
Keywords: derivative graph, antiderivative graph, adjacency graph, backbone graph property, Bayesian algebraic networks.

Abstract

The article discusses the properties of families of minimal joint graphs. The concept of non-extenuating paths of graphs is introduced. The criterion of additionality for families of backbone connected graph trees is formulated and proved. Theoretical and practical significance lies in the study of structures that will be best suited for working with algebraic Bayesian networks and, thus, become one of the goal of their machine learning. We note the novelty of looking at the problem, or rather, studying the question for which families of graphs there is a set of loads, the family of MGS over which exactly coincides with the given one.

Author Biographies

Anatoliy G. Maksimov, Saint Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14 Line, 199178, Saint Petersburg, Russia

Junior researcher, Laboratory of Theoretical and Interdisciplinary Problems of Informatics, SPIIRAS; student, Computer Science Department, SPbU, agm@dscs.pro

Arsenii D. Zavalishin, Saint Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14 Line, 199178, Saint Petersburg, Russia

Junior researcher, Laboratory of Theoretical and Interdisciplinary Problems of Informatics, SPIIRAS; student, Computer Science Department, SPbU, adz@dscs.pro

Maxim V. Abramov, Saint Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14 Line, 199178, Saint Petersburg, Russia

PhD, senior researcher, Laboratory of Theoretical and Interdisciplinary Problems of Informatics, SPIIRAS; Associate Professor, Computer Science Department, SPbU, mva@dscs.pro

Alexander L. Tulupyev, Saint Petersburg State University, Universitetskaya nab., 7-9, 199034, Saint Petersburg, Russia

PhD, Dc. Sci., professor, Computer Science Department, SPbU; Principal Researcher, Laboratory of Theoretical and Interdisciplinary Problems of Informatics, SPIIRAS, alt@dscs.pro

References

V. V. Oparin, A. A. Fil’chenkov, A. V. Sirotkin, and A. L. Tulupyev, “Matroidnoe predstavlenie semeistva grafov smezhnosti nad naborom fragmentov znanii” [Matroid representation of a family of adjacency graphs over a set of pieces of knowledge], Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki, no. 4 (68), pp. 73–76, 2010 (in Russian).

A. L. Tulupyev, S. I. Nikolenko, A. V. Sirotkin, Osnovy teorii baiesovskikh setei [Fundamentals of Bayesian Network Theory], St Petersburg, Russia: Publishing house of St. Petersburg State University, 2019 (in Russian).

A. L. Tulupyev, D. M. Stolyarov, and M. V. Mentyukov, “Predstavlenie lokal’noi i global’noi struktury algebraicheskoi baiesovskoi seti v Java-prilozheniyakh” [Representation of local and global algebraic structure Bayesian network in Java-applications], in Trudy SPIIRAN, vol. 5, pp. 71–99, 2007 (in Russian).

D. G. Levenets, M. A. Zotov, A. V. Romanov, A. L. Tulupyev, A. A. Zolotin, and A. A. Filchenkov, ”Decremental and incremental reshaping of algebraic Bayesian networks global structures“ in Proc. of the 1st International Scientific Conference Intelligent Information Technologies for Industry”(IITI’16), Advances in Intelligent Systems and Computing, vol. 451, pp. 57–67, 2016; doi: 10.1007/978-3-319-33816-3_6

V. I. Gorodetskii and A. L. Tulupyev, “Generating consistent knowledge bases with uncertainty,” Journal of Computer and Systems Sciences International, vol. 36, no 5, pp. 683–691, 1997.

A. V. Romanov, D. G. Levenets, A. A. Zolotin, and A. L. Tulupyev, ”Incremental synthesis of the tertiary structure of algebraic Bayesian networks,“ in Proc. 2016 XIX IEEE International Conference on Soft Computing and Measurements (SCM), IEEE, 2016, pp. 28–30; doi: 10.1109/SCM.2016.7519673

E. A. Mal’chevskaya, A. I. Berezin, A. A. Zolotin, and A. L. Tulupyev, ”Algebraic Bayesian Networks: Local Probabilistic-Logic Inference Machine Architecture and Set of Minimal Joint Graphs,“ in Proc. of the First International Scientific Conference “Intelligent Information Technologies for Industry” (IITI’16), Advances in Intelligent Systems and Computing, vol. 451, pp. 69–79, 2016; doi: 10.1007/978-3-319-33816-3_7

”Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks“, Vestnik St. Petersburg University: Mathematics, vol. 45, no. 2, pp. 106–113, 2012; doi: 10.3103/S1063454112020057

A. L. Tulupyev, Algebraicheskie baiesovskie seti: global’nyi logiko-veroyatnostnyi vyvod v derev’yakh smezhnosti [Algebraic Bayesian networks: global logical-probabilistic inference in adjacency trees], Moscow: Anatoliya, 2007 (in Russian).

Published
2020-03-28
How to Cite
Maksimov, A. G., Zavalishin, A. D., Abramov, M. V., & Tulupyev, A. L. (2020). Adjacency Tree Families and Complementarity Criteria. Computer Tools in Education, (1), 28-37. https://doi.org/10.32603/2071-2340-2020-1-28-37
Issue
No 1 (2020)
Section
Algorithmic mathematics and mathematical modelling

Most read articles by the same author(s)