Вокруг степенного закона распределения компонент вектора PageRank. Часть 2. Модель Бакли-Остгуса, проверка закона для этой модели и устройство реальных поисковых систем
А.В. Гасников1,2, П.Е. Двуреченский2,3, М.Е. Жуковский1,4, С.В. Ким5, С.С. Плаунов5, Д.А. Смирнов5, Ф.А. Носков6
1Московский физико-технический институт, Институтский пер., 9, Долгопрудный, Московская обл., 141700
gasnikov.av@mipt.ru
2Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Большой Каретный пер., 19, строение 1, Москва, 127051
pavel.dvurechensky@wias-berlin.de
3Институт прикладного анализа и стохастики им. К. Вейерштрасса, Моренштрассе, 39, Берлин, Германия, 10117
4ООО «Яндекс», ул. Льва Толстого, 16, Москва, 119034
zhukmax@yandex-team.ru
5Государственное бюджетное образовательное учреждение «Физматшкола № 2007», ул. Горчакова, 9, корп. 1, Москва, 117042
kims230599@gmail.com
6Национальный исследовательский университет «Высшая школа экономики», ул. Мясницкая, д. 20, Москва, 101000
fedor.noskov.99@mail.ru
Ключевые слова: марковская цепь, эргодическая теорема, мультиномиальное распределение, концентрация меры, оценка максимального правдоподобия, Google problem, градиентный спуск, автоматическое дифференцирование, степенной закон распределения, Markov chain, ergodic theorem, multinomial distribution, measure concentration, maximum likelihood estimate, Google problem, gradient descent, automatic differentiation, power law distribution
Страницы: 23-45
Аннотация
Данная статья является продолжением статьи [12]. В этой, второй части, работы рассматривается модель Бакли-Остгуса формирования сети Интернет. Для сетей, порожденных этой моделью, проводятся численные эксперименты по вычислению вектора PageRank. Обнаруживается степенной закон распределения компонент этого вектора. Обсуждаются вычислительные аспекты этой модели в контексте описанных в первой статье [12] численных способов поиска вектора PageRank. Описаны более общая модель ранжирования web-страниц и подходы к решению задачи оптимизации, возникающей при обучении этой модели.
DOI: 10.15372/SJNM20180102 |
