Video在线视频

各位同学 大家好

欢迎来到网络 群体与市场

的在线课堂

我是这门课的主讲老师——石兵

来自武汉理工大学

在这一讲 以及接下来的几讲

我们将开始介绍信息网络

我们首先会介绍万维网的结构

我们可以看一下

Web信息它有这样一个

基本的结构特征

它是以网页为基本的组成单位

一般来说

每个网页都会对应一个网址

我们在浏览网页的时候会发现

在网页上可能会有多个链接

每个链接都会指向另外一个网页

当前这个网页也被其它的网页

所指向

因此我们可以有这样一个体会

我们给定网页A和B

非常有可能我们可以通过

一个个相继的链接

经过一些中间的网页

可以从A到达B 也就是说

我们很可能从百度的网页通过

若干网页的链接到达微软的主页

如果我们可以从A到达B

很多时候我们会发现

也可以从B到达A

当然中间经过的网页很可能是

不一样的

而且这样一个路径的长度也

可能是不一样的

比如说我们可以看这样一个几篇

网页之间的链接关系示意图

这是网络这门课

这门课有一个链出去的链接

它指向了这个课程的博客

然后这个博客其实是放在

微软的一个页面上的

所以通过这个我们可以链接到

微软的主页

其实我们可以看一下

在这样一个链接的过程中

我们从网络这门课跳转到了

微软的主页

其实这个主题

偏移的还是很大的

其实这样一个主题的偏移

跟人的思维是很类似的

我们可以这样想

其实这种网页之间的链接跟

人的大脑思维存储信息

还是非常类似的

比如说我们在学博弈论的时候

会学到纳什均衡

当学到纳什均衡我们可能会

想到纳什这个人

想到纳什这个人我们就会想到

他的传记电影 美丽心灵

想到 美丽心灵 我们可能会

想到奥斯卡

就是说我们从博弈论就

跳到了奥斯卡

那么这样一个网页之间的链接

我们怎样来表达它呢

我们可以通过有向图

我们通过有向图来刻画Web

信息之间的这样一个结构

我们现在可以把有向图的一些

概念把它回忆一下 首先有节点

在我们这样一个Web信息网络

里面 节点就是什么呢

代表了网页 然后还有有向边

有向边表达的是什么呢

表达的是从一个网页到另外

一个网页的链接关系

第三个就是有向路径

有向路径从图论的角度来说

就是指两个节点之间的边

的方向一致的路径

在这里面我们就有这样

一个距离的概念

从A到B最短有向路径的长度

我们需要注意的是

在这样一个有向图里面

从A到B的距离

不一定等于从B到A的距离

因为这个边是有方向的

其实这样一个有向路径

就代表了两个网页之间的

一个可能链接的路径

比如说我们从网络这门课

经过一系列的路径

我们可以链接到微软的主页

第四个概念是强连通有向图

强连通有向图表达的什么意思呢

是指在这个有向图里面

任何两个节点之间

他们都会存在有两个方向的

有向路径

当然这样一个两个方向的有向

路径不一定经过相同的节点

但是它表达的意思是任何两个

节点互相都是可达的

就是可以从任何一个节点A

到达另外一个节点B

最后一个概念就是强连通分量

强连通分量指的是什么呢

指的是一个尽可能大的子集

其中每个节点都有到其它

任何一个节点的有向路径

也就是我们可以通过这些

概念的介绍

知道可以把万维网转化成

一个有向图

我们可以看这样一个例子

这个是一个实际的网页之间的

链接关系

比如说 这个大学的主页

它可能会链接到某个课程等等

我们可以把这样一个

实际的网页之间的链接关系

把它转成一个有向图

其中每个网页用一个节点来表达

这样网页之间的链接关系

我们通过有向边来表达

比如说

我是这个大学的学生

所以我可以指向这个大学

这个表示这个学生

这个表示大学

所以有这样一个链接关系

