Graphs of Derivatives in the Global Structures of Algebraic Bayesian Networks

Authors

  • 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 (unauthenticated)

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

Downloads

Published

2020-06-27

Issue

No. 2 (2020)

Section

Computer science

License

How to Cite

[1]
A. G. Maksimov, A. D. Zavalishin, M. V. Abramov, and A. L. Tulupyev, “Graphs of Derivatives in the Global Structures of Algebraic Bayesian Networks”, Компьютерные инструменты в образовании, no. 2, pp. 59–65, Jun. 2020, doi: 10.32603/2071-2340-2020-2-59-65.

Similar Articles

1-10 of 623

You may also start an advanced similarity search for this article.

Most read articles by the same author(s)