Another theorem about signed graphs
In class, we discussed both signed graphs and the concept of a balanced signed graph in the context of social networks. We then proved a theorem that stated that the nodes of any balanced, complete, signed graph can be partitioned into two sets X,Y such that all edges between nodes of set X are positive, all edges between nodes of Y are positive, and all edges between a node in X and a node in Y are negative. This theorem was originally proven by Frank Harary, who (according to Wikipedia) invented the study of signed graphs after being inspired by work in social psychology. Here, another theorem of his is presented, from his paper “On the Notion of Balance of a Signed Graph.” The proof of the theorem is not much altered from its original form, aside from some vocabulary updates.
First, define the sign of a path to be the product of the signs of the edges that compose it. This is computed as if one were multiplying together edges labled with 1 and -1. For example, if edges A,B,C form a path and have signs -, +, -, respectively, then the sign of that path is (-)(+)(-) = +. Were the signs of the same path something like +, +, -, then the sign of the path would be (+)(+)(-) = -.
Harary defines balance differently than we did in class because he was interested in more than just complete graphs. Rather than thinking about balanced triangles, Harary defines a balanced cycle to be one whose product (computed as for a path) is “+”. He then defines a balanced graph to be one in which every cycle is balanced. It is fairly intuitive that our definitions, based on balanced triangles in complete graphs, would agree with Harary’s, since every triangle is a cycle.
Theorem (Harary 1954)
A signed graph is balanced if an only if for each pair of distinct nodes A, B, all paths joining A and B have the same sign.
Proof
First, we show that a signed graph being balanced implies that every pair of paths joining A, B have the same sign.
Let p, q, be two paths joining A and B. Any edges that these two paths share must have the same sign, so we can safely delete them from the paths. What we have left is then a collection of cycles, each of which is composed of some edges of p and some of q.
Let c be any such cycle. Since c is a cycle, its sign must be positive. Therefore, the product of the edges of p that it contains and the product of the edges of q that it contains must be the same. Since this is true for the sub-paths of p and the sub-paths of q in every c, p and q must have the same sign.
To complete the if and only if statement, we must now prove that every pair of paths joining A and B having the same sign implies that the graph is balanced. Again, let p and q be distinct paths between A and B. Since p and q have the same sign, the the cycle formed by putting p and q together is positive. Since A and B are arbitrary points, this is true for all cycles, so the graph is balanced. ■
From the perspective of our complete social networks, this theorem can be thought of as telling us that a friend is a friend, regardless of how we walk through our social network to get to it. More explicitly, this theorem tells us that if we walk a path from A to B and change between walking through nodes in the friend set and nodes in the enemy set an even number of times, then A and B should be friends and must have a positive edge between them if this is a complete graph. If the change happens an odd number of times, then there should be a negative edge between A and B because they are enemies.
The paper containing this theorem, the one we proved in class, and a theorem similar to the one we proved in class for general signed graphs is below.
http://projecteuclid.org/download/pdf_1/euclid.mmj/1028989917