网络与图

Loading...

En provenance du cours de Peking University

人群与网络

99 notes

Peking University

人群与网络

99 notes

本课程是北京大学开设的一门在线跨学科选修课程，主要面向信息技术、社会学和经济学等专业的本科生。课程内容涉及用计算思维的方法讨论社会学和经济学的一些经典问题。学习运用计算思维分析社会学、经济学问题的方法，加深对某些生活现象的理解，体会计算与社会科学的互动。 Learn to analyze and reason about problems in social sciences with computational thinking, appreciate interactions between computing and social sciences, as well as gain deeper understanding of some common phenomena in life and society

À partir de la leçon

网络与图论

图论是研究网络结构的基础。本章首先介绍图论的一些基本概念，包括节点、边、路径、连通性、聚集系数等。进而运用这些图结构的若干基本概念探讨社会网络的一些典型结构，以及影响网络中边的形成的一些基本过程。网络的结构性因素，如关系的强弱，边的嵌入性，节点的属性，网络中的结构洞等等，在信息传播过程中都发挥着独特的作用，影响着社交网络本身的演化。

无处不在的网络21:53

网络与图6:43

路径与连通5:35

二部图与广度优先搜索13:14

Rencontrer les enseignants

李晓明（Li Xiaoming）
教授（Professor）
信息科学技术学院（School of Electronics Engineering and Computer Science）
邱泽奇（Qiu Zeqi）
教授 (Professor)
北京大学社会学系（Department of Sociology）
王卫红（Wang Weihong）
lecturer
School of Electronic of Engineering and Computer Science

在前面呢，我们谈到了，在我们的人们的

经济社会生活中，有各种各样的网络，网络呢无处不在，

而且是形形色色。这些个网络呢，有些是有组织有计划的，

把它建造出来的，有些呢，则是

这个随机的在人们的生活中，随便，随机的产生出来的。

这些个网络，有的很巨大，有的也可能很小。

那么这些形形色色的网络，在我们社会中起着很重要的作用。

那么这一段呢，我们就要讨论一个如何讨论网络，

怎么用一种比较严格的语言讨论网络的结构。

当我们想到“网络”这个词的时候，其实尽管它们是各种各样的，但是它们都有一种共性，

也就是他们都反映的是某些事物，及其它们之间的联系的这么一种状态。

那么这些个事物呢，可以是人，也可以是计算机，

那么这些个联系呢，可以表现的是人们之间的友谊关系。

也可以表现的是这个计算机之间的通信关系。

那么，为了讨论这样一种共性，

数学家呢，他们发明了一个概念，叫做图。

那么这个图呢，有两个最基本的元素，一个就是这个

节点，一个就是这个节点。另外一个呢，就是边，就是边。

因此呢，我们有的时候为了表达一个网络，我们可以画成

若干节点，以及他们之间的边相连的某种状态。

那么，到底什么是图呢？在我们日常生活中，我们见到有很多图，

比方说这些也是图，这些都是我们日常生活中可能看到的

一些的图。但是，它们都不是我们这里要讨论的图。

我们这里讨论的图呢，是一个数学的概念。

我们这儿讨论的图是这个样子，

它们抽象的表达了事物及其之间的联系这么一种

情况，这么一种情况。由节点和边组成。

比方说，我们这第一个图，它有5个节点，这5个都是节点。

然后它们有多少边呢？它们一共有这个7条边。

一个网络，

可以表达为一个图，以这个最初的这个我们互联网最初的雏形

为例，这是我们互联网在40年前的样子。

它们体现的是美国的一些个机构

和大学之间的计算机的连接关系。

那么如果我们不考虑地理位置，也不考虑它们距离的远近，

就考虑它们之间的直接联系，我们就可以用下面的这一个图来表示，这么一个互联网。

那么这样一个情况呢，就是说

把一个现实的网络的

结构，用一个图表达出来。还有一个经典的例子，就是我们在

研究社会网络中，

常用的一个例子。表达的是，一个俱乐部，人和人之间的关系。比方说这个俱乐部里有

34个人。两个人之间的关系很好，他们之间就有一条边。

如果两个人关系一般，或者比较糟糕，就没有边。比方说这个1号和

和这个13号，他们的关系不错，所以他们之间有一条边。比方这个1号和34号，

尽管他们分别都是这个俱乐部很重要的人物，一个是教练，一个是创始人，

但是他们之间没有边，这就表示他们，可以想象呢，他们的关系不怎么样。

一个图，可以画成各种各样的样子，

一个图强调的是它的结构，

但是它的表现形式可以是各种各样的。比方说这个图我们前面看过，它是表达了

那个互联网雏形的那么一个图。也可以画成这个样子，

比方说只要我们把这个节点标注成相应的对应关系就可以。比方这也是MIT，

这个地方也是MIT，那么这周边MIT跟三个相连，比方说一个是BBN，一个是这个，

一个是BBN，一个是Lincoln，一个是Utah，我们可以看看呢，这个地方是BBN，这个地方应该是

Lincoln，这个地方应该是Utah，等等。这样的联系关系

一致，那么这个图就是一样的。

这也是一样的，这我们前面见过这样两个图，它们本质上也是同一个图。

判断这样一种说法的一个办法呢，就是尝试给它们进行一种编号。

如果我们对两个看起来不一样的图，能够给予某种编号，

使得它们这个相邻的节点

都是一致的，那么这两个图，我们就说它们是，本质上就是同一个图。

用图论的术语呢，它们就叫同构的。同构，也就是同一个图的画法不一样，

但本质上呢，结构上是相同的。比方说，这里的节点1，这里的节点1，

它是连着3、4、5，

那么这个节点1呢，它是连着也是3、4、5。

那么，再挑一个吧，比方说节点4吧，

节点4呢，连的是1、5、2。 1、5、2，这边是1、5、2。

这个也是，4也连的是1、5、2。所以一个个检查呢，我们能看到它们的相邻关系是一样的。

也就是说，它们实质上是一样的图。这一段呢，我们

有三个要点。第一个呢，讲的是图

是网络结构信息的抽象，表达的是网络中各种事物之间的关系。

第二点呢，我们这里所说的图，是一个数学的概念，不同于

日常生活中看到的那些个图像。但是呢，这些个图，

常常也可以被画出来，呈现出一种图像的形式。

第三点，就是同一个图，可能有多重不同的画法。

也就是说同一个图，可能呈现出不同的图像形式。

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play