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

В работе рассматриваются два рандомизированных способа поиска вектора 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.