个网页 由此，我们可以体会到
给定网页A 和B，有可能通过一个个相继的链接，经过 一些中间网页，从A到达B 如果可以如此从A到达B，也可以从B到达A，中间经过 的网页很可能是不一样，路径的长度也就可能是不一 样的

5
Web组织形式
几篇网页之间的链接关系示意
注意，不仅信息所处的位置可以相距很远，其中的主题也可
2
万维网 World Wide Web
3
万维网 World Wide Web
万维网原始构想和设计包含的两个基本特征 网页(web page)，资源以网页的形式创建和存储 浏览器(browser)，访问网页的方式
4
Web组织形式
以网页为组成单位，每个网页对应一个网址 每个网页上可能有多个链接，每个链接指向另一
能“漂移”很远；不奇怪，人的思维也如此
6
超文本的技术雏形
社会学的论文引用
三元闭包，小世界
现象，结构平衡， 同质性
7
超文本的技术雏形
Wiki中博弈论文章
的交叉引用
8
Vannevar Bush and the Memex
Vannevar Bush 曼哈顿计划的发起者 发起建立NSF Memex(Memory-Extender) 1945年，Vannevar Bush在《大西洋月刊》
15
计算领结结构的算法
输入：有向图G 第一步：生成图G的“反向图”G’ 第二步：选择一个在最大强连通子图中的节点A（tricky?）
第三步：以A为出发节点，在图G中宽度优先搜索直到没有
新的节点发现，得节点集合FS 第四步：以A为出发节点，在图G’中宽度优先搜索直到没有 新的节点发现，得节点集合BS 结果
18
计算领结结构的方法算法
有向图的“领结”表示
19
一次计算中国Web结构的实践
2006 年 1 月，孟涛同学用 16 台服务器并行工作，
北大网络实验室完成了一次中国Web 的网页搜集， 得到了8亿3千多万网页 基于这些网页，构造了一个巨大的有向图，8 亿3 千多万个节点，数据占用磁盘容量400GB+

强连通有向图：任何两节点之间都存在两个方向
的有向路径（不一定经过相同节点）
强连通分量：尽可能大的节点子集，其中每个节
点都有到其中任何另一节点的有向路径
10
一组网页之间 构成的一个有 向图示例
＊具体与抽象
A
B
11
将万维网看成有向图
寻找强连通分量
下图是强连通有向图吗？
• 强连通分量 – 节点子集，其 中每个节点都 有到任何其他 节点的有向路 径 – 不存在真包含 这个集合的连 通分量
14
万维网的“领结”结构
给定一个网络结构，如何得到强连通分量？ 显然不一定就一个。强连通分量的划分性 以最大的强连通分量为基础，如何描述其他部分
与它的关系？

链入，链出，卷须（管道），游离
为了回答第一个问题，我们问一个更具体些的问 题：给定一个节点，如何确定包含它的强连通分 量？
基本方法：广度优先搜索
上 发 表 了 一 篇 文 章 《As We May Think》，提出一种信息机器的构想 机器内部用微缩胶卷存储信息，也就是自 动翻拍，可以不断添加新的信息；桌面上 有阅读屏，用来放大阅读微缩胶卷；还有 许多个按钮，每一个按钮代表一个主题， 按一下，相应的微缩胶卷就会显示

读者可以建立指向某些微缩胶卷片段的链 接，并依照自己的喜好形成新的线性顺 序，甚至加上自己的补充或评论。这些可
13 万维网结构 The Structure of the Web
1
万维网(Wan Wei Wang) World Wide Web
定义 The World Wide Web, is a system of interlinked hypertext documents accessed via the Internet. With a web browser, one can view web pages that may contain text, images, videos, and other multimedia, and navigate between them via hyperlinks. (Wikipedia) The web was developed between March 1989 and December 1990 by Tim Berneers-Lee. 起源 1989年3月，李撰写了《关于信息化管理的建议》一文，文中提及 ENQUIRE 并且描述了一个更加精巧的管理模型 1991 年 8 月 6 日，他在 alt.hypertext 新闻组上贴了万维网项目简介 的文章。这一天也标志着因特网上万维网公共服务的首次亮相
12
从有向图的角度看，Web宏观上是 个什么样子（“形状”）？
对于由巨量元素构成的事物，人们往往希 望能得到对其整体性态的有意义的刻画
13
万维网的“领结”结构
1999，Andrei Broder等发现万维网包含一个超大强
连通分量SCC，加上其他部分，显示出一种形象的结 构

链入，链出，卷须（管道），游离
计算领结结构的算法
FS={1, 3,4,5,
8,9,10, 13,14,15,16, 18} BS={1, 3,4, 6,7,8,9, 11,12,13,14,15, 18} SCC=FS∩BS= {1, 3,4, 8,9, 13,14,15, 18} IN=BS-SCC={6,7,11,12} OUT=FS-SCC={5,10,16} 2和17是卷须

SCC＝FS和BS的交集，即共同元素 IN（链入）＝BS－SCC OUT（链出）＝FS－SCC
16
基于G和G’，FS和BS，进一步集合运算可得到卷须和游离
计算领结结构的算法
从一个具体例子入手
FS={1, 3,4,5,
8,9,10, 13,14,15,16, 18} BS={1, 3,4, 6,7,8,9, 11,12, 自相似、层次性
21
本章要点
Web组织形式 尤其是对于表达信息之间的“引用关系”（“认可”关 系） 将万维网看成有向图 有向路径 强连通分量 万维网的“领结”结构 “领结” 领结结构的计算方法
• 广度优先搜索，基本集合运算
22
Q/A
23
以成为共享，他人只要键入建立链接的作 者的索引代码，就可以追溯到这些关联
9
将万维网看成有向图
节点：网页（可能用网址标识） 有向边：表示从一个节点到另一个节点的直接链
接关系；节点的出向边与入向边 有向路径：两节点之间边的方向一致的路径
节点A到B的距离：从A到B最短有向路径的长度 注意，从A到B的距离不一定等于从B到A的距离
在这个有向图数据上，实现了前述算法，一个程
序（在16 台机器上）运行了一周，得到了有关结 构形状的参数
20
网页: http://.../....html, (完整地址) 网站: http://.../*, 对应例如大学的一
个系
机构: http://*..../*, 对应例如一所大
学所有院系网站的集合