علوم رایانش و فناوری اطلاعات

الگوریتمی ابتکاری جهت مسأله تشخیص یکریختی گراف‌ها مبتنی بر دوری از مرکز گراف

نویسندگان

دانشکده مهندسی کامپیوتر، دانشگاه تربیت دبیر شهید رجایی، تهران، ایران

چکیده

مسأله یکریختی گراف‌ها از مجموعه مسائل باز از لحاظ پیچیدگی محاسباتی است که فقط تعلق آن به کلاس NP مشخص است ولی تعلق آن به P یا NP-Complete مشخص نیست. راه‌حل مسأله در زمان چندجمله‌ای هنوز ناشناخته است و لذا زمینه برای تحقیق و ایده‌پردازی فراهم می‌باشد. از این رو الگوریتم‌های چندجمله­ای برای این مسأله جزو الگوریتم‌های ابتکاری محسوب می‌شوند. این مقاله به بررسی راه‌های تعیین یکریختی دو گراف متناهی با یکدیگر و ارائه یک روش ابتکاری جدید می‌پردازد. الگوریتمی پیشنهاد می‌شود که گراف ورودی را به یک رشته‌کد پرانتزی تبدیل می‌کند و سپس به جای مقایسه دو گراف رشته­ کدهای آن دو گراف با هم مقایسه می‌شوند و یکریختی یا عدم یکریختی میان آن‌ها تشخیص داده می‌شود. زمان اجرای این الگوریتمO(ne)i می‌باشد که در آن n تعداد رأس‌های گراف و e تعداد یال‌های گراف است و در دسته الگوریتم‌های "برچسب‌گذاری کانونی" برای گراف‌های "ساده، همبند و بدون برچسب" قرار دارد. بعد از پیاده­سازی این الگوریتم و بررسی نتایج آن مشخص شد که با عملکرد صحیح بیشتر از 99%، عدم یکریختی میان گراف‌های غیریکریخت به درستی تشخیص داده می‌شود.

کلیدواژه‌ها

  • [1] S. Wasserman, and K. Faust, "Social Network Analysis: Methods and Applications", 9th ed., United Kingdom: Cambridge University Press, 1994.
  • [2] Th. Coffman, S. Greenblatt, and Sh. Marcus, "Graph–based technologies for intelligence", Communications of the ACM, Vol. 47, No. 3, pp. 45–47, 2004.
  • [3] V. Lacroix, C. G. Fernandes, and M. F. Sagot, "Motif search in graphs: application to metabolic networks", IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Vol. 3, No. 4, pp. 360–368, 2006.
  • [4] T. Aittokallio, and B. Schwikowski, "Graph–based methods for analysing networks in cell biology", Briefings in Bioinformatics, Vol. 7, No. 3, pp. 243–255, 2006.
  • [5] M. Terzer, N. D. Maynard, M. W. Covert, and J. Stelling, "Genome‐scale metabolic networks", WIREs: Systems Biologhy and Medicine, Vol. 1, No. 3, pp. 285–297, 2009.
  • [6] L. P. Cordella, P. Foggia, and C. Sansone, "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 10, pp. 1367–1372, 2004.
  • [7] M. A. Abdulrahim, and M. Misra, "A Graph Isomorphism Algorithm for Object Recognition", Pattern Analysis and Applications, Vol. 1, No. 3, pp. 189–201, 1998.
  • [8] A. Aparo, V. Bonnici, G. Micale, A. Ferro, D. Shasha, A. Pulvirenti, and R. Giugno, "Fast Subgraph Matching Strategies Based on Pattern–Only Heuristics", Interdisciplinary Sciences: Computational Life Sciences, Vol. 11, No. 1, pp. 21–32, 2019.
  • [9] R. M. Karp, "Reducibility Among Combinatorial Problems", R. E. Miller; J. W. Thatcher; J.D. Bohlinger (eds.). Complexity of Computer Computations, New York: Plenum. pp. 85–103, 1972.
  • [10] S. D. Stoichev, "New Exact and Heuristic Algorithms for Graph Automorphism Group and Graph Isomorphism", Journal of Experimental Algorithmics (JEA), Vol. 24, No. 1, pp. 1-15, 2019.
  • [11] B. D. McKay, and A. Piperno, "Practical graph isomorphism, II", Journal of Symbolic Computation, Vol. 60, pp. 94-112, 2014.
  • [12] V. M. V. Rachna Somkunwar, "A Comparative Study of Graph Isomorphism Applications", International Journal of Computer Applications, Vol. 162, No. 7, pp. 34-37, 2017.
  • [13] G. Chartrand, L. Lesniak, and P. Zhang, "Graphs & Digraphs", (6th ed.). Chapman & Hall/CRC, 2015.
  • [14] A. Hou, Q. Zhong, Y. Chen, and Zh. Hao, "A Practical Graph Isomorphism Algorithm with Vertex Canonical Labeling", Journal of Computers (JCP), Vol. 9, No. 10, pp. 2467–2474, 2014.
  • [15] R. C. Read, D. G. Corneil, "The graph isomorphism disease", Graph Theory, Vol. 1, No. 4, pp. 339-363, 1977.
  • [16] P. D. G. Valiente, "Algorithms on Trees and Graphs", Springer, 2002.
  • [17] 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, pp. 569-584, 2019.
  • [18] T. P. Zivković, "On graph isomorphism and graph automorphism", Journal of Mathematical Chemistry, Vol. 8, No. 1, pp. 19–37, 1991.
  • [19] L. Babai, "Graph isomorphism in quasipolynomial time", Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC "16). ACM, New York, NY, USA, 684-697, 2016.
  • [20] J. E. Hopcroft, and J. Wong, "Linear time algorithm for isomorphism of planar graphs", Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172–184, 1974.
  • [21] E. M. Luks, "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, Vol. 25, pp. 42–65, 1982.
  • [22] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974.
  • [23] ANU College of Engineering & Computer Science. "collections of non-isomorphism graphs", Available: http://users.cecs.anu.edu.au/~ bdm/data/graphs.html.
  • [24] Graph canonical labeling and automorphism group computation. “Nauty and Traces”, Available: http://pallini.di.uniroma1.it/index.html.
  • [25] B. D. McKay, “Practical Graph Isomorphism”, Congressus Numerantium, Vol. 30, pp. 45-87, 1981.
  • [26] A. Piperno, “Search space contraction in canonical labeling of graphs”, preprint 2008 (v2: 2011). Available: http://arxiv.org/abs/0804.4881.
  • [27] The House of Graphs. “Database of interesting graphs”, Available: https://hog.grinvin.org/Init.action.
علوم رایانش و فناوری اطلاعات
دوره 17، شماره 2
پاییز و زمستان
آذر 1398