Все выпуски

Задача поиска PageRank вектора представляет большой научный и практический интерес ввиду своей применимости к работе современных поисковых систем. Несмотря на то, что данная задача сводится к поиску собственного вектора стохастической матрицы $P$, потребность в новых алгоритмах для ее решения обусловлена большими размерами входных данных. Для достижения не более чем линейного времени работы применяются различные рандомизированные методы, возвращающие ожидаемый ответ лишь с некоторой достаточно близкой к единице вероятностью. Нами рассматриваются два таких способа, сводящие задачу поиска вектора PageRank к задаче поиска равновесия в антагонистической матричной игре, которая затем решается с помощью алгоритма Григориадиса – Хачияна. При этом данная реализация эффективно работает в предположении о разреженности матрицы, подаваемой на вход. Насколько нам известно, до сих пор не было ни одной успешной реализации ни алгоритма Григориадиса – Хачияна, ни его применения к задаче поиска вектора PageRank. Данная статья ставит перед собой задачу восполнить этот пробел. В работе приводится описание двух версий алгоритма с псевдокодом и некоторые детали их реализации. Кроме того, в работе рассматривается другой вероятностный метод поиска вектора PageRank, а именно Markov chain Monte Carlo (MCMC), с целью сравнения результатов работы указанных алгоритмов на матрицах с различными значениями спектральной щели. Последнее представляет особый интерес, поскольку значение спектральной щели сильно влияет на скорость сходимости MCMC, и не оказывает никакого влияния на два других подхода. Сравнение проводилось на сгенерированных графах двух видов: цепочках и $d$-мерных кубах. Проведенные эксперименты, как и предсказывает теория, демонстрируют эффективность алгоритма Григориадиса – Хачияна по сравнению с MCMC для разреженных графов с маленьким значением спектральной щели. Весь код находится в открытом доступе, так чтобы все желающие могли воспроизвести полученные результаты самостоятельно, или же использовать данную реализацию в своих нуждах. Работа имеет чисто практическую направленность, никаких теоретических результатов авторами получено не было.

Рассматривается модель, описывающая пространственно-временную динамику сообщества, состоящего из трех популяций, представляющих звенья трофической цепи. Локальные взаимодействия популяций строятся по типу «хищник – жертва», причем хищник потребляет не только жертву, но и ресурс, составляющий рацион жертвы. В предыдущей работе автором был проведен анализ модели без учета пространственной неоднородности. Данное исследование продолжает модельное изучение сообщества, учитывая диффузию особей, а также направленные перемещения хищника. Предполагается, что хищник реагирует на пространственное изменение ресурса и жертвы, занимая области с более высокой плотностью или избегая их. В модели такое поведение описывается адвективным членом со скоростью, пропорциональной градиенту плотности ресурса и жертвы. Система рассматривается в одномерной области в предположении нулевых потоков через границу. Динамика модели определяется устойчивостью системы в окрестности пространственно-однородного равновесия к малым пространственно-неоднородным возмущениям. В работе проведен анализ возможности возникновения в системе волновой неустойчивости, приводящей к возникновению автоволн и неустойчивости Тьюринга, в результате которой образуются стационарные структуры. Получены достаточные условия существования обоих видов неустойчивости, определяющие границы области значений коэффициентов таксиса, при которых система может потерять устойчивость. Анализ влияния параметров локальной кинетики модели на возможность образования пространственных структур показал, что при положительном таксисе на ресурс возможна лишь неустойчивость Тьюринга, а при отрицательном — оба вида неустойчивости. Для поиска численного решения системы использован метод линий с расщеплением разностного оператора по физическим процессам. Пространственно-временная динамика системы представлена в нескольких вариантах, реализующих один из типов неустойчивости. В случае положительного таксиса на жертву в областях меньшего размера возможно как реализация автоволнового режима, так и образование стационарных структур; с увеличением области тьюринговы структуры не образуются. Если же таксис на жертву отрицательный, то стационарные структуры возникают в областях любого размера, периодические структуры появляются только в более крупных областях.

В статье рассматривается проблема рационального использования водных ресурсов на уровне региона. Приводится обзор существующих методов контроля качества и количества водных ресурсов на различных уровнях — от отдельных домохозяйств до мирового. В самой работе проблема рассматривается для регионов России с малой водообеспеченностью — количеством воды на человека в год. Особое внимание уделяется регионам, в которых данный показатель мал из-за природных особенностей региона, а не большого числа жителей. В таких регионах много ресурсов выделяется на различную водную инфраструктуру, в том числе водохранилища, переброску воды из соседних регионов. При этом основными потребителями воды являются промышленность и сельское хозяйство. В работе представлена динамическая двухуровневая модель, сопоставляющая потребление регионом воды и объем производства в регионе (валовый региональный продукт, ВРП). На верхнем уровне модели находится администрация региона (центр), назначающая плату за использование воды, а на нижнем — предприятия региона (агенты). Проведены аналитическое исследование и идентификация модели. Аналитическое исследование позволяет с помощью принципа максимума Понтрягина найти оптимальные управления агентов. Идентификация модели позволяет, используя статистические данные для региона, определить коэффициенты модели таким образом, чтобы она соответствовала данному региону. Для идентификации модели используются данные Росстата. Далее следует численное исследование модели для конкретных регионов с использованием алгоритма trust region reflective.

Для ряда регионов РФ с низким уровнем водообеспеченности приведены результаты идентификации модели на основе данных Росстата, а также возможные значения ВРП и потребления воды в зависимости от выбранной стратегии центра. Для многих регионов расчеты показывают возможность существенного (>20%) сокращения потребления воды при некотором сокращении производства (≈10%).

Приведенная в работе модель позволяет рассчитывать размер дополнительной платы за использование воды для достижения оптимального соотношения экономических и экологических последствий.