Comparing classical and quantum PageRanks

T. Loke, J. W. Tang, J. Rodriguez, M. Small, J. B. Wang*

*Corresponding author for this work

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

Following recent developments in quantum PageRanking, we present a comparative analysis of discrete-time and continuous-time quantum-walk-based PageRank algorithms. Relative to classical PageRank and to different extents, the quantum measures better highlight secondary hubs and resolve ranking degeneracy among peripheral nodes for all networks we studied in this paper. For the discrete-time case, we investigated the periodic nature of the walker’s probability distribution for a wide range of networks and found that the dominant period does not grow with the size of these networks. Based on this observation, we introduce a new quantum measure using the maximum probabilities of the associated walker during the first couple of periods. This is particularly important, since it leads to a quantum PageRanking scheme that is scalable with respect to network size.

Original languageEnglish
Article number25
Pages (from-to)1-22
Number of pages22
JournalQuantum Information Processing
Volume16
Issue number1
DOIs
Publication statusPublished - Jan 2017
Externally publishedYes

Keywords

  • Szegedy quantum walk
  • open system quantum walk
  • network analysis
  • PageRanking

Fingerprint Dive into the research topics of 'Comparing classical and quantum PageRanks'. Together they form a unique fingerprint.

  • Cite this

    Loke, T., Tang, J. W., Rodriguez, J., Small, M., & Wang, J. B. (2017). Comparing classical and quantum PageRanks. Quantum Information Processing, 16(1), 1-22. [25]. https://doi.org/10.1007/s11128-016-1456-z