Вокруг степенного закона распределения компонент вектора PageRank. Часть 1. Численные методы поиска вектора PageRank
А.В. Гасников1,2, Е.В. Гасникова1, П.Е. Двуреченский2,3, А.А.М. Мохаммед1, Е.О. Черноусова1
1Московский физико-технический институт, Институтский пер., 9, Долгопрудный, Московская обл., 141700
gasnikov.av@mipt.ru
2Институт проблем передачи информации им. А.А. Харкевича РАН, Большой Каретный пер., 19, строение 1, Москва, 127051
pavel.dvurechensky@wias-berlin.de
3Институт прикладного анализа и стохастики им. К. Вейерштрасса, Моренштрассе, 39, Берлин, Германия, 10117
Ключевые слова: марковская цепь, эргодическая теорема, мультиномиальное распределение, концентрация меры, оценка максимального правдоподобия, Google problem, градиентный спуск, автоматическое дифференцирование, степенной закон распределения, Markov chain, ergodic theorem, multinomial distribution, measure concentration, maximum likelihood estimate, Google problem, gradient descent, automatic differentiation, power law distribution
Страницы: 359-378
Аннотация
В этой, первой из двух, части работы рассматривается задача поиска вектора рангов веб-страниц, также известная как задача поиска вектора PageRank и Google problem. Обсуждается связь этой задачи и эргодической теоремы, дается описание различных численных методов решения этой задачи и используемых в них теоретических конструкций, таких как Markov chain Monte Carlo, равновесие макросистемы.
DOI: 10.15372/SJNM20170402 |
