Все выпуски

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

Finding PageRank vector is of great scientific and practical interest due to its applicability to modern search engines. Despite the fact that this problem is reduced to finding the eigenvector of the stochastic matrix $P$, the need for new algorithms is justified by a large size of the input data. To achieve no more than linear execution time, various randomized methods have been proposed, returning the expected result only with some probability close enough to one. We will consider two of them by reducing the problem of calculating the PageRank vector to the problem of finding equilibrium in an antagonistic matrix game, which is then solved using the Grigoriadis – Khachiyan algorithm. This implementation works effectively under the assumption of sparsity of the input matrix. As far as we know, there are no successful implementations of neither the Grigoriadis – Khachiyan algorithm nor its application to the task of calculating the PageRank vector. The purpose of this paper is to fill this gap. The article describes an algorithm giving pseudocode and some details of the implementation. In addition, it discusses another randomized method of calculating the PageRank vector, namely, Markov chain Monte Carlo (MCMC), in order to compare the results of these algorithms on matrices with different values of the spectral gap. The latter is of particular interest, since the magnitude of the spectral gap strongly affects the convergence rate of MCMC and does not affect the other two approaches at all. The comparison was carried out on two types of generated graphs: chains and $d$-dimensional cubes. The experiments, as predicted by the theory, demonstrated the effectiveness of the Grigoriadis – Khachiyan algorithm in comparison with MCMC for sparse graphs with a small spectral gap value. The written code is publicly available, so everyone can reproduce the results themselves or use this implementation for their own needs. The work has a purely practical orientation, no theoretical results were obtained.

В нейробиологии исследование механизмов кодирования запахов требует анализа пространственных паттернов активации обонятельных структур (гломерул), реконструируемых по данным мультифотонной микроскопии. Однако отсутствие формального статистического аппарата для анализа обобщенных карт, полученных на группе животных, ограничивает воспроизводимость результатов и затрудняет синтез прогностических моделей. Для преодоления этих ограничений разработана методология анализа карт ольфакторной активности, суммарно зарегистрированных на нескольких животных, основанная на теории немаркированных случайных точечных процессов. Методология включает процедуру предобработки данных и алгоритм численного анализа, реализованный в среде R с использованием пакета spatstat. Предложенный подход позволяет: (1) перейти от исходных карт гломерулярной активности к точечным паттернам с сохранением информации о размерах гломерул; (2) выполнить анализ точечных паттернов и рассчитать пространственно-морфологические характеристики специфичных для каждого одоранта областей (доменов) устойчивой активации гломерул; (3) выполнить статистическую проверку гипотез о пространственной случайности точечных паттернов с использованием $K$-функции Рипли, $G$-функции ближайших соседей и метода Монте-Карло; (4) синтезировать параметрическую модель парных взаимодействий Штрауса, параметры которой $(r_{PI}, \gamma)$ имеют ясную биологическую интерпретацию — масштаб пространственного взаимодействия гломерул и силу комодуляции ответов соответственно.

Валидация методологии выполнена на экспериментальных данных, полученных на 24 лабораторных крысах (10 особей стимулированы камфорой, 14 — метилбензоатом). Подобранные модели Штрауса продемонстрировали близкие, но специфичные для каждого одоранта параметры: радиус взаимодействия $r_{PI}$ составил 150 мкм для камфоры и 120 мкм для метилбензоата, коэффициент взаимодействия $\gamma$ — 0,95 и 0,89 соответственно. Валидация с использованием $Q$-$Q$-графиков сглаженных остатков подтвердила адекватность моделей, а рассчитанные на этапе (2) суммарная площадь доменов (0,60 мм² и 0,73 мм²) и плотность реакций (38 и 43 точки/мм²) полностью согласуются с параметрическими сигнатурами $(r_{PI}, \gamma)$ моделей.

Предложенный подход обеспечивает воспроизводимую количественную оценку гломерулярных доменов в единой стереотаксической системе координат и может быть распространен на другие одоранты и биологические виды. Все выводы получены на наркотизированных животных; экстраполяция на активные обонятельные стратегии бодрствующих животных требует дополнительных исследований.

In neuroscience, the study of odor coding mechanisms requires the analysis of spatial activation patterns of olfactory structures (glomeruli) reconstructed from multiphoton microscopy data. However, the lack of a formal statistical framework for analyzing population-level summary maps limits result reproducibility and hinders the development of predictive models. To address these limitations, we developed a novel methodology for the analysis of olfactory activity maps aggregated across multiple animals, based on the theory of unmarked spatial point processes. The methodology includes a data preprocessing procedure and a numerical analysis algorithm implemented in the R environment using the spatstat package.

The proposed approach enables: (1) transformation of raw glomerular activity maps into point patterns while preserving information about glomerular sizes (replacing size information with local point density is a methodological compromise reflecting the “functional weight” of glomerular input); (2) analysis of point patterns based on spatial morphometric characteristics of domains — regions of stable glomerular activation in the olfactory bulb, each approximated by an ellipse, with ellipse parameters (center coordinates in stereotaxic space, major and minor axis lengths, orientation angles), areas, and intra-ellipse point densities reflecting odorant-specific response signatures; (3) statistical hypothesis testing for spatial randomness (Complete Spatial Randomness) using Ripley’s $K$-function, the nearest-neighbor G-function, and Monte Carlo simulations; (4) synthesis of a parametric pairwise interaction model (Strauss process), whose parameters $(r_{PI}, \gamma)$ have a clear biological interpretation — the spatial interaction scale of glomeruli and the strength of response comodulation, respectively.

The methodology was validated using experimental data obtained from 24 laboratory rats: 10 animals stimulated with camphor and 14 with methyl benzoate. The fitted Strauss models yielded close but odorant-specific parameters: interaction radii $r_{PI}$ of 150 $\mu$m (camphor) and 120 μm (methyl benzoate); interaction parameters $gamma$ of 0.95 and 0.89, respectively. The total domain areas (0.60 mm² and 0.73 mm²) and point densities (38 and 43 points/mm²) calculated at the first stage of analysis are fully consistent with the parametric signatures $(r_{PI}, \gamma)$ of the Strauss model. Model validation using $Q$-$Q$ plots of smoothed residuals confirmed their adequacy.

Our results are consistent with data previously obtained using genetic labeling and functional mapping techniques, demonstrating the correctness of the proposed methodology and the effectiveness of multiphoton laser scanning microscopy for such applications. The proposed framework provides reproducible quantitative assessment of glomerular domains within a unified stereotaxic coordinate system and can be extended to other odorants and biological species. All findings were obtained under anesthesia; extrapolation to active olfactory strategies in awake animals requires further investigation.

Изображения рельефа поверхности ультратонких магнитных пленок использовались для Монте-Карло моделирования в рамках ферромагнитной модели Изинга с целью исследования гистерезисных и термодинамических свойств наноматериалов. Для высокопроизводительных вычислений использовался параллельный сверхмасштабируемый алгоритм поиска равновесной конфигурации. Исследовано изменение распределения спинов на поверхности в процессе обращения намагниченности и динамика нанодоменной структуры тонких магнитных пленок под влиянием изменяющегося внешнего магнитного поля.

Images of surface topography of ultrathin magnetic films have been used for Monte Carlo simulations in the framework of the ferromagnetic Ising model to study the hysteresis and thermal properties of nanomaterials. For high performance calculations was used super-scalable parallel algorithm for the finding of the equilibrium configuration. The changing of a distribution of spins on the surface during the reversal of the magnetization and the dynamics of nanodomain structure of thin magnetic films under the influence of changing external magnetic field was investigated.

