Dynamic cavity method and problems on graphs
Andrey Lohhov, LPTMS
A large number of optimization, inverse, combinatorial and out-of-equilibrium problems, arising in the statistical physics of complex systems, allow for a convenient representation in terms of disordered interacting variables defined on a certain network. Although a universal recipe for dealing with these problems does not exist, the recent years have seen a serious progress in understanding and quantifying an important number of hard problems on graphs. A particular role has been played by the concepts borrowed from the physics of spin glasses and field theory, that appeared to be extremely successful in the description of the statistical properties of complex systems and in the development of efficient algorithms for concrete problems.
In the first part of the thesis, we study the out-of-equilibrium spreading problems on networks. Using dynamic cavity method on time trajectories, we show how to derive dynamic message-passing equations for a large class of models with unidirectional dynamics — the key property 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 dynamic message-passing equations for susceptible-infected-recovered model to the inverse problem of inference of epidemic origin.
In the second part of the manuscript, we address the optimization problem of finding optimal planar matching configurations on a line. Making use of field-theory techniques and combinatorial arguments, we characterize a topological phase transition that occurs in the simple Bernoulli model of disordered matching. As an application to the physics of the RNA secondary structures, we discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition at low temperatures, and suggest generalized models that incorporate a one-to-one correspondence between the contact matrix and the nucleotide sequence, thus giving sense to the notion of effective non-integer alphabets.