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

Figure 1

A triad of type ${\mathrm{\Delta }}_k$ contains $k$ enmity edges. The imbalanced triads ${\mathrm{\Delta }}_1$ and ${\mathrm{\Delta }}_3$ can be made balanced by flipping any one edge. A sequence of flips typically reaches a state where all triads are balanced. The rank $r_e$ of edge $e$ is the number of imbalanced triads containing $e$.

Figure 2

A jammed state consisting of $4d+2$ roughly equal clusters, each connected by friendships to the clusters at most $d$ steps apart.

Figure 3

A jammed state $J_n$ (right) on $n$ vertices can be reached from any not-too-friendship-dense initial state $I_n$ (left). Moreover, once it is reached, it cannot be escaped, even if a substantial portion of edges around each vertex are perturbed.

Figure 4

An example of a signed graph (left) and the corresponding red-black graph (right).

Figure 5

Left: Started from $J_n$, BED reaches balance in $\mathcal{O}\left(n^2\right)$ expected steps. Right: Friendship densities in different portions of the signed graph $J_{100}$, in a single run of BED. Apart from possibly the very end, the friendships within clusters ($aa, bb, cc$) are never flipped. Eventually, one pair of clusters (here $a$ and $b$) merges.

Figure 6

A jammed state $J_n^{\prime }$ from which BED reaches a balanced state in $\mathcal{O}\left(n^2\right)$ expected steps.

Figure 7

Average number of steps until balance for CTD (excluding the runs that get jammed) and BED over ${10}^5$ runs. The friendships in the initial signed graphs form the Erdős-Rényi graph with edge probability $p=\frac{1}{2}$ and size $n\le 400$. Both quantities scale as $\mathrm{\Theta }\left(n^2\right)$.

Figure 8

Distribution of the relative difference of the clique sizes once balance is reached for BED (left) and CTD (right) over ${10}^5$ runs. Here $n=128$.

Figure 9

The jamming probability for CTD, when friendships form an Erdős-Rényi graph with size $n=250$ and edge density $p\in [0,1]$ exhibits a threshold behavior.

Figure 10

The jamming probability for CTD, when friendships form an Erdős-Rényi graph with size $n\le 400$ and edge density $p\in \{0,0.5,0.6,0.75\}$. When $p\ge 0.75$ (or $p\ge 0.6$ and $n$ large), the dynamics typically reaches utopia, otherwise there is a non-negligible probability of reaching a jammed state.

Figure 11

Average number of steps until balance for CTD (excluding the runs that get jammed) and BED over ${10}^5$ runs. The initial signed graphs are Barabási-Albert with degree parameter $d=0.5$ and size $n\le 400$. Both quantities scale as $\mathrm{\Theta }\left(n^2\right)$.

Figure 12

The jamming probability in CTD, for Barabási-Albert networks with size $n=250$ and parameter $d\in [0,0.7]$ exhibits a threshold behavior comparable to Erdős-Rényi graphs but with significantly lower edge density.

Figure 13

The jamming probability in CTD, for Barabási-Albert networks with size $n\le 400$ and parameters $d\in \{0.0,0.3,0.5,0.7\}$.

Figure 14

A blinker. Under both CTD and BED, the thick edge in the middle keeps toggling between friendship (blue) and enmity (red) indefinitely. There is always only one imbalanced triangle (shaded) and flipping any other its edge would create more imbalanced triangles.