By the same authors

From the same journal

String edit distance, random walks and graph matching

Research output: Contribution to journalArticlepeer-review

Author(s)

Department/unit(s)

Publication details

JournalINTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE
DatePublished - 1 May 2004
Issue number3
Volume18
Number of pages13
Pages (from-to)315-327
Original languageEnglish

Abstract

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 normalized 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 minimize edit distance.

    Research areas

  • Markov chains, graph seriation, graph-spectral methods, ALGORITHM, RECOGNITION

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations