P1 Structure of Graphs

So what I want to do in the next last 20 minutes
所以我想在接下来的20分钟内做什么

I wanna go and just talk about concepts
我想去谈论概念

vocabulary for talking about graphs so that we are all on the same page
讨论图表的词汇，以便我们都在同一页面上

Right? So
对？所以

Our network is a collection of objects, where some pairs of objects
我们的网络是对象的集合，其中一些对象对

are connected, or with links, or interact with each other
连接，或链接，或彼此交互

and what we’ll be interested in are early on is to think about what
而我们感兴趣的是尽早考虑

Structure of Networks?

How do we describe a structure of the network, right?
我们如何描述网络的结构，对吗？

So
所以

Components of a Network

Essential I’ll have two types of things
必不可少的我有两种类型的东西

I will have these objects or entities that I will call nodes
我将拥有这些我称为节点的对象或实体

or I will call them vertices
否则我称它们为顶点

And then I will have interactions between pairs of objects
然后我将在成对的对象之间进行交互

that I will call these interactions links or edges
我将这些交互称为链接或边缘

and nodes are usually denote as N the set of edges are really denote as capitally
节点通常用N表示边的集合实际上用资本表示

and then the graph of the network is a graph that has a set of nodes and a set of edges
然后网络图是具有一组节点和一组边的图

Right
对

So that’s
所以那是

That’s a graph
那是一张图

And here is here’s an example
这是一个例子

Networks or Graphs?

OK
好

now I
现在我

as I mentioned early on the way we will try to say
正如我在前面提到的那样，我们将尝试说

is when I say network
当我说网络

I will usually use it to refer to a real system
我通常会用它来指代一个真实的系统

I can take a social network
我可以参加社交网络

I can say metabolic network and you can
我可以说代谢网络，你可以

and graph
而图

is a mathematical representation of the network
是网络的数学表示

So I can think of the Social graph
所以我可以想到社交图

Knowledge graph
知识图

Web graph
网络图

All right and I will try to make this distinction as clear as possible
好的，我会尽力使这种区分尽可能清楚

but in many cases we’ll be using the two simultaneously
但在许多情况下，我们会同时使用两者

So don’t get in some things
所以不要进一些东西

don’t get too confused
不要太困惑

Networks : Common Language

And as I said before
正如我之前所说

what is beautiful about networks is this kind of common language
网络的优点是这种通用语言

that you can go and analyze how actors collaborate with each other
您可以去分析演员之间的合作方式

You can go and analyze how different people are related to each other
您可以分析不同的人之间的关系

or you can go and analyze how molecules go and interact with each other
或者你可以去分析分子如何去相互影响

And the point is that all these different domains
关键是所有这些不同的域

all these cases at the end have the same underlying mathematical representation
最后所有这些情况都具有相同的基本数学表示形式

of four nodes, in four edges, or four interactions.
四个节点，四个边缘或四个交互中的一个。

Right?
对？

And what is the very important is to choose a proper representation for a given question
最重要的是为给定问题选择适当的表示形式

Right
对

If I, for example
例如，如果我

connect individuals into the network based on whether they work together
根据他们是否一起工作将个人连接到网络

I will be defining a professional network, right?
我将定义一个专业网络，对吗？

If
如果

for example
例如

I would connect people who had sexual relationships with each other
我会联系有性关系的人

I would be exploring sexual networks
我会探索性网络

It’s a different kind of network, OK?
是另一种网络，好吗？

and if I would connect scientific papers that cite each other
如果我能互相引用互相引用的科学论文

I would be studying a citation network, right?
我会研究一个引文网络，对吗？

Choosing Proper Representations

• 如果您将彼此合作的人联系起来，那么您将探索一个专业的网络
• ¡如果您与有性关系的人建立联系，那么您将探索性网络

• ¡如果连接相互引用的科学论文，您将在研究引文网络

• ¡如果您用标题中的相同单词连接所有论文，您将探索什么？ 尽管如此，这是一个网络

