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

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

Full description

Saved in:
Bibliographic Details
Main Authors: CHATTERJEE, Krishnendu, SVOBODA, Jakub, ZIKELIC, Dorde, PAVLOGIANNIS, Andreas, TKADLEC, Josef
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2024
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/9075
https://ink.library.smu.edu.sg/context/sis_research/article/10078/viewcontent/2210.02394v1.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-10078
record_format dspace
spelling sg-smu-ink.sis_research-100782024-08-01T15:20:59Z Social balance on networks: Local minima and best-edge dynamics CHATTERJEE, Krishnendu SVOBODA, Jakub ZIKELIC, Dorde PAVLOGIANNIS, Andreas TKADLEC, Josef 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. 2024-05-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9075 info:doi/10.1103/physreve.106.034321 https://ink.library.smu.edu.sg/context/sis_research/article/10078/viewcontent/2210.02394v1.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University OS and Networks
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic OS and Networks
spellingShingle OS and Networks
CHATTERJEE, Krishnendu
SVOBODA, Jakub
ZIKELIC, Dorde
PAVLOGIANNIS, Andreas
TKADLEC, Josef
Social balance on networks: Local minima and best-edge dynamics
description 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.
format text
author CHATTERJEE, Krishnendu
SVOBODA, Jakub
ZIKELIC, Dorde
PAVLOGIANNIS, Andreas
TKADLEC, Josef
author_facet CHATTERJEE, Krishnendu
SVOBODA, Jakub
ZIKELIC, Dorde
PAVLOGIANNIS, Andreas
TKADLEC, Josef
author_sort CHATTERJEE, Krishnendu
title Social balance on networks: Local minima and best-edge dynamics
title_short Social balance on networks: Local minima and best-edge dynamics
title_full Social balance on networks: Local minima and best-edge dynamics
title_fullStr Social balance on networks: Local minima and best-edge dynamics
title_full_unstemmed Social balance on networks: Local minima and best-edge dynamics
title_sort social balance on networks: local minima and best-edge dynamics
publisher Institutional Knowledge at Singapore Management University
publishDate 2024
url https://ink.library.smu.edu.sg/sis_research/9075
https://ink.library.smu.edu.sg/context/sis_research/article/10078/viewcontent/2210.02394v1.pdf
_version_ 1814047724652199936