Structure Theorems for Signed Graphs

Introduction

The signed graph is an object that combines graph theory and social science to arrive at interesting conclusions. We assign each of a simple unweighted undirected graph with either a + or − sign, and we are able to derive structural theorems based on these signs. From [CH56] we find that this simple addition can model social situations of friendship and enmity. Imagine each vertex as a person, a + edge as a positive relationship and a − edge as a negative relationship. A signed graph is balanced if the product of edge signs along every cycle is positive, a notion that extends to balance in social situations.

In the following theorems, we observe the behavior of a signed graph as a complete social system.

Harary’s Theorems

A signed graph $(G, \sigma)$ is a graph $G = (V,E)$ with an assignment of signs $\sigma : E \to \{-1,+1\}$. We call an edge positive or negative if its sign is +1 or −1 respectively. The sign of a path is the product of the path's edges. By Harary [Har53] we get the following theorems.

Definition. A signed graph is balanced if every cycle in the graph has a positive sign.

Theorem 1. For every complete signed graph $G = (K_n, \sigma)$, $G$ is balanced if and only if there is a cut $S, T$ such that all internal edges $S \leftrightarrow S, T \leftrightarrow T $ are positive and all cross edges $S \leftrightarrow T$ edges are negative.

A social interpretation of this theorem is that a balanced social system consists of two tightly knit cliques who oppose each other.

Proof.

→ Direction: Suppose $G$ is balanced. Let $v$ be an arbitrary vertex in $G$. Let $X \subseteq V$ be the set of vertices connected to $v$ by a positive edge and $v$ itself, and let $Y$ be the set of all other vertices (i.e., vertices connected to $v$ by a negative edge since $G$ is the complete graph.) It is clear that $X,Y$ are disjoint and $X \cup Y = V$.

Any pair of vertices $x_1, x_2 \subseteq X$ must have a positive edge between them. If one of them is $v$, then this is true by construction. Otherwise, there is a cycle $v \rightarrow x_1 \rightarrow x_2$ that must be positive since $G$ is balanced. Since $(v, x_1)$ and $(v, x_2)$ are positive by definition, it follows that $(x_1, x_2)$ must be positive as well.

Any pair of vertices $y_1, y_2 \subseteq Y$ must have a positive edge between them. Otherwise, there is a cycle $v \rightarrow y_1 \rightarrow y_2$ that must be positive since $G$ is balanced. Since $(v, y_1)$ and $(v, y_2)$ are negative by definition, it follows that $(y_1, y_2)$ must be positive. This satisfies the theorem.

← Direction: Suppose there is a cut $S, T$ that satisfies the theorem. Since any cycle must have an even number of edges crossing the cut, the cycle will be positive.

Lemma 2. Every subgraph of a balanced signed graph is also balanced.

Proof.

Every cycle in the subgraph corresponds to a cycle in the original graph, so it must be positive.

Theorem 3. A signed graph is balanced if and only if for all pairs of distinct vertices $u, v$ all paths between $u$ and $v$ have the same sign.

Proof.

→ Direction: Suppose $G$ is balanced. Consider any two paths $\alpha_1, \alpha_2$ connecting $u$ and $v$. Deleting the common edges from $\alpha_1$ and $\alpha_2$ (if any) yields a collection of edge-disjoint cycles. Let $z$ be an arbitrary cycle from this collection. $z$ is comprised of a subset of edges from $\alpha_1$ and a subset from $\alpha_2$. Since $G$ is balanced, $z$ is a positive cycle, so the subsets $\alpha_1$ and $\alpha_2$ must have the same sign. Since each subset shares the same sign, and the common edges are common to both paths, it follows that $\alpha_1$ and $\alpha_2$ must have the same sign.

← Direction: Suppose all paths between any pair of vertices $u, v$ have the same sign. Then any cycle containing $u$ and $v$ must be positive. Since $u$ and $v$ are arbitrary, all cycles must be positive.

We are now ready to extend Theorem 1 to general signed graphs.

Theorem 4. A signed graph is balanced if and only if there is a cut $S, T$ such that all internal edges $S \leftrightarrow S, T \leftrightarrow T$ are positive and all cross edges $S \leftrightarrow T$ edges are negative.

Proof.

→ Direction: Suppose $G$ is balanced, and without loss of generality that $G$ is connected. Let $u, v$ be a pair of vertices that are not connected by an edge. By Theorem 3, all paths between $u$ and $v$ must have the same sign. If we add an edge $(u, v)$ with this sign, all new cycles introduced are positive, and $G$ remains balanced. If we continue this process until $G$ is the complete graph, the theorem follows from Theorem 1.

← Direction: Suppose a cut $S, T$ exists. For each pair of vertices $u, v$ that are not connected by an edge, add a positive edge between them if they are both in $S$ or both in $T$. Otherwise, add a negative edge. Once $G$ is the complete graph, the theorem follows from Theorem 1.

Random Signed Graphs

Now we explore a model of random signed graphs $G_{n,p,q}$ that closely follows the Erdős–Rényi model. Let $p, q$ be fixed with $0 < p+q < 1$. Given a set of $n$ vertices, between each pair of distinct vertices $x$ and $y$ there is either a positive edge with probability $p$ or a negative edge with probability $q$, or else there is no edge at all with probability $1 - (p+q)$. The edges between different pairs of vertices are chosen independently.