В работе рассматривается метод исследования панельных данных, основанный на использовании агломеративной иерархической кластеризации — группировки объектов на основании сходства и разли- чия их признаков в иерархию вложенных друг в друга кластеров. Применялись 2 альтернативных способа вычисления евклидовых расстояний между объектами — расстояния между усредненными по интервалу наблюдений значениями и расстояния с использованием данных за все рассматриваемые годы. Сравнивались 3 альтернативных метода вычисления расстояний между кластерами. В первом случае таким расстоянием считается расстояние между ближайшими элементами из двух кластеров, во втором — среднее по парам элементов, в третьем — расстояние между наиболее удаленными элементами. Исследована эффективность использования двух индексов качества кластеризации — индекса Данна и Силуэта для выбора оптимального числа кластеров и оценки статистической значимости полученных решений. Способ оценивания статистической достоверности кластерной структуры заключался в сравнении качества кластеризации, на реальной выборке с качеством кластеризаций на искусственно сгенерированных выборках панельных данных с теми же самыми числом объектов, признаков и длиной рядов. Генерация производилась из фиксированного вероятностного распределения. Использовались способы симуляции, имитирующие гауссов белый шум и случайное блуждание. Расчеты с индексом Силуэт показали, что случайное блуждание характеризуется не только ложной регрессией, но и ложной кластеризацией. Кластеризация принималась достоверной для данного числа выделенных кластеров, если значение индекса на реальной выборке оказывалось больше значения 95%-ного квантиля для искусственных данных. В качестве выборки реальных данных использован набор временных рядов показателей, характеризующих производство в российских регионах. Для этих данных только Силуэт показывает достоверную кластеризацию на уровне $p < 0.05$. Расчеты также показали, что значения индексов для реальных данных в целом ближе к значениям для случайных блужданий, чем для белого шума, но имеют значимые отличия и от тех, и от других. Визуально можно выделить скопления близко расположенных друг от друга в трехмерном признаковом пространстве точек, выделяемые также в качестве кластеров применяемым алгоритмом иерархической кластеризации.

The paper considers a method for studying panel data based on the use of agglomerative hierarchical clustering — grouping objects based on the similarities and differences in their features into a hierarchy of clusters nested into each other. We used 2 alternative methods for calculating Euclidean distances between objects — the distance between the values averaged over observation interval, and the distance using data for all considered years. Three alternative methods for calculating the distances between clusters were compared. In the first case, the distance between the nearest elements from two clusters is considered to be distance between these clusters, in the second — the average over pairs of elements, in the third — the distance between the most distant elements. The efficiency of using two clustering quality indices, the Dunn and Silhouette index, was studied to select the optimal number of clusters and evaluate the statistical significance of the obtained solutions. The method of assessing statistical reliability of cluster structure consisted in comparing the quality of clustering on a real sample with the quality of clustering on artificially generated samples of panel data with the same number of objects, features and lengths of time series. Generation was made from a fixed probability distribution. At the same time, simulation methods imitating Gaussian white noise and random walk were used. Calculations with the Silhouette index showed that a random walk is characterized not only by spurious regression, but also by “spurious clustering”. Clustering was considered reliable for a given number of selected clusters if the index value on the real sample turned out to be greater than the value of the 95% quantile for artificial data. A set of time series of indicators characterizing production in the regions of the Russian Federation was used as a sample of real data. For these data only Silhouette shows reliable clustering at the level p < 0.05. Calculations also showed that index values for real data are generally closer to values for random walks than for white noise, but it have significant differences from both. Since three-dimensional feature space is used, the quality of clustering was also evaluated visually. Visually, one can distinguish clusters of points located close to each other, also distinguished as clusters by the applied hierarchical clustering algorithm.

На финансовых рынках деривативы предлагают широкие возможности для инвестиций и хеджирования. Однако доминирующий пласт стохастических моделей требует наличия ликвидного рынка опционов для процесса калибровки. На неликвидных рынках, включая современный финансовый рынок РФ, это является критической проблемой.

В настоящей работе исследуется использование моделей реализованной волатильности и эмпирической рискнейтральной коррекции для оценки стоимости производных финансовых инструментов на один базовый актив. Применяются модель HARGL, обученная на исторических высокочастотных данных, и метод эмпирической мартингальной симуляции (Empirical Martingale Simulation, EMS) для корректировки сгенерированных траекторий. Выбор реализованной волатильности оправдан тем, что модель симулирует динамику интегрированной дисперсии и доходности актива, не требуя наличия поверхности волатильности. Выбор риск-нейтральной меры необходим для выполнения первой фундаментальной теоремы об отсутствии арбитража. В условиях неполного рынка таких мер существует бесконечное множество, поэтому алгоритм EMS выступает оптимальным правилом: он минимально искажает историческую динамику, но гарантирует строгую мартингальность процесса цены.