so it will be very important in some sense that for the question we have in mind
因此从某种意义上来说，对于我们要考虑的问题非常重要

we choose appropriate network representation, right?
我们选择合适的网络代表，对不对？

So we find I’m interested in monitoring
所以我们发现我有兴趣进行监控

the spread of diseases may be sexually transmitted diseases
疾病的传播可能是性传播疾病

This is the network I would want to use if I want to measure the spread of scientific ideas
如果要衡量科学思想的传播，这是我要使用的网络

I would probably use the citation network and so on
我可能会使用引文网络等

OK
好

So how do you define a network?

那么如何定义网络？

• 如何建立图表：
  • §什么是节点？
  • §什么是边缘？
• 选择给定域/问题的正确网络表示形式，决定了我们成功使用网络的能力：
  • §在某些情况下，存在唯一，明确的表示形式
  • §在其他情况下，表示绝不是唯一的
  • §分配链接的方式将决定您可以研究的问题的性质

You need to ask yourself what are the nodes and what are the edges
您需要问自己什么是节点，什么是边

and as I said,
正如我所说，

the choice of proper network representation of a given domain or a problem
选择给定域或问题的适当网络表示形式

We’ll basically determine our ability to use networks successfully
我们将基本确定我们成功使用网络的能力

in a sense that in some cases
在某种意义上说

this network representation will be unique
该网络表示形式将是唯一的

unambiguous and in other cases
明确的，在其他情况下

represent they like the way to encode network or the mean of the network
代表他们喜欢网络编码方式或网络均值

won’t be clear at the beginning
一开始不会很清楚

so it will require some intuition and some experimentation, right?
所以需要一些直觉和一些实验，对吗？

and the way we design links will essentially determine the questions will be able to study
而我们设计链接的方式从本质上决定了可以研究的问题

So what I wanna do next is show you some examples or some choices of the network’s representation
所以我接下来要做的是向您展示一些网络表示的示例或选择

and again
然后再次

by doing this
通过做这个

I’ll be introducing vocabulary and concept
我将介绍词汇和概念

Directed vs. Undirected Graphs

so you can think about two types of networks
因此您可以考虑两种类型的网络

you can think about undirected networks and you can think about directed networks
您可以考虑非定向网络，也可以考虑定向网络

and the only difference is that you know one has arrows on the edges
唯一的区别是您知道边缘上有箭头

so edges are directed
所以边缘是有方向的

and in one case
在一种情况下

edges are undirected
边缘是无向的

So if you think what would be a good example of these types of networks
因此，如果您认为这将是此类网络的一个很好的例子

could be collaborations right if we work together
如果我们一起工作，可能是正确的合作

it’s not that I work with you
不是我和你一起工作

but you don’t work with me
但是你不和我一起工作

so it’s kind of a mutual relationship or friendships
所以这是一种相互关系或友谊

for example in the Facebook network are also undirected, right?
例如在Facebook网络中也是非定向的，对吗？

But if you think about directed cases
但是，如果您考虑直接案例

you could imagine phone calls
你可以想象电话

because every phone call has an originator and has a destination
因为每个电话都有始发者和目的地

Or if you think about following edges on Twitter
或者，如果您考虑在Twitter上追随优势

those are naturally directed right
那些自然是对的

I follow you
我跟着你

You don’t necessarily follow me back
你不一定跟着我

but if you follow me back
但是如果你跟着我回来

then it would have this type of edge in one direction and another edge in the other direction
那么它将在一个方向上具有这种类型的边缘，而在另一个方向上具有另一种边缘

So that directed versus undirected
因此，有向与无向

Node Degrees

Then the next concept that is important is is this notion of a degree of a node
那么下一个重要的概念是节点度的概念

and degree of a node is simply the number of edges that touch a given note
节点的度只是接触给定音符的边数

So
所以

for example node A here
例如这里的节点A

here’s the degree 4
这是4度

