Affiliations: Department of Applied Computer Science, University of Winnipeg, Portage avenue R3B 2E9, Manitoba, Canada. ch.henry@uwinnipeg.ca
Correspondence:
[†]
Address for correspondence: University Of Winnipeg, Department of Applied Computer Science, Winnipeg, R3B 2E9,
Canada.
Note: [*] The authors extend their profound thanks to Francesc Serratosa and Xavier Cortés for providing a Matlab implementation of their GED algorithm. This research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant 418413.
Abstract: This article proposes the tolerance nearness measure (TNM) as a computationally reduced alternative to the graph edit distance (GED) for performing graph comparisons. The TNM is defined within the context of near set theory, where the central idea is that determining similarity between sets of disjoint objects is at once intuitive and practically applicable. The TNM between two graphs is produced using the Bron-Kerbosh maximal clique enumeration algorithm. The result is that the TNM approach is less computationally complex than the bipartite-based GED algorithm. The contribution of this paper is the application of TNM to the problem of quantifying the similarity of disjoint graphs and that the maximal clique enumeration-based TNM produces comparable results to the GED when applied to the problem of content-based image processing, which becomes important as the number of nodes in a graph increases.
