Graphs of Derivatives in the Global Structures of Algebraic Bayesian Networks

  • 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 Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия
  • Alexander L. Tulupyev Saint Petersburg State University, Universitetskaya nab., 7-9, 199034, Saint Petersburg, Russia https://orcid.org/0000-0003-1814-4646
DOI: https://doi.org/10.32603/2071-2340-2020-2-59-65
Keywords: joint graphs, graph theory, invariants on graphs, algebraic Bayesian networks.

Abstract

The article is aimed at summarizing the concepts of a derivative graph and a primitive graph for graphs with backbone connectivity. Theorems are formulated and proved on the main connectedness of the graph of the derivative and on the primitive graph of the main connected graphs. The theoretical and practical significance of the result is to simplify the search for successful visualization of algebraic Bayesian networks, which would help to identify the features of their structure, as well as the definition of new types of global structures of these networks. Such structures would allow us to store the same information, but use other output algorithms, which would simplify the software implementation of this model. Note that maintaining the property of trunk connectivity when finding the graph of the derivative is considered in this article for the first time.

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, Санкт-Петербургский институт информатики и автоматизации Российской академии наук, 14 линия, 39, 199178, Санкт-Петербург, Россия

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

H. Whitney, “Congruent graphs and the connectivity of graphs,” Hassler Whitney Collected Papers. Contemporary Mathematicians, pp. 61–79, 1992; doi: 10.1007/978-1-4612-2972-8_4

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, and 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

A. A. Filchenkov and A. L. Tulupyev, “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

F. Harary, Graph Theory, Moscow: Librocom, 2009 (in Russian).

G. Sabidussi, “Graphs with given group and given graph-theoretical properties,” Canadian journal of mathematics, vol. 9, pp. 515-525, 1957; doi: 10.4153/CJM-1957-060-7

Published
2020-06-27
How to Cite
Maksimov, A. G., Zavalishin, A. D., Abramov, M. V., & Tulupyev, A. L. (2020). Graphs of Derivatives in the Global Structures of Algebraic Bayesian Networks. Computer Tools in Education, (2), 59-65. https://doi.org/10.32603/2071-2340-2020-2-59-65
Issue
No 2 (2020)
Section
Computer science

Most read articles by the same author(s)