Geodesic
About the power law of the PageRank vector distribution. Part~1. Numerical methods for finding the PageRank vector
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 4, pp. 359-378.

Voir la notice de l'article provenant de la source Math-Net.Ru

In Part 1 of this paper, we consider the web-pages ranking problem also known as the problem of finding the PageRank vector or Google problem. We discuss the connection of this problem with the ergodic theorem and describe different numerical methods to solve this problem together with their theoretical background, such as Markov Chain Monte Carlo and equilibrium in a macrosystem. 
@article{SJVM_2017_20_4_a1,
     author = {A. Gasnikov and E. Gasnikova and P. Dvurechensky and A. Mohammed and E. Chernousova},
     title = {About the power law of the {PageRank} vector distribution. {Part~1.} {Numerical} methods for finding the {PageRank} vector},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {359--378},
     publisher = {mathdoc},
     volume = {20},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a1/}
}
TY  - JOUR
AU  - A. Gasnikov
AU  - E. Gasnikova
AU  - P. Dvurechensky
AU  - A. Mohammed
AU  - E. Chernousova
TI  - About the power law of the PageRank vector distribution. Part~1. Numerical methods for finding the PageRank vector
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2017
SP  - 359
EP  - 378
VL  - 20
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a1/
LA  - ru
ID  - SJVM_2017_20_4_a1
ER  - 
%0 Journal Article
%A A. Gasnikov
%A E. Gasnikova
%A P. Dvurechensky
%A A. Mohammed
%A E. Chernousova
%T About the power law of the PageRank vector distribution. Part~1. Numerical methods for finding the PageRank vector
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2017
%P 359-378
%V 20
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a1/
%G ru
%F SJVM_2017_20_4_a1
A. Gasnikov; E. Gasnikova; P. Dvurechensky; A. Mohammed; E. Chernousova. About the power law of the PageRank vector distribution. Part~1. Numerical methods for finding the PageRank vector. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 4, pp. 359-378. http://geodesic.mathdoc.fr/item/SJVM_2017_20_4_a1/

[1] Agaev R. P., Chebotarev P. Yu., “Skhodimost i ustoichivost v zadachakh soglasovaniya kharakteristik (obzor bazovykh rezultatov)”, Upravlenie bolshimi sistemami, 30.1, 2010, 470–505

[2] Anikin A. S., Gasnikov A. V., Gornov A. Yu., Kamzolov D. I., Maksimov Yu. V., Nesterov Yu. E., “Effektivnye chislennye metody resheniya zadachi PageRank dlya dvazhdy razrezhennykh matrits”, Trudy MFTI, 7:4 (2015), 74–94

[3] Arnold V. I., Tsepnye drobi, Biblioteka “Matematicheskoe prosveschenie”, 14, Izd-vo MTsNMO, M., 2001

[4] Baimurzina D. R., Gasnikov A. V., Gasnikova E. V., “Teoriya makrosistem s tochki zreniya stokhasticheskoi khimicheskoi kinetiki”, Trudy MFTI, 7:4 (2015), 95–103

[5] Batischeva Ya. G., Vedenyapin V. V., “II-i zakon termodinamiki dlya khimicheskoi kinetiki”, Mat. modelirovanie, 17:8 (2005), 106–110 | MR | Zbl

[6] Blank M. L., Ustoichivost i lokalizatsiya v khaoticheskoi dinamike, Izd-vo MTsNMO, M., 2001

[7] Bogdanov K. Yu., “Kinetika sotsialnogo neravenstva”, Kvant, 2004, no. 5, 7–12

[8] Bogdanov K. Yu., “Khischnik i zhertva: uravnenie sosuschestvovaniya”, Kvant, 2014, no. 4–5, 13–17

[9] Buzun N. O., Gasnikov A. V., Goncharov F. O., Gorbachev O. G., Guz S. A., Krymova E. A., Natan A. A., Chernousova E. O., Stokhasticheskii analiz v zadachakh, Chast 1, Izd-vo MFTI, M., 2016

[10] Vaidlikh V., Sotsiodinamika: sistemnyi podkhod k matematicheskomu modelirovaniyu v sotsialnykh naukakh, Per. s angl., 3-e izd., URSS, M., 2010

[11] Galperin G. A., Zemlyakov A. N., Matematicheskie bilyardy, Seriya “Bibliotechka Kvant”, 77, Nauka, M., 1990 | MR

[12] Gardiner K. V., Stokhasticheskie metody v estestvennykh naukakh, Mir, M., 1986 | MR

[13] Gasnikov A. V. i dr., Vvedenie v matematicheskoe modelirovanie transportnykh potokov, 2-e izd., Izd-vo MTsNMO, M., 2013