because there are 4 edges that touch the node and this is in undirected graphs
因为有四个接触该节点的边，这在无向图中

You talk about the degree in directed graphs
您谈论有向图的程度

You talk about in degree and out degree, right?
你说的是学位和学位，对吗？

So
所以

for example
例如

the note C here has in degree of 2 because there are 2 edges pointing to it
这里的音符C的阶数为2，因为有2个边指向它

and has out the degree of 1 because there is 1 edge pointing out of a node C
且度数为1，因为有1个边指向节点C

and then
然后

for example
例如

here in these types of you can also talk about source node and sink notes
在这些类型的这里，您还可以讨论源节点和接收器注释

So
所以

for example
例如

node that G is a source node because there is no other notes pointing to it
G是源节点的节点，因为没有其他注释指向它

and then you could define a sink node
然后您可以定义一个接收器节点

this is an node with out degree 0
这是度数为0的节点

there is no sink in this graph
该图中没有下沉

Okay
好的

so those are the concept of degree
所以这些是度的概念

which is the number of edges a node has
这是一个节点的边数

and then
然后

of course
当然

you can define an average degree
您可以定义平均程度

which is simply the average over the degrees of the node
这只是节点度数的平均值

And if you think about it the way the average is the total number of edges times two divided by the number of nodes
如果考虑一下，平均值就是边的总数乘以2除以节点数

and the reason why that number two is up there
以及第二个出现的原因

because when you count degrees every edge point
因为当你数度每个边缘点

every edge gets counted twice because every edge has two end points
每个边缘都有两次计数，因为每个边缘都有两个端点

That’s the reason for it
这就是原因

Complete Graph

A very special type of graph is called a complete graph
图的一种非常特殊的类型称为完整图

and a complete graph is a graph where there are all the edges between all the notes
完整的图是所有音符之间都有边的图

And if you ask how many edges are possible in a graph of N nodes
如果您问在N个节点的图中可以有多少条边

the number of possible edges is N choose 2 if the graph is undirected right
如果图形是无向的，则可能的边数为N选择2

So this would be N times N minus one divided by 2
因此，这将是N乘以N减去1除以2

So it’s kind of the number of edges is quadratic in the number of nodes, right?
所以这是边的数量是节点数量的二次方，对吗？

And this would be called if you have a graph where everyone links to everyone
如果您有一个图表，其中每个人都链接到每个人，则这将被称为

you have a complete graph
你有一个完整的图

Here is an example
这是一个例子

OK
好

and now what I wanted to to show is another special type of graph
现在我想展示的是另一种特殊类型的图

That is called a bipartite graph
那就是所谓的二部图

• 二部图是一种图，其节点可以分为两个不相交的集合U和V，

  从而每个链接都将U中的节点连接到V中的一个节点。
  也就是说，U和V是独立的集合

• 例子：

  • §作者草稿（由作者撰写）
  • §电影演员（他们出现在）
  • §电影用户（他们评价）
  • §配方成分（包含）
• ¡“折叠式”网络：
  • §作者协作网络
  • §电影分级网络

and this was an example of a graph and I was telling you about the Pinterest use case and bipartite graph
这是一个图的示例，我告诉您有关Pinterest用例和二部图的信息

the idea is that we have these two sides to partitions
这个想法是我们将这两个方面都划分为分区

left and right, and edges can only cross the partition, right?
左右，边缘只能穿过隔板，对吗？

So the red nodes don’t link to each other
因此，红色节点不会相互链接

green nodes don’t link to each other
绿色节点不相互链接

but edges only go from between red and green.
但是边缘仅在红色和绿色之间。

And these types of graphs are useful when you have different types of nodes
当您具有不同类型的节点时，这些类型的图很有用

so
所以

for example
例如

you could connect authors to the papers they have written
您可以将作者与他们撰写的论文联系起来

or you could connect actors to the movies in which they appeared
或者您可以将演员与出现的电影联系起来

