Node centrality for continuous-time quantum walks

Luca Rossi, Andrea Torsello, Edwin R. Hancock

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

Abstract

The study of complex networks has recently attracted increasing interest because of the large variety of systems that can be modeled using graphs. A fundamental operation in the analysis of complex networks is that of measuring the centrality of a vertex. In this paper, we propose to measure vertex centrality using a continuous-time quantum walk. More specifically, we relate the importance of a vertex to the influence that its initial phase has on the interference patterns that emerge during the quantum walk evolution. To this end, we make use of the quantum Jensen-Shannon divergence between two suitably defined quantum states. We investigate how the importance varies as we change the initial state of the walk and the Hamiltonian of the system. We find that, for a suitable combination of the two, the importance of a vertex is almost linearly correlated with its degree. Finally, we evaluate the proposed measure on two commonly used networks.

Original languageEnglish
Title of host publicationStructural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2014, Proceedings
PublisherSpringer Verlag
Pages103-112
Number of pages10
ISBN (Print)9783662444146
DOIs
Publication statusPublished - Aug 2014
Externally publishedYes
EventJoint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, S+SSPR 2014 - Joensuu, Finland
Duration: 20 Aug 201422 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8621 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceJoint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, S+SSPR 2014
Country/TerritoryFinland
CityJoensuu
Period20/08/1422/08/14

Keywords

  • Complex Network
  • Quantum Jensen-Shannon Divergence
  • Quantum Walk
  • Vertex Centrality

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Node centrality for continuous-time quantum walks'. Together they form a unique fingerprint.

Cite this