article published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Jakub Svoboda author 130759D2-D7DD-11E9-87D2-DE0DE66974250000-0002-1419-3267 Dorde Zikelic author 294AA7A6-F248-11E8-B48F-1D18A9856A870000-0002-4681-1699 Andreas Pavlogiannis author 49704004-F248-11E8-B48F-1D18A9856A870000-0002-8943-0722 Josef Tkadlec author 3F24CCC8-F248-11E8-B48F-1D18A9856A870000-0002-1097-9684 KrCh department Quantitative Graph Games: Theory and Applications project Formal Methods for Stochastic Models: Algorithms and Applications project Modern Graph Algorithmic Techniques in Formal Verification project Game Theory project International IST Doctoral Program project Structural balance theory is an established framework for studying social relationships of friendship and enmity. These relationships are modeled by a signed network whose energy potential measures the level of imbalance, while stochastic dynamics drives the network toward a state of minimum energy that captures social balance. It is known that this energy landscape has local minima that can trap socially aware dynamics, preventing it from reaching balance. Here we first study the robustness and attractor properties of these local minima. We show that a stochastic process can reach them from an abundance of initial states and that some local minima cannot be escaped by mild perturbations of the network. Motivated by these anomalies, we introduce best-edge dynamics (BED), a new plausible stochastic process. We prove that BED always reaches balance and that it does so fast in various interesting settings. American Physical Society2022 eng 2470-0045 2470-0053 2210.02394 00087024310000110.1103/physreve.106.034321 1063 https://research-explorer.ista.ac.at/record/20138 Chatterjee K, Svoboda J, Zikelic D, Pavlogiannis A, Tkadlec J. 2022. Social balance on networks: Local minima and best-edge dynamics. Physical Review E. 106(3), 034321. Chatterjee, Krishnendu, Jakub Svoboda, Dorde Zikelic, Andreas Pavlogiannis, and Josef Tkadlec. “Social Balance on Networks: Local Minima and Best-Edge Dynamics.” <i>Physical Review E</i>. American Physical Society, 2022. <a href="https://doi.org/10.1103/physreve.106.034321">https://doi.org/10.1103/physreve.106.034321</a>. Chatterjee K, Svoboda J, Zikelic D, Pavlogiannis A, Tkadlec J. Social balance on networks: Local minima and best-edge dynamics. <i>Physical Review E</i>. 2022;106(3). doi:<a href="https://doi.org/10.1103/physreve.106.034321">10.1103/physreve.106.034321</a> Chatterjee, Krishnendu, et al. “Social Balance on Networks: Local Minima and Best-Edge Dynamics.” <i>Physical Review E</i>, vol. 106, no. 3, 034321, American Physical Society, 2022, doi:<a href="https://doi.org/10.1103/physreve.106.034321">10.1103/physreve.106.034321</a>. K. Chatterjee, J. Svoboda, D. Zikelic, A. Pavlogiannis, J. Tkadlec, Physical Review E 106 (2022). Chatterjee, K., Svoboda, J., Zikelic, D., Pavlogiannis, A., &#38; Tkadlec, J. (2022). Social balance on networks: Local minima and best-edge dynamics. <i>Physical Review E</i>. American Physical Society. <a href="https://doi.org/10.1103/physreve.106.034321">https://doi.org/10.1103/physreve.106.034321</a> K. Chatterjee, J. Svoboda, D. Zikelic, A. Pavlogiannis, and J. Tkadlec, “Social balance on networks: Local minima and best-edge dynamics,” <i>Physical Review E</i>, vol. 106, no. 3. American Physical Society, 2022. 122572023-01-16T09:57:57Z2026-04-07T11:49:11Z