Matching graphs with unique node labels

作者：Dickinson PJ^*; Bunke H; Dadej A; Kraetzl M

来源：Pattern Analysis and Applications, 2004, 7(3): 243-254.

DOI：10.1007/s10044-044-0222-5

• graph matching
• graph isomorphism
• maximum common subgraph
• graph edit distance
• median graph
• unique node label

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.

• 出版日期2004-12