Structural Balance
The principles underlying structural balance are based on a theory in
social psychology dating back to the work of Heider in the 1940s, which
was generalized and extended to graphs by Cartwright and Harary in the
1950s. In its simplest form, it is defined via triangles. A triangle is
balanced if all ties are positive (“the friend of a friend is a friend”)
or only one tie is positive (“the enemy of my enemy is my friend”). The
remaining configurations are said to be unbalanced.
A network is balanced if i.a., it can be partitioned into two vertex
subsets, such that intra-group edges are all positive and inter-group
edges are all negative.
A (random) balanced network can be obtained with the function
sample_islands_signed() which is pretty much the same as
sample_islands() from the igraph package.
g <- sample_islands_signed(islands.n = 2,islands.size = 10,
islands.pin = 0.8,n.inter = 5)
(The function ggsigned() can be used to visualize signed
networks. Note that this requires the package ggraph to be
installed.) Increasing islands.n leads to “clusterable”
networks as defined by Davis.
A balanced network only contains balanced triangles. This can be
verified with count_signed_triangles().
count_signed_triangles(g)
#> +++ ++- +-- ---
#> 102 0 8 0
Note the absence of ++- and ---
triangles.
To list all triangles use signed_triangles().
head(signed_triangles(g))
#> V1 V2 V3 P
#> [1,] 18 7 8 1
#> [2,] 18 10 14 1
#> [3,] 18 10 7 1
#> [4,] 18 10 8 1
#> [5,] 18 10 12 1
#> [6,] 18 12 19 3
The column P indicated the number of positive ties in the triangle. A
value of 3 indicates that the triangle is “+++”.
Balancedness
Determining if a network is balanced or not is easy, but measuring a
degree of balancedness (i.e. how close is a network to be balanced?) is
not. The package, so far, implements three methods to calculate balance
scores. All are defined such that a value of one indicates perfect
balance and zero perfect unbalance. Though for intermediate networks,
results may vary significantly. Check the paper by Samin Aref (and his
other work) for more details.
balance_score(g, method = "triangles")
#> [1] 1
balance_score(g, method = "walk")
#> [1] 1
balance_score(g, method = "frustration")
#> [1] 1
“triangles” returns the fraction of balanced triangles.
“walk” is based on eigenvalues of the signed and underlying unsigned
network. Check the paper by Estrada for details.
“frustration” assumes that the network can be partitioned into two
groups, where intra group edges are positive and inter group edges are
negative. The index is defined as the sum of intra group negative and
inter group positive edges. Note that the problem is NP complete and
only an upper bound is returned (based on simulated annealing). The
function frustration_exact() implements an integer program
to solve the exact optimization problem. More details can be found in
the work of Aref.
There disagreement for non-balanced networks can be seen with the
included “tribes” dataset.
data("tribes")
balance_score(tribes, method = "triangles")
#> [1] 0.8676471
balance_score(tribes, method = "walk")
#> [1] 0.3575761
balance_score(tribes, method = "frustration")
#> [1] 0.7586207
References
Heider, Fritz. 1946. “Attitudes and Cognitive Organization.” The
Journal of Psychology 21 (1): 107–12.
Cartwright, Dorwin, and Frank Harary. 1956. “Structural Balance: A
Generalization of Heider’s Theory.” Psychological Review 63 (5):
277.
Davis, James A. 1967. “Clustering and Structural Balance in Graphs.”
Human Relations 20 (2): 181–87.
Aref, Samin, and Mark C. Wilson. 2018. “Measuring Partial Balance in
Signed Networks.” Journal of Complex Networks 6 (4): 566–95.
Estrada, Ernesto. 2019. “Rethinking Structural Balance in Signed
Social Networks.” Discrete Applied Mathematics