The week's pick
Reseach Article
Graph Isomorphism Algorithm using Pieces Patching Puzzle Technique (ppp - Technique)
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 176 - Number 12 |
| Year of Publication: 2020 |
| Authors: Mohammad Alhashmi, Abdulaziz Alroomi |
10.5120/ijca2020920044
|
Mohammad Alhashmi, Abdulaziz Alroomi . Graph Isomorphism Algorithm using Pieces Patching Puzzle Technique (ppp - Technique). International Journal of Computer Applications. 176, 12 ( Apr 2020), 1-7. DOI=10.5120/ijca2020920044
Abstract
This paper proposes a novel technique for a polynomial time algorithm to detect an existence of isomorphism between two unlabeled graphs that is fast and accurate for the mass majority of large random graphs. This technique, namely ppp-Technique, is based on cutting the first graph into large sub-graphs to mimic the pieces ( or patches ) of a puzzle that have to be patched to their correct places (or matches ) on the second graph. It is a difficult process to draw the borders of each patch for best results. In other words, deciding the sizes of the patches is an optimization problem. Clearly, the larger these patches are, the faster the algorithm can decide whether an isomorphism exists. The greedy concept has been applied in the process of creating patches which led to high efficiency. The time complexity of the proposed algorithm is O(n3 log n) . Examples that clarify the process of constructing the patches from one graph and matching them to the places in the other one are shown. The algorithm is tested with many graphs with different sizes of nodes and different densities of connecting edges which gave complete accurate results.
References
- M. Zaslavskiy, F. Bach, and J.-P. Vert, “A path following algorithm for the graph matching problem,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 12, pp. 2227–2242, 2008.
- K. Liu, Y. Zhang, K. Lu, X. Wang, X. Wang, and G. Tian, “Mapeff: An effective graph isomorphism agorithm based on the discrete-time quantum walk,” Entropy, vol. 21, no. 6, p. 569, 2019.
- D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty years of graph matching in pattern recognition,” International journal of pattern recognition and artificial intelligence, vol. 18, no. 03, pp. 265–298, 2004.
- A. Dawar and K. Khan, “Constructing hard examples for graph isomorphism,” arXiv preprint arXiv:1809.08154, 2018.
- L. Babai, A. Dawar, P. Schweitzer, and J. Tor´an, “The graph isomorphism problem (dagstuhl seminar 15511),” in Dagstuhl Reports, vol. 5, no. 12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
- G. L. Miller, “Graph isomorphism, general remarks,” Journal of Computer and System Sciences, vol. 18, no. 2, pp. 128–142, 1979.
- B. D. McKay and A. Piperno, “Practical graph isomorphism, ii,” Journal of Symbolic Computation, vol. 60, pp. 94–112, 2014.
- G. Nikolentzos, P. Meladianos, and M. Vazirgiannis, “Matching node embeddings for graph similarity,” in Thirty-First AAAI Conference on Artificial Intelligence, 2017.
- V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha, and A. Ferro, “A subgraph isomorphism algorithm and its application to biochemical data,” BMC bioinformatics, vol. 14, no. S7, p. S13, 2013.
- S. B. Akers, “The star graph: An attractive alternative to the n-cube,” in Proc. Int’l Conf. Parallel Processing., 1987, 1987.
- M. Verma and S. Sharma, “A greedy approach for coverage hole detection and restoration in wireless sensor networks,” Wireless Personal Communications, vol. 101, no. 1, pp. 75– 86, 2018.
- H. Joudrier and F. Thiard, “A greedy approach for a rolling stock management problem using multi-interval constraint propagation,” Annals of Operations Research, vol. 271, no. 2, pp. 1165–1183, 2018.
- Y. Duan, J. Wu, and H. Zheng, “A greedy approach for carpool scheduling optimisation in smart cities,” International Journal of Parallel, Emergent and Distributed Systems, pp. 1–15, 2018.
- E. Oh and C. Woo, “Performance analysis of dynamic channel allocation based on the greedy approach for orthogonal frequency-division multiple access downlink systems,” International Journal of Communication Systems, vol. 25, no. 7, pp. 953–961, 2012.
- N. Meghanathan, “A greedy algorithm for neighborhood overlap-based community detection,” Algorithms, vol. 9, no. 1, p. 8, 2016.
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An improved algorithm for matching large graphs,” in 3rd IAPRTC15 workshop on graph-based representations in pattern recognition, 2001, pp. 149–159.
- C. McCreesh, P. Prosser, C. Solnon, and J. Trimble, “When subgraph isomorphism is really hard, and why this matters for graph databases,” Journal of Artificial Intelligence Research, vol. 61, pp. 723–759, 2018.
Index Terms
Keywords