Graphs and Social Networks

Positive and Negative Links

Usually, links represent friendly relationships. Here we discuss networks with edges labelled by $+$ and $-$, where $+$ stands for friendly relationship, and $-$ for antagonism. More on signed links and their applications can be found in [Easley-Kleinberg, Chapter 5].

Structural Balance

This concept provides an example of a local condition (on collections of three nodes) that has an effect on the global structure of a network.

Suppose first that the network in question is a complete graph, with edges labelled $+$ or $-$. Such a network will be called a signed complete network. The triangles in a signed complete network have one of four possible types:

  • All three edges are labelled $+$: the nodes form a set of mutual friends, a constellation that can be considered stable.

  • One edge labelled $+$ and two edges labelled $-$: the nodes represent two friends with a common enemy, another constellation that is considered stable.

  • Two edges labelled $+$ and one edge labelled $-$: here one node has two friends that don’t like each other, an unstable constellation as there are incentives to either resolve the conflict and all be friends with each other, or to side with one friend against the other.

  • All edges labelled $-$: a set of mutual enemies is considered unstable, as again there is an incentive for two nodes to team up against the third.

On the basis of this classification, one can formulate the following property.

Structural Balance Property. A signed complete graph is balanced, if the edges between any 3 nodes are either all labelled $+$, or exactly one is labelled $+$.

An example of a network $G = (X, E)$ that is balanced in this sense is one where the node set $X$ consists of two parts, $Y$ and $Z$, say, such that all nodes within $Y$ are mutual friends, all nodes within $Z$ are mutual friends, and there is mutual antagonism between the two sets $Y$ and $Z$. In fact, these are the only examples of balanced graphs.

Balance Theorem (Harary 1953). If a signed complete graph $G = (X, E)$ is balanced then the nodes can be divided into two groups, $Y$ and $Z$ (possibly empty), such that all links within $Y$, and within $Z$, are labelled $+$, and all links between a node in $Y$ and a node in $Z$ are $-$.

