By the same authors

From the same journal

From the same journal

A Quantum-inspired Similarity Measure for the Analysis of Complete Weighted Graphs

Research output: Contribution to journalArticle

Full text download(s)

Published copy (DOI)

Author(s)

Department/unit(s)

Publication details

JournalIEEE Transactions on Cybernetics
DateAccepted/In press - 19 Apr 2019
DatePublished (current) - 28 Apr 2019
Number of pages13
Original languageEnglish

Abstract

We develop a novel method for measuring the similarity between complete weighted graphs, which are probed by means of discrete-time quantum walks. Directly probing complete graphs using discrete-time quantum walks is intractable due to the cost of simulating the quantum walk. We overcome this problem by extracting a commute-time minimum spanning tree from the complete weighted graph. The spanning tree is probed by a discrete time quantum walk which is initialised using a weighted version of the Perron-Frobenius operator. This naturally encapsulates the edge weight information for the spanning tree extracted from the original graph. For each pair of complete weighted graphs to be compared, we simulate a discrete-time quantum walk on each of the corresponding commute time minimum spanning trees, and then compute the associated density matrices for the quantum walks. The probability of the walk visiting each edge of the spanning tree is given by the diagonal elements of the density matrices. The similarity between each pair of graphs is then computed using either a) the inner product or b) the negative exponential of the Jensen-Shannon divergence between the probability distributions. We show that in both cases the resulting similarity measure is positive definite and therefore corresponds to a kernel on the graphs. We perform a series of experiments on publicly available graph datasets from a variety of different domains, together with time-varying financial networks extracted from data for the New York Stock Exchange. Our experiments demonstrate the effectiveness of the proposed similarity measures.

Bibliographical note

This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

    Research areas

  • cs.DS

Discover related content

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

View graph of relations