Abstract
This paper presents a new algorithm that was developed for graph isomorphism, the main goal being obtaining the correct results with the best execution times. The things described are the utility and domains of usage for the algorithm, the nomenclature, the input data, the preconditions and graph definitions, the access of GNS1 to the query graphs and the data graph, the implementation details for the algorithm structure, methods and pruning techniques, then a series of test cases, the system specifications, the acknowledgment, the conclusions and the references. Motif graph finding has gathered increased popularity due to its vast domain of applicability. GNS1 is a backtracking algorithm with new pruning techniques for reducing the search space. It returns to the user all occurrences of a query graph found in a data graph while at the same time having much lower execution times than the STwig [1] and VF2 [2,3,4] algorithms. The algorithms can be used in a multitude of domains.
Supported by Dr. Pârv Bazil, Professor Emeritus, Dr. Niculescu Virginia, Associate Professor and Dr. Sterca Adrian, Lecturer Professor.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Sun Z, Wang H, Wang H, Shao B, Li J (2012) Efficient subgraph matching on billion node graphs. In: Proceedings of the VLDB endowment. PVLDB. https://doi.org/10.14778/2311906.2311907
Cordella LP, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 26(10):1367–1372
Lee J, Han WS, Kasperovics R, Lee JH (2012) An in-depth comparison of subgraph isomorphism algorithms in graph databases. In: PVLDB
Gheorghica R-I (2018) Algorithms for graph isomorphism. A comparative study. In: 8th international multidisciplinary scientific symposium “challenges and opportunities for sustainable development through quality and innovation in engineering and research management”, Universitaria SIMPRO 2018, Petroşani, 11–13 Oct 2018
Gheorghica R-I: Algorithms for graph isomorphism. A comparative study on STwig and VF2. In: Proceedings of the 26th workshop on information and communication technologies, 28th international conference on software, telecommunications and computer networks (SOFTCOM 2020), Hvar, Croatia Sept 2020, pp 17–19. ISSN 2623-7350
Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824–827
Ferro A, Pulvirenti A, Alaimo S, Micale G, Marceca GP, Sciacca E, Maria AD, Sciacca E, Ferlita AL, Martorana E (2020) University of Catania, Department of Clinical and Molecular Biomedicine (MEDBIO). https://www.researchgate.net/profile/Alfredo_Ferro, http://www.medclin.unict.it/faculty/alfredo.ferro. Accessed 14 Aug 2020
The randomized networks used for detecting three node motifs preserve the numbers of incoming, outgoing, and double edges with both incoming and outgoing arrows for each node. The randomized networks used for detecting four-node motifs preserve the above characteristics as well as the numbers of all 13 three-node subgraphs as in the real network. Algorithms for constructing these randomized network ensembles are described [8]. Additional information is available at www.weizmann.ac.il/mcb/UriAlon [6]
Methods are available as supporting material on Science Online [6]
Shen-Orr S, Milo R, Mangan S, Alon U (2002) Nat Genet 31:64
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press
Hagberg A, Shult D, Swart P (2020) Network analysis in Python. https://networkx.github.io/. Accessed 14 Aug 2020
Neo4j (2020) Neo4j documentation. https://neo4j.com/docs/. Accessed 14 Aug 2020
Docker Hub. https://hub.docker.com/. Accessed 28 Sep 2020
Spiegelberg E (2020) Neo4j causal cluster docker Quickstart. https://graphaware.com/neo4j/2018/01/03/casual-cluster-quickstart.html, 3 Jan 2018. Accessed 28 Sept 2020
Neo4j (2020) Neo4j operations manual, clustering introduction. Available at: https://neo4j.com/docs/operations-manual/3.5/clustering/introduction/. Accessed 28 Sept 2020
JetBrains s.r.o, PyCharm Professional Edition. https://www.jetbrains.com/pycharm/ Accessed 14 Aug 2020
van Rossum G (2020) Python Software Foundation. https://www.python.org/. Accessed 14 Aug 2020
Oliphant T et al (2020) The fundamental package for scientific computing with Python. https://numpy.org. Accessed 14 Aug 2020
Neo4j Sweden AB (2020) Neo4j Bolt connector for Python. https://github.com/neo4j-drivers/neobolt. Accessed 15 Aug 2020
Neo4j Drivers Team (2020) Nanosecond resolution temporal types. https://neotime.readthedocs.io. Accessed 15 Aug 2020
Small N (2020) Python client library and toolkit for Neo4j. https://py2neo.org/v4/. Accessed 15 Aug 2020
Acknowledgements
This research was supported by Babeş-Bolyai University Cluj Napoca, Faculty of Mathematics and Computer Science. Thanks to my Supervisor Dr. P\(\hat{a}\)rv Bazil, Professor Emeritus, Dr. Niculescu Virginia, Associate Professor and Dr. Sterca Adrian, Lecturer Professor who provided insight and expertise in helping me learn graph theory and how to implement and understand graph isomorphism algorithms.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Gheorghica, RI. (2022). The GNS1 Algorithm for Graph Isomorphism. In: Patgiri, R., Bandyopadhyay, S., Borah, M.D., Emilia Balas, V. (eds) Edge Analytics. Lecture Notes in Electrical Engineering, vol 869. Springer, Singapore. https://doi.org/10.1007/978-981-19-0019-8_19
Download citation
DOI: https://doi.org/10.1007/978-981-19-0019-8_19
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-0018-1
Online ISBN: 978-981-19-0019-8
eBook Packages: EngineeringEngineering (R0)