### 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 | |

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 | Finland |

City | Joensuu |

Period | 20/08/14 → 22/08/14 |

### Fingerprint

### Keywords

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

### Cite this

*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

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 -