Каркасный алгоритм оценки схожести невзвешенных неориентированных графов
Аннотация
Общеизвестно, что проблема алгоритмов оценки схожести графов упирается в сложность их вычисления. Большинство предлагаемых алгоритмов оценки схожести графов основаны на алгоритме Ульмана. Философия алгоритма Ульмана заключается в работе с матрицами смежности. Алгоритм Ульмана имеет высокую сложность вычисления, применение параллельных вычислений, в том числе, на видеокартах, оставляет алгоритм Ульмана NP – сложным. При этом алгоритм Ульмана дает только информацию, изоморфны ли графы или является ли один из них подграфом другого, а для получения численной оценки схожести необходимо проводить дополнительные вычисления.
Предлагаемый в статье каркасный алгоритм оценки схожести призывает отойти от философии алгоритма Ульмана, а именно, работы с матрицами смежности. Новый алгоритм основан на построении и изучении каркасов сравниваемых графов. В статье приводится определение и алгоритм построения каркаса графа, который, в свою очередь, строятся на основе ранее опубликованном итерационном алгоритме нахождения всех наикратчайших путей между двумя вершинами. Каркасный алгоритм имеет асимптотическую сложность O(|V|2), способен выявить гомоморфизм графов и дать количественную оценку схожести двух сравниваемых графов.
Литература
2. Ullmann J.R. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. ACM Journal of Experimental Algorithmics. 2011;15(1.6):1.1-1.64. doi: https://doi.org/10.1145/1671970.1921702
3. Fomin F.V., Kratsch D., Woeginger G.J. Exact (Exponential) Algorithms for the Dominating Set Problem. In: Hromkovič J., Nagl M., Westfechtel B. (eds.) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science. Vol. 3353. Berlin, Heidelberg: Springer; 2004. doi: https://doi.org/10.1007/978-3-540-30559-0_21
4. Abu-Khzam F.N., Daudjee K., Mouawad A.E., Nishimura N. On scalable parallel recursive backtracking. Journal of Parallel and Distributed Computing. 2015;84:65-75. doi: http://doi.org/10.1016/j.jpdc.2015.07.006
5. Wang R., Guo L., Ai C., Li J., Ren M., Li K. An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU. In: 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing. Zhangjiajie, China: IEEE Computer Society; 2013. p. 1089-1096. doi: http://doi.org/10.1109/HPCC.and.EUC.2013.154
6. Sysoev V.V. Iterative Algorithm for Finding the Shortest Ways in an Unweighted Undirected Graph. Modern Information Technologies and IT-Education. 2021;17(3):585-592. (In Russ., abstract in Eng.) doi: https://doi.org/10.25559/SITITO.17.202103.585-592
7. Bunke H., Dickinson P.J., Kraetzl M., Wallis W.D. A Graphtheoretic Approach to Enterprise Network Dynamics. In: Progress in Computer Science and Applied Logic. Vol. 24. Birkhäuser Boston, MA; 2007. 226 p. doi: https://doi.org/10.1007/978-0-8176-4519-9
8. Kruskal J.B. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika. 1964;29(1):1-27. doi: https://doi.org/10.1007/BF02289565
9. Papadimitriou P., Dasdan A., Garcia-Molina H. Web graph similarity for anomaly detection. Journal of Internet Services and Applications. 2010;1(1):19-30. doi: https://doi.org/10.1007/s13174-010-0003-x
10. Kanigalpula S., Naveen S. Subgraph Similarity Search in Large Graphs. In: The Eighth International Conference on Advances in Databases, Knowledge, and Data Applications (DBKDA 2016). IARIA; 2016. p. 84-93. doi: https://doi.org/10.48550/arXiv.1512.05256
11. Yang X., Qiao H., Liu Z. -Y. An Algorithm for Finding the Most Similar Given Sized Subgraphs in Two Weighted Graphs. IEEE Transactions on Neural Networks and Learning Systems. 2018;29(7):3295-3300. doi: https://doi 10.1109/TNNLS.2017.2712794
12. Broder A., Kumar R., Maghoul F., Raghavan P., Rajagopalan S., Stata R., Tomkins A., Wiener J. Graph structure in the Web. Computer Networks. 2000;33(1-6):309-320. doi: https://doi.org/10.1016/S1389-1286(00)00083-9
13. Huang X., Lai J., Jennings S.F. Maximum common subgraph: some upper bound and lower bound results. BMC Bioinformatics. 2006. Vol. 7. Article number: S6. doi: https://doi.org/10.1186/1471-2105-7-S4-S6
14. Moskin N.D. Metric for comparing graphs with ordered vertices based on the maximum common subgraph. Applied Discrete Mathematics. 2021;(52):105-113 . (In Russ., abstract in Eng.) doi: https://doi.org/10.17223/20710410/52/7
15. Bunke H. , a href="https://elibrary.ru/author_items.asp?refid=826829282&fam=Shearer&init=K" Shearer K. /a A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters. 1998;19(3-4):255-259. doi: https://doi.org/10.1016/S0167-8655(97)00179-7
16. Boytyakov A.A., Egorov Yu.S. A data transfer model based on comparison of proximity graphs and graph structures of geometric models. Modern high technologies. 2019;(6):20-25 . Available at: https://elibrary.ru/item.asp?id=38597151 (accessed 04.08.2022). (In Russ., abstract in Eng.)
17. Sayfullina E.F. Consistent comparison of graph invariants in the problem of verification of isomorphism. Science Vector of Togliatti State University. 2013;(3):87-90. Available at: https://elibrary.ru/item.asp?id=21458448 (accessed 04.08.2022). (In Russ., abstract in Eng.)
18. Tuzhilkin A.Yu., Zakharov A.A. Finding matches in the images using inexact comparison of graphs. Scientific and Technical Volga region Bulletin. 2015;(4):130-132. Available at: https://elibrary.ru/item.asp?id=24115121 (accessed 04.08.2022). (In Russ., abstract in Eng.)
19. Mendivelso J., Kim S., Elnikety S., He Y., Hwang S., Pinzon Y. Solving Graph Isomorphism Using Parameterized Matching. In: Kurland O., Lewenstein M., Porat E. (eds.) String Processing and Information Retrieval. SPIRE 2013. Lecture Notes in Computer Science. Vol. 8214. Cham: Springer; 2013. p. 230-242. doi: https://doi.org/10.1007/978-3-319-02432-5_26
20. Bonnici V., Giugno R., Pulvirenti A., Shasha D., Ferro A. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics. 2013. Vol. 14. Article number: S13. doi: https://doi.org/10.1186/1471-2105-14-S7-S13
21. Bouhenni S., Yahiaoui S., Nouali-Taboudjemat N., Kheddouci H. A Survey on Distributed Graph Pattern Matching in Massive Graphs. ACM Computing Surveys. 2021;54(2):36. doi: https://doi.org/10.1145/3439724
22. Cordella L.P., Foggia P., Sansone C., Vento M. A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004;26(10):1367-1372. doi: https://10.1109/TPAMI.2004.75
23. Lv L., Liu J., Li Q., Li J. Optimization of Subgraph Matching over Knowledge Graph Based on Subgraph Indexing. In: 2022 5th International Conference on Artificial Intelligence and Big Data (ICAIBD). Chengdu, China: IEEE Computer Society; 2022. p. 543-546. doi: https://doi.org/10.1109/ICAIBD55127.2022.9820592
24. Llados J., Marti E., Villanueva J.J. Symbol recognition by error-tolerant subgraph matching between region adjacency graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002;23(10):1137-1143. doi: https://doi.org/10.1109/34.954603
25. Prihozhy A.A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms. System analysis and applied information science. 2021;(3):40-50. doi: https://doi.org/10.21122/2309-4923-2021-3-40-50
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