or maybe users to the movies they liked or they rated or they watched
或用户喜欢他们喜欢的电影或他们评分或观看的电影

or may be recipes to ingredients they contact
或可能是他们接触的食材的食谱

You can create networks out of food recipes
您可以根据食物食谱创建网络

it’s super fascinating
超级迷人

so this is one way how we could create a network out of the food
所以这是我们可以从食物中建立网络的一种方式

and then as we have defined this notion of a bipartite graph
然后我们定义了二部图的概念

Folded/Projected Bipartite Graphs

I also want to define this notion of a Folded Graph
我也想定义折叠图的概念

where the idea is that you think the bipartite graph and you fold it in a sense that
想法是您认为二部图，然后在某种意义上将其折叠

you connect two nodes on one side if they share at least one common neighbor
如果它们共享至少一个公共邻居，则在一侧连接两个节点

So
所以

for example
例如

if you think of this as the authors to the paper’s write, right?
如果您认为这是该论文的作者，对吗？

then the Folded Network would be a collaboration network
那么折叠网络将是一个协作网络

because C and D would be connected because they have coauthored a paper together right
因为C和D之所以会被连接是因为他们共同撰写了一篇论文

and this would be now
这将是现在

let’s say
比方说

a collaboration network
协作网络

So the way to show this pictorially
因此，以图形方式显示此内容的方式

here is the bipartite graph
这是二部图

and then here are two examples of the folded networks
这是折叠网络的两个例子

If I fold to the right partition or if I fold to the left partition
如果我折叠到右分区或如果我折叠到左分区

And the point is the following you know why C and D are connected
重点是以下内容，您知道C和D连接的原因

C and D are connected because they have a neighboring common number 5
C和D已连接，因为它们具有相邻的公共数字5

or for example
或者例如

why A and C are not connected because A and C don’t have a yellow node in common
为什么A和C没有连接，因为A和C没有共同的黄色节点

But for example
但是例如

B and C have a yellow node in common
B和C共有一个黄色节点

it’s number 5 and then on this
它是5号，然后在此

on this side
在这边

everything is the same
一切都一样

We connect 6 and 7 because they have a neighboring D
我们连接6和7，因为它们有一个相邻的D

so there is an edge 6 and 7, okay?
所以有6和7的优势，好吗？

and this is called folded or projected bipartite graph
这称为折叠或投影二部图

Okay
好的

Good
好

So now that kind of I’ll showed you these graphs and defined some concepts
现在，我将向您展示这些图并定义一些概念

Representing Graphs: Adjacency Matrix

Next thing is that how do you represent a graph?
接下来的事情是，您如何表示图表？

Right?
对？

So far we’ve just drawn circles and lines
到目前为止，我们仅绘制了圆和直线

but the way you represent the graph
但是你代表图形的方式

there are two ways to do that
有两种方法可以做到这一点

One way to represent these to represent it as a matrix
表示这些的一种方式将其表示为矩阵

and this matrix is called an adjacency matrix and adjacency matrix is the following objects
这个矩阵叫做邻接矩阵，邻接矩阵是下面的对象

Adjacency Matrix 邻接矩阵

so essentially the number of rows and the number of columns equals the number of nodes
所以从本质上说，行数和列数等于节点数

and then there is a 1 or a 0
然后有一个1或0

where 1 says that a given pair of nodes is connected right
其中1表示给定的一对节点正确连接

so if nodes I and J are connected than that entry that cell of the adjacency matrix is 1 and otherwise that the given entry is 0, right?
所以如果节点I和J连接，那么矩阵的那个单元格的条目是1，否则给定的条目是0，对吧？

So for example you ask
所以例如你问

why is there this thing
为什么有这个东西

this one here
这里这个1

So this is the second row first column
所以这是第二行第一列

so this would be saying that node number 2 is linking to node 1
所以这就是说节点号2链接到节点1

and yes
是的

it is right
这是正确的

or for example down here
或者例如在这里

This would say that node number 4 links to node number 1 and there is a link
这表示4号节点链接到1号节点，并且存在一个链接