Процесс валидации включает проверку прогнозов волатильности, отсутствия арбитража, сходимости и сравнение с биржевыми котировками. Модель HARGL дает содержательно корректное описание распределения дисперсии (среднее значение показателя преобразования вероятностного интеграла (PIT) равно 0,46 при эталоне 0,5), показывая умеренно консервативное смещение: в 90% доверительный интервал попадает 96% значений. На неликвидных рынках такая консервативность является существенным плюсом. Сравнение с реальными котировками ванильных опционов показало, что модель, абсолютно не опираясь на опционные данные при калибровке, дала среднюю абсолютную ошибку всего 0,5 рубля. Для 26% инструментов цена оказалась между котировками покупки и продажи, остальные цены — выше котировки продажи. Умеренная переоценка активов подтверждает адекватность предложенного подхода. Вычислительная сходимость алгоритма достигается уже при 10 000 симуляциях. Анализ чувствительности выявил критическую важность процедуры EMS: оценка в физической мере без нее искажает цену на 37%. Также зафиксирована ожидаемая чувствительность к начальной цене актива (4,7%) и прогнозной дисперсии (6%).

В результате исследования показано, что связка HARGL и EMS представляет собой надежный вычислительный инструмент для оценки стоимости деривативов и хеджирования. Поскольку на выходе алгоритм формирует готовые траектории, он легко масштабируется на экзотические деривативы. Предложенный подход численно реализует условия фундаментальных теорем финансовой математики, обеспечивая устойчивую безарбитражную оценку инструментов в условиях острой нехватки ликвидности.

Derivatives offer broad opportunities for investment and hedging in financial markets. However, most stochastic pricing models rely on a liquid options market for calibration. In illiquid markets, including the current Russian financial market, this becomes a critical limitation.

This paper studies the use of realized-volatility models and an empirical risk-neutral correction for pricing derivatives written on a single underlying asset. The framework combines the HARGL model, estimated on historical high-frequency data, with the Empirical Martingale Simulation (EMS) technique used to adjust the simulated price paths. The choice of realized volatility is motivated by the fact that the model simulates both integrated variance and asset returns without requiring an implied-volatility surface. The choice of a risk-neutral measure is needed to satisfy the first fundamental theorem of asset pricing. In an incomplete market, infinitely many such measures exist, so EMS is used as an operational rule: it alters the historical dynamics as little as possible while enforcing strict martingality of the price process.

The validation procedure includes volatility-forecast testing, no-arbitrage checks, convergence analysis, and comparison with exchange-traded option quotes. The HARGL model describes the variance distribution accurately, with a mean PIT value of 0.46 versus the benchmark value of 0.5, while showing a moderately conservative bias: 96% of the observations fall inside the 90% confidence interval. In an illiquid market, such conservatism is a meaningful advantage. A comparison with observed vanilla option quotes shows that, even without using option data in calibration, the model gives a mean absolute pricing error of only 0.5 rubles. For 26% of the instruments, the model price falls inside the bid–ask spread, while the remaining prices lie slightly above the ask quote. This moderate upward bias supports the adequacy of the framework. The algorithm reaches numerical convergence already at 10 000 simulations. The sensitivity analysis shows that EMS is critically important: pricing under the physical measure without this correction distorts the option value by 37%. The expected sensitivity to the initial asset price (4.7%) and to forecast variance (6%) is also documented.

The results show that the HARGL – EMS combination provides a reliable computational tool for pricing and hedging. Since the algorithm produces full simulated paths, it can be extended naturally to exotic derivatives. In this sense, the framework gives a numerical implementation of the core ideas behind the fundamental theorems of asset pricing and provides a stable no-arbitrage valuation procedure under severe illiquidity.