[14] Gasnikov A. V., Effektivnye chislennye metody poiska ravnovesii v bolshikh transportnykh setyakh, Dis. $\dots$ dokt. fiz.-mat. nauk: 05.13.18, Izd-vo MFTI, M., 2016

[15] Gasnikov A. V., Gasnikova E. V., “Ob entropiino-podobnykh funktsionalakh, voznikayuschikh v stokhasticheskoi khimicheskoi kinetike pri kontsentratsii invariantnoi mery i v kachestve funktsii Lyapunova dinamiki kvazisrednikh”, Mat. zametki, 94:6 (2013), 819–827 | DOI | MR | Zbl

[16] Gasnikov A. V., Gasnikova E. V., Mendel M. A., Chepurchenko K. V., “Evolyutsionnye vyvody entropiinoi modeli rascheta matritsy korrespondentsii”, Mat. modelirovanie, 28:4 (2016), 111–124 | MR | Zbl

[17] Gasnikov A. V., Dmitriev D. Yu., “Ob effektivnykh randomizirovannykh algoritmakh poiska vektora PageRank”, Zhurn. vychisl. matem. i mat. fiziki, 55:3 (2015), 355–371 | DOI | MR | Zbl

[18] Ermakov S. M., Metod Monte-Karlo v vychislitelnoi matematike. Vvodnyi kurs, Binom. Laboratoriya znanii, M., 2009

[19] Zang V.-B., Sinergeticheskaya ekonomika: vremya i peremeny v nelineinoi ekonomicheskoi teorii, Mir, M., 1999

[20] Zorich V. A., Matematicheskii analiz zadach estestvoznaniya, Izd-vo MTsNMO, M., 2008

[21] Ibragimov I. A., Khasminskii R. Z., Asimptoticheskaya teoriya otsenivaniya, Nauka, M., 1979 | MR

[22] Kalinkin A. V., “Markovskie vetvyaschiesya protsessy s vzaimodeistviem”, Uspekhi mat. nauk, 57:2(344) (2002), 23–84 | DOI | MR | Zbl

[23] Kats M., Veroyatnost i smezhnye voprosy v fizike, Mir, M., 1965

[24] Kelbert M. Ya., Sukhov Yu. M., Markovskie tsepi kak otpravnaya tochka teorii sluchainykh protsessov i ikh prilozhenii. Veroyatnost i statistika v primerakh i zadachakh, v. 2, Izd-vo MTsNMO, M., 2010

[25] Krasnoselskii M. A., Krein S. G., “Zamechanie o raspredelenii oshibok pri reshenii sistemy lineinykh uravnenii pri pomoschi iteratsionnogo protsessa”, Uspekhi mat. nauk, 7:4(50) (1952), 157–161 | MR | Zbl

[26] Krasnoselskii M. A., Lifshits E. A., Sobolev A. V., Pozitivnye lineinye sistemy. Metod polozhitelnykh operatorov, Nauka, M., 1985 | MR

[27] Lagutin M. B., Naglyadnaya matematicheskaya statistika, Uchebnoe posobie, 3-e izd., Binom. Laboratoriya znanii, M., 2013

[28] Malyshev V. A., Pirogov S. A., “Obratimost i neobratimost v stokhasticheskoi khimicheskoi kinetike”, Uspekhi mat. nauk, 63:1(379) (2008), 3–36 | DOI | MR | Zbl

[29] Nikaido Kh., Vypuklye struktury i matematicheskaya ekonomika, Mir, M., 1972

[30] Polyak B. T., Tremba A. A., “Reshenie zadachi PageRank dlya bolshikh matrits s pomoschyu regulyarizatsii”, Avtomatika i telemekhanika, 2012, no. 11, 144–166 | Zbl

[31] Purmal A. P., Slobodetskaya E. M., Travin S. O., Kak prevraschayutsya veschestva, Seriya “Bibliotechka Kvant”, 36, Nauka, M., 1984

[32] Razzhevaikin V. N., Analiz modelei dinamiki populyatsii, Uchebnoe posobie, Izd-vo MFTI, M., 2010 | MR

[33] Raigorodskii A. M., Modeli interneta, Izd. dom “Intellekt”, Dolgoprudnyi, 2013

[34] Sanov I. N., “O veroyatnosti bolshikh otklonenii sluchainykh velichin”, Mat. sbornik, 42(84):1 (1957), 11–44 | MR | Zbl

[35] Sinai Ya. G., “Kak matematiki izuchayut khaos”, Mat. prosveschenie, 5, 2001, 32–46

