الگوریتم مکاشفه ای بهبود یافته جهت مساله یکریختی گراف

نوع مقاله : علمی-پژوهشی

نویسندگان

1 آزمایشگاه تحقیق و توسعه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی

2 آزمایشگاه تحقیق و توسعه نرم‌افزار- گروه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی

چکیده

مساله یکریختی گراف  (GIP) از لحاظ پیچیدگی محاسباتی یک مساله باز است. تاکنون هیچ الگوریتم قطعی با زمان اجرای چندجمله‌ای برای حل آن پیشنهاد‌نشده و روش‌های اکتشافی و فرا‌اکتشافی تنها راه‌حل آن بوده‌است. از آنجا که NP-complete بودن این مساله هنوز به اثبات نرسیده لذا این مساله را جز مسائل NP در نظر گرفته‌اند. در این مقاله یک الگوریتم چندجمله‌ای ساده اما کاربردی هم از لحاظ پیچیدگی زمانی و هم از لحاظ پیچیدگی فضا معرفی شده‌است که در زمان چندجمله‌ای، یکریختی میان گراف‌های همبند بدون برچسب را تشخیص می‌دهد. الگوریتم پیشنهادی دو تابع جهت محاسبه‌ی ویژگی‌های تمامی یال‌ها و برگ‌ها ارائه می‌دهد. خروجی این توابع به ازای هر گراف ورودی یک برچسب کانونی‌ است و تشخیص یکریختی میان گراف‌ها با مقایسه میان برچسب‌ها صورت می‌گیرد. نتایج بدست‌آمده نشان می‌دهد که الگوریتم پیشنهادی با صحت بالاتر از 99درصد یکریختی میان گراف‌ها را تشخیص می‌دهد. پیچیدگی زمانی الگوریتم  O(n^3 ) می‌باشد که n برابر تعداد راس‌های گراف ورودی است.

کلیدواژه‌ها

عنوان مقاله [English]

An Improved Heuristic Algorithm for the Graph Isomorphism Problem

نویسندگان [English]

  • Somayeh Check 1
  • Ali Nourollah 2
1 Software Systems Research and Development Laboratory / Faculty of Computer Engineering, Shahid Rajaee Teacher Training University
2 Software Systems Research and Development Laboratory / Faculty of Computer Engineering, Shahid Rajaee Teacher Training University
چکیده [English]

The Graph Isomorphism Problem (GIP) is an open problem because of its computational complexity. No polynomial-time deterministic algorithm has been proposed yet, and heuristic and meta-heuristic approaches have been the only ways to solve it. Because its belonging to the NP-complete problem has not yet been proven, it is considered an NP problem. This paper introduces a simple but efficient polynomial algorithm, both in terms of computational complexity and memory complexity, to determine the isomorphism of connected unlabeled graphs. The proposed algorithm introduces two functions that compute the features for all vertices and edges. The outputs of the function provide canonical labeling to the given graphs, and a comparison of these labels specifies the graph isomorphism of the given graphs. The experimental results show that the proposed algorithm correctly detects the isomorphism of the graphs in more than 99% of cases. The algorithm requires Ο(n^3) time where n is the number of vertices of the given graphs.

کلیدواژه‌ها [English]

  • Graph isomorphism
  • polynomial-time algorithm
  • heuristic algorithm
  • canonical labeling

مراجع