通过这样一个转换我们就从

具体的网页的关系把它

抽象成了一个有向图

那么我们现在有这样一个问题

我们从有向图的角度来看这个

万维网宏观上应该是什么样子

我们知道

现在万维网上有很多很多的网页

对于这样一个巨量元素

构成的事物

我们很希望从宏观上对它的整体

形态有一个有意义的刻画

在1999年

Andrei Broder

发现了什么呢

万维网包含了一个超大的

强连通分量

在这个超大的强连通分量里面

任何两个网页之间

都是互相可达的

然后再加上其它部分

它显示出一种非常形象的结构

我们可以看一下

最终它显示出这样一个结构

这个结构像什么呢

就像我们常戴的领结

这是领结的圆心部分

它表达的就是这样一个

超大的强连通分量

这里面任何两个网页之间

都互相可达

领结的这一部分表示链入

它表示这里面所有的网页

都有一个链接指向了这个

超大的强连通分量

然后还有就是链出

它表示超大的强连通分量里面

的网页可以通过一些路径到达

这个链出里面的网页

当然可能还包括一些其它的部分

比如管道

就是从链入直接到链出

卷须

还有就是这些游离的信息孤点

我们通过这个分析可以发现

其实万维网可以用领结这样

一个比较形象的词来刻画

那么这是怎么知道的呢

这里面就有这样一个基本问题

我们给定一个有向图

我们需要知道里面的强连通分量

而且显然这里面还不一定就一个

我们要找到最大的那个

当我们知道最大的强连通分量

之后

我们就可以刻画其它部分跟

它的关系

比如链入 链出 卷须 管道

游离等等

那么为了回答第一个问题

我们首先要知道怎么来

找一个强连通分量

也就是说我们给定一个节点

怎么找到包含他的强连通分量

我们采用的基本方法还是

广度优先搜索

我们可以看这样一个算法的流程

这个流程就可以帮助我们找到

这样一个强连通分量

并且据此可以找到这样一个

网络结构里面的其它部分

包括链入 链出 卷须等等

首先我们对于给定的有向图G

我们生成他的反向图G’

然后我们在这样一个图里面

找一个含有最大强连通子图

的节点A

注意一下其实这个寻找不是

这么容易的

因为那么多节点你很有可能

找错了

这时候你可能会要重复好多次

我们以A为出发点

在这个图G里面我们通过

广度优先搜索算法直到

没有新的节点被发现

这时我们得到一个

节点的子集FS

同样的步骤

我们以A为出发点

在它的反向图G'里面

使用广度优先搜索算法

我们可以得到所有的跟它

有关系的节点

然后得到一个节点的集合BS

我们在得到FS和BS之后

采用集合运算

取FS和BS的交集

我们就可以得到这样一个

超大的强连通分量

而链入部分就等于BS减去

这样一个强连通分量

链出部分等于FS减去

这样一个强连通分量

我们基于这样一个图G和他的

反向图G’ FS和BS

我们可以进一步求到

一些其他的部分

比如说卷须 游离等等

我们可以通过一个例子看一下

这个算法具体怎么操作

首先这个是原来的图G

这个是他的反向图G'

我们随机选一个点

比如说我们选择A

我们通过宽度优先搜索算法

可以算出FS和BS

然后FS和BS取它们的交集

就得到了这样一个结果

这就是一个超大的强连通分量

而其它部分就可以接着求出来

最终我们可以看到这样一个形式

我们可以看到

这个中间是一个强连通分量

这边是链入部分

这边是链出部分

然后其它还有一些卷须

通过刚才的学习我们知道

有向图是信息组织的一种

非常有效的形式

这里面链接其实就表达

信息之间的引用关系

也是认可关系

有向图里面有些重要的基本概念

大家可以去复习一下

另外我们发现对于万维网

他的信息结构类似于领结

接着我们还介绍了

领结的计算方法

这一讲的内容就到这里 谢谢