Understanding and quantifying the out-of-equilibrium dynamics is one of the major tasks of today's science. Using dynamic cavity method on time trajectories, we show how to derive dynamic message-passing (DMP) equations for a large class of models with irreversible dynamics - the key point that makes the problem solvable. These equations are asymptotically exact for locally tree-like graphs and generally provide a good approximation for real-world networks. We illustrate the approach by applying the DMP equations for susceptible-infected-recovered (SIR) and ignorant-spreader-stifler models (ISS) models to the problems of inference of epidemic origin and optimal information spreading with awareness.
Мы рассмотрим задачу о планарных паросочетаниях на линии, заданную случайной матрицей контактов, и покажем, что существование планарной структуры возможно только при плотности контактов, превышающей некоторое критическое значение p_c. Используя формализм полевых моделей и случайных блужданий, а также комбинаторные аргументы, мы получим аналитическую оценку точки перехода, которая оказывается близка к значению p_с ≈ 0.379, полученному с помощью точного численного моделирования. Наконец, мы обсудим связь исследуемой критической модели с известным фазовым переходом в стекольную фазу, изученным в контексте образования вторичной структуры в случайных РНК. В частности, мы покажем, что переход в стекольную фазу при нулевой температуре происходит в точке p_c.