Журнал вычислительной математики и математической физики
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Ж. вычисл. матем. и матем. физ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Журнал вычислительной математики и математической физики, 2015, том 55, номер 3, страницы 355–371
DOI: https://doi.org/10.7868/S0044466915030060
(Mi zvmmf10164)
 

Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)

Об эффективных рандомизированных алгоритмах поиска вектора PageRank

А. В. Гасниковab, Д. Ю. Дмитриевba

a 141000 Долгопрудный, М.о., Институтский пер., 9, МФТИ
b ИППИ РАН
Список литературы:
Аннотация: В работе рассматриваются два рандомизированных способа поиска вектора PageRank, т.е. решения системы $\mathbf{p}^{\mathrm{T}}=\mathbf{p}^{\mathrm{T}}P$, со стохастической матрицей $P$ размера $n\times n$ (решение ищется в классе распределений вероятностей), где $n\sim 10^7$$10^9$, с точностью $\varepsilon: \varepsilon\gg n^{-1}$, таким образом исключается возможность “честного” умножения матрицы $P$ на столбец, если рассматривать не разреженные объекты. Первый способ базируется на идее Markov chain Monte Carlo. Этот подход эффективен в случае “быстрого” выхода итерационного процесса $\mathbf{p}_{t+1}^{\mathrm{T}}=\mathbf{p}_t^{\mathrm{T}}P$ на стационар, и учитывает также другую специфику матрицы $P$ — равенство отличных от нуля вне диагональных элементов матрицы $P$ по строчкам (это используется при организации случайного блуждания по графу с матрицей $P$). На основе современных неравенств концентрации меры в работе приводятся новые оценки времени работы такого метода, учитывающие специфику матрицы $P$. В основе второго способа лежит идея сведения поиска ранжирующего вектора к поиску равновесия в антагонистической матричной игре:
$$ \min_{\mathbf{p}\in S_n(1)}\max_{\mathbf{u}\in S_n(1)}\langle \mathbf{u}, (P^{\mathrm{T}}-I)\mathbf{p}\rangle, $$
где $S_n(1)$ — единичный симплекс в $\mathbb{R}^n$, а $I$ — единичная матрица. Возникшая задача решается с помощью небольшой модификации алгоритма Григориадиса–Хачияна (1995). Этот метод, также как метод Назина–Поляка (2009), является рандомизированным вариантом метода зеркального спуска А. С. Немировского. Отличие заключается в том, что у Григориадиса–Хачияна рандомизация осуществляется на этапе проектирования на симплекс, а не на этапе вычисления стохастического градиента. Для разреженных матриц $P$ предложенный нами метод показывает заметно лучшие результаты. Библ. 67.
Ключевые слова: метод зеркального спуска, Markov chain Monte Carlo, стохастическая оптимизация, рандомизация, PageRank.
Поступила в редакцию: 03.09.2014
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2015, Volume 55, Issue 3, Pages 349–365
DOI: https://doi.org/10.1134/S0965542515030069
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.62
MSC: Primary 68W20; Secondary 90C15, 90C47, 90C90
Образец цитирования: А. В. Гасников, Д. Ю. Дмитриев, “Об эффективных рандомизированных алгоритмах поиска вектора PageRank”, Ж. вычисл. матем. и матем. физ., 55:3 (2015), 355–371; Comput. Math. Math. Phys., 55:3 (2015), 349–365
Цитирование в формате AMSBIB
\RBibitem{GasDmi15}
\by А.~В.~Гасников, Д.~Ю.~Дмитриев
\paper Об эффективных рандомизированных алгоритмах поиска вектора PageRank
\jour Ж. вычисл. матем. и матем. физ.
\yr 2015
\vol 55
\issue 3
\pages 355--371
\mathnet{http://mi.mathnet.ru/zvmmf10164}
\crossref{https://doi.org/10.7868/S0044466915030060}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3334436}
\zmath{https://zbmath.org/?q=an:06458213}
\elib{https://elibrary.ru/item.asp?id=22995522}
\transl
\jour Comput. Math. Math. Phys.
\yr 2015
\vol 55
\issue 3
\pages 349--365
\crossref{https://doi.org/10.1134/S0965542515030069}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000352701800001}
\elib{https://elibrary.ru/item.asp?id=24024017}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84928170216}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf10164
  • https://www.mathnet.ru/rus/zvmmf/v55/i3/p355
  • Эта публикация цитируется в следующих 8 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Статистика просмотров:
    Страница аннотации:705
    PDF полного текста:258
    Список литературы:92
    Первая страница:9
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024