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 HancockThis 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
2396Pagination
104 - 112Publisher DOI
Link to full text
ISSN
0302-9743eISSN
1611-3349ISBN-13
9783540440116ISBN-10
3540440119Publication classification
E1.1 Full written paper - refereedTitle of proceedings
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC