Four new centrality measures for directed networks based on unitary, continuous-time quantum walks (CTQW) in n dimensions—where n is the number of nodes—are presented, tested and discussed. The main idea behind these methods consists in re-casting the classical HITS and PageRank algorithms as eigenvector problems for symmetric matrices, and using these symmetric matrices as Hamiltonians for CTQWs, in order to obtain a unitary evolution operator. The choice of the initial state is also crucial. Two options were tested: a vector with uniform occupation and a vector weighted w.r.t. in- or out-degrees (for authority and hub centrality, respectively). Two methods are based on a HITS-derived Hamiltonian, and two use a PageRank-derived Hamiltonian. Centrality scores for the nodes are defined as the average occupation values. All the methods have been tested on a set of small, simple graphs in order to spot possible evident drawbacks, and then on a larger number of artificially generated larger-sized graphs, in order to draw a comparison with classical HITS and PageRank. Numerical results show that, despite some pathologies found in three of the methods when analyzing small graphs, all the methods are effective in finding the first and top ten nodes in larger graphs. We comment on the results and offer some insight into the good accordance between classical and quantum approaches.

Ranking nodes in directed networks via continuous-time quantum walks

Boito P.;
2023-01-01

Abstract

Four new centrality measures for directed networks based on unitary, continuous-time quantum walks (CTQW) in n dimensions—where n is the number of nodes—are presented, tested and discussed. The main idea behind these methods consists in re-casting the classical HITS and PageRank algorithms as eigenvector problems for symmetric matrices, and using these symmetric matrices as Hamiltonians for CTQWs, in order to obtain a unitary evolution operator. The choice of the initial state is also crucial. Two options were tested: a vector with uniform occupation and a vector weighted w.r.t. in- or out-degrees (for authority and hub centrality, respectively). Two methods are based on a HITS-derived Hamiltonian, and two use a PageRank-derived Hamiltonian. Centrality scores for the nodes are defined as the average occupation values. All the methods have been tested on a set of small, simple graphs in order to spot possible evident drawbacks, and then on a larger number of artificially generated larger-sized graphs, in order to draw a comparison with classical HITS and PageRank. Numerical results show that, despite some pathologies found in three of the methods when analyzing small graphs, all the methods are effective in finding the first and top ten nodes in larger graphs. We comment on the results and offer some insight into the good accordance between classical and quantum approaches.
2023
Boito, P.; Grena, R.
File in questo prodotto:
File Dimensione Formato  
QW_ranking_QIP.pdf

accesso aperto

Descrizione: Pre-print
Tipologia: Documento in Pre-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 402.29 kB
Formato Adobe PDF
402.29 kB Adobe PDF Visualizza/Apri
s11128-023-03975-6.pdf

non disponibili

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - accesso privato/ristretto
Dimensione 642.2 kB
Formato Adobe PDF
642.2 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1183907
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact