Signed Networks and Social Balance Flashcards
What is a signed network?
A signed network is an undirected graph, where each as is either labeled “+” or “-“.
What is the sign of a path?
A sign of a path or cycle is “+”, iff. there is an even number of “-“ signs along the path.
A sign of a path or cycle is “-“, iff. there is an odd number of “-“ signs along the path.
What is a balanced graph?
- A graph is balanced, iff. every cycle has a positive sign
What is the Cartwright-Harary Theorem?
If a labeled complete graph is balanced, then either all pairs of nodes are friends, or else the nodes can be divided into two groups (X and Y) such that every pair of people in Y like each other, and everyone in X is the enemy of everyone in Y.
–> Not necessarily a good thing
What is a weakly balanced network?
A complete graph with each edge labelled by + or - is weakly balanced, if there is no set of three nodes such that the edges among them consist of exactly two positive and one negative edge.
Theorem: If a labeled complete graph is weakly balanced, then its nodes can be divided into groups in such a way that every two nodes belonging to the same group are friends and every two nodes belonging to different groups are enemies.
When is a non complete graph balanced?
In local view: Balanced, if it can be completed by adding edges to form a signed completed graph that is balanced.
Global View: Division of the network into two mutually opposed sets of friends
Actually equivalent.
