×

Comparing classical and quantum pageranks. (English) Zbl 1373.81114

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

MSC:

81P45 Quantum information, communication, networks (quantum-theoretic aspects)
05C81 Random walks on graphs
81S25 Quantum stochastic calculus

Software:

NetworkX; SciPy
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brin, S., Page, L.: Reprint of: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. 56, 3825 (2012) · doi:10.1016/j.comnet.2012.10.007
[2] Page, L., Brin, S., Motwani, R., Winograd, T.: The Pagerank Citation Ranking: Bringing Order to the Web, Technical Report, Stanford University, Stanford, CA (1998) · Zbl 1205.82086
[3] Ambainis, A.: Quantum walks and their algorithmic applications. Int. J. Quantum Inf. 1, 507 (2003) · Zbl 1069.81505 · doi:10.1142/S0219749903000383
[4] Paparo, G.D., Martin-Delgado, M.: Google in a quantum network. Sci. Rep. 2, 444 (2012)
[5] Sánchez-Burillo, E., Duch, J., Gómez-Gardeñes, J., Zueco, D.: Quantum navigation and ranking in complex networks. Sci. Rep. 2, 605 (2012)
[6] Montanaro, A.: Quantum walks on directed graphs. Quantum Inf. Comput. 7, 93 (2007) · Zbl 1152.81781
[7] Paparo, G.D., Müller, M., Comellas, F., Martin-Delgado, M.A.: Quantum Google in a complex network. Sci. Rep. 3 (2013)
[8] Berry, S.D., Wang, J.B.: Quantum-walk-based search and centrality. Phys. Rev. A 82, 042333 (2010) · doi:10.1103/PhysRevA.82.042333
[9] Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, pp. 32-41 (2004)
[10] Szegedy, M.: Spectra of quantized walks and a \[\sqrt{\delta \epsilon }\sqrt{δϵ}\] rule. arXiv: quant-ph/0401053 (2004)
[11] Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. ACM, pp. 50-59 (2001) · Zbl 1323.81020
[12] Childs, A.: Lecture 11: Discrete-time quantum walk. http://www.cs.umd.edu/ amchilds/teaching/w13/l11.pdf, 14 Aug 2015
[13] Schult, D.A., Swart, P.: Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in Science Conferences (SciPy 2008), vol. 2008, pp. 11-16 (2008)
[14] Chiang, C.-F., Nagaj, D., Wocjan, P.: Efficient circuits for quantum walks. Quantum Inf. Comput. 10, 420 (2010) · Zbl 1237.81047
[15] Loke, T., Wang, J.B.: Efficient quantum circuits for Szegedy quantum walks. arXiv:1609.00173 (2016) · Zbl 1366.81116
[16] Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915 (1998) · doi:10.1103/PhysRevA.58.915
[17] Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010) · Zbl 1288.81001
[18] Rivas, Á., Huelga, S.F.: Open Quantum Systems. Springer, Berlin (2012) · Zbl 1246.81006 · doi:10.1007/978-3-642-23354-8
[19] Saalfrank, P.: Open system density matrix theory: numerics and chemical applications. Course notes (1998-2000)
[20] Comellas, F., Miralles, A.: Modeling complex networks with self-similar outerplanar unclustered graphs. Phys. A 388, 2227 (2009) · Zbl 1180.90032 · doi:10.1016/j.physa.2009.02.004
[21] Comellas, F., Miralles, A.: Vertex labeling and routing in self-similar outerplanar unclustered graphs modeling complex networks. J. Phys. A Math. Theor. 42, 425001 (2009) · Zbl 1180.90032 · doi:10.1088/1751-8113/42/42/425001
[22] Everett, M.G.: Role similarity and complexity in social networks. Soc. Netw. 7, 353 (1985) · doi:10.1016/0378-8733(85)90013-9
[23] Borgatti, S.P., Everett, M.G.: Notions of position in social network analysis. Soc. Methodol. 22, 1 (1992) · doi:10.2307/270991
[24] Barabáasi, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286, 509 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[25] Albert, R., Jeong, H., Barabási, A.-L.: Internet: diameter of the world-wide web. Nature 401, 130 (1999) · doi:10.1038/43601
[26] Eguiluz, V.M., Chialvo, D.R., Cecchi, G.A., Baliki, M., Apkarian, A.V.: Scale-free brain functional networks. Phys. Rev. Lett. 94, 018102 (2005) · doi:10.1103/PhysRevLett.94.018102
[27] Albert, R.: Scale-free networks in cell biology. J. Cell Sci. 118, 4947 (2005) · doi:10.1242/jcs.02714
[28] Hein, D.-I.O., Schwind, D.-W.-I.M., König, W.: Scale-free networks. Wirtschaftsinformatik 48, 267 (2006) · doi:10.1007/s11576-006-0058-2
[29] Barabási, A.-L., et al.: Scale-free networks: a decade and beyond. Science 325, 412 (2009) · Zbl 1226.91052 · doi:10.1126/science.1173299
[30] Barabási, A.-L., Albert, R., Jeong, H.: Scale-free characteristics of random networks: the topology of the world-wide web. Phys. A 281, 69 (2000) · doi:10.1016/S0378-4371(00)00018-2
[31] Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Directed scale-free graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 132-139 (2003) · Zbl 1094.68605
[32] Gilbert, E.N.: Random graphs. Ann. Math. Stat. 30, 1141 (1959) · Zbl 0168.40801
[33] Erdös, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960) · Zbl 0103.16301
[34] Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47 (2002) · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[35] Martin, T., Zhang, X., Newman, M.: Localization and centrality in networks. Phys. Rev. E 90, 052808 (2014) · doi:10.1103/PhysRevE.90.052808
[36] Donato, D., Laura, L., Leonardi, S., Millozzi, S.: Large scale properties of the webgraph. Eur. Phys. J. B Condens. Matter Complex Syst. 38, 239 (2004) · doi:10.1140/epjb/e2004-00056-6
[37] Pandurangan, G., Raghavan, P., Upfal, E.: Using pagerank to characterize web structure. In: Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON), 2002 · Zbl 1077.68527
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.