[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? Westeros的命运吗？
[MUSIC PLAYING] 音乐
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 这些网络可能表示Facebook上的好友
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-- Ned，Robert，和Rhaegar——
who are all friendly, symbolized by the green edges. 他们都是友好的，用绿边表示。
But if Rhaegar and Robert get into a fight, 但如果Rhaegar和Rober打了起来，
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-- Ned，Robert，Rhaegar都是朋友——
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 但如果Robert和Rhaegar打了起来，
so there's one red and two green edges? 于是有了一条红边和两条绿边，会怎样呢？
That's an awkward position for Ned. 对Ned来说这是一个尴尬的处境。
He's likely to either pick a side 他可能选边站
and become enemies with Robert or Rhaegar, which 从而与Robert或Rhaegar为敌，
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 不幸的是，对Rhaegar来说，那
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 现在，Robert和Rhaegar是对立的，
and Ned and Rhaegar are fighting. 而Ned和Rhaegar也是对立的。
Here applies the saying, the enemy of my enemy is my friend. 这里应用了这个说法，敌人的敌人就是朋友。
Ned and Robert agree that Rhaegar is bad news. Ned和Robert都认为Rhaegar是坏消息。
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. 绿色或红色，确切地说，是32768种。
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 当Montagues家族和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 实际上，在1953年Frank Harary证明了
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 对Westeros来说，许多不同派别
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 因为Skyval Ream回答了几乎
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 Edelopo问如果所有选民没有区别
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 Cantor's Cat和David de Kloet是我们
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. 谢谢大家。