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

Fingerprint

Quantum Walk
Centrality
Complex networks
Continuous Time
Hamiltonians
Vertex of a graph
Complex Networks
Quantum State
Walk
Divergence
Linearly
Interference
Vary
Evaluate
Graph in graph theory

Keywords

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

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). Berlin (DE): Springer. https://doi.org/10.1007/978-3-662-44415-3_11
Rossi, Luca ; Torsello, Andrea ; Hancock, Edwin R. / Node centrality for continuous-time quantum walks. Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, S+SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings. editor / Pasi Fränti ; Gavin Brown ; Marco Loog ; Francisco Escolano ; Marcello Pelillo. Berlin (DE) : Springer, 2014. pp. 103-112 (Lecture notes in computer science).
@inproceedings{032b0c62a3a245d0a6c17305b326fbba,
title = "Node centrality for continuous-time quantum walks",
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.",
keywords = "complex network, quantum Jensen-Shannon divergence, quantum walk, vertex centrality",
author = "Luca Rossi and Andrea Torsello and Hancock, {Edwin R.}",
year = "2014",
month = "12",
day = "31",
doi = "10.1007/978-3-662-44415-3_11",
language = "English",
isbn = "978-3-662-44414-6",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "103--112",
editor = "Pasi Fr{\"a}nti and Gavin Brown and Marco Loog and Francisco Escolano and Marcello Pelillo",
booktitle = "Structural, Syntactic, and Statistical Pattern Recognition",
address = "Germany",

}

Rossi, L, Torsello, A & Hancock, ER 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. Lecture notes in computer science, vol. 8621, Springer, Berlin (DE), pp. 103-112, Joint IAPR international workshop on Structural, Syntactic, and Statistical Pattern Recognition, Joensuu, Finland, 20/08/14. https://doi.org/10.1007/978-3-662-44415-3_11

Node centrality for continuous-time quantum walks. / Rossi, Luca; Torsello, Andrea; Hancock, Edwin R.

Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, S+SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings. ed. / Pasi Fränti; Gavin Brown; Marco Loog; Francisco Escolano; Marcello Pelillo. Berlin (DE) : Springer, 2014. p. 103-112 (Lecture notes in computer science; Vol. 8621).

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

TY - GEN

T1 - Node centrality for continuous-time quantum walks

AU - Rossi, Luca

AU - Torsello, Andrea

AU - Hancock, Edwin R.

PY - 2014/12/31

Y1 - 2014/12/31

N2 - 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.

AB - 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.

KW - complex network

KW - quantum Jensen-Shannon divergence

KW - quantum walk

KW - vertex centrality

UR - http://www.scopus.com/inward/record.url?scp=84906311483&partnerID=8YFLogxK

UR - http://link.springer.com/chapter/10.1007%2F978-3-662-44415-3_11

U2 - 10.1007/978-3-662-44415-3_11

DO - 10.1007/978-3-662-44415-3_11

M3 - Conference contribution

AN - SCOPUS:84906311483

SN - 978-3-662-44414-6

T3 - Lecture notes in computer science

SP - 103

EP - 112

BT - Structural, Syntactic, and Statistical Pattern Recognition

A2 - Fränti, Pasi

A2 - Brown, Gavin

A2 - Loog, Marco

A2 - Escolano, Francisco

A2 - Pelillo, Marcello

PB - Springer

CY - Berlin (DE)

ER -

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