Department of Applied Mathematics, University of California, Merced, CA, 95343, USA.
Department of Mathematics, University of California, Davis, CA, 95616, USA.
Sci Rep. 2022 Sep 5;12(1):15056. doi: 10.1038/s41598-022-18953-8.
Suppose we are given a system of coupled oscillators on an unknown graph along with the trajectory of the system during some period. Can we predict whether the system will eventually synchronize? Even with a known underlying graph structure, this is an important yet analytically intractable question in general. In this work, we take an alternative approach to the synchronization prediction problem by viewing it as a classification problem based on the fact that any given system will eventually synchronize or converge to a non-synchronizing limit cycle. By only using some basic statistics of the underlying graphs such as edge density and diameter, our method can achieve perfect accuracy when there is a significant difference in the topology of the underlying graphs between the synchronizing and the non-synchronizing examples. However, in the problem setting where these graph statistics cannot distinguish the two classes very well (e.g., when the graphs are generated from the same random graph model), we find that pairing a few iterations of the initial dynamics along with the graph statistics as the input to our classification algorithms can lead to significant improvement in accuracy; far exceeding what is known by the classical oscillator theory. More surprisingly, we find that in almost all such settings, dropping out the basic graph statistics and training our algorithms with only initial dynamics achieves nearly the same accuracy. We demonstrate our method on three models of continuous and discrete coupled oscillators-the Kuramoto model, Firefly Cellular Automata, and Greenberg-Hastings model. Finally, we also propose an "ensemble prediction" algorithm that successfully scales our method to large graphs by training on dynamics observed from multiple random subgraphs.
假设我们给定了一个在未知图上的耦合振荡器系统，以及系统在某段时间内的轨迹。我们能否预测系统是否最终会同步？即使知道潜在的图结构，这在一般情况下也是一个重要但分析上难以解决的问题。在这项工作中，我们通过将其视为基于以下事实的分类问题来解决同步预测问题，即任何给定的系统最终将同步或收敛到非同步的极限环。通过仅使用基础图的一些基本统计信息，例如边密度和直径，我们的方法在基础图的拓扑结构在同步和非同步示例之间存在显著差异的情况下可以达到完美的准确性。然而，在这些图统计信息不能很好地区分这两个类的问题设置中（例如，当图是从相同的随机图模型生成时），我们发现，将初始动力学的几个迭代与图统计信息配对作为输入到我们的分类算法中，可以显著提高准确性；远远超过经典振荡器理论所知道的。更令人惊讶的是，我们发现，在几乎所有这些设置中，放弃基本图统计信息并仅使用初始动力学训练我们的算法可以达到几乎相同的准确性。我们在三个连续和离散耦合振荡器模型上展示了我们的方法——Kuramoto 模型、萤火虫元胞自动机和 Greenberg-Hastings 模型。最后，我们还提出了一种“集成预测”算法，该算法通过从多个随机子图中观察到的动力学进行训练，可以成功地将我们的方法扩展到大型图。