Proof. Pick a node $A \in X$. Every other node will be either a friend or an enemy of $A$. Let $Y$ be $A$ and all its friends, and let $Z$ be all of $A$’s enemies. Then clearly $\{Y, Z\}$ forms a partition of the node set $X$. It remains to show that

  • any two nodes in $Y$ are friends (which they are as either one of the nodes is $A$ and the other is $A$’s friend by the definition of $Y$, or the two nodes are friends of $A$, making them friends by structural balance),

  • any two nodes in $Z$ are friends (which they are, both having $A$ as their enemy by the definition of $Z$ and hence being friends by structural balance),

  • every node in $Y$ is an enemy of every node in $Z$ (which they are, as the node in $Y$ is either $A$, and thus an enemy of every node in $Z$ by the definition of $Z$, or the node in $Y$ is a friend and the node in $Z$ an enemy of $A$, making them enemies as structural balance requires the third edge of a triangle with at least one positive and one negative edge to be negative.

Applications. In international relations it is often natural to assume that all nodes (nations, in this case) have an opinion ($+$ or $-$) about one another. Structural balance can (sometimes) provide an explanation for the behaviour of nations during international crises.

Weaker Forms of Structural Balance

The notion of structural balance is somewhat extreme, and in applications might not be present in its pure form. There are several ways to soften the requirements on structural balance.

In a complete graph, for example, one might require only a certain proportion of the triangles to be balanced.

Alternatively, one can relax the condition that every possible edge must be present, and study structural balance in non-complete networks.

Here, we briefly study the following property on a complete graph:

Weak Structural Balance Property. A signed complete network is weakly balanced, if no three nodes have exactly two positive edges between them (and one negative edge).

The techniques of the proof of Harary’s Balance Theorem can be adjusted to characterize weakly balanced networks as follows.

Weak Balance Theorem. If a signed complete graph $G = (X, E)$ is weakly balanced, then then the nodes $X$ can be partitioned into groups $X_1, X_2, \dots, X_k$, so that any two nodes within a group are friends, and any two nodes from different groups are enemies.

Proof. As before, we pick an arbitrary node $A \in X$ and let $Y \subset X$ to be the set consisting of $A$ and its friends, and let $Z \subseteq X$ be the set of all of $A$’s enemies.

We then argue by induction on the size $ X $ of the network.

If $|X| = 1$ then $A$ is the only node and $G$ is weakly balanced as it has no triangles that could violate the Weak Structural Balance Property.

Now suppose that $|X| > 1$ and partition $X$ into $Y$ and $Z$ as above. One needs to show that

(i) all edges within $Y$ are $+$ (which they are by the same argument as in the proof of (strong) Balance Theorem),

(ii) all edges between $Y$ and $Z$ are $-$ (which they are, as before).

We can no longer show that within $Z$ all the edges are $+$ (which indeed they might not be).

But we do know, by induction on $|X|$, and since $|Z| < |X|$ that the induced signed complete network on the vertex set $Z$ is weakly balanced, with respect to a partition $\{X_2, X_3, \dots X_k \}$ of $Z$.

Setting $X_1 = Y$ yields a partition $\{X_1, X_2, \dots X_k \}$ of $X$ which, together with (i) and (ii), completes the proof of the theorem.

Structural Balance in non-complete networks.

Let $G = (X, E)$ be a network whose edges are labelled either $+$ or $-$. We call such a graph a signed network.

Definition. A signed network $G = (X, E)$ is balanced if its node set $X$ can be divided into two sets $Y$ and $Z$ such that all edges within those sets are positive, and all edges between the sets are negative.

This condition on $G= (X, E)$ is equivalent to the condition that $G$ can be completed to a signed complete graph, by adding the missing edges, and labelling them in a consistent way.

Balanced networks can be characterized in terms of cycles with an odd number of negative edges. For this purpose we call such a cycle a negatively odd cycle.

Theorem. A signed network is balanced if and only if it contains no negatively odd cycles.

Proof. In order to prove this statement on needs to establish two implications for a signed network $G = (x, E)$: (1) if $G$ is balanced then $G$ contains no negatively odd cycles, (2) if $G$ contains no negatively odd cycles then $G$ is balanced.

Clearly, if $G$ contains a cycle with an odd number of negative edges, then this cycle (and hence $G$) cannot be partitioned in a balanced way. This shows the contrapositive of implication (1) (and hence (1)).

Implication (2) is logically equivalent to the claim that $G$ is either balanced, or contains a negatively odd cycle. The following 2 step procedure does establish exactly this: starting from an arbitrary signed network, it either reveals a negatively odd cycle, or a balanced partition of the vertex set $X = Y \cup Z$.

Step 1: Supernodes. Consider the subgraph on the vertex set $X$ consisting of the $+$ edges only and let $X_1, X_2, \dots, X_k$ be its connected components. These components, or supernodes, will be used as nodes in a new graph, to be constructed next. Unless a supernode contains a negative edge (in the original signed network), because such an edge necessarily lies on a cycle with one (hence odd number of) negative edges.

Step 2: Define a new graph with vertex set $X_1, X_2, \dots, X_k$ (the supernodes), and an edge between $X_i$ and $X_k$ whenever there are nodes $x \in X_i$ and $y \in X_k$ with a (necessarily negative) edge between them.

By a classical theorem in Graph Theory, this graph is either bipartite or it contains an odd cycle. If it contains an odd cycle then the original network clearly contains a negatively odd cycle.

And if it is bipartite then the corresponding partition of the set of supernodes into two parts yields a partition of the original network into two parts which make it balanced.

In this way one either exhibits a negatively odd cycle or a balanced partition of the nodes in the given signed network. This completes the proof of the theorem.

BFS finds odd cycles.

Citing the Graph Theory characterization of bipartite graphs by means of odd cycles is sufficient for the purpose of proving the above theorem, but it does not give us an explicit odd cycle, or a bipartite partition of the vertex set, whatever may be the case.

It is worth noting, that Breadth First Search can be used to make this explicit. If applied to a graph $G = (X, E)$ and a node $A \in X$, BFS produces a layered version of $G$, according to the distance of nodes in $X$ from $A$. An edge in this graph either goes from one layer to the next, or it connects two nodes on the same layer. (There cannot be an edge between two nodes whose distance to $A$ differs by $2$ or more: this follows from the triangle inequality for the distance function of the network $G$.)

It is easy to see that an edge connecting two nodes at the same layer in the BFS graph of $A \in X$ necessarily belong to an odd cycle.

On the other hand, of the BFS graph of $A \in X$ does not contain an edge connecting two nodes at the same layer then partitioning the nodes into the set $Y$ of nodes at even layers and the set $Z$ of nodes at odd layers, obviously makes the network $G$ bipartite.