CoChat

Quantum Google in a Complex Network

Open access
Paparo, Giuseppe Davide, Müller, Markus, Comellas, Francesc, Martin-Delgado, Miguel Angel · 2013 · Scientific Reports
Cited by 93

The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.

Abstract

We investigate the behaviour of the recently proposed Quantum PageRank algorithm, in large complex networks. We find that the algorithm is able to univocally reveal the underlying topology of the network and to identify and order the most relevant nodes. Furthermore, it is capable to clearly highlight the structure of secondary hubs and to resolve the degeneracy in importance of the low lying part of the list of rankings. The quantum algorithm displays an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance, as compared to the classical algorithm. We test the performance and confirm the listed features by applying it to real world examples from the WWW. Finally, we raise and partially address whether the increased sensitivity of the quantum algorithm persists under coordinated attacks in scale-free and random networks.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/srep02773

Cites

19 of 19 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 48

  1. Brin, S. & Page, L. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems 30, 107–117 (1998). · DOI · Paper page
  2. Watts, D. & Strogatz, S. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998). · DOI · Paper page
  3. Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999). · DOI · Paper page
  4. Barabási, A.-L., Dezso, Z., Ravasz, E., Yook, S.-H. & Oltvai, Z. Scale-free and hierarchical structures in complex networks. In AIP Conference Proceedings, vol. 661, 1 (2003).
  5. Newman, M. E. The structure and function of complex networks. SIAM Review 45, 167–256 (2003). · DOI · Paper page
  6. Newman, M. Networks: an introduction (Oxford University Press, Inc., 2010). · DOI · Paper page
  7. Cohen, R. & Havlin, S. Complex networks: structure, robustness and function (Cambridge University Press, 2010). · DOI · Paper page
  8. Barabási, A.-L. Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371, ( 2013 March 28). · DOI · Paper page
  9. 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 132–139 (Society for Industrial and Applied Mathematics, 2003).
  10. Elliott, C. The DARPA quantum network. Quantum Communications and cryptography 83–102 (2006). · DOI
  11. Poppe, A., Peev, M. & Maurhart, O. Outline of the secoqc quantum-key-distribution network in Vienna. International Journal of Quantum Information 6, 209–218 (2008). · DOI
  12. Sasaki, M. et al. Field test of quantum key distribution in the tokyo qkd network. Optics Express 19, 10387–10409 (2011). · DOI · Paper page
  13. Lancho, D., Martinez, J., Elkouss, D., Soto, M. & Martin, V. Qkd in standard optical telecommunications networks. Quantum Communication and Quantum Networking 142–149 (2010). · DOI
  14. Länger, T. & Lenhart, G. Standardization of quantum key distribution and the etsi standardization initiative isg-qkd. New Journal of Physics 11, 055051 (2009). · DOI
  15. Szegedy, M. Quantum speed-up of Markov chain based algorithms. In: Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on 32–41 (IEEE, 2004). · DOI
  16. Albert, R. & Barabási, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47 (2002). · DOI · Paper page
  17. Barabási, A.-L., Albert, R. & Jeong, H. Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: Statistical Mechanics and its Applications 281, 69–77 (2000). · DOI · Paper page
  18. Barrat, A., Barthelemy, M., Pastor-Satorras, R. & Vespignani, A. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America 101, 3747–3752 (2004). · DOI · Paper page
  19. Jeong, H., Mason, P., Barabasi, A.-L. & Oltvai, Z. Lethality and centrality in protein networks. Nature 411, 41–42 (2001). · DOI · Paper page
  20. Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. & Barabási, A.-L. The large-scale organization of metabolic networks. Nature 407, 651–654 (2000). · DOI · Paper page
  21. Albert, R., Jeong, H. & Barabási, A.-L. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000). · DOI · Paper page
  22. Callaway, D. S., Newman, M. E., Strogatz, S. H. & Watts, D. J. Network robustness and fragility: Percolation on random graphs. Phys. Rev. Lett. 85, 5468–5471 (2000). · DOI · Paper page
  23. Vázquez, A. & Moreno, Y. Resilience to damage of graphs with degree correlations. Phys. Rev. E 67, 015101 (2003). · DOI · Paper page
  24. Carmi, S., Carter, S., Sun, J. & Ben-Avraham, D. Asymptotic behavior of the Kleinberg model. Phys. Rev. Lett. 102, 238702 (2009). · DOI
  25. Lee, S. H. & Holme, P. Exploring maps with greedy navigators. Phys. Rev. Lett. 108, 128701 (2012). · DOI
  26. Liu, Y.-Y., Slotine, J.-J. & Barabási, A.-L. Controllability of complex networks. Nature 473, 167–173 (2011). · DOI · Paper page
  27. Nepusz, T. & Vicsek, T. Controlling edge dynamics in complex networks. Nat. Phys. 8, 568–573 (2012). · DOI · Paper page
  28. Nicosia, V., Criado, R., Romance, M., Russo, G. & Latora, V. Controlling centrality in complex networks. Sci. Rep. 2, 218 (2012). 10.1038/srep00218 · DOI · Paper page
  29. Albert, R., Jeong, H. & Barabasi, A.-L. Diameter of the world wide web. Nature 401, 130–131 (1999). · DOI · Paper page
  30. Erdős, P. & Rényi, A. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl 5, 17–61 (1960).
  31. Erdős, P. & Rényi, A. On the strength of connectedness of a random graph. Acta Mathematica Hungarica 12, 261–267 (1961). · DOI · Paper page
  32. Barabási, A.-L., Ravasz, E. & Vicsek, T. Deterministic scale-free networks. Physica A: Statistical Mechanics and its Applications 299, 559–564 (2001). · DOI · Paper page
  33. Noh, J. D. Exact scaling properties of a hierarchical network model. Phys. Rev. E 67, 045103 (2003). · DOI · Paper page
  34. Comellas, F. & Miralles, A. Modeling complex networks with self-similar outerplanar unclustered graphs. Physica A: Statistical Mechanics and its Applications 388, 2227–2233 (2009). · DOI
  35. Comellas, F. & Miralles, A. Vertex labeling and routing in self-similar outerplanar unclustered graphs modeling complex networks. Journal of Physics A: Mathematical and Theoretical 42, 425001 (2009). · DOI
  36. Brandstädt, A., Le, V. B. & Spinrad, J. P. Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, vol. 3. (Society for Industrial and Applied Mathematics, 1999). · doi:10.1137/1.9780898719796
  37. Evers, F. & Mirlin, A. D. Anderson transitions. Rev. Mod. Phys. 80, 1355 (2008). · DOI · Paper page
  38. Georgeot, B., Giraud, O. & Shepelyansky, D. L. Spectral properties of the Google matrix of the world wide web and other directed networks. Phys. Rev. E 81, 056109 (2010). · DOI · Paper page
  39. Galindo, A. & Martin-Delgado, M. A. Information and computation: Classical and quantum aspects. Rev. Mod. Phys. 74, 347 (2002). · DOI · Paper page
  40. Nielsen, M. A. & Chuang, I. L. Quantum computation and quantum information (Cambridge university press, 2010).
  41. Lo, H.-K., Spiller, T. & Popescu, S. Introduction to quantum computation and information (World Scientific Publishing Company, 1998). · DOI · Paper page
  42. Donato, D., Laura, L., Leonardi, S. & Millozzi, S. Large scale properties of the webgraph. The European Physical Journal B-Condensed Matter and Complex Systems 38, 239–243 (2004). · DOI
  43. Kendall, M. G. & Smith, B. B. The problem of m rankings. The annals of mathematical statistics 275–287 (1939). · DOI · Paper page
  44. Cuquet, M. & Calsamiglia, J. Growth of graph states in quantum networks. Phys. Rev. A 86, 042304 (2012). URL http://link.aps.org/doi/10.1103/PhysRevA.86.042304. · DOI
  45. Venegas-Andraca, S. E. Quantum walks: a comprehensive review. Quantum Information Processing 1–92 (2012). · DOI · Paper page
  46. de Lima Marquezino, F., Portugal, R. & Boettcher, S. Spatial search algorithms on hanoi networks. Phys. Rev. A 87, 012329 (2013). · DOI
  47. Verstraete, F., Wolf, M. M. & Cirac, J. I. Quantum computation and quantum-state engineering driven by dissipation. Nat. Phys. 5, 633–636 (2009). · DOI · Paper page
  48. Diehl, S. et al. Quantum states and phases in driven open quantum systems with cold atoms. Nat. Phys. 4, 878–883 (2008). · DOI · Paper page

Cited by

See all 93

Metadata

Authors
Paparo, G. D., Müller, M., Comellas, F., & Martin-Delgado, M. A.
Venue
Scientific Reports
Published
2013-10-04
Volume
3
Issue
1
Pages
2773-2773
ISSN
2045-2322 (ISSN-L)
OpenAlex
W2117676143
Cited by
93
References
19
FWCI
6.70
Type
journal article
Language
en
Open access
gold
Licence

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.