О “Google problem” и эффективных рандомизированных алгоритмах поиска вектора PageRank (на основе совместных результатов с Ю.Е. Нестеровым и Д.Ю. Дмитриевым)

В докладе рассматриваются два рандомизированных способа поиска вектора PageRank, т.е. решения системы $p^{T}=p^{T}*P$ ($p^{T}$ - строка $p$), со стохастической матрицей $P$ размера $n \times n$ (решение ищется в классе распределения вероятностей), где $n \simeq 10^{8}$, т.о. исключается возможность “честного” умножения матрицы $P$ на столбец, если рассматривать не разреженные объекты. Первый способ базируется на идеи Markov chain Monte Carlo. Этот способ эффективен в случае “быстрого” выхода итерационного процесса $p_{t+1}^{T}=p_{t}^{T}*P$ на стационар, и учитывает также другую специфику матрицы $P$ – равенство отличных от нуля вне диагональных элементов матрицы $P$ по строчкам (это используется при организации случайного блуждания по графу с матрицей $P$). Другой способ использует только разреженность матрицы $P$. Его идея – свести поиск вектора к решению негладкой задачи выпуклой оптимизации: $\max_{k=1,...,n}{p^{T}*P^{<k>} - p_{k}} \to \min$ ( вектор $p$ - принадлежит единичному симплексу), где $P^{<k>}$ -k-ый столбец матрицы $P$. Возникшая задача решается рандомизированным (по Григориадису–Хачияну, 1995) вариантом метода зеркального спуска (для матричных игр). Этот метод приводит практически к таким же оценкам, что и предложенный Назиным–Поляком (2011) для поиска PageRank рандомизированный вариант метода зеркального спуска А.С. Немировского, но для разреженных матриц P предложенный метод показывает заметно лучшие результаты.