Graph embedding using quantum commute times

David Emms; Richard C. Wilson; Edwin Hancock

Graph embedding using quantum commute times

David Emms, Richard C. Wilson, Edwin Hancock

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we explore analytically and experimentally the commute time of the continuous-time quantum walk. For the classical random walk, the commute time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the commute time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum commute times with reference to their classical counterpart. Experimentally, we show that the quantum commute times can be used to emphasise cluster-structure.

Original language	English
Pages (from-to)	371-382
Number of pages	12
Journal	Graph-Based Representations in Pattern Recognition, Proceedings
Volume	4538
Publication status	Published - 2007

Keywords

RANDOM-WALKS

Cite this

@article{75cad773c2f844ca9075e96c21c3ca92,

title = "Graph embedding using quantum commute times",

abstract = "In this paper, we explore analytically and experimentally the commute time of the continuous-time quantum walk. For the classical random walk, the commute time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the commute time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum commute times with reference to their classical counterpart. Experimentally, we show that the quantum commute times can be used to emphasise cluster-structure.",

keywords = "RANDOM-WALKS",

author = "David Emms and Wilson, {Richard C.} and Edwin Hancock",

year = "2007",

language = "English",

volume = "4538",

pages = "371--382",

journal = "Graph-Based Representations in Pattern Recognition, Proceedings",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

TY - JOUR

T1 - Graph embedding using quantum commute times

AU - Emms, David

AU - Wilson, Richard C.

AU - Hancock, Edwin

PY - 2007

Y1 - 2007

N2 - In this paper, we explore analytically and experimentally the commute time of the continuous-time quantum walk. For the classical random walk, the commute time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the commute time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum commute times with reference to their classical counterpart. Experimentally, we show that the quantum commute times can be used to emphasise cluster-structure.

AB - In this paper, we explore analytically and experimentally the commute time of the continuous-time quantum walk. For the classical random walk, the commute time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the commute time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum commute times with reference to their classical counterpart. Experimentally, we show that the quantum commute times can be used to emphasise cluster-structure.

KW - RANDOM-WALKS

M3 - Article

SN - 0302-9743

VL - 4538

SP - 371

EP - 382

JO - Graph-Based Representations in Pattern Recognition, Proceedings

JF - Graph-Based Representations in Pattern Recognition, Proceedings

ER -