Homework VIII: Balance and Signed Graphs

Signed Graphs

Figure 1: A directed signed graph.

Figure 1 is a directed signed graph. In the figure teal edges represent positive ties between the two nodes and red edges represent negative ties.

  1. Write the directed signed graph’s positive edge set.





  2. Write the directed signed graph’s negative edge set.





  3. In the matrix below, write down the cell entries for the adjacency matrix corresponding to the graph shown in Figure 1:

A B C D E F G H I
A ----
B ----
C ----
D ----
E ----
F ----
G ----
H ----
I ----

Balanced and Unbalanced Triads

Figure 2: A complete signed graph.

Figure 1 is a complete signed graph. In the figure teal edges represent positive ties between the two nodes and red edges represent negative ties.

  1. Write down all the balanced triads in the graph (you refer to a triad by listing all three nodes in it, like ABC):













  2. Write down all the unbalanced triads in the graph:













  3. How many balanced triads with all positive edges exist in the graph?



  4. How many balanced triads with two negative edges exist in the graph?



  5. How many unbalanced triads with three negative edges exist in the graph?



  6. How many unbalanced triads with one negative edge exist in the graph?



For the following questions write either “positive” or “negative” as a possible answer. Remember that showing your work helps you get partial credit.

  1. What is the sign of the path ADFBC?





  2. What is the sign of the path CDEBFA?





  3. What is the sign of the cycle BDEFB?





  4. What is the sign of the cycle CADFC?





Structural Balance

Figure 3: A complete balanced signed graph.

Cartwright and Harary’s fundamental theory of structural balance says that in a balanced signed graph like the one in Figure 2, the node set can be divided into two cliques (subset of nodes) such that there are only positive ties among members of the clique and negative ties with members of the other clique.

  1. Write down the nodes that belong to each of the two cliques in Figure 2:

  • First clique:





  • Second clique: