Node centrality for continuous-time quantum walks

Luca Rossi; Andrea Torsello; Edwin R. Hancock

doi:10.1007/978-3-662-44415-3_11

Node centrality for continuous-time quantum walks

Luca Rossi, Andrea Torsello, Edwin R. Hancock

College of Engineering and Physical Sciences

Research output: Chapter in Book/Published conference output › Conference publication

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 language	English
Title of host publication	Structural, Syntactic, and Statistical Pattern Recognition
Subtitle of host publication	Joint IAPR International Workshop, S+SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings
Editors	Pasi Fränti, Gavin Brown, Marco Loog, Francisco Escolano, Marcello Pelillo
Place of Publication	Berlin (DE)
Publisher	Springer
Pages	103-112
Number of pages	10
ISBN (Electronic)	978-3-662-44415-3
ISBN (Print)	978-3-662-44414-6
DOIs	https://doi.org/10.1007/978-3-662-44415-3_11
Publication status	Published - 31 Dec 2014
Event	Joint IAPR international workshop on Structural, Syntactic, and Statistical Pattern Recognition - Joensuu, Finland Duration: 20 Aug 2014 → 22 Aug 2014

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	8621
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	Joint IAPR international workshop on Structural, Syntactic, and Statistical Pattern Recognition
Abbreviated title	S+SSPR 2014
Country/Territory	Finland
City	Joensuu
Period	20/08/14 → 22/08/14

Keywords

complex network
quantum Jensen-Shannon divergence
quantum walk
vertex centrality

Access to Document

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

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

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 = dec,

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",

note = "Joint IAPR international workshop on Structural, Syntactic, and Statistical Pattern Recognition, S+SSPR 2014 ; Conference date: 20-08-2014 Through 22-08-2014",

}

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/Published conference output › Conference publication

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 publication

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)

T2 - Joint IAPR international workshop on Structural, Syntactic, and Statistical Pattern Recognition

Y2 - 20 August 2014 through 22 August 2014

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). doi: 10.1007/978-3-662-44415-3_11

Node centrality for continuous-time quantum walks

Abstract

Publication series

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

Transitive state alignment for the quantum jensen-shannon kernel

Cite this