[36] Tikhomirov V. M., Rasskazy o maksimumakh i minimumakh, Seriya “Bibliotechka Kvant”, 56, Nauka, M., 1986 | MR

[37] Avrachenkov K., Lebedev D., “PageRank of scale-free growing networks”, Internet Math., 3:2 (2006), 207–232 | DOI | MR

[38] Aldous D., Fill J., Reversible Markov Chains and Random Walks on Graphs, University of California, Berkeley, 2002

[39] Ball K., “An elementary introduction to modern convex geometry”, Flavors of Geometry, MSRI Publ., 31, 1997, 1–58 | MR | Zbl

[40] Blum A., Hopcroft J., Kannan R., Foundations of Data Science, http://www.cs.cornell.edu/jeh/book.pdf

[41] Bogolubsky L., Dvurechensky P., Gasnikov A., Gusev G., Nesterov Yu., Raigorodskii A., Tikhonov A., Zhukovskii M., “Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods”, The Thirtieth Annual Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, 2016

[42] Boucheron S., Lugosi G., Massart P., Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013 | MR

[43] Brin S., Page L., “The anatomy of a large-scale hypertextual web search engine”, Comput. Network ISDN Syst., 30:1–7 (1998), 107–117 | DOI

[44] Diaconis P., “The Markov chain Monte Carlo revolution”, Bulletin (New Series) of the AMS, 49:2 (2009), 179–205 | MR

[45] Ethier N. S., Kurtz T. G., Markov Processes, John Wiley Sons Inc., New York, 1986 | MR | Zbl

[46] Chung F., “Laplacians and the Cheeger inequality for directed graphs”, Annals of Combinatorics, 9:1 (2005), 1–19 | DOI | MR | Zbl

[47] Franceschet M., “PageRank: Standing on the shoulders of giant”, Communication of ACM, 54:6 (2011), 92–101 | DOI

[48] Grechnikov E. A., “The degree distribution and the number of edges between nodes of given degrees in the Buckley-Osthus model of a random web graph”, Internet Math., 8:3 (2012), 257–287 | DOI | MR | Zbl

[49] Jaynes E. T., Probability Theory. The Logic of Science, Cambridge University Press, 2003 | MR | Zbl

[50] Joulin A., Ollivier Y., “Curvature, concentration and error estimates for Markov chain Monte Carlo”, The Annals of Probability, 38:6 (2010), 2418–2442 | DOI | MR | Zbl

[51] Kapur J. N., Maximum-Entropy Models in Science and Engineering, John Wiley Sons Inc., New York, 1989 | MR | Zbl

[52] Langville A. N., Meyer C. D., Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, 2006 | MR | Zbl

[53] Ledoux M., The Concentration of Measure Phenomenon, Math. Surveys Monogr., 89, AMS, Providence, RI, 2001 | MR | Zbl

[54] Levin D. A., Peres Y., Wilmer E. L., Markov Chain and Mixing Times, AMS, 2009 | MR

[55] Lezaud P., “Chernoff-type bound for finite Markov chains”, The Annals of Applied Probability, 8:3 (1998), 849–867 | DOI | MR | Zbl

[56] Meyn S. P., Tweedie R. L., Markov Chains and Stochastic Stability, Springer-Verlag, London, 2005 | MR

[57] Montenegro R., Tetali P., “Mathematical aspects of mixing times in Markov chains”, Foundations and Trends in Theoretical Computer Science, 1:3 (2016), 237–354 | DOI | MR

[58] Nesterov Yu., Nemirovski A., “Finding the stationary states of Markov chains by iterative methods”, Appl. Math. and Comput., 255 (2015), 58–65 | MR | Zbl

[59] Pandurangan G., Raghavan P., Upfal E., “Using PageRank to characterize web structure”, Internet Math., 3:1 (2006), 1–20 | DOI | MR | Zbl

[60] Paulin D., “Concentration inequalities for Markov chains by Marton couplings”, Electron J. Probab., 20:79 (2015), 1–32 | MR

[61] Sandholm W., Population Games and Evolutionary Dynamics. Economic Learning and Social Evolution, MIT Press, Cambridge, 2010 | MR

[62] Spielman D., Lecture No 7, , 2009 http://www.cse.cuhk.edu.hk/~chi/csc5160/notes/L07.pdf

[63] Spokoiny V., “Parametric estimation. Finite sample theory”, The Annals of Statistics, 10:6 (2012), 2877–2909 | DOI | MR

[64] Van Handel R., Probability in High Dimension, Lecture Notes ORF 570, Princeton University, 2014

[65] Chaos IX: Chaotic or not? Chaos research today, http://www.chaos-math.org/fr/chaos-ix-chaotique-ou-pas