there, right?
在那里，对吗？

And one thing you notice is that if the graph is undirected
您注意到的一件事是，如果图形是无向的

then this adjacency matrix is symmetric across the diagonal, right?
那么这个邻接矩阵在对角线上是对称的，对吗？

because if 1 links to 4
因为如果1链接到4

then 4 links to 1 as well, right?
那么4个链接也就1个吧？

so it has to be symmetric
所以它必须是对称的

If the graph is directed
如果图形是有向的

then it means it is not symmetric, right?
那就意味着它不对称，对吗？

For example
例如

2 links to 1
2链接到1

but 1 does not link to 2
但是1没有链接到2

Right so 1 does not link to 2, but 2 links to 1
正确，因此1不会链接到2，但是2链接到1

and there is an example of that
有一个例子

So one way
所以一种方法

how I can represent the graphs is through this adjacency matrices
我如何通过相邻矩阵表示图

as they are called
他们被称为

And the way now you can think of adjacency matrices
现在您可以想到邻接矩阵的方式

For example
例如

if I wanna compute the degree of a given node
如果我想计算给定节点的度数

I simply ask how many non zero elements are in a given column or in a given row, right?
我只是问给定列或给定行中有多少个非零元素，对吗？

So if I say what’s the degree of note 2
所以如果我说注释2的程度是多少

I can sum down the column number 2
我可以总结第二列

and I would get 2 and really the node number 2 really has degree 2, right?
我会得到2，实际上2号节点的确具有2级，对吗？

and the same thing then kind of happens for directed graphs
然后有向图发生同样的事情

where you know
你知道的地方

out degrees are sums over the rows and in degrees are sum over the columns, right?
出度是行数之和，进度是列数之和，对吗？

So the in degree of note number 4 it should be 1
所以音符4的度数应该是1

and here’s the edge, right?
这是优势，对不对？

But for example
但是例如

out degree of node number 4 should be 2
4号节点的出站度应为2

So here it is
所以这是

and it is two
这是两个

OK
好

so that’s how I can
所以我可以这样

for example
例如

compute degrees
计算度

One interesting thing is now that you can take a real graph and plot the matrix
现在一件有趣的事是，您可以拍摄真实的图形并绘制矩阵

The way you plot the matrix is that 0s will be white and 1s will be dots
绘制矩阵的方式是0将为白色，而1将为点

OK
好

So here’s a graph
这是一张图

Right so this is a graph with, I know several thousand nodes
对，所以这是一个有几千个节点的图

and then every dot means that this particular node links to that particular note
然后每个点都表示该特定节点链接到该特定音符

and if there is an empty spot
如果有空的地方

this means that this particular set of notes doesn’t link to that particular set of notes
这意味着该组特定注释不会链接到该组特定注释

Right, so this is
对，这是

this is a graph
这是一张图

Adjacency Matrices are Sparse

These are types of things we will be studying in this class, right?
这些是我们将在本课中学习的类型的东西，对吗？

So this is just a different representation of a graph
所以这只是图的不同表示

This is now the adjacency matrix representation
现在是邻接矩阵表示

There is another representation of graph where you can basically
图形的另一种表示形式

think of it as we are representing a graph as a set of edges
考虑一下它，因为我们将图形表示为一组边

and this now defines the graph, right?
现在定义了图表，对吗？

So for the graph on the right
所以对于右边的图

here is the edge list representation for the graph
这是图形的边缘列表表示

Right?
对？

so
所以

we said
我们说

we talked about adjacency matrix
我们讨论了邻接矩阵

we talked about the edge list and really what is the preferred graph representation that
我们讨论了边缘列表，实际上首选的图形表示是什么

most kind of software libraries use is what is called an adjacency list where for every node
多数软件库使用的是所谓的邻接表，其中每个节点

Representing Graphs: Adjacency list 表示图：邻接表

you store what’re the neighbors or what’re other nodes
您存储什么是邻居或其他节点

the that note links to so essentially you have a vector
那个笔记链接到本质上你有一个向量

or a list for every node of its neighbors,
或其邻居的每个节点的列表，

and this allows you to work with very large graphs
这使您可以处理非常大的图形

Now I wanna show you the first interesting property of graphs
现在我想告诉你图的第一个有趣的特性

so here are some examples
所以这是一些例子

so I have different networks
所以我有不同的网络

like the web graph between Stanford and Berkeley
像斯坦福大学和伯克利大学之间的网络图

social network of LinkedIn
领英的社交网络

some MSN communication networks
一些MSN通信网络

co-authorship graphs
合着图

graphs of the Internet
互联网图

the road network of California
加州公路网

and some protein interaction graph
和一些蛋白质相互作用图

And then this is the number of nodes, right?
这是节点数，对不对？

Like here is 240 million notes
像这里的2.4亿张钞票

for example
例如

and this is the average degree
这是平均程度

This is the average number of connections a node has
这是节点具有的平均连接数

And one thing that is already quite surprising
一件事已经很令人惊讶

that follows is that
接下来是

regardless of how big this networks are
不管这个网络有多大

this average degree is a relatively tiny
这个平均程度是相对较小的

Right?
对？

so for example
例如

here in this network
在此网络中

this is a Microsoft Instant Message network, think of it as a What’s App type chat
这是一个Microsoft Instant Message网络，可以将其视为“应用程序类型”聊天

You have 240 million people
你有2.4亿人

but on average every person only talks to 11 of them
但平均每个人只与其中11个人交谈

Right. or in other cases as well
对。或在其他情况下

So the point is that, in principle every note could talk to 240 million others
因此，重点是，原则上每个音符都可以与2.4亿个其他音符进行通话

but at the end it only talks to 11
但最后只和11说话

So the point is that these networks are amazingly sparse
关键是这些网络非常稀疏

in a sense that the average degree is much much smaller than the maximum possible degree
在某种意义上，平均程度远小于最大可能程度

And what this means is that this adjacency matrices will be amazingly sparse
这意味着邻接矩阵将非常稀疏

right that
对的

for example
例如

10 to the 8 entries, fraction of entries will be set to zero
10到8个条目，条目的分数将设置为零

Right
对

so to show you an example
举个例子

right
对

I gave you this example and this looks super empty
我给你这个例子，看起来超级空

but this is actually quite an ends in the cases I gave you you have
但这实际上是我给你的情况下的一个结局

I know
我知道

several million rows and several million columns
几百万行和几百万列

and then you know you have several million non zeros
然后你知道你有数百万个非零

So majority of this matrix is just empty
所以这个矩阵的大部分都是空的

And that’s why we generally never represent the graphs as matrices
这就是为什么我们通常从不将图表表示为矩阵的原因

because it would take too much
因为这会花费太多

or at least not as dense matrices
或至少不像密集矩阵

because it takes too much memory
因为它占用太多内存

OK
好

so this is what the first point I wanted to make here is that the real networks are very sparse
所以这是我要说的第一点是真实的网络非常稀疏

right that average degree are very low
对，平均度很低

even in protein interaction networks
即使在蛋白质相互作用网络中

On averages
平均而言

protein interacts with two other proteins
蛋白质与其他两种蛋白质相互作用

even though it could interact with 1,800 other proteins
即使它可以与1800种其他蛋白质相互作用

because there is so many in the network
因为网络中有很多

So this was about just choosing nodes and edges
所以这只是选择节点和边

Of course
当然

you can attach a lot of data to the network
您可以将大量数据附加到网络

and in particular you can attach a lot of data to the edges
特别是您可以将大量数据附加到边缘

You can attach a weight to the edge and make weighted networks
您可以将权重附加到边缘并制作加权网络

you can attach type to the edge, or rank to the edge
您可以将类型附加到边缘，或将等级排列到边缘

saying: oh, this is the best friend
说：哦，这是最好的朋友

