The work is devoted to methods for comparing and classifying graphs. This trend is known as "graph matching". An overview of metrics for comparing graphs based on the maximum common subgraph is given. A modification of the distance based on the maximum common subgraph, which takes into account the ordering of the vertices, is proposed. It is shown that this function satisfies all the properties of the metric (non-negativity, identity, symmetry, triangle inequality).
Download file
Counter downloads: 56
- Title Metric for comparing graphs with ordered vertices based on the maximum common subgraph
- Headline Metric for comparing graphs with ordered vertices based on the maximum common subgraph
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 52
- Date:
- DOI 10.17223/20710410/52/7
Keywords
graph, comparison, metric, maximum common subgraph, graph matchingAuthors
References
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.
Metric for comparing graphs with ordered vertices based on the maximum common subgraph | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 52. DOI: 10.17223/20710410/52/7
Download full-text version
Counter downloads: 153