wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/new-proof-shows-that-expander-graphs-synchronize-20230724\/#comments<\/a><\/br> In the early 1990s, together with his student Shinya Watanabe<\/a>, Strogatz showed that Kuramoto\u2019s solution was not only possible, but all but inevitable, even for a finite number of oscillators.\u00a0In 2011, Richard Taylor<\/a> of the Australian Defense Science and Technology Organization chipped away at Kuramoto\u2019s requirement that the graph be complete. He proved<\/a> that homogeneous graphs where each node is connected to at least 94% of the others are sure to globally synchronize. Taylor\u2019s result had the advantage of applying to graphs with arbitrary connectivity structures, so long as every node had a large number of neighbors.<\/p>\n In 2018, Bandeira, Ling and Ruitu Xu<\/a>, a graduate student at Yale University, lowered Taylor\u2019s requirement<\/a> 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<\/a> and Martin Kassabov<\/a> established the current record<\/a> when they showed that 75% is enough.<\/p>\n 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<\/a> to 2022<\/a>, 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.<\/p>\n 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.<\/p>\n The first is named after Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi, two prominent graph theorists who did seminal work on the model. To build a graph using the Erd\u0151s-R\u00e9nyi model, you start with a bunch of unconnected nodes. Then for each pair of nodes, you randomly link them together with some probability p<\/em>. If p<\/em> is 1%, you link the edges 1% of the time; if it\u2019s 50%, each node will connect to half the others, on average.<\/p>\n If p <\/em>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\u2019t link up). As the size of the graph grows, this threshold becomes tiny, so that for large enough graphs, even if p<\/em> is small, making the total number of edges also small, Erd\u0151s-R\u00e9nyi graphs will be connected.<\/p>\n The second type of graph they considered is called a d<\/em>-regular graph. In such graphs, every node has the same number of edges, d<\/em>. (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.)<\/p>\n Graphs that are well connected despite being sparse \u2014 having only a small number of edges \u2014 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\u2019ll find that it\u2019s a \u201csurprisingly non-trivial problem,\u201d according to<\/a> the prominent mathematician Terry Tao. Erd\u0151s-R\u00e9nyi graphs, though not always expanders, share many of their important features. And i<\/span>t turns out though that if you construct a <\/span>d<\/em>-regular graph and connect the edges randomly, you\u2019ll have an expander graph.<\/span><\/p>\n In 2018, Ling, Xu and Bandeira guessed that the connectivity threshold might also measure the emergence of global synchronization: If you generate an Erd\u0151s-R\u00e9nyi graph with p<\/em> 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.<\/p>\n 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>, a graduate student of Bandeira\u2019s, who in turn enlisted his friend Victor Souza. Abdalla and Souza began working out details, but they quickly ran into obstacles.<\/p>\n It seemed randomness came with unavoidable problems. Unless p <\/em>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. \u201cAs with every good problem, it fights back,\u201d Souza said. Abdalla and Souza realized approaching the problem from the perspective of random graphs wouldn\u2019t work. Instead, they would use the fact that most Erd\u0151s-R\u00e9nyi graphs are expanders. \u201cAfter this innocent-looking change, a lot of the pieces of the puzzle started to fall into place,\u201d Souza said. \u201cIn the end, we have a result much stronger than we bargained for.\u201d 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.<\/p>\n Over the next several months, the team filled in the rest of the argument, posting their paper online in October. Their proof<\/a> shows that given enough time, if the graph has enough expansion, the homogeneous Kuramoto model will always globally synchronize.<\/p>\n 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, \u201calmost all our tools are gone immediately,\u201d 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.<\/p>\n Beyond that, there are classes of graphs besides expanders, patterns more complex than global synchronization, and synchronization models that don\u2019t 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<\/a> for global synchronization that works when the rotators do not have identical weights and preferred frequencies. Bianconi\u2019s team<\/a> and others<\/a> have been working with networks whose links involve three, four or more nodes, rather than just pairs.<\/p>\n Bandeira and Abdalla are already attempting to move beyond the Erd\u0151s-R\u00e9nyi and d<\/em>-regular models into other, more realistic random graph models. Last August, they shared a paper<\/a>, 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\u2019re 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.<\/p>\n Of course, connecting the mathematical results to the real world is challenging. \u201cI think it would be a bit of a fib to argue this is compelled by applications,\u201d said Strogatz, who also noted that the homogeneous Kuramoto model can never capture the inherent variation in biological systems. Souza added, \u201cThere are many fundamental questions we still don\u2019t know how to do. It\u2019s more like exploring the jungle.\u201d<\/p>\n
\nNew Proof Shows That \u2018Expander\u2019 Graphs Synchronize<\/br>
\n2023-07-25 21:58:46<\/br><\/p>\nMelody and Silence<\/strong><\/h2>\n
Making Ends Meet<\/strong><\/h2>\n
Down the Only Road<\/strong><\/h2>\n