this is the second best friend
这是第二好的朋友

you can have different types of edge
你可以有不同类型的边缘

just saying these are relatives
只是说这些是亲戚

these are coworkers
这些是同事

and so on
等等

You could even think of edges as being signed so that they can be positive or negative
您甚至可以认为边缘已签名，因此它们可以是正数或负数

so you could say you are my friend or you are my foe
所以你可以说你是我的朋友或者你是我的敌人

or I trust you versus I don’t trust you
还是我相信你vs我不相信你

and these are kind of the opposite and this this will
这些是相反的，这将

and of course you could further label edges based on some structural properties from the network
当然，您可以根据网络中的某些结构属性进一步标记边缘

for example
例如

saying how many common friends do we have, and things like that
说我们有多少个普通朋友，诸如此类

And then how do you encode these attributes?
然后如何编码这些属性？

One way to encode them is to say
编码它们的一种方法是说

if I have an unweighted graph where entries of my adjacency matrix would only 0 and 1
如果我有一个非加权图，其中邻接矩阵的条目将仅为0和1

now my entries would correspond to weight, right?
现在我的输入将对应体重，对吗？

so this would mean that edge 1 to 2 has a weight of 2
所以这意味着边1到2的权重为2

and the edge between 2 and 4 has a weight of 4
而2和4之间的边的权重为4

for example
例如

so you can put real valued weights to these things
这样您就可以对这些东西进行真正有价值的评估

And then just kind of to continue
然后继续

There are two other important types of graphs
图还有另外两种重要的类型

so this loops that basically edges that link to the node itself
所以这个循环基本上会链接到节点本身的边缘

these are called self loops or self edges
这些称为自循环或自边缘

and these are essentially non-zero entries on the diagonal right
这些基本上是对角线右边的非零项

So this says that node number 1 links to node number 1
因此，这表示节点号1链接到节点号1

And that’s why I have a loop up there
这就是为什么我在那里有一个循环

and then nobody says you can only have one edge between a pair of nodes
然后没人说你在一对节点之间只能有一条边

you can have multiple edges
你可以有多个边缘

and then you call you call this objects
然后你叫你叫这个对象

you call the multigraph because you allow for multiple edges
之所以调用多图，是因为您允许多个边

different edges
不同的边缘

different types of edges between a pair of nodes
一对节点之间的不同类型的边

So this would be called a multigraph
所以这将被称为多图

So now that we have kind of defined what the graph are
现在我们已经定义了图形

I want to show you two more examples to think about the connectivity of graphs
我想向您展示另外两个示例，以考虑图形的连通性

and what do I mean by that?
我的意思是什么？

I would say that our graph is connected if there is a path between any pair of nodes in the graph
我要说的是，如果图中的任何一对节点之间都有路径，则我们的图是连接的

right so this is a connected graph
对，所以这是一个连通图

While this graph is not connected, right?
未连接此图时，对吗？

there is no way to get from H to F by traversing edges
没有办法通过遍历边从H到F

so this would be a graph that is not connected
所以这将是一个未连接的图

and then usually these groups
然后通常这些组

these components of connected nodes
连接节点的这些组件

I will call them connected components and the largest component
我将它们称为连接的组件和最大的组件

I will generally call the giant component
我通常会称其为巨型组件

OK
好

that’s why it’s called and it’s actually
这就是为什么它被称为，实际上

I will
我会

It’s actually a real term
这是一个真实的名词

so it means something
所以这意味着

and I will tell you what it means later
我会告诉你这是什么意思

OK
好

So now
所以现在

if I define this notion of connected graph and the graph that’s not connected
如果我定义了连接图和未连接图的概念

then how would you see whether the graph is connected?
那么您将如何查看图形是否已连接？

One way to see is that you would look
一种看待方式是

for example
例如

At the structure of the adjacency matrix
在邻接矩阵的结构上

right
对

and if the adjacency matrix for this type of block-diagonal structure
以及这种块对角线结构的邻接矩阵

