New Proof Shows That ‘Expander’ Graphs Synchronize

Melody and Silence

In the early 1990s, together with his student Shinya Watanabe, Strogatz showed that Kuramoto’s solution was not only possible, but all but inevitable, even for a finite number of oscillators. In 2011, Richard Taylor of the Australian Defense Science and Technology Organization chipped away at Kuramoto’s requirement that the graph be complete. He proved that homogeneous graphs where each node is connected to at least 94% of the others are sure to globally synchronize. Taylor’s result had the advantage of applying to graphs with arbitrary connectivity structures, so long as every node had a large number of neighbors.

In 2018, Bandeira, Ling and Ruitu Xu, a graduate student at Yale University, lowered Taylor’s requirement that each node be connected to 94% of the others to 79.3%. In 2020 a competing group got to 78.89%; in 2021, Strogatz, Alex Townsend and Martin Kassabov established the current record when they showed that 75% is enough.

Meanwhile, researchers also attacked the problem from the opposite direction, trying to find graphs that were highly connected but did not globally synchronize. In a series of papers from 2006 to 2022, they uncovered graph after graph that could avoid global synchronization, even though each node was linked to over 68% of the others. Many of these graphs resemble a circle of people holding hands, where each person reaches out to 10 or even 100 nearby neighbors. These graphs, called ring graphs, can settle into a state where each oscillator is slightly offset from the next.

Clearly, graph structure heavily influences synchronization. So Ling, Xu and Bandeira became curious about the synchronization properties of randomly generated graphs. To make their work precise, they used two common methods for randomly building a graph.

The first is named after Paul Erdős and Alfréd Rényi, two prominent graph theorists who did seminal work on the model. To build a graph using the Erdős-Rényi model, you start with a bunch of unconnected nodes. Then for each pair of nodes, you randomly link them together with some probability p. If p is 1%, you link the edges 1% of the time; if it’s 50%, each node will connect to half the others, on average.

If p is marginally bigger than a threshold that depends on the number of nodes in the graph, the graph will, with overwhelming likelihood, form one interconnected web (as opposed to comprising clusters that don’t link up). As the size of the graph grows, this threshold becomes tiny, so that for large enough graphs, even if p is small, making the total number of edges also small, Erdős-Rényi graphs will be connected.

The second type of graph they considered is called a d-regular graph. In such graphs, every node has the same number of edges, d. (So in a 3-regular graph, every node is connected to 3 other nodes, in a 7-regular graph, every node is connected to 7 others, and so forth.)

Graphs that are well connected despite being sparse — having only a small number of edges — are known as expander graphs. These are important in many areas of math, physics and computer science, but if you want to construct an expander graph with a particular set of properties, you’ll find that it’s a “surprisingly non-trivial problem,” according to the prominent mathematician Terry Tao. Erdős-Rényi graphs, though not always expanders, share many of their important features. And it turns out though that if you construct a d-regular graph and connect the edges randomly, you’ll have an expander graph.

Making Ends Meet

In 2018, Ling, Xu and Bandeira guessed that the connectivity threshold might also measure the emergence of global synchronization: If you generate an Erdős-Rényi graph with p just a little bigger than the threshold, the graph should globally synchronize. They made partial progress on this conjecture, and Strogatz, Kassabov and Townsend later improved on their result. But a significant space between their number and the connectivity threshold remained.

In March 2022, Townsend visited Bandeira in Zurich. They realized they had a chance at reaching the connectivity threshold and brought in Pedro Abdalla, a graduate student of Bandeira’s, who in turn enlisted his friend Victor Souza. Abdalla and Souza began working out details, but they quickly ran into obstacles.

It seemed randomness came with unavoidable problems. Unless p was significantly larger than the connectivity threshold, there were likely to be wild swings in the number of edges each node had. One might be attached to 100 edges; another might be attached to none. “As with every good problem, it fights back,” Souza said. Abdalla and Souza realized approaching the problem from the perspective of random graphs wouldn’t work. Instead, they would use the fact that most Erdős-Rényi graphs are expanders. “After this innocent-looking change, a lot of the pieces of the puzzle started to fall into place,” Souza said. “In the end, we have a result much stronger than we bargained for.” Graphs come with a number called the expansion that measures how hard it is to cut them in two normalized to the size of the graph. The bigger that number, the harder it is to split it into two by removing nodes.

Over the next several months, the team filled in the rest of the argument, posting their paper online in October. Their proof shows that given enough time, if the graph has enough expansion, the homogeneous Kuramoto model will always globally synchronize.

Down the Only Road

One of the biggest remaining mysteries in the mathematical study of synchronization only requires a small tweak to the model in the new paper: What happens if some pairs of oscillators pull each other into synchrony, but others push each other out of it? In that situation, “almost all our tools are gone immediately,” Souza said. If researchers can make progress on this version of the problem, the techniques would likely help Bandeira tackle the data-clustering problems he had set out to solve before turning to synchronization.

Beyond that, there are classes of graphs besides expanders, patterns more complex than global synchronization, and synchronization models that don’t assume every node and edge is the same. In 2018, Saber Jafarpour and Francesco Bullo of the University of California, Santa Barbara proposed a test for global synchronization that works when the rotators do not have identical weights and preferred frequencies. Bianconi’s team and others have been working with networks whose links involve three, four or more nodes, rather than just pairs.

Bandeira and Abdalla are already attempting to move beyond the Erdős-Rényi and d-regular models into other, more realistic random graph models. Last August, they shared a paper, co-authored with Clara Invernizzi, on synchronization in random geometric graphs. In random geometric graphs, which were conceived in 1961, nodes are scattered randomly in space, perhaps on a surface like a sphere or a plane. Edges are placed between pairs of nodes if they’re within a certain distance of one another. Their inventor, Edgar Gilbert, hoped to model communications networks in which messages can only travel a short distance, or the spread of infectious pathogens that require close contact for transmission. Random geometric models would also better capture links between fireflies in a swarm, which synchronize by watching their neighbors, Bandeira said.

Of course, connecting the mathematical results to the real world is challenging. “I think it would be a bit of a fib to argue this is compelled by applications,” said Strogatz, who also noted that the homogeneous Kuramoto model can never capture the inherent variation in biological systems. Souza added, “There are many fundamental questions we still don’t know how to do. It’s more like exploring the jungle.”

Editor’s note: Steven Strogatz hosts the “Joy of Why” podcast for Quanta and is a former member of the magazine’s scientific advisory board. He was interviewed for this article but did not otherwise contribute to its production.

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/new-proof-shows-that-expander-graphs-synchronize-20230724/