Unraveling complex systems: the Backtracking Method

The configuration space of a 3-regular graph with 12 nodes. The attractors in the red/cyan colours, and their basin of attraction is in blue and yellow.  © 2023 EPFL/Freya Behrens- CC-BY-SA 4.0

The configuration space of a 3-regular graph with 12 nodes. The attractors in the red/cyan colours, and their basin of attraction is in blue and yellow. © 2023 EPFL/Freya Behrens- CC-BY-SA 4.0

Scientists at EPFL and Charles University have developed a new method to analyze the dynamical, out-of-equilibrium properties of complex disordered systems, such as gold with magnetic impurities or opinions spreading on social media.

In physics, a "disordered system" refers to a physical system whose components – e.g. its atoms – are not organized in any discernible way. Like a drawer full of random socks, a disordered system lacks a well-defined, ordered pattern due to various factors like impurities, defects, or interactions between components.

This randomness makes it difficult to predict the system’s behavior accurately. And given that disordered systems are found in anything from materials science to climate or social networks and beyond, this limitation can be a serious, real-life problem.

Now, a team of scientists led by Lenka Zdeborová at EPFL have developed a novel approach to understanding how things change and evolve in disordered systems, even when they are undergoing rapid changes, like a temperature change. The study was carried out by Freya Behrens at Zdeborová’s lab, and Barbora Hudcová visiting EPFL from the Charles University in Prague.

The approach is called the Backtracking Dynamical Cavity Method (BDCM) and it works by looking first at the end state of the system rather than the beginning; instead of studying the system's trajectory forward from the start, it traces the steps backward from stable points.

But why “cavity”? The term comes from the “Cavity Method” in statistical physics and refers to isolating a particular component of a complex system to make it easier to study – putting it in a conceptual “hole” or “cavity” while ignoring all the other components.

In a similar way, the BDCM isolates a specific component of the disordered system, but working instead backwards to understand its evolution throughout time. This innovative twist provides valuable insights about the system's dynamic properties, even when it is far from equilibrium, like how materials cool down or how opinions on a social network evolve, or even how our brains work.

“From our early results, we saw that it can be quite deceiving to only look at the number of attractors of the system,” says Freya Behrens, referring to stable states that a system settles into over time. “Just because there are many attractors of a given type, it does not mean your dynamics end up there. But we really did not expect that taking just a few steps back from the attractor into its basin would reveal so many details about the complete dynamics. It was quite surprising."

Applying the BDCM to a random arrangement of magnets, the scientists found out what happens to their energy of when they rapidly cool down or what type of patterns they form when they start with different arrangements.

What I like a lot about this work is that we obtained theoretical answers to basic yet open questions about the dynamics of the Ising model, among the most studied models in statistical physics,” says Lenka Zdeborová. “The method we developed is very versatile, indicating that it will find many applications in studies of the dynamics of complex interacting systems, for which the Ising model is one of the simplest examples. Some application areas I can foresee include social dynamics, learning in neural networks or, for instance, gene regulation. I am looking forward to seeing the follow-up work!”


Czech project AI & Reasoning

European Regional Development Fund

Charles University


Freya Behrens, Barbora Hudcová, Lenka Zdeborová. The Backtracking Dynamical Cavity Method. Physical Review X 13, 031021, 21 August 2023. DOI: 10.1103/PhysRevX.13.031021

Author: Nik Papageorgiou

Source: EPFL

This content is distributed under a Creative Commons CC BY-SA 4.0 license. You may freely reproduce the text, videos and images it contains, provided that you indicate the author’s name and place no restrictions on the subsequent use of the content. If you would like to reproduce an illustration that does not contain the CC BY-SA notice, you must obtain approval from the author.