We present an alternate way to view $G_{n,p,q}$. Let $\widetilde{G}_{n,p,q}$ be a random unsigned graph which has the same probability distribution as the standard random graph $G_{n,p+q}$ with edge probability $p + q$. We denote $E(\widetilde{G}_{n,p,q})$ as this graph’s edge set. Then, for any fixed pair of vertices $x, y$ assign:

$$ P\!\left(\{x,y\}\text{ is positive in }G_{n,p,q}\ \middle|\ \{x,y\}\in E(\widetilde{G}_{n,p,q})\right) = \frac{p}{p+q} $$

$$ P\!\left(\{x,y\}\text{ is negative in }G_{n,p,q}\ \middle|\ \{x,y\}\in E(\widetilde{G}_{n,p,q})\right) = \frac{q}{p+q} $$

In other words, $G_{n,p,q}$ can be considered as the random variable on the set of the signed graphs on $n$ vertices whose probability distribution is given by

$$ P(G_{n,p,q} = G) = p^{m} q^{k} (1-p-q)^{\binom{n}{2}-m-k} $$

where $G$ is a signed graph with $m$ positive edges and $k$ negative edges. From [MMM12] we get the following theorem.

Theorem 5. Let $p, q$ be fixed with $0 < p+q < 1$. Then $G_{n,p,q}$ is unbalanced with high probability.

First, we will prove the following useful lemma.

Lemma 6. Let $H$ be a fixed set of $h$ distinct pairs of vertices of $G_{n,p,q}$. Then

$$ P\!\left(H\text{ is positive in }G_{n,p,q}\ \middle|\ H\subseteq E(\widetilde{G}_{n,p,q})\right) = \tfrac{1}{2}\left[1 + \left(\frac{p-q}{p+q}\right)^h\right] $$

$$ P\!\left(H\text{ is negative in }G_{n,p,q}\ \middle|\ H\subseteq E(\widetilde{G}_{n,p,q})\right) = \tfrac{1}{2}\left[1 - \left(\frac{p-q}{p+q}\right)^h\right] $$

Proof.

Let

$$ p_1 = P(H\text{ is positive in }G_{n,p,q}\ | \ H\subseteq E(\widetilde{G}_{n,p,q})) = \sum_{i \text{ even}} P(|H^-| = i) $$

where $|H^-|$ is the number of negative edges in $H$. Then,

$$ p_1 = \frac{1}{(p+q)^h}\sum_{i \text{ even}} \binom{h}{i} q^i p^{h-i} $$

Similarly, let

$$ p_2 = P(H\text{ is negative in }G_{n,p,q}\ | \ H\subseteq E(\widetilde{G}_{n,p,q})) = \frac{1}{(p+q)^h}\sum_{i \text{ odd}} \binom{h}{i} q^i p^{h-i} $$

Then we get the system of equations $p_1 + p_2 = 1$ and $p_1 - p_2 = \left(\frac{p-q}{p+q}\right)^h$. Solving the system completes the proof of the theorem.

Now we are ready to prove Theorem 5. Let $T$ denote a maximum set of edge-disjoint triangles in the complete graph $K_n$. To prove the theorem, we will show that $G_{n,p,q}$ contains a negative triangle from $T$ with high probability.

It is clear that $|T| \ge \left\lfloor \tfrac{n}{3} \right\rfloor$. Let $T$ be a fixed element of $T$. We have

$$ P\!\left(T \subseteq \widetilde{G}_{n,p,q} \text{ and } T \text{ is negative}\right) = P\!\left(T \text{ is negative } \middle| \ T \subseteq \widetilde{G}_{n,p,q}\right) \times P\!\left(T \subseteq \widetilde{G}_{n,p,q}\right) $$

Using Theorem 6, we get

$$ P\!\left(T \subseteq E(\widetilde{G}_{n,p,q}) \text{ and } T \text{ is negative}\right) = \tfrac{1}{2}\left[1 - \left(\frac{p-q}{p+q}\right)^3\right] (p+q)^3 = \tfrac{1}{2}\left[(p+q)^3 - (p-q)^3\right] $$

Thus, the probability that $G_{n,p,q}$ contains a negative triangle from $T$ is at least

$$ 1 - \left(1 - \tfrac{1}{2}\left[(p+q)^3 - (p-q)^3\right]\right)^{\lfloor n/3 \rfloor} $$

Since $p$ and $q$ are fixed, this expression tends to 1 as $n \to \infty$.

We can interpret this theorem to say that balance in social systems is very rare as the number of people grows without any predefined social structure.

A PDF version of these notes is available here.

References

[CH56] Dorwin Cartwright and Frank Harary. “Structural balance: a generalization of Heider’s theory”. In: Psychological Review 63.5 (1956), pp. 277–293. doi: 10.1037/h0046049.

[Har53] Frank Harary. “On the notion of balance of a signed graph”. In: Michigan Mathematical Journal 2.2 (1953), pp. 143–146. doi: 10.1307/mmj/1028989917.

[HK80] Frank Harary and Jerald A. Kabell. “A simple algorithm to detect balance in signed graphs”. In: Mathematical Social Sciences 1.1 (1980), pp. 131–136.

[MMM12] Abdelhakim El Maftouhi, Yannis Manoussakis, and Olga Megalakaki. “Balance in Random Signed Graphs”. In: Internet Mathematics 8.4 (2012), pp. 364–380. doi: 10.1080/15427951.2012.719877.