Matching graphs with unique node labels |
| |
Authors: | Peter?J?Dickinson Email author" target="_blank">Horst?BunkeEmail author Arek?Dadej Miro?Kraetzl |
| |
Affiliation: | (1) ISR Division, DSTO, PO Box 1500, 5111 Edinburgh, SA, Australia;(2) Institut für Informatik und angewandte Mathematik, Universit:at Bern, CH-3012 Neubrückstrasse 10, Bern, Switzerland;(3) ITR, University of South Australia, 5095 Mawson Lakes, SA, Australia |
| |
Abstract: | A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence
of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that
problems such as graph isomorphism, subgraph isomorphism, maximum common subgraph (MCS) and graph edit distance (GED) have
a computational complexity that is only quadratic in the number of nodes. Moreover, computing the median of a set of graphs
is only linear in the cardinality of the set. In a series of experiments, it is demonstrated that the proposed algorithms
run very fast in practice. The considered class makes the matching of large graphs, consisting of thousands of nodes, computationally
tractable. We also discuss an application of the considered class of graphs and related matching algorithms to the classification
and detection of abnormal events in computer networks. |
| |
Keywords: | Graph matching Graph isomorphism Maximum common subgraph Graph edit distance Median graph Unique node label |
本文献已被 SpringerLink 等数据库收录! |
|