Papers for

complex network analysts

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Ising model dynamics speed up on random graphs with small initial bias

Improved rapid phase ordering for Ising dynamics on random regular graphs

Abstract: We study Glauber dynamics for the Ising model on random $d$-regular graphs with $n$ vertices at low temperature, in the regime $β\geq C/d$ where $C,d$ are sufficiently large constants. In this regime, the full mixing time is exponential in $n$, because of the bottleneck between the two dominant phases: configurations with a majority of plus spins and configurations with a majority of minus spins. We show that, for sufficiently large $d$, if the dynamics is initialized with an excess of at least $ε_{C,d} n$ plus spins over minus spins, then it quasi-equilibrates in time $O(\log n)$ to the Gibbs measure conditioned on positive magnetization. In addition, the required bias $ε_{C,d}$ can be chosen so that $ε_{C,d}\to 0$ as $d,C\to\infty$. Previous bound of \cite{GSS25+} in the Ising and large-$d$ setting required $β\gtrsim (\log d)/d$. A key difficulty is that, even from the all-plus initialization, one must control the propagation of negative information in spacetime in a low-temperature model with strong local correlations. We address this by developing a new bootstrap approach to proving subcriticality of disagreement clusters under the grand coupling.

Tue 20 OctData Structures and Algorithms
The gist
The Ising model is a way to represent how things like magnets behave, especially when they can be in one of two states. When simulated on certain complex random networks, changing from mostly one state to the other usually takes a very long time due to a bottleneck. The authors figured out that if you start the system with just a slight majority of one state, the system quickly settles into a balanced state reflecting that majority, even on complicated networks. They improved how fast this settling happens and showed it works under less strict conditions than before.
Open → 2610.27673v1