[MUSIC PLAYING] From the theory of social networks, we can mathematically model and analyze the relationships between people or countries or organizations or groups.

Could this method be used to predict the outcome of Game of Thrones and determine the fate of Westeros?

[MUSIC PLAYING] 12 00:00:25,690 --> 00:00:28,960 Commonly in the field of social network analysis, one uses a graph, also called a network, where the vertices or nodes represent individuals and the edges represent something about the relationships or interactions between individuals.

These networks might represent Facebook friendships or help us understand the spread of disease.

For now, we'll focus on one model of a social network that encodes whether the relationships are positive or negative, in other words, if they're friendly or hostile and the notion of structural balance.

For example, this graph shows three people-- Ned, Robert, and Rhaegar-- who are all friendly, symbolized by the green edges.

But if Rhaegar and Robert get into a fight, we can switch the edge to red to indicate their new status as enemies.

Among three individuals, there's only four essentially different relationship triangles-- all three relationships are green, two are green and one is red, one is green and two are red, or they're all red.

Theories in social psychology suggest that some of these configurations, like the one with all green edges, are more stable than others.

They call these stable triangles structurally balanced.

If the triangle has three green edges-- Ned, Robert, and Rhaegar are all friends-- then the triangle is balanced, everyone is content, and no one has a reason to change from friends to enemies.

But what if Robert and Rhaegar get into a fight so there's one red and two green edges?

That's an awkward position for Ned.

He's likely to either pick a side and become enemies with Robert or Rhaegar, which means they'll switch to two red edges, or he'll convince them to become friends again and they'll switch back to all green.

Unfortunately, for Rhaegar, that's not the way the story played out.

Because of this instability, we say that the triangle with one red and two green edges is not balanced.

What if we have two red edges and one green?

Now, Robert and Rhaegar are fighting and Ned and Rhaegar are fighting.

Here applies the saying, the enemy of my enemy is my friend.

Ned and Robert agree that Rhaegar is bad news.

He's got to go.

No one has motivation to change the relationships and the triangle is balanced.

Finally, the triangle with all red edges, where everyone is fighting with everyone else, is not balanced.

It's likely two people will join forces uniting around a common enemy.

So these two triangles with one or three green edges are balanced and these two with zero or two green edges are not.

The assumptions behind this idea of structural balance are, of course, overly simplistic.

Social relationships are complicated, but we can still learn about them by exploring the mathematical consequences of this model.

With that in mind, let's extend this idea of structural balance to a bigger network like this one.

Each vertex represents a person and the edges encode the nature of their relationship, either green-- friends-- or red-- enemies.

Notice that any two people are either friends or enemies, that is, every person is connected to every other person by either a green or red edge.

This kind of graph, where every vertex is connected by an edge to every other vertex, is called a complete graph.

We'll focus on complete graphs which correspond to real world situations where everyone knows everyone else, such as a classroom.

Pick any three people in the graph.

Those three vertices and the edges that connect them form a triangle.

That little triangle is either balanced or not.

The graph has many different triangles in it, one for every group of three people.

And each triangle is either balanced or not.

If each of these little triangles, all the ones formed by selecting groups of three, are balanced, then we say that the complete graph is also balanced.

This is a pretty strict condition.

If just one triangle is unbalanced, the entire graph is unbalanced.

There are other ways we could have chosen to extend the definition of structural balance to bigger networks.

And each definition would have different consequences and applications, but for now, we'll stick with a very local definition of balance.

The network is balanced because all of its triangles are balanced.

There are many different ways to color the edges of this graph green or red, 32,768 to be exact.

Some of those labeling are balanced and some are not.

Given a specific coloring, an assignment of friends or foes, we can simply look at each of its triangles, check whether they're balanced, and conclude whether or not the entire network is balanced.

But as mathematicians, we like to make bigger, more general statements.

Are there categories or types of labelings that are always balanced or always unbalanced?

Pause here if you want to think about it.

The simplest way to label the graph so that it's balanced is to color everything green-- everyone is friends with everyone else.

In this case, each triangle inside the graph is all green and is obviously balanced.

Another way a graph can be balanced is if it splits into two rival factions.

All these vertices are friends with each other and all these vertices are friends with each other, but any two vertices in opposite groups are enemies.

