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

Full text not available from this repository.

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
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Computer Systems Technology
Related URLs:	Publisher Publisher Publisher
Last Modified:	20 Oct 2016 16:38
URI:	http://gala.gre.ac.uk/id/eprint/1230

Actions (login required)

View Item