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