Поиск схожих подграфов в невзвешенном неориентированном графе посредством вычисления изоморфных путевых наборов
Аннотация
Тема поиска подграфов в суперграфе является до сих пор актуальной и фундаментальной задачей. Так как графы являются наиболее удачными моделями, как для визуализации, так и для обработки сложных взаимосвязей, представленных в виде семантических сетей, как например, исходный код программ. Одной из важнейших задач анализа таких моделей данных является, задача поиска схожих подграфов. Существующие на данный момент методы, предложения и подходы, базируются на поиске изоморфных подграфов, в том числе, в виде промежуточных результатов, что не дает возможность находить подграфы по общей части с искомым графом в виде частичного графа. Представленный алгоритм работает на основе построения и анализа путевых наборов графов, по оригинальным алгоритмам построения путевого каркаса и итерационного алгоритма поиска наикратчайших путей между двумя вершинами и находит схожие подграфы в суперграфе G, выделяя общую часть с искомым графом Q в виде частичного графа FQ, которая, в конечном счете, проходит проверку на изоморфизм.
Литература
2. Sokolova O.D. [Graph models for the problems of functioning of modern data transmission networks]. Problems of Informatics. 2014;(4):61-68. (In Russ.) EDN: THSRHB
3. Shakhov V.V., Yurgenson A.N., Sokolova O.D. Fast method for generating random geometric graphs for wireless networks modeling. Applied Discrete Mathematics. 2016;(4):99-109. (In Russ., abstract in Eng.) https://doi.org/10.17223/20710410/34/8
4. Ullmann J.R. An algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery. 1976;23(1):31-42. https://doi.org/10.1145/321921.321925
5. Ullmann J.R. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. Journal of Experimental Algorithmics. 2011;15:1.6. https://doi.org/10.1145/1671970.1921702
6. Cordella L., 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. https://doi.org/10.1109/TPAMI.2004.75
7. Bonnici V., Giugno R., Pulvirenti A., et al. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics. 2013;14(Suppl 7):S13. https://doi.org/10.1186/1471-2105-14-S7-S13
8. Nguyen D.Q., Nguyen T.T., Jo J., Poux F., Anirban S., Quan T.T. Explainable Neural Subgraph Matching With Learnable Multi-Hop Attention. IEEE Access. 2024;12:130474-130492. https://doi.org/10.1109/ACCESS.2024.3458050
9. Fan W., Li J., Ma S., Tang N., Wu Y., Wu Y. Graph pattern matching: from intractable to polynomial time. Proceedings of the VLDB Endowment. 2010;3(1-2):264-275. https://doi.org/10.14778/1920841.1920878
10. Zubov M.V., Pustygin A.N. Use of finite-state automation for getting universal intermediate representation of program source code. Vestnik of Astrakhan State Technical University. Series: Management, Computer Science and Informatics. 2015;(4):57-65. (In Russ., abstract in Eng.) EDN: UYRZWV
11. Lazdin A.V., Nemolochnov O.F. [Method of constructing a graph of a functional program for solving verification and testing problems]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics. 2002;(6):118-121. (In Russ.)
12. Broder A., et al. Graph structure in the Web. Computer Networks. 2000;33(1-6):309-320. https://doi.org/10.1016/S1389-1286(00)00083-9
13. Wangmo C., Wiese L. An Experimental Evaluation of Summarisation-Based Frequent Subgraph Mining for Subgraph Searching. SN Computer Science. 2024;5:693. https://doi.org/10.1007/s42979-024-03006-w
14. Kokhov V.A., Ibrahim A.R., Kokhov V.V. System of models for the analysis of graph's similarity with account of circuit arrangement. Bulletin of Moscow Power Engineering Institute. 2009;(5):5-13. (In Russ., abstract in Eng.) EDN: KXNBUR
15. Khanna S., Putterman A., Sudan M. Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Chicago, IL, USA: IEEE Computer Society; 2024. p. 1669-1706. https://doi.org/10.1109/FOCS61266.2024.00105
16. Baskin I., Skvortsova M. On the basis of invariants of labeled molecular graphs. Journal of Chemical Information & Computer Sciences. 1995;35(3):527-531.
17. Azarmehr A., Behnezhad S., Ghafari A., Rubinfeld R. Stochastic Matching via In-n-Out Local Computation Algorithms. arXiv:2411.08805. 2024. https://doi.org/10.48550/arXiv.2411.08805
18. Emmert Streib F., Dehmer M. Networks for systems biology: conceptual connection of data and function. IET Systems Biology. 2011;5(3):185-207. https://doi.org/10.1049/iet-syb.2010.0025
19. Dehmer M., Grabner M. The discrimination power of molecular identification numbers revisited. MATCH Communications in Mathematical and in Computer Chemistry. 2013;69(3):785-794. Available at: https://match.pmf.kg.ac.rs/electronic_versions/Match69/n3/match69n3_785-794.pdf (accessed 19.01.2024).
20. Molloy M., Pralat P., Sorkin G.B. Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model. arXiv:2401.00559. 2024. https://doi.org/10.48550/arXiv.2401.00559
21. Pogrebnoy V.K. [The problem of determining the similarity estimates of the structures of two graphs based on the identification of common parts]. Bulletin of the Tomsk Polytechnic University. 2013;322(5):194-199. (In Russ.) EDN: QOXURJ
22. Sysoev V.V. A Framework Similarity Estimation of Unweighted Undirected Graphs. Modern Information Technologies and IT-Education. 2022;18(3):655-665. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITITO.18.202203.655-665
23. 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.) https://doi.org/10.25559/SITITO.17.202103.585-592
24. Sudoso A.M. A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering. INFORMS Journal on Computing. 2024. https://doi.org/10.1287/ijoc.2024.0683
25. Chancellor N., McGeoch C.C., Mniszewski S., Niera D.D. Editorial: Experience with quantum annealing computation. Frontiers in Computer Science. 2024;6:1481330. https://doi.org/10.3389/fcomp.2024.1481330
Это произведение доступно по лицензии 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.
