# A critical examination of node-similarity based graph matching algorithms

Zhao, Guoxing, Petridis, Miltos, Sidorov, Grigori and Ma, Jixin (2008) *A critical examination of node-similarity based graph matching algorithms.* Research In Computing Science, 40. pp. 73-82. ISSN 1870-4069

## Abstract

In this paper, we shall critically examine a special class of graph matching algorithms that follow the approach of node-similarity measurement. A high-level algorithm framework, namely node-similarity graph matching framework (NSGM framework), is proposed, from which, many existing graph matching algorithms can be subsumed, including the eigen-decomposition method of Umeyama, the polynomial-transformation method of Almohamad, the hubs and authorities method of Kleinberg, and the kronecker product successive projection methods of Wyk, etc. In addition, improved algorithms can be developed from the NSGM framework with respects to the corresponding results in graph theory. As the observation, it is pointed out that, in general, any algorithm which can be subsumed from NSGM framework fails to work well for graphs with non-trivial auto-isomorphism structure.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | graph matching, node-similarity |

Subjects: | Q Science > QA Mathematics |

School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Computer Systems Technology School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science |

Related URLs: | |

Last Modified: | 31 Mar 2011 18:20 |

URI: | http://gala.gre.ac.uk/id/eprint/1230 |

### Actions (login required)

View Item |