Deakin University
Browse

File(s) not publicly available

String edit distance, random walks and graph matching

conference contribution
posted on 2002-01-01, 00:00 authored by Antonio Robles-KellyAntonio Robles-Kelly, E R Hancock
This paper shows how the eigenstructure of the adjacency matrix can be used for the purposes of robust graph-matching. We commence from the observation that the leading eigenvector of a transition probability matrix is the steady state of the associated Markov chain. When the transition matrix is the normalised adjacency matrix of a graph, then the leading eigenvector gives the sequence of nodes of the steady state random walk on the graph. We use this property to convert the nodes in a graph into a string where the node-order is given by the sequence of nodes visited in the random walk. We match graphs represented in this way, by finding the sequence of string edit operations which minimise edit distance.

History

Volume

2396

Pagination

104 - 112

ISSN

0302-9743

eISSN

1611-3349

ISBN-13

9783540440116

ISBN-10

3540440119

Publication classification

E1.1 Full written paper - refereed

Title of proceedings

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Usage metrics

    Research Publications

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC