Geodesic
About the power law of the PageRank vector distribution. Part~2. Backley--Osthus model, power law verification for this model and setup of real search engines
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 21 (2018) no. 1, pp. 23-45.

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

In the second part of this paper, we consider the Buckley–Osthus model for the formation of a webgraph. For the networks generated according to this model, we numerically calculate the PageRank vector. We show that the components of this vector are distributed according to the power law. We also discuss the computational aspects of this model with respect to different numerical methods for the calculation of the PageRank vector, presented in the first part of the paper. Finally, we describe a general model for the web-page ranking and some approaches to solve the optimization problem arising when learning this model. 
@article{SJVM_2018_21_1_a1,
     author = {A. Gasnikov and P. Dvurechensky and M. Zhukovskii and S. Kim and S. Plaunov and D. Smirnov and F. Noskov},
     title = {About the power law of the {PageRank} vector distribution. {Part~2.} {Backley--Osthus} model, power law verification for this model and setup of real search engines},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {23--45},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2018_21_1_a1/}
}
TY  - JOUR
AU  - A. Gasnikov
AU  - P. Dvurechensky
AU  - M. Zhukovskii
AU  - S. Kim
AU  - S. Plaunov
AU  - D. Smirnov
AU  - F. Noskov
TI  - About the power law of the PageRank vector distribution. Part~2. Backley--Osthus model, power law verification for this model and setup of real search engines
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2018
SP  - 23
EP  - 45
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2018_21_1_a1/
LA  - ru
ID  - SJVM_2018_21_1_a1
ER  - 
%0 Journal Article
%A A. Gasnikov
%A P. Dvurechensky
%A M. Zhukovskii
%A S. Kim
%A S. Plaunov
%A D. Smirnov
%A F. Noskov
%T About the power law of the PageRank vector distribution. Part~2. Backley--Osthus model, power law verification for this model and setup of real search engines
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2018
%P 23-45
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2018_21_1_a1/
%G ru
%F SJVM_2018_21_1_a1
A. Gasnikov; P. Dvurechensky; M. Zhukovskii; S. Kim; S. Plaunov; D. Smirnov; F. Noskov. About the power law of the PageRank vector distribution. Part~2. Backley--Osthus model, power law verification for this model and setup of real search engines. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 21 (2018) no. 1, pp. 23-45. http://geodesic.mathdoc.fr/item/SJVM_2018_21_1_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] Baimurzina D. R., Gasnikov A. V., Gasnikova E. V., “Teoriya makrosistem s tochki zreniya stokhasticheskoi khimicheskoi kinetiki”, Tr. MFTI, 7:4 (2015), 95–103

[3] Barenblatt G. I., Avtomodelnye yavleniya – analiz razmernostei i skeiling, Izd. dom “Intellekt”, Dolgoprudnyi, 2009

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

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

[6] 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, ed. A. V. Gasnikov, Izd-vo MFTI, M., 2016

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

[8] Vasilev F. P., Metody optimizatsii, v. 2, Izd-vo MTsNMO, M., 2011

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

[10] A. V. Gasnikov (red.), Vvedenie v matematicheskoe modelirovanie transportnykh potokov, 2-e izd., Izd-vo MTsNMO, M., 2013

[11] 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

[12] 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

[13] Gasnikov A. V., Gasnikova E. V., Dvurechenskii P. E., Mokhammed A. A. M., Chernousova E. O., “Vokrug stepennogo zakona raspredeleniya komponent vektora PageRank. Chast 1. Chislennye metody poiska vektora PageRank”, Sib. zhurn. vychisl. matematiki (Novosibirsk), 20:4 (2017), 359–378 | DOI | MR

[14] Evtushenko Yu. G., Optimizatsiya i bystroe avtomaticheskoe differentsirovanie, Izd-vo VTs RAN, M., 2013 http://www.ccas.ru/personal/evtush/p/198.pdf

[15] Zhiglyavskii A. A., Zhilinskas A. G., Metody poiska globalnogo ekstremuma, Nauka, M., 1991 | MR

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

[17] Kabanikhin S. I., Obratnye i nekorrektnye zadachi, Sibirskoe nauchnoe izd-vo, Novosibirsk, 2009

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

[19] Litvak N., Raigorodskii A., Matematika informatsionnogo veka, MIF, M., 2017

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

[21] Nemirovskii A. S., Yudin D. B., Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, M., 1979 | MR

[22] Nesterov Yu. E., Vvedenie v vypukluyu optimizatsiyu, Izd-vo MTsNMO, M., 2010

[23] Polyak B. T., Vvedenie v optimizatsiyu, Nauka, M., 1983 | MR

[24] Podlazov A. V., “Zakon Tsipfa i modeli konkurentnogo rosta”, Novoe v sinergetike. Nelineinost v sovremennom estestvoznanii, ed. G. G. Malinetskii, Izd-vo “Librokom”, M., 2009, 229–256

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

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

[27] Raigorodskii A. M., Modeli Interneta, Izd. dom “Intellekt”, Dolgoprudnyi, 2013

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

[29] Chislennaya proverka stepennogo zakona raspredeleniya komponent vektora PageRank, , , https://github.com/KoIIdun/PageRhttps://github.com/KoIIdun/PageR/blob/master/data_exps/data_exp.txthttps://github.com/KoIIdun/PageRank-gradient

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

[31] Allen-Zhu Z., Hazan E., Variance Reduction for Faster Non-Convex Optimization, Preprint, Cornell University Library, Ithaca, 2016, arXiv: 1603.05643

[32] Baydin A. G., Pearlmutter B. A., Radul A. A., Siskand J. M., Automatic Differentiation in Machine Learning: a Survey, Preprint, Cornell University Library, Ithaca, 2016, arXiv: 1502.05767

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

[34] 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”, Advances in Neural Information Processing Systems, 29, eds. D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, R. Garnett, Curran Associates, Inc., 2016, 4914–4922

[35] 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

[36] Buffoni D., Gallinari P., Usunier N., Calauzenes C., “Learning scoring functions with order-preserving losses and standardized supervision”, Proc. of the 28th International Conference on Machine Learning (ICML-11), 2011, 825–832

[37] Burges C. J. C., From RankNet to LambdaRank to LambdaMART: An Overview, Microsoft Research Technical Report MSR-TR-2010-82, 2010

[38] Calauzenes C., Usunier N., Gallinari P., “On the (non-) existence of convex, calibrated surrogate losses for ranking”, Advances in Neural Information Processing Systems, 2012, 197–205

[39] Devolder O., Exactness, Inexactness and Stochasticity in First-Order Methods for Large-Scale Convex Optimization, PhD thesis, CORE UCL, Louvain, 2013

[40] Dvurechensky P., Gasnikov A., “Stochastic intermediate gradient method for convex problems with inexact stochastic oracle”, J. Optim. Theory Appl., 171:1 (2016), 121–145 | DOI | MR

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

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

[43] Ghadimi S., Lan G., “Accelerated gradient methods for nonconvex nonlinear and stochastic programming”, Math. Program., 156:1 (2016), 59–99 | DOI | MR

[44] Ghadimi S., Lan G., Zhang H., Generalized Uniformly Optimal Methods for Nonlinear Programming, Preprint, Cornell University Library, Ithaca, 2015, arXiv: 1508.07384

[45] Goodfellow I., Bengio Y., Courville A., Deep Learning, , MIT Press, 2016 http://www.deeplearningbook.org | MR

[46] 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

[47] Hardt M., Ma T., Identity Matters in Deep Learning, Preprint, Cornell University Library, Ithaca, 2015, arXiv: 1611.04231

[48] Hastie T., Tibshirani R., Friedman J., The Elements of Statistical Learning, Springer, 2014 | MR

[49] Jackson M. O., Social and Economics Networks, Princeton Univ. Press, 2008 | MR

[50] Jaynes E. T., Probability Theory. The Logic of Science, Cambridge Univ. Press, 2003 | MR

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

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

[53] Mitzenmacher M., “A brief history of generative models for power law and lognormal distributions”, Internet Math., 1:2 (2003), 226–251 | DOI | MR

[54] Nesterov Yu., “Efficiency of coordinate descent methods on large scale optimization problem”, SIAM J. Optim., 22:2 (2012), 341–362 | DOI | MR

[55] Nesterov Yu., “Gradient methods for minimizing composite functions”, Math. Progam., 140:1 (2013), 125–161 | DOI | MR

[56] Nesterov Yu., Random Gradient-Free Minimization of Convex Functions, CORE Discussion Paper # 2011/1, 2011

[57] Nesterov Yu., “Universal gradient methods for convex optimization problems”, Math. Program. Ser. A, 152 (2015), 381–404 | DOI | MR

[58] Newman M. E. J., Networks: An Introduction, Oxford Univ. Press, 2010 | MR

[59] Newman M. E. J., “Power laws, Pareto distributions and Zipf's law”, Contemporary physics, 46:5 (2005), 323–351 | DOI

[60] Nocedal J., Wright S., Numerical Optimization, Springer, 2006 | MR

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

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

[63] Shalev-Shwartz S., Ben-David S., Understanding Machine Learning: From Theory to Algorithms, Cambridge Univ. Press, 2014 | MR

[64] Wright S. J., Optimization algorithms for data science, IAS/Park City Math. Ser., , 2016 http://www.optimization-online.org/DB_FILE/2016/12/5748.pdf