Social balance on networks: Local minima and best-edge dynamics

Krishnendu Chatterjee; Jakub Svoboda; Đorđe Žikelić; Andreas Pavlogiannis; Josef Tkadlec

doi:10.1103/PhysRevE.106.034321

Social balance on networks: Local minima and best-edge dynamics

Krishnendu Chatterjee, Jakub Svoboda, Đorđe Žikelić, Andreas Pavlogiannis, Josef Tkadlec

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

2 Citations (Scopus)

Abstract

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.

Original language	English
Article number	034321
Journal	Physical Review E
Volume	106
Issue	3
Number of pages	11
ISSN	2470-0045
DOIs	https://doi.org/10.1103/PhysRevE.106.034321
Publication status	Published - Sept 2022

Access to Document

10.1103/PhysRevE.106.034321

https://arxiv.org/pdf/2210.02394.pdf

Cite this

@article{7a0443f3d0844bba9ada66af24615488,

title = "Social balance on networks: Local minima and best-edge dynamics",

abstract = "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.",

author = "Krishnendu Chatterjee and Jakub Svoboda and {\D}or{\d}e {\v Z}ikeli{\'c} and Andreas Pavlogiannis and Josef Tkadlec",

year = "2022",

month = sep,

doi = "10.1103/PhysRevE.106.034321",

language = "English",

volume = "106",

journal = "Physical Review E",

issn = "2470-0045",

publisher = "American Physical Society",

number = "3",

}

TY - JOUR

T1 - Social balance on networks

T2 - Local minima and best-edge dynamics

AU - Chatterjee, Krishnendu

AU - Svoboda, Jakub

AU - Žikelić, Đorđe

AU - Pavlogiannis, Andreas

AU - Tkadlec, Josef

PY - 2022/9

Y1 - 2022/9

N2 - 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.

AB - 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.

U2 - 10.1103/PhysRevE.106.034321

DO - 10.1103/PhysRevE.106.034321

M3 - Journal article

C2 - 36266862

SN - 2470-0045

VL - 106

JO - Physical Review E

JF - Physical Review E

IS - 3

M1 - 034321

ER -

Social balance on networks: Local minima and best-edge dynamics

Abstract

Access to Document

Fingerprint

Cite this