From a social perspective, the fact that a network is balanced isn't necessarily a good thing.

It's closer to a stalemate than a state of harmony.

For example, things were unpleasant when the Montagues and the Capulets were perpetually feuding, but it wasn't until Romeo and Juliet fell in love, which sent their network out of balance, that things began to change.

They were balanced as two rival groups and then, again, at the end with everyone at peace, but not while Romeo and Juliet were crossing group lines.

In fact, in 1953, Frank Harary proved that these are the only two ways a complete graph can be balanced.

In other words, in a complete balanced graph, either everyone is friends with everyone else or the vertices of the graph split into two groups where each individual is friends with each other member of its group and enemies with each member of the other group.

That's it.

Those are all the complete balanced graphs.

Let's prove this theorem.

We'll start by assuming we have some balanced complete graph.

The edges might all be green, but that's the boring case so let's assume at least one edge is red.

Our goal is to divide the vertices into two rival factions to prove the theorem.

This might seem tricky since we don't know anything specific about the number of green or red edges or where they are.

We only know the graph is balanced, but that's all we need to know.

We assumed the graph has at least one red edge so let's start there.

There are two vertices on either side of this edge.

We'll focus on this purple one.

The purple vertex is connected to every other vertex by either a green or red edge.

Color all the purple vertexes friends, the ones it's connected to by a green edge, blue.

And color all the purple vertexes enemies, the one it's connected to by a red edge, yellow.

These are the two rival groups.

The blue vertices plus the purple one form a group and the yellow vertices form a group.

How do we know everyone is friends with the other members of their group?

Let's look at two yellow vertices.

They are both enemies with the purple vertex so they must be friends with each other to form a balanced triangle.

Two blue vertices are both friends with the purple vertex so they must also be friends to form a balanced triangle.

How do we know all the blues are enemies with all the yellows?

Blue is friends with purple and yellow is enemies with purple so the only way to form a balance triangle is if blue and yellow are enemies.

We started by assuming each of the triangles in the graph is balanced which is a local property.

It's about how any three people interact with each other and we proved a global property, that the entire graph must split into two enemy groups.

Knowledge of small scale interactions told us something about the group's big scale interactions.

The vertices of the network can represent things besides people, like countries.

Here's an example from World War I.

Each graph represents the changing relationships between Great Britain, France, Russia, Italy, Germany, and Austria-Hungary as they shifted alliances.

Each graph is structurally unbalanced until, finally, they split into two groups-- a balanced configuration.

In this balance state, no one could easily be persuaded to change alliances which lead to war.

In the description, we've linked to a paper describing this example.

As for Westeros, so many different factions are fighting with each other, they're nowhere near structurally balanced, but there may be a stable configuration in their near future.

And just for fun, what happens if we tweak the definition of structural balance?

Let's define a complete graph to have weak structural balance if none of the triangles in the graph have two green edges and one red edge.

In our previous definition of structural balance, we forbid both of these triangles, but now, we only forbid this triangle.

Under this weaker definition of structural balance, what colorings of the complete graph are balanced?

Just like before, everyone can be friends or they can split into two rival groups, but this weaker definition of structural balance also allows some other possibilities.

Here's your challenge problem for the week.

What are all the possible colorings of complete graphs that have weak structural balance?

In other words, how can we color a complete graph so there is no forbidden sub-triangle-- two green and one red.

Can you prove your guess?

Leave your answer in the comments.

Hello.

I don't have many comments to respond to this week because Skyval Ream pretty much answered all the questions which is awesome for me because I can just go to the beach sooner, so thanks.

I found one question I wanted to respond to.

Edelopo asked if all voters were indistinguishable if they're all treated equally?

That's a great question and the answer is no.

In the case of a dictatorship, that's where one voter is very different than the rest, but you can also have voting systems where some people's votes count a little more than others.

Good question.

So I want to get to our challenge winners.

Cantor's Cat and David de Kloet are our collective challenge winners.

They proved that a polarizing candidate is either first or last in the overall ranking using a voting system with unanimity and independence of irrelevant alternatives.

And their proof is in a collective thread where they're collaborating, answering each other's questions and I love collaboration so go read the thread and check it out.

Thanks guys.