ГлавнаяАрхивМетрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа

Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа | Прикладная дискретная математика. 2021. № 52. DOI: 10.17223/20710410/52/7

Работа посвящена методам сравнения и классификации графов. Данное направление известно под названием «graph matching». Приводится обзор метрик для сравнения графов, основанных на максимальном общем подграфе. Предложена модификация расстояния на основе максимального общего подграфа, которое учитывает упорядоченность вершин. Показано, что эта функция удовлетворяет всем свойствам метрики (неотрицательность, тождественность, симметричность, неравенство треугольника).
  • Title Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа
  • Headline Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 52
  • Date:
  • DOI 10.17223/20710410/52/7
Ключевые слова
граф, сравнение, метрика, максимальный общий подграф, graph matching
Авторы
Ссылки
Conte D., Foggia P., Sansone C. , and Vento M. Thirty years of graph matching in pattern recognition // Int. J. Pattern Recognit. Artif. Intell. 2004. V. 18. No. 3. P.265-298.
Sharma H., Pawar A., Chourasia C., and Khatri S. Implementation of face recognition system based on elastic bunch graph matching // Intern. J. Engineering Sciences & Research Technology (IJESRT). 2016. V. 5. No. 3. P.888-895.
Schirmer S., Ponty Y., and Giegerich R. Introduction to RNA secondary structure comparison // RNA Sequence, Structure, and Function: Computational and Bioinformatic Methods. Methods in Molecular Biology. Totowa, NJ: Humana Press, 2014. V. 1097. P. 247-273.
Pawar V. and Zaveri M. K-Means graph database clustering and matching for fingerprint recognition // Intelligent Information Management. 2015. V. 7. No. 4. P.242-251.
Fischer A., Suen C., Frinken V., et al. A fast matching algorithm for graph-based handwriting recognition // LNCS. 2013. V. 7877. P. 194-203.
Ogaard K., Roy H., Kase S., et al. Discovering patterns in social networks with graph matching algorithms // LNCS. 2013. V. 7812. P.341-349.
Stauffer M., Fischer A., and Riesen K. Speeding-up graph-based keyword spotting in historical handwritten documents // LNCS. 2017. V. 10310. P.83-93.
Рогов А. А., Седов А. В., Сидоров Ю. В., Суровцова Т. Г. Математические методы атрибуции текстов. Петрозаводск: Изд-во ПетрГУ, 2014. 96 c.
Bunke H. and Shearer K. A graph distance metric based on the maximal common subgraph // Pattern Recognit. Lett. 1998. V. 19. No. 3-4. P. 255-259.
Wallis W., Shoubridge P. , Kraetz M. , and Ray D. Graph distances using graph union // Pattern Recognit. Lett. 2001. V.22. P.701-704.
Bunke H. On a relation between graph edit distance and maximum common subgraph // Pattern Recognit. Lett. 1997. V. 18. P. 689-694.
Кочкаров А. А., Сенникова Л. И. Метрические характеристики динамических графов и их применение // Новые информационные технологии в автоматизированных системах. М.: Московский институт электроники и математики НИУ ВШЭ, 2015. № 18. С. 236-241.
Bunke H., Foggia P., Guidobaldi C., et al. A comparison of algorithms for maximum common subgraph on randomly connected graphs // LNCS. 2002. V. 2396. P. 123-132.
Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа | Прикладная дискретная математика. 2021. № 52. DOI: 10.17223/20710410/52/7
Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа | Прикладная дискретная математика. 2021. № 52. DOI: 10.17223/20710410/52/7