Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
arXiv:2104.09637 · doi:10.1093/comnet/cnab038
Abstract
In this work we introduce, test and discuss three quantum methods for computing hub and authority centrality scores in directed networks. The methods are based on unitary, continuous-time quantum walks; the construction of a suitable Hermitian Hamiltonian is achieved by performing a quantum walk on the associated bipartite graph. Two methods, called CQAu and CQAw, use the same evolution operator, inspired by the classical HITS algorithm, but with different initial states; the computation of hub and authority scores is performed simultaneously. The third method, called CQG and inspired by classical PageRank, requires instead two separate runs with different evolution operators, one for hub and one for authority scores. The methods are tested on several directed graphs with different sizes and properties; a comparison with other well-established ranking algorithms is provided. CQAw emerges as the most reliable of the three methods and yields rankings that are largely compatible with results from HITS, although CQAu and CQG also present interesting features and potential for applications.
References in corpus (15)
- Quantum Computation and Decision Trees
- Quantum walks: a comprehensive review
- Exponential algorithmic speedup by quantum walk
- An example of the difference between quantum and classical random walks
- Creating superpositions that correspond to efficiently integrable probability distributions
- Google in a Quantum Network
- Quantum Navigation and Ranking in Complex Networks
- Adiabatic quantum algorithm for search engine ranking
- Quantum Random Walks do not need a Coin Toss
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Centrality measure based on continuous-time quantum walks and experimental realization
- Discrete-time quantum walk on complex networks for community detection
- Discrete-time quantum walk algorithm for ranking nodes on a network
- Experimental parity-time symmetry quantum walks on a directed graph
- Quantum centrality testing on directed graphs via PT-symmetric quantum walks