Node centrality for continuous-time quantum walks

Luca Rossi, Andrea Torsello, Edwin R. Hancock

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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
Subtitle of host publicationJoint IAPR International Workshop, S+SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings
EditorsPasi Fränti, Gavin Brown, Marco Loog, Francisco Escolano, Marcello Pelillo
Place of PublicationBerlin (DE)
PublisherSpringer
Pages103-112
Number of pages10
ISBN (Electronic)978-3-662-44415-3
ISBN (Print)978-3-662-44414-6
DOIs
Publication statusPublished - 31 Dec 2014
EventJoint IAPR international workshop on Structural, Syntactic, and Statistical Pattern Recognition - Joensuu, Finland
Duration: 20 Aug 201422 Aug 2014

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume8621
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopJoint IAPR international workshop on Structural, Syntactic, and Statistical Pattern Recognition
Abbreviated titleS+SSPR 2014
CountryFinland
CityJoensuu
Period20/08/1422/08/14

Keywords

  • complex network
  • quantum Jensen-Shannon divergence
  • quantum walk
  • vertex centrality

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

  • Research Output

    • 1 Conference contribution

    Transitive state alignment for the quantum jensen-shannon kernel

    Torsello, A., Gasparetto, A., Rossi, L., Bai, L. & Hancock, E. R., 31 Dec 2014, Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR international workshop, S+SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings. Fränti, P., Brown, G., Loog, M., Escolano, F. & Pelillo, M. (eds.). Berlin (DE): Springer, p. 22-31 10 p. (Lecture notes in computer science; vol. 8621).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Cite this

    Rossi, L., Torsello, A., & Hancock, E. R. (2014). Node centrality for continuous-time quantum walks. In P. Fränti, G. Brown, M. Loog, F. Escolano, & M. Pelillo (Eds.), Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, S+SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings (pp. 103-112). (Lecture notes in computer science; Vol. 8621). Springer. https://doi.org/10.1007/978-3-662-44415-3_11