30 Structural Balance
The concept of balance can be extended from individual triads to the entire social network, which is analyzed at the whole network level. This extension is known as Structural Balance Theory.
In its original formulation, structural balance theory applies to complete signed graphs. A signed graph is a special kind of graph featuring one set of vertices (nodes) and two disjoint sets of edges: positive links (E+) and negative links (E-).
A complete signed graph is one where every node is connected to every other node by either a positive or a negative link. In an adjacency matrix representation of a signed graph, positive links are typically represented by +1, negative links by -1, and non-adjacent nodes by 0, though for structural balance, it is often applied to complete graphs where all connections exist.
30.1 The Fundamental Theorem of Structural Balance
The Fundamental Theorem of Structural Balance was discovered by mathematicians Dorwin Cartwright and Frank Harary in 1956 (Cartwright and Harary 1956). This theorem states that if a complete signed graph only contains balanced triads (i.e., every triad within the network is balanced as defined in Chapter 29), then the graph itself is considered balanced.
Furthermore, such a balanced graph can be divided into two groups such that:
- There are only positive links within each group.
- There are only negative links between the two groups.
This theorem implies that structural balance is equivalent to perfect group polarization. For example, in a balanced network, nodes A, B, and F might form one group with positive ties among themselves, while nodes C, D, and E form another group with positive ties among themselves, and all ties between these two groups would be negative. In a balanced graph, the polarized structure of these two distinct groups can be recovered by rearranging the rows and columns of the signed adjacency matrix such that nodes in the same group are near one another.
A remarkable property of a structurally balanced graph is its resilience to change in its overall polarized structure. If new nodes are added to a structurally balanced graph, the existing group polarization pattern does not change, provided that the new nodes’ relationships to every other existing node are also balanced.
Essentially, any new node entering such a network will inherently fall into one of the two existing polarized groups, maintaining the internal positive ties and external negative ties, thus keeping the network polarized.
30.2 Cycles in a Balanced Signed Graph
The direct consequence of this two-group partitioning for cycles within a balanced signed graph is as follows: All cycles in a balanced signed graph must have a positive product of signs.
**Cycles entirely within one group*: If a cycle exists entirely within one of the two polarized groups (e.g., within Group 1 or Group 2), then all the edges forming that cycle must be positive, as per the theorem. The product of any number of positive signs is always positive. Therefore, these cycles are inherently “balanced” in terms of their sign product.
Cycles spanning between two groups: If a cycle involves nodes from both polarized groups, it must cross between the groups an even number of times to return to its starting node. For instance, to go from Group 1 to Group 2 and then back to Group 1, it must cross the “boundary” twice. Each time a link crosses between the two groups, it carries a negative sign. If there’s an even number of such negative links in the cycle, then the product of all the signs in the cycle will be positive (because an even number of negative signs multiplied together results in a positive product).
30.3 Paths in a Balanced Signed Graph
Recall that a path is a sequence of distinct vertices and edges connecting a start node to an end node. The sign of the path is the product of the sign of each edge in the path. In a balanced graph, the end nodes of a path could belong to the same group, or each could belong to different groups in the polarized structure.
- Paths with End Nodes in the Same Group: If a path begins and ends within the same polarized group (e.g., both start and end nodes are in Group 1, or both are in Group 2), the product of the signs of its edges will always be positive.
Reasoning: To start and end in the same group, the path must either stay entirely within that group (meaning all its links are positive, and thus their product is positive), or it must cross between the two groups an even number of times. Each time the path crosses from one group to the other, it traverses a negative link (by definition of the two-group partition). Since an even number of negative links multiplied together results in a positive sign (-1 * -1 = +1), and any within-group links are positive, the overall product of signs for the entire path will be positive.
- Paths with End Nodes in Different Groups: If a path begins in one polarized group and ends in the other (e.g., starts in Group 1 and ends in Group 2), the product of the signs of its edges will always be negative.
Reasoning: To connect nodes in different groups, the path must necessarily cross the boundary between the two groups an odd number of times. Each time it crosses, it utilizes a negative link. Since an odd number of negative links multiplied together results in a negative sign (+1 * -1 = -1), the overall product of signs for the entire path will be negative.
In summary, the two-group partitioning, which is a hallmark of structural balance in complete signed graphs, creates a predictable environment for path signs. Paths that “stay” within their original group’s alignment (by ending in the same group) maintain a positive sign, while paths that “cross” the fundamental division of the network (by ending in a different group) acquire a negative sign, reflecting the inherent polarization.