[1] Rafiee, P. Moradi, A. Ghaderzadeh, “A swarm intelligence based multi-label feature selection method hybridized with a local search strategy”, Tabriz Journal of Electrical Engineering, vol. 51, no. 4, pp. 443-454, 2021.
[2] Mokhtarizadeh, B. Zamani Dehkordi, M. Mosleh, Ali Barati, “Influence Maximization using Time Delay based Harmonic Centrality in Social Networks”, Tabriz Journal of Electrical Engineering, vol. 51, no. 3, pp. 359-370, 2021.
[3] K. Wong, “Model matching in robot vision by subgraph isomorphism”, Pattern Recognition, vol. 25, no. 3, pp. 287-304, 1992.
[4] Kandel, H. Bunke, M. Last, “Applied Graph Theory in Computer Vision and Pattern Recognition”, Berlin, Springer, 2007.
[5] A. Abdulrahim, M. Misra, “A graph isomorphism algorithm for object recognition”, Pattern Analysis and Applications, vol. 1, no. 3, pp. 189-201, 1998.
[6] Washio, H. Motoda, “State of the art of graph-based data mining”, ACM SIGKDD Explorations Newsletter, vol. 5, no. 1, pp. 59-68, 2003.
[7] Conte, P. Foggia, C. Sansone, M. Vento, “Graph matching applications in pattern recognition and image processing”, In IEEE International Conference on Image Processing, September 2003, Barcelona, Spain, pp. 21-24.
[8] Wasserman, K. Faust, “Social Network Analysis: Methods and Applications”, Cambridge University Press, 1994.
[9] Sanfeliua, R. Alquézarb, J. Andradea, J. Climentc, F. Serratosad, J. Vergésa, “Graph-based representations and techniques for image processing and image analysis”, Pattern Recognition, vol. 35, no. 3, pp. 639-650, 2002.
[10] H. Rouvray, A.T. Balaban, “Chemical applications of graph theory”, Academic Press London, 1979.
[11] Aittokallio, B. Schwikowski, “Graph–based methods for analysing networks in cell biology”, Briefings in Bioinformatics, vol. 7, no. 3, pp. 243-255, 2006.
[12] Valiente, “Algorithms on Trees and Graphs”, Springer-Verlag, 2002.
[13] Babai, E.M. Luks, “Canonical labeling of graphs”, In 15th Annual ACM Symposium on Theory of Computing, December 1983, New York, United States, pp. 171–183.
[14] Babai, P. Erdos, M. Selkow, “Random graph isomorphism”, SIAM Journal on Computing, vol. 9, no. 3, pp. 628-635, 1980.
[15] Babai, L. Kucera, “Canonical labeling of graphs in linear average time”, In 20th IEEE Symposium on Foundations of Computer Science, October 1979, San Juan, USA, pp. 39-46.
[16] Babai, “Graph isomorphism in quasi-polynomial time”, In 48th Annual ACM Symposium on Theory of Computing, June 2016, New York, United States, pp. 684-697.
[17] D. McKay, A. Piperno, “Practical graph isomorphism II”, Journal of Symbolic Computation, vol. 60, pp. 94-112, 2014.
[18] Miyazaki, “The complexity of McKay’s canonical labeling algorithm”, Groups and Computation, vol. 28, no. 2, pp. 239-256, 1996.
[19] M. Karp, “Reducibility Among Combinatorial Problems”, In Symposium on the Complexity of Computer Computations, March 1972, Yorktown Heights, New York, pp. 85-103.
[20] V. Aho, J.E. Hopcroft, J.D. Ullman, “The Design and Analysis of Computer Algorithms”, Addison-Wesley, 1974.
[21] E. Hopcroft, J.K. Wong, “Linear time algorithm for isomorphism of planar graphs”, In 6th Annual ACM Symposium on Theory of Computing, April 1974, Washington, USA, pp. 172-184.
[22] D. McKay, A. Piperno, "Nauty Traces", Available: http://pallini.di.uniroma1.it.
[23] Nourollah, S. Check, “A Heuristic Algorithm for Graph Isomorphism Problem Based on Eccentricity”, Computing Sciences and Information Technologies, vol. 17, no. 2, pp. 45-51, 2019 (in Persian).
[24] C. Freeman, “A set of measures of centrality based on betweenness”, Sociometry, vol. 40, no. 1, pp. 35-41, 1977.
[25] ANU College of Engineering & Computer Science. "collections of non-isomorphic graphs," Available: http://users.cecs.anu.edu.au/~bdm/data/graphs.html.
[26] Database of interesting graphs. "The House of Graphs," Available: https://hog.grinvin.org.
[27] Generate graphs. "Generate all unlabeled simple graphs on a given number of vertices," Available: http://combos.org/nauty.
[28] Regular Graphs Page. "Connected regular graphs," Available: http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html.
[29] P. Cordella, P. Foggia, C. Sansone, M. Vento, “An improved algorithm for matching large graphs”, In Proceedings of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations, May 2001, Ischia, Italy, pp. 149-159.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار