Algebraic Bayesian networks: Checking backbone connectivity.
DOI:
https://doi.org/10.21638/spbu01.2021.210Abstract
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
Downloads
Download data is not yet available.
References
Литература
1. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. Труды СПИИРАН, (5), 71–99 (2007).
2. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности. Труды СПИИРАН, (11), 142–157 (2009).
3. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логиковероятностный вывод в ациклических направленных графах. Санкт-Петербург, Изд-во С.-Петерб. ун-та (2009).
4. Фильченков А.А. Субоптимальная звездчатая структура алгебраической байесовской сети. Информационно-управляющие системы, (2), 13–17 (2013).
5. Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матроидное представление семейства графов смежности над набором фрагментов знаний. Научно-технический вестник информационных технологий, механики и оптики, (4), 73–76 (2010).
6. Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier (2014).
7. Rue H., Held L. Gaussian Markov random fields: theory and applications. CRC Press (2005).
8. Kharitonov N.A., Maximov A.G., Tulupyev A.L. Algebraic Bayesian Networks: Na¨ıve Frequentist Approach to Local Machine Learning Based on Imperfect Information from Social Media and Expert Estimates. Russian Conference on Artificial Intelligence. Springer, Cham, 234–244 (2019).
9. Madsen A. L., Jensen F., Salmer´on A., Langseth H., Nielsen T.D. A parallel algorithm for Bayesian network structure learning from large data sets. Knowledge-Based Systems 117, 46–55 (2017).
10. Baltruˇsaitis T., Ahuja C., Morency L.P. Multimodal machine learning: A survey and taxonomy. IEEE transactions on pattern analysis and machine intelligence 41 (2), 423–443 (2018).
11. Sawada K., Hashimoto K., Nankaku Y., Tokuda K. A Bayesian framework for image recognition based on hidden Markov eigen-image models. IEEJ Transactions on Electrical and Electronic Engineering 13 (9), 1335–1347 (2018).
12. Cai B., Kong X., Liu Y., Lin J., Yuan X., Xu H., Ji R. Application of Bayesian networks in reliability evaluation. IEEE Transactions on Industrial Informatics 15 (4), 2146–2157 (2018).
13. Ghahramani Z. Probabilistic machine learning and artificial intelligence. Nature 521 (7553), 452–459 (2015).
14. Smirnov S. Towards conformal invariance of 2D lattice models. Proceedings of the International Congress of Mathematicians (ICM), Madrid, Spain, August 22–30, 2006. Vol. II, 1421–1451. Z¨urich, European Mathematical Society (2006).
15. Schmidt J.M. The Mondschein sequence. In: Lecture Notes in Computer Science, 967–978 (2014).
16. Cormen T.H., Leiserson C.E., Rivest R. L., Stein C. Introduction to algorithms. MIT Press (2009).
17. Tarjan R.E. Efficiency of a good but not linear set union algorithm. Journal of the ACM (JACM) 22 (2), 215–225 (1975).
18. Tarjan R.E., Van Leeuwen J. Worst-case analysis of set union algorithms. Journal of the ACM (JACM) 31 (2), 245–281 (1984).
19. Fredman M., Saks M. The cell probe complexity of dynamic data structures. Proceedings of the twenty-first annual ACM symposium on Theory of computing, 345–354 (1989).
20. Lancia G., Vidoni P. Finding the largest triangle in a graph in expected quadratic time. European Journal of Operational Research 286 (2), 458–467 (2020).
21. Spielman D.A., Shang-Hua T. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) 51 (3), 385–463 (2004).
22. Bollob´as B. Modern graph theory. Vol. 184. Springer Science & Business Media (2013).
23. Schmidt J.M. A simple test on 2-vertex-and 2-edge-connectivity. Information Processing Letters 113 (7), 241–244 (2013).
24. Szegedy B., Szegedy C. Symplectic spaces and ear-decomposition of matroids. Combinatorica 26 (3), 353–377 (2006).
25. Whitney H. Non-separable and planar graphs. In: Classic Papers in Combinatorics. Modern Birkh¨auser Classics. Boston, Birkh¨auser, 25–48 (2009). https://doi.org/10.1007/978-0-8176-4842-8_2
26. Shang X., Chao T., Ma P., Yang M. An efficient local search-based genetic algorithm for constructing optimal Latin hypercube design. Engineering Optimization 52 (2), 271–287 (2020).
27. Ghoshal S., Sundar S. Two heuristics for the rainbow spanning forest problem. European Journal of Operational Research 285 (3), 853–864 (2020).
28. Корепанова А.А., Абрамов М.В., Тулупьева Т.В. Идентификация аккаунтов пользователей в социальных сетях "Вконтакте" и "Одноклассники". Семнадцатая Национальная конференция по искусственному интеллекту с международным участием (КИИ-2019). Ульяновск, 21–25 октября 2019, Ульяновск, УлГТУ. Т. 2, 153–163 (2019).
29. Shindarev N., Bagretsov G., Abramov M., Tulupyeva T., Suvorova A. Approach to identifying of employees’ profiles in websites of social networks aimed to analyze social engineering vulnerabilities. Advances in Intelligent Systems and Computing 679, 441–447 (2018). https://doi.org/10.1007/978-3-319-68321-8_45
30. Khlobystova A.O., Abramov M.V., Tulupyev A.L. An approach to estimating of criticality of social engineering attacks traces. In: Studies in Systems, Decision and Control 199, 446–456 (2019).
References
1. Tulupyev A. L., Stolyarov D.M., Mentyukov M.V. Representation of the local and global structure of a Bayesian algebraic network in Java applications. SPIIRAS Proceedings, (5), 71–99 (2007). (In Russian)
2. Oparin V.V., Tulupyev A.L. Synthesis of a joint graph with a minimum number of edges: formalization of the algorithm and analysis of its correctness. SPIIRAS Proceedings, (11), 142–157 (2009). (In Russian)
3. Tulupyev A. L., Sirotkin A.V., Nikolenko S.I. Bayesian beliefe networks: logical probabilistic inference in acyclic directed graphs. St. Petersburg, St.Petersburg University Press (2009). (In Russian)
4. Filchenkov A.A., Tulupyev A. L., Sirotkin A.V. The power of the set of minimal joint graphs. Information and Control Systems 15, 136–161 (2010). (In Russian)
5. Oparin V.V., Filchenkov A.A., Sirotkin A.V., Tulupyev A. L. Matroid representation of a family of joint graphs over a set of knowledge fragments. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, (4), 73–76 (2010). (In Russian)
6. Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier (2014).
7. Rue H., Held L. Gaussian Markov random fields: theory and applications. CRC Press (2005).
8. Kharitonov N.A., Maximov A.G., Tulupyev A. L. Algebraic Bayesian Networks: Na¨ıve Frequentist Approach to Local Machine Learning Based on Imperfect Information from Social Media and Expert Estimates. Russian Conference on Artificial Intelligence. Springer, Cham, 234–244 (2019).
9. Madsen A. L., Jensen F., Salmer´on A., Langseth H., Nielsen T.D. A parallel algorithm for Bayesian network structure learning from large data sets. Knowledge-Based Systems 117, 46–55 (2017).
10. Baltruˇsaitis T., Ahuja C., Morency L.P. Multimodal machine learning: A survey and taxonomy. IEEE transactions on pattern analysis and machine intelligence 41 (2), 423–443 (2018).
11. Sawada K., Hashimoto K., Nankaku Y., Tokuda K. A Bayesian framework for image recognition based on hidden Markov eigen-image models. IEEJ Transactions on Electrical and Electronic Engineering 13 (9), 1335–1347 (2018).
12. Cai B., Kong X., Liu Y., Lin J., Yuan X., Xu H., Ji R. Application of Bayesian networks in reliability evaluation. IEEE Transactions on Industrial Informatics 15 (4), 2146–2157 (2018).
13. Ghahramani Z. Probabilistic machine learning and artificial intelligence. Nature 521 (7553), 452–459 (2015).
14. Smirnov S. Towards conformal invariance of 2D lattice models. Proceedings of the International Congress of Mathematicians (ICM), Madrid, Spain, August 22–30, 2006. Vol. II, 1421–1451. Z¨urich, European Mathematical Society (2006).
15. Schmidt J.M. The Mondschein sequence. In: Lecture Notes in Computer Science, 967–978 (2014).
16. Cormen T.H., Leiserson C.E., Rivest R. L., Stein C. Introduction to algorithms. MIT Press (2009).
17. Tarjan R.E. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22 (2), 215–225 (1975).
18. Tarjan R.E., Van Leeuwen J. Worst-case analysis of set union algorithms. Journal of the ACM (JACM) 31 (2), 245–281 (1984).
19. Fredman M., Saks M. The cell probe complexity of dynamic data structures. Proceedings of the twenty-first annual ACM symposium on Theory of computing, 345–354 (1989).
20. Lancia G., Vidoni P. Finding the largest triangle in a graph in expected quadratic time. European Journal of Operational Research 286 (2), 458–467 (2020).
21. Spielman D.A., Shang-Hua T. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) 51 (3), 385–463 (2004).
22. Bollob´as B. Modern graph theory. Vol. 184. Springer Science & Business Media (2013).
23. Schmidt J.M. A simple test on 2-vertex-and 2-edge-connectivity. Information Processing Letters 113 (7), 241–244 (2013).
24. Szegedy B., Szegedy C. Symplectic spaces and ear-decomposition of matroids. Combinatorica 26 (3), 353–377 (2006).
25. Whitney H. Non-separable and planar graphs. In: Classic Papers in Combinatorics. Modern Birkh¨auser Classics. Boston, Birkh¨auser, 25–48 (2009). https://doi.org/10.1007/978-0-8176-4842-8_2
26. Shang X., Chao T., Ma P., Yang M. An efficient local search-based genetic algorithm for constructing optimal Latin hypercube design. Engineering Optimization 52 (2), 271–287 (2020).
27. Ghoshal S., Sundar S. Two heuristics for the rainbow spanning forest problem. European Journal of Operational Research 285 (3), 853–864 (2020).
28. Korepanova A.A., Oliseenko V.D., Abramov M.V., Tulupyev A.L. Application of machine learning methods in the task of identifying user accounts in two social networks. Computer tools in education, (3), 29–43 (2019). https://doi.org/10.32603/2071-2340-2019-3-29-43
29. Shindarev N., Bagretsov G., Abramov M., Tulupyeva T., Suvorova A. Approach to identifying of employees’ profiles in websites of social networks aimed to analyze social engineering vulnerabilities. Advances in Intelligent Systems and Computing 679, 441–447 (2018). https://doi.org/10.1007/978-3-319-68321-8_45
30. Khlobystova A.O., Abramov M.V., Tulupyev A.L. An approach to estimating of criticality of social engineering attacks traces. In: Studies in Systems, Decision and Control 199, 446–456 (2019).
Downloads
Published
2021-07-21
How to Cite
Maksimov, A. G., & Tulupyev, A. L. (2021). Algebraic Bayesian networks: Checking backbone connectivity. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 8(2), 305–316. https://doi.org/10.21638/spbu01.2021.210
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
