# Structural Balance

```Positive and Negative Relations
CMSC 498J: Social Media Computing
Department of Computer Science
University of Maryland
Spring 2015
[email protected]
Announcement
• Survey!
▫
▫
▫
▫
Timing
Project
Lectures
HWs
2
Lecture Topics
• Balanced and Unbalanced Networks
• Structure of Balanced Networks
▫ Weakly Balanced Networks
3
Structural Balance
• We viewed networks as having positive
connotations
▫ friendship, collaboration, membership relations, etc.
• But there are also negative relations in networks.
Support / Oppose
relations
Trust / Distrust
relations
Friend / Foe
relations
How should we reason about these networks?
4
Structural Balance- Cnt.
• Given a network, how can we annotate its links with
positive and negative signs?
• Structural Balance is one basic framework for
this purpose.
5
Structural Balance- Cnt.
• Let’s assume we have Complete Graph with links
labeled by + and – signs.
▫ Each pair of nodes are either friends or enemies
▫ Makes sense for a group of people with mutual
awareness
 a classroom, a small company, a sports team, a
fraternity or sorority, or
 international relations where nodes are countries.
We will relax the complete graph assumption later.
6
Structural Balance- Cnt.
• Considering any 2 people in isolation, the edge
between them can be labeled + or –
▫ they are either friends or enemies.
+
-
7
Structural Balance- Cnt.
triangles with one or three +'s as balanced
+
+
-
+
-
+
+
+
-
-
-
-
Balanced
Unbalanced
triangles with zero or two +'s are unbalanced
• But for 3 people, certain configurations are
socially / psychologically more plausible.
8
Structural Balance- Cnt.
• Which type is more abundant in real world
networks?
▫ People try to minimize unbalanced triangles in their
personal relationships as they are sources of stress or
psychological dissonance.
9
Structural Balance Property
• A Labeled Complete Graph is balanced if every
one of its triangles is balanced!
• Structural Balance Property
▫ For every triangle, either all its three edges are
labeled +, or else exactly one of them is labeled +.
10
Structural Balance Property- Cnt.
11
Structural Balance Property- Cnt.
• Extreme definition!
12
Structure of Balanced Nets
• What does a balanced network look like in general?
a
j
b
i
c
d
2 groups of friends (A-B and C-D),
with negative relations between
the 2 groups!
13
Structure of Balanced Nets- Cnt.
• If a Labeled Complete Graph is balanced, then
either:
▫ The network contains only positive edges, or
▫ Global division of network:
 Nodes can be divided into 2 groups X and Y such that:
 a pos link btw every pair of nodes in X,
 a pos link btw every pair of nodes in Y, and
 a neg link btw every node of X and every node of Y.
+
X
-
+
Y
Balance Theorem: These are the only ways to have a balanced network!
14
Structure of Balanced Nets- Cnt.
• Prove balanced theorem!
• Solution:
▫ Consider the network from a node’s perspective!
 Pick any node in the network, say node A,
 Let X be all of A's friends, and Y be all of A's enemies.
 This divides all nodes as the graph is complete!
▫ Prove:
 Every two nodes in X are friends, and
 Every two nodes in Y are friends, and
 Every node in X is an enemy of every node in Y.
15
Structure of Balanced Nets- Cnt.
X
Y
16
Structural Balance- Applications
• How does such a social network, labels of edges,
evolve over time?
• Social networks implicitly seek out structural
balance!
17
App 1. International Relations
• Separation of Bangladesh from Pakistan in 1972
▫ Why did US support Pakistan?





USSR was China’s enemy
China was India’s enemy
India was Pakistan’s enemy
US was China’s friend
18
App 2. International Relations
• World War I
Fr: France
Ru: Russia
It: Italy
Ge: Germany
AH: AustriaHungary
GB: Great
Britain
Structural Balance is not necessarily a good thing : hard-to-resolve opposition between two sides.
19
App 3. Trust and Distrust
• Networks with positive or negative relations!
▫ slashdot.com, epinions.com
• Important to understand the Nature of
Relationships!
▫ A trusts B, B trusts C -> natural to expect A trust C.
▫ What if A distrusts B and B distrusts C:
 A should trust or to distrust C?
 Distrust as enemy relationship:
▫ A should trust C, otherwise a triangle with 3 negative edges.
 Distrust as less knowledge relationship:
▫ A should distrust C (even more strongly than B).
Propagation of trust and distrust. Guha, et. al. WWW 2004.
20
Weak Structural Balance
Friends of friends may try to reconcile their
differences
+
+
+
+
-
2 of the 3 mutual enemies ally themselves
against the third one!
-
21
Weak Structural Balance
• Weak Structural Balance Property
▫ There is no triangle with exactly two positive edges
and one negative edge.
3 Mutual enemies are allowed as there could be less of a
force leading any 2 of them to become friend as compared
to the first case (mutual enemies with a common friend to
-
-
reconcile)!
-
22
Structure of Weakly Balanced Nets
• What does a weakly balanced network look like?
▫ If a Labeled Complete Graph is weakly balanced,
then its nodes can be divided into groups such that:
 every 2 nodes in the same group are friends, and
 every 2 nodes in different groups are enemies.
Weakly Balance Theorem: This is the only way to have a weakly balanced network!
23
Structure of Weakly Balanced Nets
• Prove weakly balanced theorem!
• Solution:
▫ Consider the network from a node’s perspective!
 Pick a node in the network, say node A,
 Let X (our 1st group) consist of A and all of A's friends,
▫ Prove:
 X is a group of mutual friends.
 A's friends are friends with each other.
 Nodes in X are enemies of nodes not in X.
 A and his friends are enemies with other nodes in graph.
24
Structure of Weakly Balanced Nets
X
Remove X from the graph and let it be 1st group.
The smaller graph is still weakly balanced, why?
Find others group in this way until all the nodes are assigned to a group.
25
Questions?
26
• Ch.05 Positive and Negative Relationships [NCM]
27
```