this means that these notes here connect to each other
这意味着这些音符在这里相互连接

these notes here connect to each other
这些笔记在这里互相联系

but there’s no nodes that you know
但是没有你知道的节点

no edges between the red nodes and the blue notes
红色节点和蓝色音符之间没有边缘

and this is how connectivity would manifest itself in the adjacency matrix
这就是连通性如何在邻接矩阵中体现出来的方式

right
对

for example
例如

here this graph is connected, and this yellow edge here is denoted here, right?
在此，此图已连接，此处的黄色边缘在此处表示，对吗？

and if I wouldn’t have it
如果我不拥有它

then I would have these two blocks and this graph would be disconnect
那么我将拥有这两个块，并且该图将断开连接

So this is how you can kind of read off from the adjacency matrix
所以这就是从邻接矩阵中读取信息的方式

whether the graph is connector
图形是否为连接器

And then this was for undirected graphs
然后这是针对无向图的

so I just wanna tell you
所以我只想告诉你

I think this is the last thing
我认为这是最后一件事

what happens with directed graphs?
有向图会发生什么？

In directed graphs, you have two notions of connectivity
在有向图中，您有两个连接概念

You have strong connectivity and weak connectivity
您具有强连通性和弱连通性

and weak connectivity, basically
和弱连接性，基本上

says a graph is weakly connected, if it’s undirected version is connected
说图是弱连接的，如果它是无向版本的

so I ignore edge directions
所以我忽略了边缘方向

and in the notion of strong connectivity
并具有强大的连通性

the idea is that there is a directed path between every pair of nodes
这个想法是每对节点之间都有一条定向路径

So
所以

for example
例如

this graph here is weakly connected
这个图在这里是弱连接的

but it’s not strongly connected
但却没有牢固的联系

Why wouldn’t it be strongly connected?
为什么不牢固地联系在一起？

Because there is no way to get from node D to node E by following edge directions, right?
因为无法通过遵循边缘方向从节点D到达节点E，对吗？

I cannot navigate this way
我不能这样导航

I can go that way
我可以走那条路

but I don’t know how to get there
但我不知道怎么去

So this graph is not strongly connect
所以这个图不是很强的联系

And you can take a graph
你可以拍一张图

and decompose it into strongly connected components
并将其分解为紧密连接的组件

right so here I have examples of two graphs and I will now show you
对，所以这里有两个图表的示例，现在我将向您展示

examples of strongly connected components and are strongly connected component
强连接组件的示例，并且是强连接组件

is a set of nodes where any node can visit each other, right?
是一组节点，任何节点都可以互相访问，对吗？

For example
例如

this should be is a strongly connected component here
这应该是一个牢固连接的组件

this is a strongly connected component because any note can visit each other because they’re on the cycle
这是一个紧密连接的组件，因为任何音符都可以在循环中互相访问

but these notes here are not part of the strongly connected component, right?
但是这些注释不是强连接组件的一部分，对吗？

and I think I have a bug here
而且我认为我在这里有一个错误

if you notice, this, right
如果您注意到，这是对的

so why is here a bug?
那么为什么这里有个bug？

Because there is no way to get from F to E
因为没有办法从F到E

for example, right?
例如吧？

So if this would be a cycle
所以如果这是一个周期

this would be a strongly connected component
这将是一个紧密联系的组成部分

But right now it’s not
但是现在不是

so that’s a mistake
所以这是一个错误

Okay
好的

so this is what I wanted to cover today
所以这就是我今天要讲的

So basically I told you about motivation and examples of applications
所以基本上我告诉你了动机和应用示例

I talked to you about the logistics for the course
我跟你谈了这门课程的物流

and now we are all on the same page
现在我们都在同一页面上

so that we have refreshed the examples from graph theory
因此我们从图论中刷新了例子

and thank you for coming and I’ll see you all on Thursday
谢谢您的光临，我星期四见

Oh, yes
哦对