---
_id: '12257'
abstract:
- lang: eng
  text: 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.
acknowledgement: "K.C. acknowledges support from ERC Start Grant No. (279307: Graph
  Games), ERC Consolidator Grant No. (863818: ForM-SMart), and Austrian Science Fund
  (FWF)\r\nGrants No. P23499-N23 and No. S11407-N23 (RiSE). This project has received
  funding from the European Union’s Horizon 2020 research and innovation programme
  under the Marie\r\nSkłodowska-Curie Grant Agreement No. 665385."
article_number: '034321'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
- first_name: Dorde
  full_name: Zikelic, Dorde
  id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
  last_name: Zikelic
  orcid: 0000-0002-4681-1699
- first_name: Andreas
  full_name: Pavlogiannis, Andreas
  id: 49704004-F248-11E8-B48F-1D18A9856A87
  last_name: Pavlogiannis
  orcid: 0000-0002-8943-0722
- first_name: Josef
  full_name: Tkadlec, Josef
  id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
  last_name: Tkadlec
  orcid: 0000-0002-1097-9684
citation:
  ama: '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>'
  apa: '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>'
  chicago: '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>.'
  ieee: '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.'
  ista: '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.'
  mla: '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>.'
  short: K. Chatterjee, J. Svoboda, D. Zikelic, A. Pavlogiannis, J. Tkadlec, Physical
    Review E 106 (2022).
date_created: 2023-01-16T09:57:57Z
date_published: 2022-09-29T00:00:00Z
date_updated: 2026-04-07T11:49:11Z
day: '29'
department:
- _id: KrCh
doi: 10.1103/physreve.106.034321
ec_funded: 1
external_id:
  arxiv:
  - '2210.02394'
  isi:
  - '000870243100001'
intvolume: '       106'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2210.02394
month: '09'
oa: 1
oa_version: Preprint
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: Physical Review E
publication_identifier:
  eissn:
  - 2470-0053
  issn:
  - 2470-0045
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
related_material:
  record:
  - id: '20138'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: 'Social balance on networks: Local minima and best-edge dynamics'
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 106
year: '2022'
...