An Incremental Algorithm for Minimal Joint Graph Synthesis
Keywords:
joint graph, probabilistic graphical model, incremental algorithm, performance statistical estimate, structure learning, machine learning
Abstract
The paper provides the description of an incremental algorithm that accelerates a minimal joint graph upgrade when a new node with a correct load is inserted. The algorithms correctness is proven. We compare relative performance statistical estimates for the new incremental algorithm and two known greedy and streightforward algorithms that implement minimal joint graph synthesis. The computational experiments results are represented with plots, discussed and summarized. For the middle and large sized sets of loads, the incremental algorithm is 3-6 times faster than the streight-for-ward one and 10-50 times faster than the greedy one. For the small sized sets of loads, the algorithms permormance differs less dramatically. The relative performance variation of compared algorithms are the larger the higher fraction of loads with 5-9 symbols the set of loads has. The paper also reaches didactical goals: in the context of minimal joint grah synthesis, we demonstrate a rational application of the algorithm incrementation, an example of relative algorithmical performance statistical estimates, an approach to the visualisation of performance comparison compuational experiments.
References
1. Золотин А.А., Тулупьев А.Л., Сироткин А.В. Матрично-векторные алгоритмы нормировки для локального апостериорного вывода в алгебраических байесовских сетях // Научнотехнический вестник информационных технологий, механики и оптики, 2015. Т. 15. № 1. С. 78–85.
2. Зотов М.А., Тулупьев А.Л. Синтез вторичной структуры алгебраических байесовских сетей // Компьютерные инструменты в образовании, 2015. № 1. C. 3–16.
3. Зотов М.А., Тулупьев А.Л., Сироткин А.Л. Статистические оценки сложности прямого и жадного алгоритмов синтеза вторичной структуры алгебраических байесовских сетей // Нечеткие системы и мягкие вычисления, 2015. Т. 10. №1. С. 75–91.
4. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Тр. СПИИРАН, 2009. № 11. C. 142–157.
5. Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010. № 4(68). С. 73–76.
6. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. С. 40. (Сер. Элементы мягких вычислений).
7. Тулупьев А.Л. Дерево смежности с идеалами конъюнктов как ациклическая алгебраическая байесовская сеть // Тр. СПИИРАН. Вып. 3, т. 1. СПб.: Наука, 2006. С. 198–227.
8. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. С. 607.
9. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логиковероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009. С. 400.
10. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99.
11. Фильченков А.А. Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей. Дисс.... к-та физ.-мат. н. Самара, 2013. С. 339. (Самарск. гос. аэрокосм. ун-т им. ак. С.П. Королева (нац. исслед.))
12. Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизированного синтеза минимального графа смежности // Тр. СПИИРАН. 2013. Вып. 2(35). С. 221–234. ун-т.
13. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Тр. СПИИРАН. 2009. № 11. C. 104–129.
14. Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Тр. СПИИРАН. 2011. № 17. С. 151–173.
15. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Минимальные графы смежности алгебраической байесовской сети: формализация основ синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления, 2011. Т. 6. № 2. С. 145–163.
16. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. № 1 (12). С. 97–118.
17. Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система алгоритмов синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. № 4(27). С. 200–244.
18. Шинкаренко В.И. Зависимость временной эффективности алгоритмов и программ обработки больших объемов данных от их кэширования // Математические машины и системы. 2007. №2. С. 43–55.
19. Barrett C., Marathe A., Marathe M., Cook D., Hicks G., Faber V., Srinivasan A., Sussmann Y., Thornquist H. Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry. Journal of Graph Algorithms and Applications (JGAA). 2003. Vol. 7. P. 3–31.
20. Gonzalez-Diaz R., Ion A., Jimenez M.J., Poyatos.R. Incremental-Decremental Algorithm for Computing AT-Models and PersistentHomology // Real, P and DiazPernil, D and MolinaAbril, H and Berciano, A and Kropatsch, W, editor, Computer analysis of images and patterns:14th international conference, CAIP 2011, PT I, volume 6854 of LNCS, p.286–293, heidelberger platz3, D-14197 Berlin, Germany, 2011. springer-verlag berlin. 14thInternational Conference on Computer Analysis of Images and Patterns (CAIP),Seville, SPAIN, AUG 29-31, 2011.
21. Incremental algoritms [Электронный ресурс]. Режим доступа: URL: http://c2.com/cgi/wiki?IncrementalAlgorithms (дата обращения 01.11.2015).
22. Jaynes E.T. Bayesian Methods: General Background // Maximum-Entropy and Bayesian Methods in Applied Statistics, by J. H. Justice (ed.). Cambridge: Cambridge Univ. Press, 1986. P. 1–19.
23. Jerzy S. Respondek. Dynamic Data Structures in the Incremental Algorithms Operating on a Certain Class of Special Matrices. // Murgante, B and Misra, Sand Rocha, AMAC and Torre, C and Rocha, JG and Falcao, MI and Taniar,D and Apduhan, BO and Gervasi, O, editor, Computational scienceand its applications, part VI - ICCSA 2014, volume 8584 of Lecture Notes in Computer Science, p.171–185, Heidelberger platz 3, D-14197 Berlin, Germany, 2014. springer-verlag Berlin. 14-th International Conference on Computational Science and Its Applications (ICCSA), Guimaraes, Portugal, jun 30-jul 03, 2014.
24. Kas M., Wachs M., Carley K.M., Carley.L.R. Incremental Algorithm for Updating Betweenness Centrality in Dynamically Growing Networks. // Ozyer, T and Carrington, P, editor,2013 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), p.39–46, 345 E 47TH ST, Newyork, NY 10017 USA, 2013. IEEE. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Niagara Falls, Canada, aug. 25-28, 2013.
25. Pearl J. Causality: Models, Reasoning, and Inference. Cambridge: Cambridge University Press, 2000. P. 400.
26. Sariyuce A.E., Kaya K., Saule E., Umit V. Catalyurek. Incremental Algorithms for Closeness Centrality. // Hu, X and Lin, TY and Raghavan, V and Wah, B and Yates, R and Fox, G and Shahabi, C and Smith, M and Yang, Q and Ghani, R and Fan, W and Lempel, R and Nambiar,R, editor,2013 IEEE International conference on big data, 345E 47-th st, Newyork, NY 10017 USA, 2013. IEEE. IEEE International Conference on Big Data (Big Data), Santa Clara, CA, oct. 06-09, 2013.
27. Song X., Yu L., Sun H. An Incremental Query Algorithm for Optimal Path Queries Under Traffic Jams.
// Yu, F and Chen, W and Chen, Z and Yuan, J, editor, ISCSCT 2008: International Symposiumon Computer Science and Computational Technology, Proceedings, p.472–475, 10662 Los Vaqueros Circle, PO BOX3014, Los Alamitos, CA 90720-1264 USA, 2008. IEEE Computer SOC. International Symposium on Computer Science and Computational Technology, Shanghai, Peoples R China, dec.20-22, 2008.
2. Зотов М.А., Тулупьев А.Л. Синтез вторичной структуры алгебраических байесовских сетей // Компьютерные инструменты в образовании, 2015. № 1. C. 3–16.
3. Зотов М.А., Тулупьев А.Л., Сироткин А.Л. Статистические оценки сложности прямого и жадного алгоритмов синтеза вторичной структуры алгебраических байесовских сетей // Нечеткие системы и мягкие вычисления, 2015. Т. 10. №1. С. 75–91.
4. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Тр. СПИИРАН, 2009. № 11. C. 142–157.
5. Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010. № 4(68). С. 73–76.
6. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. С. 40. (Сер. Элементы мягких вычислений).
7. Тулупьев А.Л. Дерево смежности с идеалами конъюнктов как ациклическая алгебраическая байесовская сеть // Тр. СПИИРАН. Вып. 3, т. 1. СПб.: Наука, 2006. С. 198–227.
8. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. С. 607.
9. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логиковероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009. С. 400.
10. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99.
11. Фильченков А.А. Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей. Дисс.... к-та физ.-мат. н. Самара, 2013. С. 339. (Самарск. гос. аэрокосм. ун-т им. ак. С.П. Королева (нац. исслед.))
12. Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизированного синтеза минимального графа смежности // Тр. СПИИРАН. 2013. Вып. 2(35). С. 221–234. ун-т.
13. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Тр. СПИИРАН. 2009. № 11. C. 104–129.
14. Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Тр. СПИИРАН. 2011. № 17. С. 151–173.
15. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Минимальные графы смежности алгебраической байесовской сети: формализация основ синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления, 2011. Т. 6. № 2. С. 145–163.
16. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. № 1 (12). С. 97–118.
17. Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система алгоритмов синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. № 4(27). С. 200–244.
18. Шинкаренко В.И. Зависимость временной эффективности алгоритмов и программ обработки больших объемов данных от их кэширования // Математические машины и системы. 2007. №2. С. 43–55.
19. Barrett C., Marathe A., Marathe M., Cook D., Hicks G., Faber V., Srinivasan A., Sussmann Y., Thornquist H. Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry. Journal of Graph Algorithms and Applications (JGAA). 2003. Vol. 7. P. 3–31.
20. Gonzalez-Diaz R., Ion A., Jimenez M.J., Poyatos.R. Incremental-Decremental Algorithm for Computing AT-Models and PersistentHomology // Real, P and DiazPernil, D and MolinaAbril, H and Berciano, A and Kropatsch, W, editor, Computer analysis of images and patterns:14th international conference, CAIP 2011, PT I, volume 6854 of LNCS, p.286–293, heidelberger platz3, D-14197 Berlin, Germany, 2011. springer-verlag berlin. 14thInternational Conference on Computer Analysis of Images and Patterns (CAIP),Seville, SPAIN, AUG 29-31, 2011.
21. Incremental algoritms [Электронный ресурс]. Режим доступа: URL: http://c2.com/cgi/wiki?IncrementalAlgorithms (дата обращения 01.11.2015).
22. Jaynes E.T. Bayesian Methods: General Background // Maximum-Entropy and Bayesian Methods in Applied Statistics, by J. H. Justice (ed.). Cambridge: Cambridge Univ. Press, 1986. P. 1–19.
23. Jerzy S. Respondek. Dynamic Data Structures in the Incremental Algorithms Operating on a Certain Class of Special Matrices. // Murgante, B and Misra, Sand Rocha, AMAC and Torre, C and Rocha, JG and Falcao, MI and Taniar,D and Apduhan, BO and Gervasi, O, editor, Computational scienceand its applications, part VI - ICCSA 2014, volume 8584 of Lecture Notes in Computer Science, p.171–185, Heidelberger platz 3, D-14197 Berlin, Germany, 2014. springer-verlag Berlin. 14-th International Conference on Computational Science and Its Applications (ICCSA), Guimaraes, Portugal, jun 30-jul 03, 2014.
24. Kas M., Wachs M., Carley K.M., Carley.L.R. Incremental Algorithm for Updating Betweenness Centrality in Dynamically Growing Networks. // Ozyer, T and Carrington, P, editor,2013 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), p.39–46, 345 E 47TH ST, Newyork, NY 10017 USA, 2013. IEEE. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Niagara Falls, Canada, aug. 25-28, 2013.
25. Pearl J. Causality: Models, Reasoning, and Inference. Cambridge: Cambridge University Press, 2000. P. 400.
26. Sariyuce A.E., Kaya K., Saule E., Umit V. Catalyurek. Incremental Algorithms for Closeness Centrality. // Hu, X and Lin, TY and Raghavan, V and Wah, B and Yates, R and Fox, G and Shahabi, C and Smith, M and Yang, Q and Ghani, R and Fan, W and Lempel, R and Nambiar,R, editor,2013 IEEE International conference on big data, 345E 47-th st, Newyork, NY 10017 USA, 2013. IEEE. IEEE International Conference on Big Data (Big Data), Santa Clara, CA, oct. 06-09, 2013.
27. Song X., Yu L., Sun H. An Incremental Query Algorithm for Optimal Path Queries Under Traffic Jams.
// Yu, F and Chen, W and Chen, Z and Yuan, J, editor, ISCSCT 2008: International Symposiumon Computer Science and Computational Technology, Proceedings, p.472–475, 10662 Los Vaqueros Circle, PO BOX3014, Los Alamitos, CA 90720-1264 USA, 2008. IEEE Computer SOC. International Symposium on Computer Science and Computational Technology, Shanghai, Peoples R China, dec.20-22, 2008.
Published
2015-12-30
How to Cite
Левенец, Д. Г., Зотов, М. А., & Тулупьев, А. Л. (2015). An Incremental Algorithm for Minimal Joint Graph Synthesis. Computer Tools in Education, (6), 3-18. Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1447
Issue
Section
Computer science
This work is licensed under a Creative Commons Attribution 4.0 International License.
